Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:csp:lab2 [2016/03/08 22:51] msl [Problem wielo-plecakowy] |
pl:dydaktyka:csp:lab2 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 30: | Linia 30: | ||
| - Uruchomić model z dołączonym plikiem: | - Uruchomić model z dołączonym plikiem: | ||
| * Problem może być za trudny do rozwiązania. | * Problem może być za trudny do rozwiązania. | ||
| + | * Gdyby solver zwracał wynik "UNSATISFIABLE", proszę spróbować użyć solvera "G12 fd" w zakładce "Configuration" | ||
| - Dodać do kodu łamanie symetrii korzystająć z ograniczenia globalnego [[http://www.minizinc.org/2.0/doc-lib/doc-globals-lexicographic.html|''lex_less'']]. Pozwala ona na wymuszenie kolejności plecaków. Plecaki muszą być zawsze uporządkowe leksykograficznie ze względu na swoją zawartość. | - Dodać do kodu łamanie symetrii korzystająć z ograniczenia globalnego [[http://www.minizinc.org/2.0/doc-lib/doc-globals-lexicographic.html|''lex_less'']]. Pozwala ona na wymuszenie kolejności plecaków. Plecaki muszą być zawsze uporządkowe leksykograficznie ze względu na swoją zawartość. | ||
| - Uruchomić nowy model z tymi samymi danymi. | - Uruchomić nowy model z tymi samymi danymi. | ||
| Linia 40: | Linia 41: | ||
| ==== Magiczne ciągi ===== | ==== Magiczne ciągi ===== | ||
| + | |||
| + | Jeżeli ktoś nie zrobił tego wcześniej, proszę przed przystąpieniem do ćwiczenia przynajmniej przeczytać opis problemu na stronie poprzedniego laboratorium. | ||
| * Należy: | * Należy: | ||
| - | - Odkopać model magicznych ciągów z poprzednich zajęć. | + | - Ściągnąć i zrozumieć model: {{:pl:dydaktyka:csp:csp_magic_series.zip|}} |
| - Dodać do niego nadmiarowe ograniczenia. Podpowiedzi: | - Dodać do niego nadmiarowe ograniczenia. Podpowiedzi: | ||
| * ile powinna wynosić suma magicznego ciągu? | * ile powinna wynosić suma magicznego ciągu? | ||
| - | * ile powinna wynosić suma elementów magicznego ciągu, pomnożonych przez numery swoich indeksów (indeksując od 0). | + | * ile powinna wynosić suma elementów magicznego ciągu, pomnożonych przez numery swoich indeksów (indeksując od 0)? |
| - Porównać działanie modelu ''z'' i ''bez'' dodatkowych ograniczeń na dłuższych ciągach. | - Porównać działanie modelu ''z'' i ''bez'' dodatkowych ograniczeń na dłuższych ciągach. | ||
| - Czerpać zyski. | - Czerpać zyski. | ||
| Linia 55: | Linia 58: | ||
| * Problem: ponownie problem n-hetmanów. | * Problem: ponownie problem n-hetmanów. | ||
| * Należy: | * Należy: | ||
| - | - Odkopać model n-hetmanów z poprzednich zajęć. | + | - Odkopać model n-hetmanów z poprzednich zajęć. Ewentualnie pobrać ten: {{:pl:dydaktyka:csp:csp_n_hetmans.zip|}} |
| - Dopisać do niego drugą możliwość wyboru zmiennych decyzyjnych i ograniczeń | - Dopisać do niego drugą możliwość wyboru zmiennych decyzyjnych i ograniczeń | ||
| - | * Jeżeli ostatnio zmienne były indeksowane kolumanmi i wskazywały na numer wiersza, należy dopisać model odwrotny . | + | * Jeżeli ostatnio zmienne były indeksowane kolumnami i wskazywały na numer wiersza, należy dopisać model odwrotny. |
| - Powiązać ze sobą ograniczeniami oba zestawy zmiennych. | - Powiązać ze sobą ograniczeniami oba zestawy zmiennych. | ||
| + | * Pomocne może być globalne ograniczenie [[http://www.minizinc.org/2.0/doc-lib/doc-globals-channeling.html|''inverse'']] | ||
| - Porównać działanie modelu pojedynczego i dualnego na problemach wielu hetmanów. | - Porównać działanie modelu pojedynczego i dualnego na problemach wielu hetmanów. | ||
| - | - Czerpać zyski. | + | - Czerpać zyski <wrap lo>z nabytej wiedzy, bowiem nowe solvery radzą sobie z n-hetmanami lepiej bez nadmiarowych ograniczeń. Niemniej w innych modelach technika ta może okazać się istotną optymalizacją.</wrap> |
| ===== Sterowanie przeszukiwaniem ===== | ===== Sterowanie przeszukiwaniem ===== | ||
| Linia 74: | Linia 78: | ||
| daje solverovi znać, że tablica zmiennych array zawiera liczby i należy ją przeszukiwać, najpierw wybierając zmienne o najmniejszej dziedzinie (''first_fail''), następnie przypisywać im jak najmniejsze wartości (''indomain_min'') i przeszukiwać całą przestrzeń rozwiązań (''complete''). | daje solverovi znać, że tablica zmiennych array zawiera liczby i należy ją przeszukiwać, najpierw wybierając zmienne o najmniejszej dziedzinie (''first_fail''), następnie przypisywać im jak najmniejsze wartości (''indomain_min'') i przeszukiwać całą przestrzeń rozwiązań (''complete''). | ||
| - | Istnieją bardziej zaawansowane metody określania strategii w poszczególnych solverach, ale MiniZinc chcąc być językiem niezależnych od solvera nie może sobie na to pozwolić. Aktualnie konstrukcje pozwalające na pełną kontrolę nad procesem przeszukiwania działają jedynie dla solvera Gecode i wymagają dodania pewnych patchy do standardowej dystrybucji MiniZinc. | + | Istnieją bardziej zaawansowane metody określania strategii w poszczególnych solverach, ale MiniZinc chcąc być językiem niezależnym od solvera nie może sobie na to pozwolić. Aktualnie konstrukcje pozwalające na pełną kontrolę nad procesem przeszukiwania działają jedynie dla solvera Gecode i wymagają dodania pewnych patchy do standardowej dystrybucji MiniZinc. |
| ==== n-hetmans again ==== | ==== n-hetmans again ==== | ||
