Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:prolog:prolog_lab:csp_eclipse [2013/03/06 09:08] mbr poprawki literówek |
pl:prolog:prolog_lab:csp_eclipse [2019/06/27 15:50] (aktualna) |
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. |
=== 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) |
=== 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 === |
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: |
:- 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? |
</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ą. |
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: |
| Zmodyfikuj warunek opóźnienia tak, aby ograniczenie obliczało pozycję elementu na liście, o ile występuje on na niej dokładnie raz, i było niespełnione, gdy na niej nie występuje. Sprawdź poprawność swojego kodu. |
| |
=== Drugi problem fabryki === | === Drugi problem fabryki === |
| |
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> |