Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:prolog_lab:csp_eclipse [2013/02/04 12:28] mbr |
pl:prolog:prolog_lab:csp_eclipse [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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? | ||
| - | |||
