Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:csp:intro [2014/05/14 10:30] msl [Kolorowanie grafu] |
pl:dydaktyka:csp:intro [2019/06/27 15:50] (aktualna) |
====== Constraint Programming ====== | ====== Constraint Programming: Wprowadzenie ====== |
| |
Programowanie z ograniczeniami (ang. //Constraint Programming//, dalej nazywane CSP) jest deklaratywnym paradygmatem programowania, skupionym na modelowaniu problemu i wskazaniu wymagań (ograniczeń) stawianych jego rozwiązaniom. Do obowiązków programisty należy: | Programowanie z ograniczeniami (ang. //Constraint Programming//, dalej nazywane CSP) jest deklaratywnym paradygmatem programowania, skupionym na modelowaniu problemu i wskazaniu wymagań (ograniczeń) stawianych jego rozwiązaniom. Do obowiązków programisty należy: |
| |
* zamodelowanie problemu poprzez zdefiniowanie zmiennych o odpowiedniych dziedzinach, | * zamodelowanie problemu poprzez zdefiniowanie zmiennych o odpowiedniych dziedzinach, |
* zdefiniowanie ograniczenia, które określają dozwolone wartości zmiennych w rozwiązaniu | * zdefiniowanie ograniczeń, które określają dozwolone wartości zmiennych w rozwiązaniu |
* [opcjonalne] podanie kryterium oceny rozwiązania, np. minimalizacja długości trasy w problemie komiwojażera | * [opcjonalne] podanie kryterium oceny rozwiązania, np. minimalizacja długości trasy w problemie komiwojażera |
* [opcjonalne] sprecyzowanie procesu przeszukiwania przestrzeni możliwych rozwiązań. | * [opcjonalne] sprecyzowanie procesu przeszukiwania przestrzeni możliwych rozwiązań. |
| |
== Do ściągnięcia: == | == Do ściągnięcia: == |
* [[http://www.minizinc.org/downloads/release-1.6/minizinc-1.6-x86_64-unknown-linux-gnu.tar.gz|MiniZinc (CSP solver)]] | <WRAP center round tip 60%> |
* [[http://www.minizinc.org/downloads/MiniZincIDE/MiniZincIDE-0.9.3-linux-x86_64.tgz|MiniZinc IDE]] | Sala 316 ma już zainstalowane wszystkie potrzebne narzędzia. Jeżeli właśnie w niej siedzisz, możesz pominąć tę sekcję :) |
| </WRAP> |
| |
| * [[http://www.minizinc.org/downloads/release-1.6/minizinc-1.6-x86_64-unknown-linux-gnu.tar.gz|MiniZinc (CSP solver) w wersji 1.6]] lub [[http://www.minizinc.org/downloads/release-2.0.1/minizinc-2.0.1-linux64.tar.gz|nowsza wersja]] |
| * [[http://www.minizinc.org/downloads/MiniZincIDE/MiniZincIDE-0.9.3-linux-x86_64.tgz|MiniZinc IDE w wersji 0.9.3]] lub [[http://www.minizinc.org/downloads/MiniZincIDE/MiniZincIDE-0.9.6-linux-x86_64.tgz|nowsza wersja]] |
| |
| Wybór wersji nowszej ma wady: |
| * nie testowana na borgu (możesz być pierwsz(-y/-a), który tego dokona) |
| * nie powstała jeszcze oficjalna dokumentacja dla tej wersji |
| i zalety: |
| * zostało usuniętych wiele ograniczeń, który w duży stopniu utrudniały modelowanie |
| * ma nowe funkcjonalności, użyteczne, gdyby ktoś się chciał zając tematem bardziej poważnie |
| * IDE stało się bardziej profesjonalne |
| |
== Instalacja: == | == Instalacja: == |
- Należy zadbać, aby koszt zamówienia nie musiał być równy wartości ''money_limit'', ale mógł być również od niego mniejszy. | - Należy zadbać, aby koszt zamówienia nie musiał być równy wartości ''money_limit'', ale mógł być również od niego mniejszy. |
| |
===== Kolorowanie grafu ===== | |
| |
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/Graph_coloring#Vertex_coloring|Kolorowanie na angielskim wiki]] | |
| |
=== Ćwiczenie === | |
| |
- Proszę zamodelować problem kolorowania grafu w MiniZinc. | |
| |
<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> | |
W razie problemów, poniżej jest link do tutoriala. | |
</WRAP> | |
| |
| |
===== Zadanie domowe ====== | |
| |
Proszę zapoznać się pobieżnie z [[http://www.minizinc.org/downloads/doc-latest/minizinc-tute.pdf|tutorialem dla MiniZinc]]. | |
| |