--- pl:dydaktyka:csp:lab1 [2014/05/21 10:22]
msl [Rozgrzewka: problem n hetmanów]
+++ pl:dydaktyka:csp:lab1 [2019/06/27 15:50] (aktualna)
@@ Linia 1: / Linia 1: @@
-====== Lab CSP: Podstawowe techniki modelowania ======
+====== Lab CSP: Podstawowe problemy ======
 W ramach laboratorium będziemy rozwiązywać standardowe problemy pojawiające się w literaturze dotyczącej programowania z ograniczeniami. Zaprogramowane modele będą następnie ulepszane poprzez stosowanie podstawowych technik modelowania w CSP.
-===== Rozgrzewka: problem n hetmanów =====
+===== Rozgrzewka =====
-  * Treść problemu: w jaki sposób na szachownicy o wymiarach nxn umieścić n hetmanów w taki sposób, by żaden z nich nie mógł zbić innego w jednym ruchu (patrz: http://pl.wikipedia.org/wiki/Problem_o%C5%9Bmiu_hetman%C3%B3w).
+==== Problem n-hetmanów ====
+  * Treść problemu: w jaki sposób na szachownicy o wymiarach nxn umieścić n hetmanów w taki sposób, by żaden z nich nie mógł zbić innego w jednym ruchu (patrz: [[http://pl.wikipedia.org/wiki/Problem_o%C5%9Bmiu_hetman%C3%B3w|wikipedia]]).
   * Ćwiczenia:
-    - Proszę zamodelować problem n hetmanów w MiniZinc.
+    - Proszę uzupełnić poniższy model problemu n-hetmanów <code>
-    - Proszę się zastanowić, czy stworzony model jest jedynym możliwym dla tego problemu.
+%%%%%%%%%%%%%
-    - Poniżej kod wypisujący rozwiązanie dla zmeinnych w tablic ''rows'' oraz rozmiarze problemu ''N'':
+% DZIEDZINA %
-<code>output [ if fix(rows[j]) == i then "H" else "." endif ++
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-if j == N then "\n" else "" endif | i,j in 1..N]</code>
+% miejsce na dziedzinę           %
+% podpowiedź:                    %
-   <WRAP center round tip 60%>
+% var 1..N: x; deklaruje zmienną %
-''var 0..N: zmienna;'' pozwala na szybkie określenie dziedziny zmiennej.
+% o dziedzinie 1..N;             %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%
+% OGRANICZENIA %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% miejsce na ograniczenia                    %
+% podpowiedź:                                %
+% row_i = row_j (-/+) (j - i)                %
+% opisuje hetmanów stojących na              %
+% tej samej diagonali, gdzie:                %
+% - i,j - numery kolumn                      %
+% - row_n - pozycja hetmana w n-tej kolumnie %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+solve satisfy;
+%%%%%%%%%%%%%%%%%%%%%%%%
+% PRZYKŁADOWE WYJŚCIE  %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% - rows[i] pozycja hetmana w i-tym wierszu %
+% - N - liczba hetmanów                     %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+output [ if fix(rows[j]) == i then "H" else "." endif ++
+  if j == N then "\n" else "" endif | i,j in 1..N]</code>
+<WRAP center round tip 70%>
+Przykładowe złożone wyrażenie agregujące:\\
+''forall([tablica[i,j] = z | i,j in 1..M, z in 1..N where j < i])''\\
+lub równoważnie:\\
+''forall(i,j in 1..M, z in 1..N where j < i)(tablica[i,j] = z)''
 </WRAP>
-===== Globalne ograniczenia: sudoku =====
+==== Kolorowanie grafów ====
+  * treść problemu: problem kolorowania grafu polega na przyporządkowaniu wierzchołkowom grafu odpowiednich kolorów tak, aby wierzchołki o wspólnej krawędzi miały różne kolory. W najgorszym przypadku (klika) będzie potrzebne tyle kolorów, ile jest wierzchołków. W przypadku grafu planarnego zawsze wystarczą cztery (sławny dowód matematyczny, warto sprawdzić, dlaczego). [[http://en.wikipedia.org/wiki/Four_color_theorem|Twierdzenie o czterech barwach]] [[http://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring|Kolorowanie na angielskim wiki]].
+  * Ćwiczenia:
+    - Proszę uzupełnić poniższy model kolorowania grafu ({{:pl:dydaktyka:csp:csp_coloring_data.dzn.zip|przykładowe dane wejściowe}}):
+<code>
+%%%%%%%%%%%%%
+% PARAMETRY %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Powinny być wczytane z pliku z danymi.%
+% Traktujmy graf jako tablicę booli     %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%
+% DZIEDZINA %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% miejsce na dziedzinę           %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%
+% OGRANICZENIA %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% miejsce na ograniczenia                    %
+% podpowiedź:                                %
+% - warto użyć if'a, by sprawdzić, czy dwa   %
+% wierzchołki są połączone                   %
+% - liczba kolorów to może być maksymalny    %
+% numer użytego koloru                       %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%
+% CEL  %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Zminimalizuj użytą liczbę kolorów %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+solve minimize coloursNumber;
+%%%%%%%%%%%%%%%%%%%%%%%%
+% PRZYKŁADOWE WYJŚCIE  %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% - coloursNumber - liczba użytych kolorów  %
+% - nodes - tablica wierzchołków grafu z    %
+%           ich kolorami                    %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+output [show(coloursNumber), " colours\n",] ++
+       [show(nodes[i]) ++ " " | i in 1..nodesNumber]
+</code>
+<WRAP center round tip 60%>
+Definicja tablicy dwuwymiarowej booli:
+<code>
+array[1..2,1..3] of bool: bool_array = [|true, true, true | true, true, true|];
+</code>
+Konstrukcja warunkowa:
+<code>
+if bool then val1 else val2 endif
+</code>
+Operatory logiczne:
+<code>
+/\ -- i, \/ -- lub, != -- różne, == -- równe
+</code>
+</WRAP>
+===== Globalne ograniczenia =====
+Jedną z najprostszych metod tworzenia dobrego modelu w programowaniu z ograniczeniami jest korzystanie z gotowych globalnych ograniczeń. Dzięki wyspecjalizowanym algorytmom i implementacji są one w stanie lepiej wykorzystać informacje na temat struktury problemu od ograniczeń na pojedynczych zmiennych. Niektóre z globalnych ograniczeń są nawet w stanie zamodelować dynamiczne zachowanie systemu, np. ograniczenie ''cumulative'' uniemożliwia równoczesne wykorzystanie zasobu przez kilka zadań. W MiniZinc, aby korzystać z globalnego ograniczenia, należy je najpierw zaimportować, np. aby korzystać z ograniczenia ''cumulative'' należy wcześniej dopisać do kodu linijkę: <code>include "cumulative.mzn";</code>
-Jedną z najprostszych metod tworzenia dobrego modelu w programowaniu z ograniczeniami jest korzystanie z gotowych globalnych ograniczeń. Dzięki wyspecjalizowanym algorytmom i implementacji są one w stanie lepiej wykorzystać informacje na temat struktury problemu od ograniczeń na pojedynczych zmiennych. Niektóre z globalnych ograniczeń są nawet w stanie zamodelować dynamiczne zachowanie systemu, np. ograniczenie ''cumulative'' uniemożliwia równoczesne wykorzystanie zasobu przez kilka zadań.
+==== Sudoku ====
-  * Treść problemu: należy zaimplementować solver sudoku (http://pl.wikipedia.org/wiki/Sudoku)
+  * Treść problemu: należy zaimplementować solver sudoku (patrz: [[http://pl.wikipedia.org/wiki/Sudoku|wikipedia]])
   * Ćwiczenia:
-    - Proszę zamodelować sudoku w MiniZinc korzystając z ograniczenia ''alldiferent''. Aby móc korzystać z ograniczenia należy na początku pliku dopisać ''include "alldifferent.mzn";''
+    - Proszę uzupełnić poniższy model sudoku: <code>
-    - Proszę rozszerzyć model tak, by obsługiwał jedną z rozszerzonych wersji Sudoku (również opisane na wikipedii), np. Sudoku o rozmiarze innym niż 9x9.
+%%%%%%%%%%%%%%%%%
-    - Czy wcześniej opracowany model n hetmanów można usprawnić wykorzystując globalne ograniczenia?
+% PRZYPOMNIENIE %
-  * Przykładowe dane wejściowe:
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Coś tu jeszcze powinno być.%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-<code>  % 0 to pola o nieznanej wartości
+%%%%%%%%%%%%%
+% DZIEDZINA %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% miejsce na dziedzinę, podpowiedź:  %
+% dwie oddzielne tablice, jedna      %
+% odpowiedzialna z stan początkowy;  %
+% druga przechowuje zmienne decyzyjne%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%
+% Ograniczenia %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% - constraint alldifferent(tablica zmiennych);  %
+% globalne ograniczenie, w którym wszystkie      %
+% zmienne z tablicy muszą mieć różną wartość     %
+% - należy zapewnić, aby wartości zmiennych były %
+%   równe odpowiednik polom stanu początkowego   %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+solve satisfy;
+%%%%%%%%%%%%%%%%%%%%%%%%
+% PRZYKŁADOWE WYJŚCIE  %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% - puzzle - dwuwumiarowa tablica zmiennych %
+%            o rozmiarze NxN                %
+% - N - rozmiar planszy, równy S*S          %
+% - S - rozmiar sektora planszy             %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+output [ show(puzzle[i,j]) ++ " " ++
+  if j mod S == 0 then " " else "" endif ++ if j == N /\ i != N then
+  if i mod S == 0 then "\n\n" else "\n" endif else "" endif
+    | i,j in PuzzleRange ] ++ ["\n"];
+</code>
+    - Poniżej przykładowe dane wejściowe: <code>  % 0 to pola o nieznanej wartości
 board = array2d(1..9, 1..9, [
 ,  0,  0,  2,  0,  5,  0,  0,  0,
@@ Linia 42: / Linia 184: @@
 ]);
 </code>
+    - Proszę zastosować globalne ograniczenia do problemu n-hetmanów
 <WRAP center round tip 60%>
 Lista globalnych ograniczeń dostępnych w MiniZinc:
-http://www.minizinc.org/downloads/doc-1.6/mzn-globals.html
+http://www.minizinc.org/downloads/doc-latest/mzn-globals.html
-Kluczem do ładnego zamodelowania sudoku jest inteligentne użycie array comprehensions wprowadzonych na poprzednich zajęciach.
 </WRAP>
-===== Łamanie symetrii: kolorowanie grafu =====
-Mówimy, że dany problem przejawia symetrię, jeśli istnieją dla niego rozwiązania symetryczne, tj. takie, które pomimo różnych wartości zmiennych decyzyjnych, są sobie równoważne. Przykładem może być problem kolorowania wierzchołków grafu przedstawiony na poprzednim laboratium --- w każdym rozwiązaniu tego problemu możemy bez przeszkód zamienić ze sobą dwa kolory, wszystkie wierzchołki zielono przemalować na niebieskie, niebieskie zaś na zielone. Tak powstałe rozwiązania w niczym nie ustępuje oryginalnemu, niemniej istnienie symetrii niesie ze sobą jedną zasadniczą wadę, mianowicie ogromną przestrzeń rozwiązań, w której wiele stanów jest nadmiarowych. Usunięcie ich prowadzi do znacznie efektywniejszego przeszukiwania naprawdę interesujących rozwiązań.
+==== Zadanie Dodatkowe: Magiczne ciągi ====
-  * Ćwiczenia:
-    - Proszę się zastanowić, jak w prosty sposób można wyeliminować symetrię w problemie kolorowania wierzchołków grafu.
-    - Proszę uzupełnić model kolorowania grafu z poprzednich zajęć o prostą redukcję symetrii.
-===== Ograniczenia nadmiarowe: magiczne ciągi =====
-Jedną z podstawowych zasad programowania z ograniczeniami mówi, że ograniczenia są jak pieniądze --- nawet jeżeli jest ich wystarczająco, przydałoby się więcej. Załóżmy, że udało nam się opisać wszystkie ograniczenia konieczne do opisu zadanego problemu (tj. spełnione tylko i wyłącznie przez rozwiązania prawidłowe oraz nie eliminujące żadnych rozwiązań prawidłowych); nie oznacza to wcale, że powinniśmy na nich zaprzestać. Każde kolejne ograniczenie, które dodaje jakąś informację, pozwala
-na zmniejsze przestrzeni przeszukiwania --- solver jest dzięki nim w stanie wcześniej "odciąć" gałęzie przeszukiwania niedające nadziei na przyszłość.
   * Treść problemu: magicznym ciągiem nazywamy taki ciąg liczb ''x0, x1, x2,.., xN'' w którym wartość ''xi'' dla dowolnego ''i'' jest równa liczbie wystąpień ''i'' w tym ciągu. Przykładowy magiczny ciąg o długości 5 to ''2, 1, 2, 0, 0'' --- na ''0''-wym miejscu znajduje się liczba wszystkich ''0'' w ciągu, na miejscu o indeksie ''1'' liczba ''1'' w ciągu, etc.
   * Ćwiczenia:
-    - Zamodelować znajdywanie magicznych ciągów o zadadnej długości w MiniZinc.
+    - Zamodelować znajdywanie magicznych ciągów o zadanej długości w MiniZinc.
-    - Proszę zastanowić się nad nadmiarowymi ograniczeniami, które można dodać do modelu.
+    - Zastosować globalne ograniczenia. <code>
-    - Czy dodanie dodatkowych ograniczeń przyśpieszyło rozwiązanie problemu?
-<WRAP center round tip 60%>
+%%%%%%%%%%%%%
-Przydatna może się okazać funkcja ''bool2int''.
+% DZIEDZINA %
-Czy nie jesteśmy w stanie użyć jednego z globalnych ograniczeń?
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-</WRAP>
+% miejsce na dziedzinę                 %
+% - parametr określający długość ciągu %
+% - tablica zmiennych decyzyjnych      %
-==== Modele łączone ====
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-Jedną z technik dodawania dodatkowych ograniczeń jest wykorzystanie kilku modeli tego samego problemu równocześnie. Pomimo tego, że wszystkie te modele mogą wskazywać na te same rozwiązania, zawarte w nich ograniczenia w innej kolejności zawężają dziedziny zmiennych. Kombinacja kilku modeli pozwala na ograczenie przestrzeni przeszukiwania z kilku "perspektyw" równocześnie.
+%%%%%%%%%%%%%%%%
+% Ograniczenia %
-  - Ćwiczenie: Proszę połączyć ze sobą dwa intuicyjne modele problemu n hetmanów. Czy skróciło to czas rozwiązywania problemu?
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Podpowiedzi:                                 %
-====== Dla niezmordowanych: saper ======
+% - sum(wyrażenie tablicowe) sumuje elementy   %
+% - bool2int(5==5) da w wyniku 1               %
-  - Zadanie z gwiazdką: proszę napisać w MiniZinc prosty solver do gry typu saper. Przykładowe dane wejściowe:
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-<code>
-% -1 to pola o nieznanej zawartości
+solve satisfy;
+%%%%%%%%%%%%%%%%%%%%%%%%
+% PRZYKŁADOWE WYJŚCIE  %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% - magic - magiczny ciąg     %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+output [ "magiczny ciag = ", show(magic),";\n"];</code>
-w = 6;
-h = 6;
-game = array2d(1..w, 1..h, [
-  -1,-1,2,-1,3,-1,
-  -1,-1,-1,-1,-1,-1,
-  -1,-1,2,4,-1,3,
-,-1,3,4,-1,-1,
-  -1,-1,-1,-1,-1,3,
-  -1,3,-1,3,-1,-1,
-    ]);
-</code>

pl/dydaktyka/csp/lab1.1400660537.txt.gz · ostatnio zmienione: 2019/06/27 15:52 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice