Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

pl:prolog:prolog_lab:csp_eclipse [2013/02/01 13:34]
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]]. 
- 
-===== -. 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? 
- 
-===== -. 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? 
- 
  
pl/prolog/prolog_lab/csp_eclipse.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0