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/27 10:16]
mbr [Eplex -- programowanie liniowe w ECLiPSe]
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 503: Linia 508:
  
 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>​
pl/prolog/prolog_lab/csp_eclipse.1364375807.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