Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:csp:intro [2014/05/14 01:14] msl [Dodanie karty menu] |
pl:dydaktyka:csp:intro [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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ń. | ||
| Linia 23: | Linia 23: | ||
| == 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 ===== | ||
| Linia 35: | Linia 52: | ||
| === 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> | ||
| Linia 86: | Linia 103: | ||
| ==== 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> | ||
| Linia 94: | Linia 111: | ||
| 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. W IDE można to wszystko "wyklikać" we względnie intuicyjny sposób. | + | 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%> | ||
| Linia 172: | Linia 189: | ||
| </code> | </code> | ||
| W IDE należy mieć otwarty plik ''.dzn'' i należy go wybrać jako ''Data file'' w zakładce ''Configuration''. | W IDE należy mieć otwarty plik ''.dzn'' i należy go wybrać jako ''Data file'' w zakładce ''Configuration''. | ||
| - | ==== Menu na miarę XXI wieku ==== | + | ===== 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. | ||
| + | |||
| + | |||
| + | |||
