Różnice

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

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:prolog:prolog_lab:csp_eclipse [2013/03/06 12:32]
mbr
pl:prolog:prolog_lab:csp_eclipse [2019/06/27 15:50] (aktualna)
Linia 38: Linia 38:
 Jest to program rozwiązujący zagadkę SEND+MORE=MONEY. 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).+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.+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. Ostatnia linijka powoduje rozpoczęcie wyszukiwania rozwiązania.
Linia 46: Linia 49:
 === Uruchamianie programu === === Uruchamianie programu ===
  
-Uruchom ​eclipse poleceniem tkeclipse.+Wpisz w powłoce: 
 +  export PATH=$PATH:/​usr/​local/​eclipse-clp/bin/ 
 +Następnie uruchom ECLiPSe ​poleceniem ​**tkeclipse**.
  
-Wybierz File>​Compile i wskaż utworzony plik.+Wybierz ​//File>​Compile// i wskaż utworzony plik.
  
-Wywołaj w Query entry predykat ''​sendmore'':​+Wywołaj w //Query entry// predykat ''​sendmore'':​
 <code prolog> <code prolog>
 sendmore(Digits) sendmore(Digits)
Linia 130: Linia 135:
 === Opis programu === === 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.+Po pierwsze, model zawiera [[http://​eclipseclp.org/​doc/​tutorial/​tutorial025.html|pętle]] (''​fromto'',​ ''​foreach'',​ ''​count'',​ ''​param''​). Umożliwiają one bardziej zwarty zapis ograniczeń. ​Po drugie, brakuje użycia predykatu ​''​labeling''​, przez co nie zostanie znalezione żadne rozwiązanie.
  
 === Ćwiczenie === === Ćwiczenie ===
Linia 168: Linia 173:
 Przeanalizuj działanie predykatu ''​middle_first''​. Jak zachowywałby się predykat ''​labeling_c'',​ gdyby pętla przebiegała po ''​AllVars''?​ 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.+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: Sprawdź, po zmianach kod dalej działa, wywołując zmodyfikowany predykat. Następnie użyj predykatu ''​benchmark''​ do sprawdzenia szybkości działania:
Linia 225: Linia 230:
 :- lib(ic). :- lib(ic).
 :- lib(branch_and_bound). :- lib(branch_and_bound).
-:- lib(lists).+:- lib(listut).
  
-delay constr_nth(Domain,​ Which, Value) if var(Which). +delay constr_nth(Domain,​ Which, Value) if (var(Which); var(Domain)). 
-constr_nth(Domain,​ Which, Value) :- nth_value(Domain, ​Which, Value).+constr_nth(Domain,​ Which, Value) :- nth1(Which, Domain, Value).
  
 % który z CostPerLiter daje największy zysk? % który z CostPerLiter daje największy zysk?
Linia 241: Linia 246:
 </​code>​ </​code>​
 Opiszmy nowe elementy po kolei: Opiszmy nowe elementy po kolei:
-  - ''​constr_nth''​ jest predykatem ''​nth_value''​ zamienionym w ograniczenie. Jak dokładnie działa i co oznacza linijka powyżej będzie wyjaśnione na kolejnym laboratorium.+  - ''​constr_nth''​ jest predykatem ''​nth1''​ zamienionym w ograniczenie. Jak dokładnie działa i co oznacza linijka powyżej będzie wyjaśnione na kolejnym laboratorium.
   - Predykaty zaczynające się dolarem definiują ograniczenia zmiennoprzecinkowe. Używana jest przy tym arytmetyka przedziałów -- zmienne reprezentowane są jako zakres wartości, które mogą przyjmować. Zakresy te są odpowiednio dostosowywane w zależności od stosowanych funkcji czy działań arytmetycznych.   - Predykaty zaczynające się dolarem definiują ograniczenia zmiennoprzecinkowe. Używana jest przy tym arytmetyka przedziałów -- zmienne reprezentowane są jako zakres wartości, które mogą przyjmować. Zakresy te są odpowiednio dostosowywane w zależności od stosowanych funkcji czy działań arytmetycznych.
   - Predykat ''​minimize''​ działa tak jak wcześniej, przy czym tym razem optymalizuje zmienną zmiennoprzecinkową.   - Predykat ''​minimize''​ działa tak jak wcześniej, przy czym tym razem optymalizuje zmienną zmiennoprzecinkową.
Linia 296: Linia 301:
 Na początek wróćmy do ograniczenia ''​constr_nth''​ z poprzedniej części. Na początek wróćmy do ograniczenia ''​constr_nth''​ z poprzedniej części.
 <code prolog> <code prolog>
-delay constr_nth(Domain,​ Which, Value) if var(Which). +delay constr_nth(Domain,​ Which, Value) if (var(Which); var(Domain)). 
-constr_nth(Domain,​ Which, Value) :- nth_value(Domain, ​Which, Value).+constr_nth(Domain,​ Which, Value) :- nth1(Which, Domain, Value).
 </​code>​ </​code>​
-Pierwsza linijka powyższego fragmentu kodu określa, że sprawdzanie poniższego predykatu należy opóźnić, dopóki ​zmienna ​''​Which''​ nie zostanie ustalona. Jest to typowy przykład tworzenia własnego ograniczenia -- poza predykatem, co ograniczenie oznacza, określamy, kiedy ma zostać sprawdzane. Sprawdź, co się stanie, jeśli usuniesz linijkę określającą opóźnienie. Wypróbuj różne tablice z optymalnymi wyborami na różnych pozycjach. Przemyśl, dlaczego tak się dzieje. Dlaczego ograniczenie ''​constr_nth''​ nie może po prostu sprawdzać spójności?​+Pierwsza linijka powyższego fragmentu kodu określa, że sprawdzanie poniższego predykatu należy opóźnić, dopóki ​zmienne ​''​Which''​ oraz ''​Domain''​ nie zostaną ustalone. Jest to typowy przykład tworzenia własnego ograniczenia -- poza predykatem, co ograniczenie oznacza, określamy, kiedy ma zostać sprawdzane. Sprawdź, co się stanie, jeśli usuniesz linijkę określającą opóźnienie. Wypróbuj różne tablice z optymalnymi wyborami na różnych pozycjach. Przemyśl, dlaczego tak się dzieje. Dlaczego ograniczenie ''​constr_nth''​ nie może po prostu sprawdzać spójności?​
  
 Zadanie dla chętnych: Zadanie dla chętnych:
Linia 416: Linia 421:
  
 Sprawdź, czy otrzymujesz poprawne wyniki (porównując z poprzednim programem nie korzystającym z biblioteki eplex. Proszę pamiętać o załączeniu biblioteki eplex w kodzie i stworzeniu instancji o nazwie ''​my_instance''​. Sprawdź, czy otrzymujesz poprawne wyniki (porównując z poprzednim programem nie korzystającym z biblioteki eplex. Proszę pamiętać o załączeniu biblioteki eplex w kodzie i stworzeniu instancji o nazwie ''​my_instance''​.
 +
 +=== Rabaty od dostawców ===
 +
 +Sytuacja może być jednak jeszcze bardziej skomplikowana. Na przykład, sprzedający mogą oferować rabaty przy zamawianiu dużej ilości towaru. Co należy zmodyfikować,​ aby program poprawnie obsługiwał takie sytuacje? Przyjrzymy się obywdu przypadkom: z wykorzystaniem biblioteki eplex i bez.
 +
 +Podstawową zmianą, wspólną w obu scenariuszach jest konieczność obsługi wielu przypadków dostarczania jednego towaru przez danego dostawcę.
 +
 +<​code="​prolog">​
 +problem4([CPLS,​ CPIS], [P1, P2, P3],
 +         ​Money,​ Income, [W1, W2, WW1, WW2], [[R11, R12], [R21, R22], [R31, R32]],
 +         [Q1, Q2, Q3]) :-
 +        length(CPLS,​ N),
 +        length(CPIS,​ M),
 +        W1 :: 1 .. N,
 +        W2 :: 1 .. M,
 +        constr_nth(CPLS,​ W1, CC1), % wybór dostawcy
 +        constr_nth(CPIS,​ W2, CC2), % wybór dostawcy
 +        W2 #\= W1, % dostawcy muszą być różni
 +        constr_length(CC1,​ NC1), % nie znamy CC1 i CC2 w tym momencie!
 +        constr_length(CC2,​ NC2),
 +        WW1 :: 1 .. 10, %dlaczego nie NC1? jak to uogólnić?
 +        WW2 :: 1 .. 10,
 +        ic: (WW1 #=< NC1),
 +        ic: (WW2 #=< NC2),
 +        constr_nth(CC1,​ WW1, C1), % wybór oferty dostawcy
 +        constr_nth(CC2,​ WW2, C2), % wybór oferty dostawcy
 +</​code>​
 +
 +Powyżej znajduje się zmodyfikowany kod, w którym CPLS i CPIS zamieniły się w listy list -- zamiast pojedynczej oferty, jest lista ofert. Każda z pozycji oznacza cenę. W tym przypadku wybór dostawców jest oznaczany czterema zmiennymi -- ''​W1'',​ ''​W2'',​ ''​WW1''​ i ''​WW2''​. Pierwsze dwie oznaczają dostawcę odpowiedniego towaru, a drugie numer oferty. Proszę przyjrzeć się kodowi i zrozumieć jak działa. Ciekawym ćwiczeniem może być próba dokładnego zdefiniowania zakresu dla zmiennych ''​WW1''​ i ''​WW2''​ -- proszę pamiętać, że na każdej liście może być różna liczba ofert. Predykat ''​constr_length''​ jest analogiczny do ''​constr_nth'',​ tyle, że opiera się na predykacie length. Jego napisanie jest pozostawione jako ćwiczenie.
 +
 +== Eplex ==
 +
 +Jak już było wspomniane, w tym miejscu mamy już określone ceny produktów, brakuje jednak ograniczeń wynikających z ofert. Ponieważ w tym punkcie korzystamy z eplex, należy je wyrazić w sposób liniowy w ''​solve4_lp''​ -- analogu ''​solve3_lp''​. Jedyne wymagane zmiany to rozszerzenie listy argumentów o listę wyborów ''​W = [W1, W2, WW1, WW2]''​ i użycie predykatu ustanawiającego dodatkowe warunki w zależności od oferty.
 +
 +<​code="​prolog">​
 +eplex_offer([_,​ 1, _, 2], R1, R2) :-
 +        my_instance:​ (R1 $>= 4000),
 +        !. % uwaga na cut -- dzięki temu nie natrafiamy
 +           % na zawsze działający przypadek poniżej, gdy
 +           % dopasujemy się tutaj
 +eplex_offer(_,​ _, _).
 +</​code>​
 +
 +Ten przykładowy predykat ustalający ograniczenia ofert działa dla drugiej oferty pierwszego dostawcy drugiego towaru. Ustala minimalną wielkość zamówienia. Istotną rzeczą jest ucięcie backtrackingu na końcu -- domyślnym stanem oferty jest brak wymagań (druga definicja predykatu) i nie jest wskazane, aby oferty pasujące do przypadku szczególnego były rozważane też bez wymagań. Jest jednak pewien problem z tym predykatem -- jeśli wybierzemy dwie oferty z ograniczeniami,​ to zostaną nałożone warunki tylko jednej z nich. Jak sobie z tym poradzić?
 +
 +----
 +----
 +----
 +Komentarz:
 +
 +Powyższy problem jest nietrywialny. Kilka godzin nad nim siedziałem,​ choć na pierwszy rzut oka wydaje się dość prosty. Okazało się, że backtracking powoduje wycofanie naniesionych ograniczeń,​ co dość istotnie utrudnia stworzenie poprawnej implementacji. W tej chwili moje rozwiązanie wygląda tak:
 +<code prolog>
 +eplex_offer(W,​ R1, R2, 1) :-
 +        W = [_, 1, _, 2],
 +        writeln('​bb'​),​
 +        my_instance:​ (R1 $= 400000),
 +        writeln('​bb'​),​!,​ member(X, [2,3]), eplex_offer(W,​ R1, R2, X).
 +                         % uwaga na cut -- dzięki temu nie natrafiamy
 +                         % na zawsze działający przypadek poniżej, gdy
 +                         % dopasujemy się tutaj
 +eplex_offer(_,​ _, _, 2) :- writeln('​fail'​),​ fail.
 +eplex_offer(_,​ _, _, 3) :- writeln('​vc'​),​ !.
 +</​code>​
 +member na końcu pierwszej definicji pozwala przechodzić do kolejnych. fail w drugiej obrazuje niespełnienie warunków koniecznych do wprowadzenia ograniczenia. Ostatnia definicja ma na końcu cut, aby predykat był deterministyczny (jeden z warunków poprawnego działania). Ostatni argument predykatu po prostu numeruje definicje i umożliwia przechodzenie do następnych.
 +
 +Dałoby się to zrobić bardziej ogólnie metaprogramowaniem (lista predykatów warunek+ograniczenie,​ które po kolei są callowane), ale nie jestem pewien, czy to dobry pomysł -- może odstraszyć studentów.
 +
 +<code prolog>
 +call_all([],​ _,  _, _).
 +call_all([P|T],​ W, R1, R2) :-
 +        CC =.. [P, W, R1, R2],
 +        writeln('​f'​),​
 +        (call(CC); true), !,
 +        writeln('​m'​),​
 +        call_all(T, W, R1, R2).
 +offer1(W, R1, R2) :- W = [_, 1, _, 2], my_instance:​ (R1 $= 400000), writeln('​bb'​).
 +offer2(W, R1, R2) :- fail.
 +meta_offer(W,​ R1, R2) :-
 +        call_all([offer1,​ offer2], W, R1, R2).
 +</​code>​
 +----
 +----
 +----
 +
 +== Bez Eplex ==
 +
 +Z uwagi na brak konieczości wyrażania ograniczeń w eplex i jednopoziomowość metody, dodanie odpowiednich ograniczeń nie powinno stanowić problemu -- wszystkie potrzebne elementy zostały już pokazane i powinieneś móc sam zaimplementować odpowiednie zmiany.
 +
 +
 +===== -. Wizualizacja przeszukiwania w ECLiPSe =====
 +
 +Środowisko ECLiPSe umożliwia przyglądanie się przeszukiwaniu przestrzeni rozwiazań. Robi się to za pomocą specjalnych adnotacji w programie oraz klienta wizualizacji. Poniższy kod rozwiązuje zagadkę SEND+MORE=MONEY. Ma przy tym wywołanie predykatu umożliwiające śledzenie pracy predykatu przeszukującego.
 +
 +<code prolog>
 +:- lib(ic).
 +:- lib(viewable).
 +
 +sendmore(Digits) :-
 +    Digits = [S,​E,​N,​D,​M,​O,​R,​Y],​
 +    Digits :: [0..9],
 +    viewable_create(digits,​ Digits),
 +    Carries = [C1,​C2,​C3,​C4],​
 +    Carries :: [0..1],
 +    alldifferent(Digits),​
 +    S #\= 0,
 +    M #\= 0,
 +    C1         #= M,
 +    C2 + S + M #= O + 10*C1,
 +    C3 + E + O #= N + 10*C2,
 +    C4 + N + R #= E + 10*C3,
 +         D + E #= Y + 10*C4,
 +    labeling(Carries),​
 +    labeling(Digits).
 +</​code>​
 +
 +Normalne uruchomienie tego tego programu spowoduje po prostu uzyskanie rozwiązania zagadki. Wybierz polecenie Options > Visualization Client i wróć do okna programu ECLiPSe. Uruchom ponownie predykat ''​sendmore''​. Klient wizualizacji zapyta o metody, jakimi chcemy wizualizować problem. Należy wybrać TextTable. Wybranie więcej niż jednej może spowodować nieoczekiwane problemy w dalszej części ćwiczenia.
 +
 +Rozciągając okno, skalując widok (View > Zoom ...) i rozszerzając kolumnę dostosuj tabelkę tak, aby dobrze widzieć jej zawartość. Są to kolejne zmienne z opisywanego problemu. Wciśnięcie przycisku Resume spowoduje zobrazowanie rozwiązywania -- sprawdź. Pola tabeli aktualizowały się jednak zbyt często. Aby to zmienić, należy zaznaczyć wszystkie pola (View > Select all viewlets) i wybrać z menu kontekstowego Hold on updates. Spowoduje to, jak wskazuje nazwa, zatrzymanie po każdej aktualizacji. Można wznawiać ręcznie lub wybrać Options > Auto resume (sprawdź oba rozwiązania).
 +
 +=== Poprawianie widoku ===
 +
 +Omówiony mechanizm jest już stosunkowo przydatny, jednak można go znacznie ulepszyć konstruując widok rozwiązania lepiej oddający problem. Sumowanie może być w naturalny sposób przedstawione w postaci tablicy:
 +<​code>​
 +[ 0 S E N D ]
 +[ 0 M O R E ]
 +[ M O N E Y ]
 +</​code>​
 +Taką strukturę widoku można uzyskać zmieniając polecenie ''​viewable_create''​ w następujący sposób:
 +<code prolog>
 +viewable_create(equation,​[[0,​ S, E, N, D],[0, M, O, R, E],[M, O, N, E, Y]])
 +</​code>​
 +
 +Jeśli w trakcie już po stworzeniu widoku chcielibyśmy modyfikować rozmiary wyświetlanej tablicy, należy to odpowiednio zaznaczyć w wywołaniu ''​viewable_create''​. Można to osiągnąć w trójargumentowej wersji tego predykatu:
 +<code prolog>
 +viewable_create(equation,​
 +                [[0, S, E, N, D],
 +                 [0, M, O, R, E],
 +                 [M, O, N, E, Y]],
 +                array([flexible,​fixed],​ any)),
 +</​code>​
 +Pierwszym argumentem termu ''​array''​ jest lista określająca,​ czy dany wymiar jest stały, czy nie. W podanym przykładzie tylko pierwszy wymiar (ten zewnętrzny) może się zmieniać. drugi argument określa rodzaj danych, jakie będą wizualizowane.
 +
 +Aby przetestować działanie opisanej funkcjonalności,​ należy na końcu programu umieścić polecenie wyświetlające wartosci przeniesień:​
 +<code prolog>
 +    labeling(Carries),​
 +    labeling(Digits),​
 +    viewable_expand(equation,​ 1, [C1, C2, C3, C4, 0]).
 +</​code>​
 +
 +Możliwe jest też nazwanie poszczególnych kolumn i wierszy:
 +<code prolog>
 +viewable_create(equation,​
 +                [[0, S, E, N, D],
 +                 [0, M, O, R, E],
 +                 [M, O, N, E, Y]],
 +                array([flexible,​fixed],​ numeric_bounds),​
 +                    [["​send",​ "​more",​ "​money"​],​
 +                     ​["​ten thousands",​ "​thousands",​
 +                      "​hundreds",​ "​tens",​ "​units"​]]),​
 +</​code>​
 +=== Widok problemu grafowego ===
 +
 +ECLiPSe umożliwia także wizualizację problemów grafowych. Dla przykładu przedstawiony jest problem szukania przepływów w sieci -- mamy zadany wypływ ze źródła (i zarazem wpływ do ujścia) i zadaniem jest ustalenie wartości przepływów na krawędziach tak, aby z każdego węzła wychodziło tyle, ile do niego wchodzi.
 +
 +Przeanalizuj krótko działanie poniższego programu. Skompiluj go i uruchom. Porównaj różne metody wizualizacji grafu.
 +
 +UWAGA:
 +Początkowo wszystkie węzły są umieszczane w tym samym miejscu. Można je poprzesuwać ręcznie lub skorzystać z automatycznego rozmieszczania (opcja graph > layout graph ...).
 +
 +<code prolog>
 +:​-lib(graph_algorithms).
 +:​-lib(viewable).
 +:-lib(ic).
 +
 +test:-
 +    make_graph(7,​
 +               ​[e(1,​2,​F12),​ e(2,3,F23), e(2,4,F24), e(3,5,F35),
 +                e(4,5,F45), e(4,6,F46), e(5,6,F56), e(6,3,F63),
 +                e(6,​7,​F67)],​
 +               ​Graph),​
 +    Flows = [F23,​F24,​F35,​F45,​F46,​F56,​F63],​
 +    Flows :: 0..5,
 +    (for(Node, 2, 6), param(Graph) do
 +        graph_get_incoming_edges(Graph,​ Node, InEdges),
 +        graph_get_adjacent_edges(Graph,​ Node, OutEdges),
 +        (foreach(e(_From,​ _To, Flow), InEdges),
 +         ​foreach(Flow,​ InFlow) do true),
 +        (foreach(e(_From,​ _To, Flow), OutEdges),
 +         ​foreach(Flow,​ OutFlow) do true),
 +        sum(InFlow) #= sum(OutFlow)
 +    ),
 +    F12 #= 9,
 +    viewable_create(flow_viewable,​ Graph, graph(fixed),​
 +                    [node_property([0->​[name(nodes),​ label]]),
 +                     ​edge_property([0->​[name(edges),​ label]])
 +                    ]),
 +    labeling(Flows).
 +</​code>​
pl/prolog/prolog_lab/csp_eclipse.1362569558.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (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