Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:csp:lab2 [2016/03/08 23:18] msl [Magiczne ciągi] |
pl:dydaktyka:csp:lab2 [2019/06/27 15:50] (aktualna) |
- 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. |
| |
==== 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? |
* 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 ===== |
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 ==== |