--- pl:dydaktyka:csp:lab1 [2015/05/20 02:23]
msl [Sudoku]
+++ pl:dydaktyka:csp:lab1 [2019/06/27 15:50] (aktualna)
@@ Linia 49: / Linia 49: @@
 </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:
-    - 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 %
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% 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  %
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% - 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 =====
@@ Linia 144: / Linia 184: @@
 ]);
 </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
 </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>

pl/dydaktyka/csp/lab1.1432081397.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