|
|
pl:dydaktyka:csp:lab3 [2016/03/16 01:44] msl [Rozgrzewka: problem pakowania] |
pl:dydaktyka:csp:lab3 [2019/06/27 15:50] |
====== Lab CSP: Zastosowanie w praktyce ===== | |
| |
Na tym laboratorium spróbujemy zamodelować w MiniZincu w miarę rzeczywisty problem. Rzeczywiste problemy mają to do siebie, że są trudne - dlatego są doskonałym testem umiejętności. Planowany czas wymagany na zrealizowanie tego laboratorium to dwa zajęcia (2x1h30min) plus czas poświęcony w domu między nimi (w razie potrzeby). | |
| |
===== Rozgrzewka: problem pakowania ====== | |
| |
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?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. | |
* **Etap 1:** | |
- Proszę uzupełnić poniższy model a brakujące granice dziedzin. | |
- Podpowiedź - należy użyć set comprehension (np. ''[i | in SQUARES]'') | |
* **Etap 2:** | |
- Należy uzupełnić ograniczenia pod odpowiednimi komentarzami tak, aby problem był rozwiązywalny dla małych ''n'' | |
* **Etap 3:** | |
- zastosować globalne ograniczenie [[http://www.minizinc.org/2.0/doc-lib/doc-globals-packing.html|diffn]] | |
- Podpowiedź - może być konieczne dodanie kolejnego parametru w postaci tablicy | |
* **Etap 4:** | |
- 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ź - wygodne może być złożenie ograniczeń korzystając z alternatywy ''\/'' | |
* **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''. | |
| |
| |
<code> | |
% Parametry | |
%%%%%%%%%%% | |
int: n; % liczba kwadratów | |
set of int: SQUARES = 1..n; % zbiór dostępnych kwadratów | |
| |
% Zmienne | |
%%%%%%%%%%% | |
var <min>..<max>: height; % wysokość prostokątnego pojemnika | |
var <min>..<max>: width; % szerokość prostokątnego pojemnika | |
var <min>..<max>: area = height * width; % pole pojemnika | |
array[SQUARES] of var <min>..<max>: x; % współrzędne kwadratów w pojemniku | |
array[SQUARES] of var <min>..<max>: y; % współrzędne kwadratów w pojemniku | |
| |
% Ograniczenia | |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| |
% Ograniczenie 1: kwadraty nie powinny wychodzić poza prostokąt | |
| |
% Ograniczenie 2: kwadraty nie powinny nachodzić na siebie | |
| |
% Cel | |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
solve minimize area; | |
| |
| |
% Nudne wyjście % | |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
output [ show(i) ++ " > (" ++ show(x[i]) ++ "," ++ show(y[i]) ++ ")\n" | i in 1..n] ++ | |
["area = " ++ show(width) ++ " * " ++ show(height) ++ " = " ++ show(area)] | |
</code> | |
| |
| |
| |