Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:csp:intro [2014/05/14 00:43] msl [Uruchomienie programu] |
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: == |
Ściągnięte archiwa zawierają skompilowane już pliki binarne. Instalacja sprowadza się do rozpakowania plików. W przypadku paczki zawierającej solver rozsądne jest wywołanie skryptu ''SETUP'', który przygotowuje środowisko do działania. W przypadku paczki zawierającej IDE, uruchamia się ono poprzez uruchomienie skryptu ''MiniZincIDE.sh''. Po pierwszym uruchomieniu może być konieczne wskazanie ściezki do katalogu z solverem. | Ściągnięte archiwa zawierają skompilowane już pliki binarne. Instalacja sprowadza się do rozpakowania plików. W przypadku paczki zawierającej solver rozsądne jest wywołanie skryptu ''SETUP'', który przygotowuje środowisko do działania. W przypadku paczki zawierającej IDE, uruchamia się ono poprzez uruchomienie skryptu ''MiniZincIDE.sh''. Po pierwszym uruchomieniu może być konieczne wskazanie ściezki do katalogu z solverem. |
| |
| <WRAP center round important 60%> |
| Aby IDE zadziałało na serwerze borg, należy do katalogu ''lib'' skopiować bibliotekę z archiwum: {{:pl:dydaktyka:csp:libqt5network.so.5.zip}} |
| </WRAP> |
| |
| |
===== Rozwiązanie problemu ===== | ===== Rozwiązanie problemu ===== |
=== 1. Krok pierwszy: zmienne decyzyjne === | === 1. Krok pierwszy: zmienne decyzyjne === |
| |
Chcemy ustalić z czego ma składać się zamówienie, zatem potrzebujemy wiedzieć, ile razy ma zostać zamówione każde danie z osobna. Każda zmienna ma opisywać ile egzemplarzy danego dania zamówiono, powinna być więc typu liczby całkowitej (zakładamy, że nie można zamówić połowy dania). W MiniZinc zapiszemy to następująco: | Chcemy ustalić z czego ma składać się zamówienie, zatem potrzebujemy wiedzieć, ile razy ma zostać zamówione każde danie z osobna. Każda zmienna ma opisywać ile egzemplarzy danego dania zamówiono, powinna być więc typu liczby całkowitej (zakładamy, że nie można zamówić połowy dania). W MiniZinc zapiszemy to następująco (słowo kluczowe ''var''wskazuje na zmienne decyzyjne): |
| |
<code> | <code> |
==== Uruchomienie programu ==== | ==== Uruchomienie programu ==== |
| |
Wszystkie powyższe linijki należy skopiować w danej kolejności do pliku z rozszerzeniem ''.mzn''. Następnie w katalogu z plikiem, należy wykonać: | Wszystkie powyższe linijki należy skopiować w danej kolejności do pliku z rozszerzeniem :!:''.mzn'':!:. Następnie w katalogu z plikiem, należy wykonać: |
<code> | <code> |
mzn-g12fd <nazwa_pliku> | mzn-g12fd <nazwa_pliku> |
mzn-g12fd --all-solutions <nazwa_pliku> | mzn-g12fd --all-solutions <nazwa_pliku> |
</code> | </code> |
jeżeli nie chcemy, by solver zatrzymał się pierwszym możliwym rozwiązaniu. | jeżeli nie chcemy, by solver zatrzymał się pierwszym możliwym rozwiązaniu. W IDE można to wszystko "wyklikać" we względnie intuicyjny sposób (menu na górze -> run, configuration -> print all solutions). |
<WRAP center round tip 60%> | <WRAP center round tip 60%> |
Należy zadbać, żeby katalog ''bin'' solvera był na liście ściezek PATH:\\ | Należy zadbać, żeby katalog ''bin'' solvera był na liście ściezek PATH:\\ |
</WRAP> | </WRAP> |
| |
| ===== Napiwek 50% ===== |
| |
| Komiks twierdzi, że dostaniemy napiwek, jeżeli zdołamy stworzyć rozwiązanie ogólne. Napiwki są przydatne, zatem bierzemy się do roboty i parametryzujemy nasz problem. |
| |
| === 1. Krok pierwszy: parametry === |
| Najpierw ustalamy, ile pozycji zawiera menu i do jakiej liczby ma się równać koszt zamówienia. Brak słówka ''var'' sugeruje, że te wartości są niezmienne. |
| |
| <code> |
| int: menu_length = 6; |
| int: money_limit = 1505; |
| </code> |
| |
| Następnie posłużymy się tablicami w celu opisania zawartości menu. Każda tablica ma ustalony zakres indeksów i typ swoich elementów. |
| |
| <code> |
| array[1..menu_length] of int: menu_prices = [215, 275, 335, 355, 420, 580]; |
| array[1..menu_length] of string: menu_names = ["fruit", "fries", "salad", "wings", "sticks", "sampler"]; |
| </code> |
| |
| === 2. Krok drugi: definicja zmiennych === |
| |
| W wersji za napiwek liczba zmiennych również jest sparametryzowana -- jest ich tyle samo, ile pozycji w menu. |
| |
| <code> |
| array[1..menu_length] of var int: order; |
| </code> |
| |
| === 3. Krok trzeci: ograniczenia === |
| |
| Liczba ograniczeń również zależy od rozmiarów menu. Aby je zdefiniować, posłużymy się funkcjami agregującymi: ''forall'' --- dołącza wszystkie ograniczenia w tablicy, ''sum'' --- sumuje liczby zawarte w tablicy. Notacja ''[array[i]*2 | i in 1..array_length]'' jest nazywana ''array comprehension'' i należy ją rozumieć jako wyrażenie przetwarzające elementy z jednej tablicy (''1..array_length'') na nową tablicę zawierającą elementy po lewej stronie ''|''. |
| |
| <code> |
| constraint forall([order[i] >= 0 | i in 1..menu_length]); |
| constraint sum([order[i] * menu_prices[i] | i in 1..menu_length]) == money_limit; |
| </code> |
| |
| === 4. Krok czwarty: cel === |
| |
| Cel nie ulega zmianie. |
| |
| === 5. Krok piąty: wypisanie wyniku === |
| |
| Aby wypisać wynik, również posłużymy się notacją ''array comprehension''. Operator '++' łączy napisy, funkcja ''show'' przekształca liczbę w napis. |
| |
| <code> |
| output [menu_names[i] ++ ": " ++ show(order[i]) ++ "\n" | i in 1..menu_length]; |
| </code> |
| |
| ==== Uruchomienie kodu ==== |
| |
| Przebiega bez zmian. Proszę uruchomić program i zainkasować 50% z wyimaginowanej sumy pieniędzy. |
| ===== Dodanie karty menu ===== |
| |
| Słabym elementem naszej dotychczasowej pracy jest zapisywanie wszystkich parametrów wewnątrz programu --- przy zmianie menu musielibyśmy zmieniać program, co nie jest szczególnie ogólne i być może ten napiwek to nam się jeszcze do końca nie należy. Aby poradzić sobie z tym problemem, MiniZinc może wczytywać problemy z zewnętrznych plików. Proszę stworzyć plik o rozszerzeniu ''.dzn'' i zawartości: |
| |
| <code> |
| menu_length = 6; |
| money_limit = 1505; |
| menu_prices = [215, 275, 335, 355, 420,580]; |
| menu_names = ["fruit", "fries", "salad", "wings", "sticks", "sampler"]; |
| </code> |
| |
| Następnie proszę usunąć z programu wartości parametrów, zostawiając jedynie ich deklaracje, np. w miejsce linijki ''int: menu_length = 6;'' ma się znaleźć jedynie ''int: menu_length;''. |
| |
| ==== Uruchamianie programu ==== |
| |
| Z poziomu konsoli należy wpisać: |
| <code> |
| mzn-g12fd -d <plik.dzn> <plik.mzn> |
| </code> |
| W IDE należy mieć otwarty plik ''.dzn'' i należy go wybrać jako ''Data file'' w zakładce ''Configuration''. |
===== Problem portfelowy ===== | ===== Problem portfelowy ===== |
| |
| Dotychczas nasz cel był zdefiniowany jedynie jako ''satisfy'' --- istnieją jeszcze dwa inne rodzaje celów: ''maximize <wyrażenie>'' oraz ''minimize wyrażenie'', które odpowiednio poszukują rozwiązań, które maksymalizują/minimalizują wartość wyrażenia, np. |
| <code> |
| solve minimize sum(order); |
| </code> |
| znajdzie takie zamówienie, które spełnia wymagane ograniczenia i zawiera jak najmniej dań. |
| |
| === Ćwiczenie === |
| |
| - Proszę dodać do programu kolejny parametr o nazwie ''yumyum_factors''. Będzie to tablica liczb całkowitych, które wskazują jak bardzo dana pozycja w menu jest smaczna (im większy współczynnik yumyum, tym smaczniejsze danie). |
| - Poszukujemy takiego rozwiązania, który maksymalizuję sumę wartości yumyum zamiówionych dań, |
| - 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. |
| |
| |
==== Dodanie karty menu ==== | |
| |
| |
==== Menu na miarę XXI wieku ==== | |
| |