[[
✎ pl:prolog:prolog_lab:csp_eclipse
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== 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> Czwarta metoda polega na połączeniu metod drugiej i trzeciej -- wybierane są zmienne najbardziej ograniczone, lecz jeśli dwie zmienne mają tak samo liczną dziedzinę, pierwsza wybierana jest ta leżąca bliżej środka. Zmodyfikuj predykat ''labeling_b'' tak, aby wykorzystywał kolejność zmiennych z ''labeling_c''. Która zmienna (predykatu) odpowiada za kolejność i dlaczego ''AllVars''? Sprawdź czasy działania tej metody. Ostatnia z proponowanych metod to niewielka modyfikacja poprzedniej. Oprócz preferowania środkowych zmiennych, rozpatruje się też środkowe wartości w pierwszej kolejności. Wymaga to tylko modyfikacji użycia predykatu ''indomain'' poprzez zastąpienie go wersją dwuargumentową: ''indomain(Vars, middle)''. 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 / 170 * najpierw środkowe: 28 / 28 * najbardziej ograniczona, możliwie najbliższa środkowi zmienna: 82 / 290 * jw, z wyborem środkowych wartości zmiennej 92 / 300 Druga liczba w powyższych ograniczeniach jest tylko dolnym limitem na opisaną wielkość. Celem tych rozważań jest pokazanie, że właściwy dobór metody przeszukiwania może mieć ogromny wpływ na szybkość uzyskania wyniku. Platrofma ECLiPSe zostawia szerokie pole do optymalizacji wysokopoziomowych zostawiając jednocześnie możliwość szybkiego, deklaratywnego napisania prototypu dla niewielkich problemów. === 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> fll :- writeln('NOT OK'), !. time_is_acceptable :- ( for(I, 4, 120, 2) do writeln(I), timeout:timeout( (!, queens(I, _, labeling), writeln('OK')), 2, fll) ). </code> ====== LAB: Ograniczenia i ich implementowanie w środowisku ECLiPSe ====== Właściwe określenie i implementacja ograniczeń jest drugim, obok metody przeszukiwania, kluczowym elementem rozwiązywania problemów w programowaniu z ograniczeniami. Najprostszą ich realizacją jest napisanie odpowiednich predykatów je określających, co było robione w laboratorium wprowadzającym. Czasami jednak istnieje wiele metod określania ograniczeń, bądź osiągnięcie dobrej szybkości rozwiązywania problemu wymaga podania pewnych metainformacji o ograniczeniu. ===== -. Przed laboratorium ===== Zapoznać się z metodami propagacji ograniczeń [[http://eclipseclp.org/doc/tutorial/tutorial100.html]]. ===== -. Jak działają ograniczenia ===== Deklaratywnie normalny predykat (na przykład ''<='') ma takie samo znaczenie jak jego wersja będąca ograniczeniem. Podstawową różnicą jest to, że normalny predykat jest wykonywany od razu, zaś wykonanie ograniczenia jest opóźniane. To, jak bardzo sprawdzanie ograniczeń jest opóźniane, zależy od programisty. W przypadku **sprawdzania spójności** sprawdzenie odwleka się, dopóki wszystkie zmienne ograniczenia nie będą termami bazowymi. Otwórz środowisko tkeclipse i wpisz w polu ''Query entry'' poniższe zapytania. Używane ograniczenia pochodzą z biblioteki ''suspend'', stąd nazwa modułu i dwukropek przed użyciem predykatu (nie było potrzeby stosowania tej notacji wcześniej, gdyż wykorzystywaliśmy konstrukcję '':- lib(nazwa_biblioteki).''). <code prolog> ?- X > 0 ?- X > 0, X is 2 ?- X is 2, X > 0 ?- suspend : (X > 0) ?- suspend : (X > 0), X is 42 ?- suspend : (X > 0), X is -42 </code> Nie jest to jedyne, i nie zawsze najlepsze, zachowanie. Weźmy na przykład predykat ''#\='' ze znanego nam modułu ''ic''. Jak pamiętamy, w tym module mogliśmy określać dziedziny zmiennych. Zatem jeśli jedna ze zmiennych w predykacie ma już określoną wartość, możemy ją wyrzucić z dziedziny drugiej zmiennej. Zachowanie takie nazywa się **sprawdzaniem wprzód**. Wpisz w tkeclipse: <code prolog> ?- ic : (X :: 1 .. 5), ic : (X #\= 2) ?- ic : (X :: 1 .. 5), ic : (X #\= 2), X is 2 ?- ic : (X :: 1 .. 5), ic : (X #\= 2), X is 3 ?- ic : (X :: 1 .. 5), suspend : (X > 2) ?- ic : (X :: 1 .. 5), suspend : (X > 2), X is 3 ?- ic : (X :: 1 .. 5), suspend : (X > 2), X is 2 ?- ic : (X :: 1 .. 5), ic : (X > 2) </code> Jak widać, predykat ''ic:#\='' działa zgodnie z opisem, dziedzina się zmniejsza, zaś podstawianie wartości za X jest należycie sprawdzane. Mimo, że użycie predykatu ''suspend:>'' również mogłoby zmniejszyć dziedzinę, nie dzieje się tak, gdyż realizuje on inny schemat zachowania. Dziedzinę zmniejsza analogiczny predykat z modułu ''ic'', jednak robi to w jeszcze dalej idący sposób. Wspomniany predykat ''ic:>'' realizuje tak zwaną **spójność łukową**. Poza opisanym już ograniczaniem dziedzi, gdy tylko jedna zmienna jest podstawiona, analogiczny proces odbywa się, gdy obie zmienne nie są podstawione. Najlepiej ilustrują to poniższe przykłady: <code prolog> ic : ([X,Y] :: 1 .. 5), ic : (X > Y) ic : ([X,Y] :: 1 .. 5), ic : (X > Y), ic : (Y > 2) </code> Zauważ, co się stało w drugim przypadku. Dołożenie ograniczenia na zmienną Y spowodowało dalsze ograniczenie zmiennej X. Zachowanie takie jest istotą omawianej propagacji ograniczeń i jedocześnie powodem rozróżniania tylu ich rodzajów -- im więcej informacji staramy się wyciągnąć z ograniczenia, tym drożej to kosztuje. Z tego powodu różnież na przykład predykat ''ic:#='' propaguje tylko ograniczenia na zakres dziedziny, a nie na jej poszczególne elementy w środku.
pl/prolog/prolog_lab/csp_eclipse.1360328797.txt.gz
· ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry