Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:csp:lab2 [2016/03/08 23:18] msl [Magiczne ciągi] |
pl:dydaktyka:csp:lab2 [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== Lab CSP: Podstawowe techniki modelowania ===== | ||
| - | |||
| - | ===== Łamanie symetrii ===== | ||
| - | |||
| - | Mówimy, że dany problem przejawia symetrię, jeśli istnieją dla niego rozwiązania symetryczne, tj. takie, które pomimo różnych wartości zmiennych decyzyjnych, są sobie równoważne. Przykładem może być problem kolorowania wierzchołków grafu przedstawiony na poprzednim laboratium --- w każdym rozwiązaniu tego problemu możemy bez przeszkód zamienić ze sobą dwa kolory, wszystkie wierzchołki zielone przemalować na niebieskie, niebieskie zaś na zielone. Tak powstałe rozwiązania w niczym nie ustępuje oryginalnemu, niemniej istnienie symetrii niesie ze sobą jedną zasadniczą wadę, mianowicie ogromną przestrzeń rozwiązań, w której wiele stanów jest nadmiarowych. Usunięcie ich prowadzi do znacznie efektywniejszego przeszukiwania naprawdę interesujących rozwiązań. | ||
| - | |||
| - | ==== Kolorowanie wierzchołków grafu ==== | ||
| - | * Problem: mając dany graf, należy pomalować jego wierzchołki w taki sposób, by wierzchołki połączone krawędzią miały różne kolory. | ||
| - | * Należy: | ||
| - | - Pobrać i rozpakować {{:pl:dydaktyka:csp:csp_coloring.zip|}}. | ||
| - | - Przyjrzeć się modelowi ''csp_coloring.mzn''. | ||
| - | - Korzystając z modelu spróbować rozwiązać problem kolorowania grafu zapisanego w ''csp_coloring_data.dzn''. | ||
| - | * W razie posiadania własnego modelu z pierwszego laboratorium, można go wykorzystać. | ||
| - | * Istnieje szansa, że problem jest zbyt duży, żeby rozwiązać go w rozsądnym czasie. | ||
| - | - Plik ''csp_coloring_data2.dzn'' prócz informacji o grafie zawiera informacje o największej klice w grafie: | ||
| - | * ''minColoursNumber'' - rozmiar największej kliki | ||
| - | * ''maxClique'' - indeksy wierzchołków należących do największej kliki | ||
| - | - Zmienić model tak, aby wykorzystywał informacje z ''csp_coloring_data2.dzn''. | ||
| - | - Spróbować rozwiązać problem opisany w ''csp_coloring_data2.dzn'' korzystając z nowego modelu. | ||
| - | |||
| - | ==== Problem wielo-plecakowy ==== | ||
| - | * Problem: Problem plecakowy z kilkoma identycznymi plecakami zamiast jednego. | ||
| - | * Należy: | ||
| - | - Zastanowić się, gdzie leży symetria w tym problemie. | ||
| - | - Pobrać i rozpakować {{:pl:dydaktyka:csp:csp_n_knapsack.zip|}} | ||
| - | - Przyjrzeć się modelowi ''csp_n_knapsack.mzn''. | ||
| - | * Uwaga: ten model nie jest zbyt dobry; ma jedynie pokazać prostą technikę łamania niektórych symetrii. | ||
| - | * Proszę zwrócić uwagę na zastosowane ograniczenie globalne ''at_most''. | ||
| - | * Model zawiera zdefiniowany predykat ''knapsack'' -> warto wiedzieć, że coś takiego typu można modelować w MiniZinc. Pozwala to na większą modularyzację kodu. | ||
| - | - Uruchomić model z dołączonym plikiem: | ||
| - | * Problem może być za trudny do rozwiązania. | ||
| - | - 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. | ||
| - | - Czerpać zyski. | ||
| - | |||
| - | ===== Ograniczenia nadmiarowe ===== | ||
| - | |||
| - | Jedną z podstawowych zasad programowania z ograniczeniami mówi, że ograniczenia są jak pieniądze --- nawet jeżeli jest ich wystarczająco, przydałoby się więcej. Załóżmy, że udało nam się opisać wszystkie ograniczenia konieczne do opisu zadanego problemu (tj. spełnione tylko i wyłącznie przez rozwiązania prawidłowe oraz nie eliminujące żadnych rozwiązań prawidłowych); nie oznacza to wcale, że powinniśmy na nich zaprzestać. Każde kolejne ograniczenie, które dodaje jakąś informację, pozwala | ||
| - | na zmniejszenie przestrzeni przeszukiwania --- solver jest dzięki nim w stanie wcześniej "odciąć" gałęzie przeszukiwania niedające nadziei na przyszłość. | ||
| - | |||
| - | ==== Magiczne ciągi ===== | ||
| - | |||
| - | * Należy: | ||
| - | - Odkopać model magicznych ciągów z poprzednich zajęć. | ||
| - | - Dodać do niego nadmiarowe ograniczenia. Podpowiedzi: | ||
| - | * 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)? | ||
| - | - Porównać działanie modelu ''z'' i ''bez'' dodatkowych ograniczeń na dłuższych ciągach. | ||
| - | - Czerpać zyski. | ||
| - | |||
| - | ==== Modele łączone - n-hetmans return! ==== | ||
| - | |||
| - | Jedną z technik dodawania dodatkowych ograniczeń jest wykorzystanie kilku modeli tego samego problemu równocześnie. Pomimo tego, że wszystkie te modele mogą wskazywać na te same rozwiązania, zawarte w nich ograniczenia w innej kolejności zawężają dziedziny zmiennych. Kombinacja kilku modeli pozwala na ograczenie przestrzeni przeszukiwania z kilku "perspektyw" równocześnie. | ||
| - | |||
| - | * Problem: ponownie problem n-hetmanów. | ||
| - | * Należy: | ||
| - | - Odkopać model n-hetmanów z poprzednich zajęć. | ||
| - | - 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 . | ||
| - | - Powiązać ze sobą ograniczeniami oba zestawy zmiennych. | ||
| - | - Porównać działanie modelu pojedynczego i dualnego na problemach wielu hetmanów. | ||
| - | - Czerpać zyski. | ||
| - | |||
| - | ===== Sterowanie przeszukiwaniem ===== | ||
| - | |||
| - | O ile budowanie modelu w programowaniu z ograniczeniami jest zadaniem czysto deklaratywnym, często wiele zależy od sposobu, w jaki przeszukiwana jest przestrzeń rozwiązań. Istnieje wiele możliwych strategii, jednak w podstawowym przypadku można je zdefiniować poprzez dwa parametry: | ||
| - | |||
| - | - kolejność wyboru zmiennych - np. w kolejnym kroku solver ustali wartość zmiennej, która ma najmniejszą dziedzinę; ma największą dziedzinę; w kolejności zdefiniowania przez użytkownika, etc. | ||
| - | - kolejność wyboru wartości - po wyborze zmiennej, solver musi przypisać jej wartość z dziedziny, np. wartość najmniejszą, medianę dziedziny, wartość losową, etc. | ||
| - | |||
| - | Aby w MiniZincu wymusić na solverze strategię przeszukiwania, należy użyć tzw. adnotacji (ang. //annotations//). W ogólnym przypadku można je przypisywać do zmiennych podobnie jak inne parametry, ale najczęściej używa się ich przy specyfikacji celu, np. <code> | ||
| - | solve :: int_search(array, first_fail, indomain_min, complete) satisfy; | ||
| - | </code> | ||
| - | 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. | ||
| - | |||
| - | ==== n-hetmans again ==== | ||
| - | |||
| - | * Problem: już chyba każdy go zna. | ||
| - | * Należy: | ||
| - | - Spróbować różnych adnotacji do przeszukiwania dla tego problemu, np. <code> | ||
| - | int_search(rows, input_order, indomain_min, complete); | ||
| - | int_search(rows, input_order, indomain_median, complete); | ||
| - | int_search(rows, first_fail, indomain_min, complete); | ||
| - | int_search(rows, first_fail, indomain_median, complete);</code> | ||
| - | - Zerknąć do [[http://www.minizinc.org/downloads/doc-latest/flatzinc-spec.pdf|dokumentacji flatzinc, rozdział 5.6.1]]. Przeczytać opisy różnych strategii i wypróbować jakąś szaloną. | ||
| - | - Porównać prędkość działania solvera n-hetmanów dla różnych strategii. | ||
| - | - Wyczerpać zyski z dzisiejszego laboratorium. | ||
| - | |||
