Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:csp:lab1 [2015/05/20 02:23] msl [Sudoku] |
pl:dydaktyka:csp:lab1 [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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 ==== | ||
| - | |||
| - | * 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ę 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; % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | | ||
| - | %%%%%%%%%%%%%%%% | ||
| - | % 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> | ||
| - | |||
| - | |||
| - | ==== Magiczne ciągi ==== | ||
| - | |||
| - | * 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 zadanej długości w MiniZinc. <code> | ||
| - | |||
| - | %%%%%%%%%%%%% | ||
| - | % DZIEDZINA % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | % miejsce na dziedzinę % | ||
| - | % - parametr określający długość ciągu % | ||
| - | % - tablica zmiennych decyzyjnych % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | | ||
| - | %%%%%%%%%%%%%%%% | ||
| - | % Ograniczenia % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | % Podpowiedzi: % | ||
| - | % - sum(wyrażenie tablicowe) sumuje elementy % | ||
| - | % - bool2int(5==5) da w wyniku 1 % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | | ||
| - | solve satisfy; | ||
| - | | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | % PRZYKŁADOWE WYJŚCIE % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | % - magic - magiczny ciąg % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | output [ "magiczny ciag = ", show(magic),";\n"];</code> | ||
| - | |||
| - | ===== 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: | ||
| - | - Proszę uzupełnić poniższy model sudoku: <code> | ||
| - | %%%%%%%%%%%%%%%%% | ||
| - | % PRZYPOMNIENIE % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | % Coś tu jeszcze powinno być.% | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| - | |||
| - | %%%%%%%%%%%%% | ||
| - | % 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, 0, 2, 0, 5, 0, 0, 0, | ||
| - | 0, 9, 0, 0, 0, 0, 7, 3, 0, | ||
| - | 0, 0, 2, 0, 0, 9, 0, 6, 0, | ||
| - | 2, 0, 0, 0, 0, 0, 4, 0, 9, | ||
| - | 0, 0, 0, 0, 7, 0, 0, 0, 0, | ||
| - | 6, 0, 9, 0, 0, 0, 0, 0, 1, | ||
| - | 0, 8, 0, 4, 0, 0, 1, 0, 0, | ||
| - | 0, 6, 3, 0, 0, 0, 0, 8, 0, | ||
| - | 0, 0, 0, 6, 0, 8, 0, 0, 0 | ||
| - | ]); | ||
| - | </code> | ||
| - | - Proszę zastosować globalne ograniczenia do problemu n-hetmanów i magicznych ciągów. | ||
| - | | ||
| - | |||
| - | <WRAP center round tip 60%> | ||
| - | Lista globalnych ograniczeń dostępnych w MiniZinc: | ||
| - | http://www.minizinc.org/downloads/doc-latest/mzn-globals.html | ||
| - | </WRAP> | ||
