Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:csp:lab1 [2015/05/20 02:22] msl [Problem n-hetmanów] |
pl:dydaktyka:csp:lab1 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 49: | Linia 49: | ||
| </WRAP> | </WRAP> | ||
| + | ==== Kolorowanie grafów ==== | ||
| - | ==== Magiczne ciągi ==== | + | * 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]]. |
| - | + | ||
| - | * 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 zadanej długości w MiniZinc. <code> | + | - 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 % | % DZIEDZINA % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | + | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| - | % miejsce na dziedzinę % | + | % miejsce na dziedzinę % |
| - | % - parametr określający długość ciągu % | + | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| - | % - tablica zmiennych decyzyjnych % | + | |
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | + | |
| - | + | ||
| %%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%% | ||
| - | % Ograniczenia % | + | % OGRANICZENIA % |
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | + | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| - | % Podpowiedzi: % | + | % miejsce na ograniczenia % |
| - | % - sum(wyrażenie tablicowe) sumuje elementy % | + | % podpowiedź: % |
| - | % - bool2int(5==5) da w wyniku 1 % | + | % - warto użyć if'a, by sprawdzić, czy dwa % |
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | + | % wierzchołki są połączone % |
| - | + | % - liczba kolorów to może być maksymalny % | |
| - | solve satisfy; | + | % numer użytego koloru % |
| - | + | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| + | |||
| + | %%%%%%%% | ||
| + | % CEL % | ||
| + | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| + | % Zminimalizuj użytą liczbę kolorów % | ||
| + | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| + | solve minimize coloursNumber; | ||
| %%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%% | ||
| % PRZYKŁADOWE WYJŚCIE % | % PRZYKŁADOWE WYJŚCIE % | ||
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | + | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| - | % - magic - magiczny ciąg % | + | % - coloursNumber - liczba użytych kolorów % |
| - | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | + | % - nodes - tablica wierzchołków grafu z % |
| - | output [ "magiczny ciag = ", show(magic),";\n"];</code> | + | % 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 ===== | ===== Globalne ograniczenia ===== | ||
| Linia 91: | Linia 131: | ||
| * Ć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); % |
| - | % globalne 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 | ||
| Linia 144: | Linia 184: | ||
| ]); | ]); | ||
| </code> | </code> | ||
| - | - Proszę zastosować globalne ograniczenia do problemu n-hetmanów i magicznych ciągów. | + | - Proszę zastosować globalne ograniczenia do problemu n-hetmanów |
| | | ||
| Linia 151: | Linia 191: | ||
| http://www.minizinc.org/downloads/doc-latest/mzn-globals.html | http://www.minizinc.org/downloads/doc-latest/mzn-globals.html | ||
| </WRAP> | </WRAP> | ||
| + | |||
| + | |||
| + | ==== Zadanie Dodatkowe: 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. | ||
| + | - Zastosować globalne ograniczenia. <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> | ||
