Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:prolog:prolog_lab:csp_eclipse [2013/03/13 12:16] mbr ograniczenia ofert |
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 456: | Linia 461: | ||
| % na zawsze działający przypadek poniżej, gdy | % na zawsze działający przypadek poniżej, gdy | ||
| % dopasujemy się tutaj | % dopasujemy się tutaj | ||
| - | eplex_offer(_, _, _) :- true. | + | eplex_offer(_, _, _). |
| </code> | </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ć? | 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 == | == 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. | 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> | ||
