|
|
pl:prolog:prolog_lab:csp_eclipse [2013/02/05 14:39] mbr [3. Problem n hetmanów] |
pl:prolog:prolog_lab:csp_eclipse [2019/06/27 15:50] |
====== LAB: Wprowadzenie do środowiska ECLiPSe ====== | |
| |
| |
ECLiPSe jest jednym ze środowisk do programowania z ograniczeniami. Zapewnia ono szerokie możliwości tworzenia własnych ograniczeń oraz doboru właściwego sposobu poszukiwania rozwiązania. Składnia języka ECLiPSe jest oparta o Prolog. Istotne różnice opisane są w następującym przewodniku: [[http://eclipseclp.org/doc/tutorial/tutorial023.html]]. | |
| |
===== -. Przed laboratorium ===== | |
| |
Zapoznać się z ideą algorytmów [[http://en.wikipedia.org/wiki/Branch_and_bound|branch and bound]]. | |
| |
===== -. Podstawy środowiska ===== | |
| |
Proszę utworzyć plik o poniższej zawartości (tradycyjnie pliki z kodem ECLiPSe mają rozszerzenie .ecl): | |
| |
<code prolog> | |
:- lib(ic). | |
| |
sendmore(Digits) :- | |
% zmienne | |
Digits = [S,E,N,D,M,O,R,Y], | |
| |
% przypisanie dziedziny | |
Digits :: [0..9], | |
| |
% Ograniczenia | |
alldifferent(Digits), | |
S #\= 0, | |
M #\= 0, | |
1000*S + 100*E + 10*N + D | |
+ 1000*M + 100*O + 10*R + E | |
#= 10000*M + 1000*O + 100*N + 10*E + Y, | |
| |
% szukanie rozwiązania | |
labeling(Digits). | |
</code> | |
| |
=== Opis programu === | |
| |
Jest to program rozwiązujący zagadkę SEND+MORE=MONEY. | |
| |
Przed uruchomieniem przeanalizuj działanie programu. Pierwsza linijka informuje, że będziemy korzystać ze standardowej biblioteki dla dziedzin skończonych. Predykat sendmore Najpierw unifikuje Digits z listą zmiennych wykorzystywanych do opisu problemu. Następnie zmiennym przypisywana jest dziedzina (liczby całkowite od 0 do 9). | |
| |
Kolejnym etapem jest określenie ograniczeń. predykat alldifferent zapewnia, że wszystkie zmienne będą różne. Następnie wykorzystywane są operatory ''#\='' oraz ''#='' określające odpowiednio relację różności i równości. Istnieją różwnież analogiczne operatory większości i mniejszości, należy jednak pamiętać o znaku ''#'' na początku operatora. | |
| |
Ostatnia linijka powoduje rozpoczęcie wyszukiwania rozwiązania. | |
| |
=== Uruchamianie programu === | |
| |
Uruchom eclipse poleceniem tkeclipse. | |
| |
Wybierz File>Compile i wskaż utworzony plik. | |
| |
Wywołaj w Query entry predykat ''sendmore'': | |
<code prolog> | |
sendmore(Digits) | |
</code> | |
Zwróć uwagę, aby na liście rozwijanej z lewej strony wybrany był moduł eclipse. | |
| |
Aby sprawdzić, czy nie istnieje więcej rozwiązań, wciśnij przycisk more. | |
| |
=== Alternatywna wersja === | |
| |
Problem SEND + MORE = MONEY można też opisać w alternatywny sposób wprowadzając przeniesienia. Dodaj je do modelu | |
<code prolog> | |
Carries = [C1,C2,C3,C4], | |
Carries :: [0..1], | |
</code> | |
i przepisz ograniczenia tak, aby je wykorzystywały. Sprawdź poprawność porównując z poprzednią wersją. | |
| |
=== Kolorowanie mapy === | |
| |
Na podstawie ostatniego programu napisz predykat rozwiązujący problem kolorowania [[http://en.wikipedia.org/wiki/Australia#States_and_territories|mapy Australii]]. Dwa sąsiednie stany muszą mieć różne kolory. Czy trzy kolory wystarczą do pokolorowania mapy? | |
| |
=== Przydział zasobów === | |
| |
Ważną klasą problemów rozwiązywaną przez programowanie z ograniczeniami jest przydział zasobów. Przykładowy problem można znaleźć na [[http://www.hakank.org/eclipse/schedule1.ecl|tej]] stronie. Poniżej znajduje się zaczerpnięty z niej kod: | |
<code prolog> | |
:- lib(ic). | |
:- lib(ic_cumulative). | |
:- lib(branch_and_bound). | |
:- lib(lists). | |
| |
schedule(Ss, End,Capacity) :- | |
length(Ss, 7), | |
Ds = [16, 6,13, 7, 5,18, 4], | |
Ss :: 1..30, | |
| |
Rs = [ 2, 9, 3, 7,10, 1,11], | |
End :: 1..50, | |
| |
after(Ss, Ds, End), | |
cumulative(Ss, Ds, Rs, Capacity), | |
append(Ss, [End], Vars), | |
| |
minimize(labeling(Vars),End). | |
| |
after([], [], _). | |
after([S|Ss], [D|Ds], E) :- E #>= S+D, after(Ss, Ds, E). | |
</code> | |
| |
Dany jest zbiór zadań do wykonania (ich czasów oraz potrzebnych zasobów) oraz ograniczona liczba zasobów. zasoby są niewyczerpywalne -- jest to np. liczba sal w budynku albo maszyn w fabryce. Zadaniem jest tak ustalić początki wykonania, żeby zadanie skończyło się możliwie jak najszybiciej. | |
| |
Sprawdź wynik działania programu dla ograniczenia wynoszącego 13. Dodaj nowy zasób (procesy potrzebują go odpowiednio 1, 2, 3, 4, 5, 6, 7) z ograniczeniem 8. Jakie jest wyjście programu? | |
| |
Co należałoby zmienić w programie, jeśli maszyny wymagałyby przerwy technologicznej o zadanej długości pomiędzy zadaniami? Nanieś odpowiednie zmiany i sprawdź wyniki. | |
| |
W tym momencie wszystkie predykaty użyte w programie (prawdopodobnie z wyjątkiem ''minimize'') powinny być zrozumiałe. Predykat ''minimize'' pochodzi z biblioteki ''branch_and_bound'' i minimalizuje cel zadany pierwszym argumentem ze względu na zmienną podaną jako drugi argument. Używaną techniką jest metoda branch and bound -- po każdym znalezieniu rozwiązania do ograniczeń jest dodawane nowe ograniczenie na minimalizowaną zmienną. Szczegóły opisane są na [[http://eclipseclp.org/doc/bips/lib/branch_and_bound/bb_min-3.html|tej]] stronie. | |
| |
===== -. Problem n hetmanów ===== | |
| |
Trochę bardziej zaawansowane możliwości systemu ECLiPSe prezentuje program rozwiązujący problem n hetmanów. | |
| |
<code prolog> | |
:- lib(ic). | |
| |
queens(N, Board) :- | |
length(Board, N), | |
Board :: 1..N, | |
( fromto(Board, [Q1|Cols], Cols, []) do | |
( foreach(Q2, Cols), count(Dist,1,_), param(Q1) do | |
noattack(Q1, Q2, Dist) | |
) | |
). | |
| |
noattack(Q1,Q2,Dist) :- | |
Q2 #\= Q1, | |
Q2 - Q1 #\= Dist, | |
Q1 - Q2 #\= Dist. | |
</code> | |
| |
=== Opis programu === | |
| |
Po pierwsze, model zawiera [[http://eclipseclp.org/doc/tutorial/tutorial025.html|pętle]] (''fromto'', ''foreach'', ''count'', ''param''). Umożliwiają one bardziej zwarty zapis ograniczeń. Pod drugie, brakuje użycia predykatu label, przez co nie zostanie znalezione żadne rozwiązanie. | |
| |
=== Ćwiczenie === | |
| |
Proszę zapisać do pliku i wykonać powyższy kod. Co pojawia się w oknie wyników? | |
| |
Okazuje się, że propagacja ograniczeń przy określaniu modelu nie jest wystarczająca i potrzebne jest przeszukiwanie. Najprostsze przeszukiwanie realizowane jest przez predykat ''labeling''. Przeszukuje ono zmienne od początku listy do końca i próbuje przypisać kolejne liczby począwszy od najmniejszej. Spróbuj zastosować to przeszukiwanie (było używane we wcześniejszych przykładach). Ile czasu potrzeba, aby wyszukać rozwiązanie dla planszy 24x24? | |
| |
Jedną z heurystyk, jakie można zastosować jest wybór najbardziej ograniczonej zmiennej (mającej najmniej liczną dziedzinę). Opis kluczowego predykatu ''delete'' znajduje się [[http://eclipseclp.org/doc/bips/lib/ic/delete-5.htm|tutaj]]. | |
| |
<code prolog> | |
:- lib(ic_search). | |
labeling_b(AllVars) :- | |
( fromto(AllVars, Vars, VarsRem, []) do | |
delete(Var, Vars, VarsRem, 0, first_fail), % wybór zmiennej | |
indomain(Var) % wybór wartości | |
). | |
</code> | |
| |
Porówanaj czasy działania dla różnych wielkości planszy. Czy druga metoda przeszukiwania jest zawsze lepsza od pierwszej? | |
| |
Trzecia metoda to wybór środkowych zmiennych w pierwszej kolejności. Hetman na środku planszy atakuje więcej pól, przez co szybciej możliwe będzie wykrycie niepoprawnego rozstawienia. Skompiluj poniższy kod: | |
<code prolog> | |
:- lib(lists). | |
| |
middle_first(List, Ordered) :- | |
halve(List, Front, Back), | |
reverse(Front, RevFront), | |
splice(Back, RevFront, Ordered). | |
| |
labeling_c(AllVars) :- | |
middle_first(AllVars, AllVarsPreOrdered), % static var-select | |
( foreach(Var, AllVarsPreOrdered) do | |
indomain(Var) % select value | |
). | |
</code> | |
Przeanalizuj działanie predykatu ''middle_first''. Jak zachowywałby się predykat ''labeling_c'', gdyby pętla przebiegała po ''AllVars''? | |
| |
Zanim przetestujemy szybkość działania z nowym wyborem zmiennych, zmodyfikujmy predykat queens tak, aby mógł obsługiwać dowolną metodę wyszukiwania. Dodaj w tym celu dodatkową zmienną ''Labeling'' oraz zmodyfikuj wywołanie szukania tak, aby korzystało z nazwy predykatu podanej w tej zmiennej. Podpowiedź: użyj predykatu apply/2. | |
| |
Sprawdź, po zmianach kod dalej działa, wywołując zmodyfikowany predykat. Następnie użyj predykatu ''benchmark'' do sprawdzenia szybkości działania: | |
<code prolog> | |
:- lib(util). | |
| |
benchmark :- | |
( for(I, 4, 26, 2) do | |
write(I), | |
util:time(queens(I, _, labeling)), | |
util:time(queens(I, _, labeling_b)) | |
util:time(queens(I, _, labeling_c)) | |
). | |
</code> | |
| |
Limity dla metod (największa, do której szybko liczą się wszystkie o rozmiarze parzystym/największa, dla której szybko się liczy): | |
* naiwna: 26 / 26 | |
* najbardziej ograniczona zmienna: 86 / 160 | |
* najpierw środkowe: ? / ? | |
* najbardziej ograniczona, możliwie najbliższa środkowi zmienna: ? / ? | |
* jw, z wyborem środkowych wartości zmiennej ? / ? | |
| |
=== Zadania fakultatywne === | |
| |
- Wybróbuj swoje własne heurystyki dla problemu n hetmanów. Porównaj ich szybkość działania z tymi zaproponowanymi w ćwiczeniu. | |
- Spróbuj znaleźć możliwie duże plansze, na których szybko działają heurystyki z ćwiczenia. Możesz do tego celu wykorzystać (odpowiednio zmodyfikowany) poniższy predykat: | |
<code prolog> | |
time_is_acceptable :- | |
( for(I, 4, 120, 2) do | |
writeln(I), | |
timeout:timeout( | |
(!, queens(I, _, labeling), writeln('OK')), | |
2, | |
fll) | |
). | |
</code> | |