Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:csp:lab3 [2016/03/16 01:18] msl utworzono |
pl:dydaktyka:csp:lab3 [2019/06/27 15:50] (aktualna) |
Na rozgrzewkę rozwiążmy prosty problem, który w znaczny sposób ułatwi nam modelowanie problemu końcowego. Zajmijmy się tak zwanym problemem pakowania. Istnieje wiele rodzajów problemów pakowania - to, co je łączy, to konieczność upakowania n-wymiarowych brył w n-wymiarowym pojemniku. My zajmiemy się bardzo prostym przypadkiem pakowania kwadratów w pojemniku o kształcie prostokąta. | Na rozgrzewkę rozwiążmy prosty problem, który w znaczny sposób ułatwi nam modelowanie problemu końcowego. Zajmijmy się tak zwanym problemem pakowania. Istnieje wiele rodzajów problemów pakowania - to, co je łączy, to konieczność upakowania n-wymiarowych brył w n-wymiarowym pojemniku. My zajmiemy się bardzo prostym przypadkiem pakowania kwadratów w pojemniku o kształcie prostokąta. |
| |
{{ :pl:dydaktyka:csp:square_packing.png?400|}} | {{ :pl:dydaktyka:csp:square_packing.png?300|}} |
* **Definicja problemu**: mając ''n'' kwadratów o rozmiarach kolejno ''1x1,2x2,...,nxn'', należy znaleźć prostokąt a najmniejszym polu, wewnątrz którego zmieszczą się te kwadraty bez nachodzenia na siebie. | * **Definicja problemu**: mając ''n'' kwadratów o rozmiarach kolejno ''1x1,2x2,...,nxn'', należy znaleźć prostokąt a najmniejszym polu, wewnątrz którego zmieszczą się te kwadraty bez nachodzenia na siebie. |
* **Etap 1:** | * **Etap 1:** |
- Należy uzupełnić ograniczenia pod odpowiednimi komentarzami tak, aby problem był rozwiązywalny dla małych ''n'' | - Należy uzupełnić ograniczenia pod odpowiednimi komentarzami tak, aby problem był rozwiązywalny dla małych ''n'' |
- Podpowiedź - wygodne może być złożenie ograniczeń korzystając z alternatywy ''\/'' | - Podpowiedź - wygodne może być złożenie ograniczeń korzystając z alternatywy ''\/'' |
* **Etap 2:** | |
- Zmienić procedurę szukania tak, aby najpierw próbowała ustalić położenie największych kwadratów | |
- Podpowiedź - kolejność przeszukiwania zmiennych można wymusić przez adnotację ''input_order'' - w tym celu należy wcześniej zmienne włożyć w odpowiedniej kolejności do jednej tablicy | |
* **Etap 3:** | * **Etap 3:** |
- zastosować globalne ograniczenie [[http://www.minizinc.org/2.0/doc-lib/doc-globals-packing.html|diffn]] | - zastosować globalne ograniczenie [[http://www.minizinc.org/2.0/doc-lib/doc-globals-packing.html|diffn]] |
- Dodać nadmiarowe ograniczenia | - Dodać nadmiarowe ograniczenia |
- Podpowiedź - jaka jest relacja między pakowanie a harmonogramowaniem pracy, np. używając ograniczenia {{:pl:dydaktyka:csp:cumulative.png?linkonly|cumulative}} | - Podpowiedź - jaka jest relacja między pakowanie a harmonogramowaniem pracy, np. używając ograniczenia {{:pl:dydaktyka:csp:cumulative.png?linkonly|cumulative}} |
| * **Etap 5:** |
| - Zmienić procedurę szukania tak, aby najpierw próbowała ustalić rozmiar prostokąta, zaczynając od najmniejszych wartości |
| - Zmienić procedurę szukania tak, aby najpierw próbowała ustalić położenie największych kwadratów. |
| - Połączyć obie strategie używając ''seq_search'' ([[http://www.minizinc.org/downloads/doc-latest/minizinc-tute.pdf|Tutorial MiniZinca, s. 57]]) |
| - Porównać obie strategie szukania z domyślną - która strategia wydaje się bardziej opłacalna w trudnych przypadkach? |
| - Podpowiedź 1 - kolejność przeszukiwania zmiennych można wymusić przez adnotację ''input_order'' - w tym celu należy wcześniej zmienne włożyć w odpowiedniej kolejności do jednej tablicy zmiennych używając np. ''array comprehension''. |
| - Podpowiedź 2 - dla uproszczenia tablicę można odwrócić używające funkcji ''reverse'' --- ale nie jest to konieczne. |
| |
| |
<code> | <code> |
["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)] | ["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)] |
</code> | </code> |
| |
| ===== Prawdziwy problem: ładowanie węgla ===== |
| |
| ==== Krótki opis ==== |
| Głównym problemem, z którym przyjdzie nam się zmierzyć, będzie problem harmonogramowania pracy portu, który ma załadować węgiel na odpowiednie kontenerowce. Zastosowane poniżej materiały pochodzą z Uniwersytetu w Melbourne, ponieważ problem ten jest realnym wyzwaniem dla prężnie funkcjonującego w Australii eksportu węgla. |
| |
| |
| ==== Plan Zajęć ==== |
| |
| W ramach pierwszego laboratorium należy zapoznać się z problemem i rozwiązać poziom "A". Jest on analogiczny do problemu pakowania, przedstawionego powyżej. W ramach drugiego laboratorium zajmiemy się pozostałymi fazami. |
| |
| <WRAP center round tip 60%> |
| Sortowanie tablicy na potrzeby definiowania kolejności przeszukiwania zmiennych można zrealizować używając funkcji [[http://www.minizinc.org/2.0/doc-lib/doc-builtins-array.html|sort_by]]. |
| </WRAP> |
| |
| ==== Materiały ==== |
| |
| - Proszę pobrać i rozpakować {{:pl:dydaktyka:csp:portschedule.zip|dane problemu}}. |
| - Plik ''handout.pdf'' zawiera szczegółowy opis projektu |
| - Plik ''portschedule.mzp'' jest plikiem projektu MiniZinc. Należy go otworzyć w MiniZincIDE. Plik źródłowy jest wzbogacony o liczne komentarze, które powinny ułatwić budowę modelu. |
| |
| |
| |