Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:csp:lab1 [2014/05/27 17:10] msl [Globalne ograniczenia: sudoku] |
pl:dydaktyka:csp:lab1 [2019/06/27 15:50] (aktualna) |
====== 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. | 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: | * Ćwiczenia: |
- Proszę uzupełnić poniższy model problemu n-hetmanów | - Proszę uzupełnić poniższy model problemu n-hetmanów <code> |
| %%%%%%%%%%%%% |
| % DZIEDZINA % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| % miejsce na dziedzinę % |
| % podpowiedź: % |
| % var 1..N: x; deklaruje zmienną % |
| % o dziedzinie 1..N; % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
<code> | %%%%%%%%%%%%%%%% |
%%%%%%%%%%%%% | % OGRANICZENIA % |
% DZIEDZINA % | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | % miejsce na ograniczenia % |
% miejsce na dziedzinę % | % podpowiedź: % |
% podpowiedź: % | % row_i = row_j (-/+) (j - i) % |
% var 1..N: x; deklaruje zmienną % | % opisuje hetmanów stojących na % |
% o dziedzinie 1..N; % | % tej samej diagonali, gdzie: % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | % - i,j - numery kolumn % |
| % - row_n - pozycja hetmana w n-tej kolumnie % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
%%%%%%%%%%%%%%%% | solve satisfy; |
% 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 satify; | %%%%%%%%%%%%%%%%%%%%%%%% |
| % PRZYKŁADOWE WYJŚCIE % |
%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
% PRZYKŁADOWE WYJŚCIE % | % - rows[i] pozycja hetmana w i-tym wierszu % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | % - N - liczba hetmanów % |
% - rows[i] pozycja hetmana w i-tym wierszu % | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
% - N - liczba hetmanów % | output [ if fix(rows[j]) == i then "H" else "." endif ++ |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
output [ if fix(rows[j]) == i then "H" else "." endif ++ | |
if j == N then "\n" else "" endif | i,j in 1..N]</code> | 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> |
| |
| ==== Kolorowanie grafów ==== |
| |
===== Globalne ograniczenia: sudoku ===== | * 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ę % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
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ń. | %%%%%%%%%%%%%%%% |
| % 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 % |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
* Treść problemu: należy zaimplementować solver sudoku (http://pl.wikipedia.org/wiki/Sudoku) | %%%%%%%% |
| % 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> |
| |
| |
| ==== Sudoku ==== |
| |
| * Treść problemu: należy zaimplementować solver sudoku (patrz: [[http://pl.wikipedia.org/wiki/Sudoku|wikipedia]]) |
* Ćwiczenia: | * Ćwiczenia: |
- Proszę uzupełnić poniższy model sudoku: <code> | - Proszę uzupełnić poniższy model sudoku: <code> |
%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%% |
% PRZYPOMNIENIE % | % PRZYPOMNIENIE % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
% Coś tu jeszcze powinno być.% | % Coś tu jeszcze powinno być.% |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
%%%%%%%%%%%%% | %%%%%%%%%%%%% |
% DZIEDZINA % | % DZIEDZINA % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
% miejsce na dziedzinę, podpowiedź: % | % miejsce na dziedzinę, podpowiedź: % |
% dwie oddzielne tablice, jedna % | % dwie oddzielne tablice, jedna % |
% odpowiedzialna z stan początkowy; % | % odpowiedzialna z stan początkowy; % |
% druga przechowuje zmienne decyzyjne% | % druga przechowuje zmienne decyzyjne% |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%% |
% Ograniczenia % | % Ograniczenia % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
% - constraint alldifferent(tablica zmiennych); % | % - constraint alldifferent(tablica zmiennych); % |
% dodaje ograniczenie, w którym wszystkie % | % globalne ograniczenie, w którym wszystkie % |
% zmienne z tablicy muszą mieć różną wartość % | % zmienne z tablicy muszą mieć różną wartość % |
% - należy zapewnić, aby wartości zmiennych były % | % - należy zapewnić, aby wartości zmiennych były % |
% równe odpowiednik polom stanu początkowego % | % równe odpowiednik polom stanu początkowego % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
solve satisfy; | solve satisfy; |
| |
%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%% |
% PRZYKŁADOWE WYJŚCIE % | % PRZYKŁADOWE WYJŚCIE % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
% - puzzle - dwuwumiarowa tablica zmiennych % | % - puzzle - dwuwumiarowa tablica zmiennych % |
% o rozmiarze NxN % | % o rozmiarze NxN % |
% - N - rozmiar planszy, równy S*S % | % - N - rozmiar planszy, równy S*S % |
% - S - rozmiar sektora planszy % | % - S - rozmiar sektora planszy % |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
output [ show(puzzle[i,j]) ++ " " ++ | output [ show(puzzle[i,j]) ++ " " ++ |
if j mod S == 0 then " " else "" endif ++ if j == N /\ i != N then | 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 | if i mod S == 0 then "\n\n" else "\n" endif else "" endif |
| i,j in PuzzleRange ] ++ ["\n"]; | | i,j in PuzzleRange ] ++ ["\n"]; |
</code> | </code> |
- Poniżej przykładowe dane wejściowe: <code> % 0 to pola o nieznanej wartości | - Poniżej przykładowe dane wejściowe: <code> % 0 to pola o nieznanej wartości |
]); | ]); |
</code> | </code> |
- Poszę zastosować globalne ograniczenie do problemu n-hetmanów. | - Proszę zastosować globalne ograniczenia do problemu n-hetmanów |
| |
| |
<WRAP center round tip 60%> | <WRAP center round tip 60%> |
Lista globalnych ograniczeń dostępnych w MiniZinc: | 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 |
</WRAP> | </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. | * 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: | * Ć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,-1,3,4,-1,-1, | |
-1,-1,-1,-1,-1,3, | |
-1,3,-1,3,-1,-1, | |
]); | |
</code> | |