AIwiki

Strona Główna

Dla Studentów

Zima / Winter 2021:

Computer Science: Introduction to AI
ISI: Podstawy Sztucznej Inteligencji

Old specialized AI courses

SMaDA/SMaIDA/AIDA

1. semester:

2. semester:

WSHOP -- Development Workshop

Informatyka (EAIiIB)

1. rok:

2. i 3. rok:

4. rok:

Systemy i technologie wirtualizacji

Studia Dr

HeKatE

Public

The KESE workshop (EN only)
Mindstorms (archive)

Prolog Lab

Część główna

Część fakultatywna

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/04 12:28]
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.
-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.
@@ Linia 46: / Linia 49: @@
 === 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>
 sendmore(Digits)
@@ Linia 98: / Linia 103: @@
 </code>
-Dany jest zbiór zadań do wykonania (ich czasów oraz potrzebnych zasobów) oraz ograniczona liczba zasobów. zasoby są niewyczerpywalne -- jest to np. liczba sal w budynku albo maszyn w fabryce. Zadaniem jest tak ustalić początki wykonania, żeby zadanie skończyło się możliwie jak najszybiciej.
+Dany jest zbiór zadań do wykonania (ich czasów oraz potrzebnych zasobów) oraz ograniczona liczba zasobów. zasoby są niewyczerpywalne -- jest to np. liczba sal w budynku albo maszyn w fabryce. Zadaniem jest tak ustalić początki wykonania, żeby zadanie skończyło się możliwie jak najszybciej.
 Sprawdź wynik działania programu dla ograniczenia wynoszącego 13. Dodaj nowy zasób (procesy potrzebują go odpowiednio 1, 2, 3, 4, 5, 6, 7) z ograniczeniem 8. Jakie jest wyjście programu?
@@ Linia 130: / Linia 135: @@
 === 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 ===
@@ Linia 151: / Linia 156: @@
 Porówanaj czasy działania dla różnych wielkości planszy. Czy druga metoda przeszukiwania jest zawsze lepsza od pierwszej?
+Trzecia metoda to wybór środkowych zmiennych w pierwszej kolejności. Hetman na środku planszy atakuje więcej pól, przez co szybciej możliwe będzie wykrycie niepoprawnego rozstawienia. Skompiluj poniższy kod:
+<code prolog>
+:- lib(lists).
+middle_first(List, Ordered) :-
+        halve(List, Front, Back),
+        reverse(Front, RevFront),
+        splice(Back, RevFront, Ordered).
+labeling_c(AllVars) :-
+        middle_first(AllVars, AllVarsPreOrdered), % static var-select
+        ( foreach(Var, AllVarsPreOrdered) do
+            indomain(Var)                         % select value
+        ).
+</code>
+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''.
+Sprawdź, po zmianach kod dalej działa, wywołując zmodyfikowany predykat. Następnie użyj predykatu ''benchmark'' do sprawdzenia szybkości działania:
+<code prolog>
+:- lib(util).
+benchmark :-
+        ( for(I, 4, 26, 2) do
+            write(I),
+            util:time(queens(I, _, labeling)),
+            util:time(queens(I, _, labeling_b))
+            util:time(queens(I, _, labeling_c))
+        ).
+</code>
+Czwarta metoda polega na połączeniu metod drugiej i trzeciej -- wybierane są zmienne najbardziej ograniczone, lecz jeśli dwie zmienne mają tak samo liczną dziedzinę, pierwsza wybierana jest ta leżąca bliżej środka. Zmodyfikuj predykat ''labeling_b'' tak, aby wykorzystywał kolejność zmiennych z ''labeling_c''. Która zmienna (predykatu) odpowiada za kolejność i dlaczego ''AllVars''? Sprawdź czasy działania tej metody.
+Ostatnia z proponowanych metod to niewielka modyfikacja poprzedniej. Oprócz preferowania środkowych zmiennych, rozpatruje się też środkowe wartości w pierwszej kolejności. Wymaga to tylko modyfikacji użycia predykatu ''indomain'' poprzez zastąpienie go wersją dwuargumentową: ''indomain(Vars, middle)''.
+Limity dla metod (największa, do której szybko liczą się wszystkie o rozmiarze parzystym/największa, dla której szybko się liczy):
+  * naiwna: 26 / 26
+  * najbardziej ograniczona zmienna: 86 / 170
+  * najpierw środkowe: 28 / 28
+  * najbardziej ograniczona, możliwie najbliższa środkowi zmienna: 82 / 290
+  * jw, z wyborem środkowych wartości zmiennej 92 / 300
+Druga liczba w powyższych ograniczeniach jest tylko dolnym limitem na opisaną wielkość.
+Celem tych rozważań jest pokazanie, że właściwy dobór metody przeszukiwania może mieć ogromny wpływ na szybkość uzyskania wyniku. Platforma ECLiPSe zostawia szerokie pole do optymalizacji wysokopoziomowych zostawiając jednocześnie możliwość szybkiego, deklaratywnego napisania prototypu dla niewielkich problemów.
+=== Zadania fakultatywne ===
+  - Wypróbuj swoje własne heurystyki dla problemu n hetmanów. Porównaj ich szybkość działania z tymi zaproponowanymi w ćwiczeniu.
+  - Spróbuj znaleźć możliwie duże plansze, na których szybko działają heurystyki z ćwiczenia. Możesz do tego celu wykorzystać (odpowiednio zmodyfikowany) poniższy predykat:
+<code prolog>
+fll :- writeln('NOT OK'), !.
+time_is_acceptable :-
+        ( for(I, 4, 120, 2) do
+            writeln(I),
+            timeout:timeout(
+                     (!, queens(I, _, labeling), writeln('OK')),
+,
+                     fll)
+        ).
+</code>
+===== -. Fabryka słodyczy, część 1. =====
+Na wieść o dużych możliwościach programowania z ograniczeniami zgłosił się właściciel fabryki słodyczy. Chce, aby pomóc mu zoptymalizować produkcję poznawanymi na laboratoriach metodami. Pierwszy problem jest dość łatwy i rozwiązywalny na inne sposoby, jednak na kolejnych laboratoriach będzie rozbudowywany o kolejne elementy i już nie będzie można przeliczyć go ręcznie.
+Otóż na nowy dział produkcji czekolad zamierza przeznaczyć 500.0 złotych (oczywiście nie polskich). Ceną sprzedaży będzie 5.0 złotych za litr. Do wyboru ma trzy procesy produkcyjne, w których koszt wyprodukowania litra czekolady wynosi odpowiednio 1.0, 2.0 i 1.5 złotego. Który proces powinien wybrać i ile wtedy zarobi?
+Przełożenie problemu na język programowania z ograniczeniami wymaga zastosowania ograniczeń zmiennoprzecinkowych oraz napisania własnego ograniczenia (więcej o pisaniu własnych ograniczeń w kolejnym ćwiczeniu).
+<code prolog>
+:- lib(ic).
+:- lib(branch_and_bound).
+:- lib(listut).
+delay constr_nth(Domain, Which, Value) if (var(Which); var(Domain)).
+constr_nth(Domain, Which, Value) :- nth1(Which, Domain, Value).
+% który z CostPerLiter daje największy zysk?
+problem(CPLS, PricePerLiter, Money, Income, Which) :-
+        length(CPLS, N),
+        Which :: 1 .. N,
+        nth_value(CPLS, Which, CPL),
+        Liters $= Money / CPL,
+        Income $= Liters * PricePerLiter - Money,
+        Loss $= -1.0 * Income,
+        minimize(labeling([Which]), Loss).
+</code>
+Opiszmy nowe elementy po kolei:
+  - ''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.
+  - Predykat ''minimize'' działa tak jak wcześniej, przy czym tym razem optymalizuje zmienną zmiennoprzecinkową.
+Uruchom program w ECLiPSe i sprawdź działanie. Czy wyniki się zgadzają z oczekiwaniami?
+====== LAB: Ograniczenia i ich implementowanie w środowisku ECLiPSe ======
+Właściwe określenie i implementacja ograniczeń jest drugim, obok metody przeszukiwania, kluczowym elementem rozwiązywania problemów w programowaniu z ograniczeniami. Najprostszą ich realizacją jest napisanie odpowiednich predykatów je określających, co było robione w laboratorium wprowadzającym. Czasami jednak istnieje wiele metod określania ograniczeń, bądź osiągnięcie dobrej szybkości rozwiązywania problemu wymaga podania pewnych metainformacji o ograniczeniu.
+===== -. Przed laboratorium =====
+Zapoznać się z metodami propagacji ograniczeń [[http://eclipseclp.org/doc/tutorial/tutorial100.html]].
+Przeczytać czym są problemy programowania liniowego [[http://en.wikipedia.org/wiki/Linear_programming]].
+===== -. Jak działają ograniczenia =====
+Deklaratywnie normalny predykat (na przykład ''<='') ma takie samo znaczenie jak jego wersja będąca ograniczeniem. Podstawową różnicą jest to, że normalny predykat jest wykonywany od razu, zaś wykonanie ograniczenia jest opóźniane.
+To, jak bardzo sprawdzanie ograniczeń jest opóźniane, zależy od programisty. W przypadku **sprawdzania spójności** sprawdzenie odwleka się, dopóki wszystkie zmienne ograniczenia nie będą termami bazowymi.
+Otwórz środowisko tkeclipse i wpisz w polu ''Query entry'' poniższe zapytania. Używane ograniczenia pochodzą z biblioteki ''suspend'', stąd nazwa modułu i dwukropek przed użyciem predykatu (nie było potrzeby stosowania tej notacji wcześniej, gdyż wykorzystywaliśmy konstrukcję '':- lib(nazwa_biblioteki).'').
+<code prolog>
+?- X > 0
+?- X > 0, X is 2
+?- X is 2, X > 0
+?- suspend : (X > 0)
+?- suspend : (X > 0), X is 42
+?- suspend : (X > 0), X is -42
+</code>
+Nie jest to jedyne, i nie zawsze najlepsze, zachowanie. Weźmy na przykład predykat ''#\='' ze znanego nam modułu ''ic''. Jak pamiętamy, w tym module mogliśmy określać dziedziny zmiennych. Zatem jeśli jedna ze zmiennych w predykacie ma już określoną wartość, możemy ją wyrzucić z dziedziny drugiej zmiennej. Zachowanie takie nazywa się **sprawdzaniem wprzód**. Wpisz w tkeclipse:
+<code prolog>
+?- ic : (X :: 1 .. 5), ic : (X #\= 2)
+?- ic : (X :: 1 .. 5), ic : (X #\= 2), X is 2
+?- ic : (X :: 1 .. 5), ic : (X #\= 2), X is 3
+?- ic : (X :: 1 .. 5), suspend : (X > 2)
+?- ic : (X :: 1 .. 5), suspend : (X > 2), X is 3
+?- ic : (X :: 1 .. 5), suspend : (X > 2), X is 2
+?- ic : (X :: 1 .. 5), ic : (X > 2)
+</code>
+Jak widać, predykat ''ic:#\='' działa zgodnie z opisem, dziedzina się zmniejsza, zaś podstawianie wartości za X jest należycie sprawdzane. Mimo, że użycie predykatu ''suspend:>'' również mogłoby zmniejszyć dziedzinę, nie dzieje się tak, gdyż realizuje on inny schemat zachowania. Dziedzinę zmniejsza analogiczny predykat z modułu ''ic'', jednak robi to w jeszcze dalej idący sposób.
+Wspomniany predykat ''ic:>'' realizuje tak zwaną **spójność łukową**. Poza opisanym już ograniczaniem dziedzi, gdy tylko jedna zmienna jest podstawiona, analogiczny proces odbywa się, gdy obie zmienne nie są podstawione. Najlepiej ilustrują to poniższe przykłady:
+<code prolog>
+ic : ([X,Y] :: 1 .. 5), ic : (X > Y)
+ic : ([X,Y] :: 1 .. 5), ic : (X > Y), ic : (Y > 2)
+</code>
+Zauważ, co się stało w drugim przypadku. Dołożenie ograniczenia na zmienną Y spowodowało dalsze ograniczenie zmiennej X. Zachowanie takie jest istotą omawianej propagacji ograniczeń i jednocześnie powodem rozróżniania tylu ich rodzajów -- im więcej informacji staramy się wyciągnąć z ograniczenia, tym drożej to kosztuje. Z tego powodu również na przykład predykat ''ic:#='' propaguje tylko ograniczenia na zakres dziedziny, a nie na jej poszczególne elementy w środku.
+===== -. Fabryka słodyczy, część 2. =====
+Na początek wróćmy do ograniczenia ''constr_nth'' z poprzedniej części.
+<code prolog>
+delay constr_nth(Domain, Which, Value) if (var(Which); var(Domain)).
+constr_nth(Domain, Which, Value) :- nth1(Which, Domain, Value).
+</code>
+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 ===
+Po ostatniej próbie przyszedł w końcu czas na trudniejsze zadanie. Będziemy je rozwiązywać etapami. Najpierw jednak przedstawmy na czym polega sam problem:
+Fabryka słodyczy może produkować dwa rodzaje czekolady bądź czekoladki z orzechami. Do każdego z tych wyrobów potrzebuje odpowiednią ilość składników: kakao oraz orzechów. Towary te są oferowane przez dwóch dostawców po różnych cenach. Z powodu ustawy antykorupcyjnej, która niedawno weszła w życie nie można jednak zamówić obydwu towarów u tego samego dostawcy. Fabryka ma określoną ilość pieniędzy, które może przeznaczyć na produkcję oraz zadane ceny, po których sprzedaje każdy ze swoich wyrobów. Fabryka może sprzedać maksymalnie 200 jednostek każdego z wyrobów. Celem jest maksymalizacja zysku fabryki.
+Zanim przejdziemy do kodu, zastanówmy się chwilę nad zadaniem. Jego główna część jest zadaniem programowania liniowego (maksymalizacja zysku przy ograniczeniu pieniędzy), jednak stawiane są dodatkowe wymogi, w związku z czym nie można po prostu zastosować znanych procedur rozwiązujących zadania PL. Zostanie jednak pokazane jak można z nich skorzystać w celu poprawy efektywności rozwiązania.
+Pierwsza wersja rozwiązania będzie zawierała drobne oszustwo -- zmienne decyzyjne odpowiedzialne za określenie wielkości dostaw będą dyskretne. Tak uproszczoną wersję każdy powinien móc rozwiązać w tym momencie i próba rozwiązania jest zalecana.
+Predykat testujący:
+<code prolog>
+callP3(Income, W, Q) :- problem3([[1.5, 1], [3, 2]], [2, 3, 4],
+, Income, W, [[1.0, 0],
+                                                             [0.7, 0],
+                                                             [0.5, 1]],
+                                 Q).
+</code>
+Kolejnymi argumentami predykatu ''problem3'' rozwiązującego zadanie są koszty towarów u poszczególnych dostawców, ceny sprzedaży produktów, pieniądze przeznaczone na produkcję, zysk, wybrani dostawcy poszczególnych towarów, lista ilości towarów potrzebnych do wyprodukowania produktów oraz wielkości produkcji poszczególnych produktów.
+Poniżej znajduje się przykładowe rozwiązanie dla porównania:
+<code prolog>
+problem3([CPLS, CPIS], [P1, P2, P3],
+         Money, Income, [W1, W2], [[R11, R12], [R21, R22], [R31, R32]],
+         [Q1, Q2, Q3]) :-
+        length(CPLS, N),
+        length(CPIS, M),
+        W1 :: 1 .. N, % który dostawca dostarcza zasób 1
+        W2 :: 1 .. M, % który dostawca dostarcza zasób 2
+        constr_nth(CPLS, W1, C1),
+        constr_nth(CPIS, W2, C2),
+        W2 #\= W1, % muszą być różni dostawcy
+        Q1 :: 0 .. 200, % ile produkujemy czekolady 1
+        Q2 :: 0 .. 200, % ile produkujemy czekolady 2
+        Q3 :: 0 .. 200, % ile produkujemy czekoladek
+        R1 $= Q1 * R11 + Q2 * R21 + Q3 * R31, % ile potrzeba zasobu 1
+        R2 $= Q1 * R12 + Q2 * R22 + Q3 * R32, % ile potrzeba zasobu 2
+        Cost $= C1 * R1 + C2 * R2,
+        Cost $=< Money,
+        Income $= P1*Q1 + P2*Q2 + P3*Q3 - Cost,
+        Loss $= -1.0 * Income,
+        minimize(labeling([W1, W2, Q1, Q2, Q3]), Loss).
+</code>
+Wykonanie powyższego kodu zostawia 3 opóźnione cele. Jeśli jakaś zmienna decyzyjna nie zostałaby znaleziona, mogłoby to wskazywać na przyczynę. Jednak często jest to wyłącznie efekt wykorzystywania arytmetyki przedziałów (zmienne rzeczywiste). Można to potwierdzić otwierając okno Tools>Delayed Goals w ECLiPSe.
+Można również zauważyć, że kod wykonuje się bardzo wolno -- kilka sekund. Jest to spowodowane koniecznością przejrzenia dużej przestrzeni rozwiązań (zmienne Q1, Q2, Q3), która nie jest zmniejszana przez wprowadzane ograniczenia (na całkowity koszt). Nie jest wykorzystywana również struktura przestrzeni rozwiązań. Informatyk może tu jednak dostrzec problem programowania liniowego i wykorzystać to spostrzeżenie do optymalizacji programu.
+==== Eplex -- programowanie liniowe w ECLiPSe ====
+Eplex jest biblioteką ECLiPSe będącą interfejsem do zewnętrznych programów rozwiązujących problemy programowania liniowego (ciągłe, całkowitoliczbowe oraz mieszane). Pełna dokumentacja znajduje się pod adresem [[http://www.eclipseclp.org/doc/libman/libman052.html]]. Poniżej omówione zostaną najważniejsze elementy biblioteki, co umożliwi jej wykorzystanie do sprawnego rozwiązania problemu fabryki.
+Na początek skompiluj i uruchom poniższy kod:
+<code prolog>
+:- lib(eplex).
+:- eplex_instance(my_instance). % tworzy instancję biblioteki
+lp_example(Cost) :-
+     my_instance: eplex_solver_setup(min(X)),
+     my_instance: (X+Y $>= 3),
+     my_instance: (X-Y $= 0),
+     my_instance: eplex_solve(Cost).
+</code>
+Druga linia kodu tworzy instację ''my_instance''. Jest to jakby kontener na zmienne i ograniczenia -- każda instancja ma osobne ich zbiory. Istnieje również domyślna instancja o nazwie ''eplex''. Predykat ''lp_solve'' działa na instancji ''my_instance'', co widać po składni -- korzysta on z predykatów z modułu o takiej właśnie nazwie.
+Predykat ''eplex_solver_setup'' ustawia cel optymalizacji. Może to być minimalizacja (jak w przykładzie) lub maksymalizacja (wtedy zamiast min jest max). ''X'' jest celem optymalizacji -- w przykładzie szukamy rozwiązania dopuszczalnego z najmniejszą wartością ''X''. Zamiast ''X'' możemy wpisać dowolne wyrażenie liniowe od zmiennych decyzyjnych (dla problemu programowania liniowego), np. ''2*X+Y''. Sprawdź i zobacz, co się stanie.
+Kolejne dwie linie po prostu określają ograniczenia liniowe na zmienne. W przeciwieństwie do biblioteki ic, nie ma tu potrzeby wcześniejszego definiowania zmiennych, choć jest to możliwe (również za pomocą operatorów ''::'' oraz ''$::''). Ostatnia linijka wywołuje samą procedurę optymalizacji, unifikując znalezioną wartość celu ze zmienną ''Cost''.
+Przed pracą z biblioteką należy uczynić jeszcze trzy uwagi:
+  - Wprowadzane ograniczenia akumulują się cały czas. Jedynym sposobem ich usunięcia jest skorzystanie z predykatu ''my_instance: eplex_cleanup'' czyszczącego daną instancję.
+  - Czasami przydatna jest wiedza dla jakich wartości zmiennych osiągana jest optymalna wartość celu. Używa się do tego predykatu ''eplex_var_get'' jak w przykładzie poniżej. Dla jasności zmienna w instancji eplex i w środowisku ECLiPSe mają różne nazwy. Co się stanie, jeśli nazwy będą takie same? A co, jeśli zmienna X miałaby określoną wartość (np. 5.0) przed określeniem ograniczeń?
+  - Sprawdź, co robi predykat ''my_instance: integers([X])'' (przyjmuje on listę zmiennych).
+<code prolog>
+lp_example(Cost, XX) :-
+     my_instance: eplex_solver_setup(min(2*X+Y)),
+     my_instance: (X+Y $>= 3),
+     my_instance: (X-Y $= 0),
+     my_instance: eplex_solve(Cost),
+     my_instance: eplex_var_get(X, typed_solution, XX).
+</code>
+Przetestuj, jak eplex reaguje na problemy PL różnych typów (posiada rozwiązanie, jest sprzeczny, jest nieograniczony). Sam skonstruuj odpowiednie problemy.
+=== Powrót do fabryki ===
+W tym momencie wiemy już wszystko, co jest potrzebne do zastosowania biblioteki eplex w drugim problemie fabryki. Jest jednak pewien haczyk. Nie mamy pojedynczego problemu programowania liniowego, lecz jego postać zależy od wartości zmiennych ''W1'' i ''W2''. Nie jest to oczywiście duży problem, jednak wymaga zmiany dotychczasowego schematu zmienne -> ograniczenia -> przeszukiwanie. Poszukiwanie rozwiązania musi być tu dwustopniowe: zewnętrzne przeszukiwanie przeszukuje przestrzeń wartości zmiennych ''W1'' i ''W2'', zaś wewnętrzne jest już samym problemem programowania liniowego. Poniżej znajduje się pomocniczy predykat, który go rozwiązuje. Zawiera on jednak kilka dziur (trzykropki) do samodzielnego uzupełnienia. Nazwy argumentów zgadzają się z wcześniej stosowanymi nazwami zmiennych.
+<code prolog>
+solve3_lp([C1, C2], [P1, P2, P3],
+         Money, Income, [[R11, R12], [R21, R22], [R31, R32]],
+         [Q1, Q2, Q3], Loss) :-
+        my_instance: ([Q1, Q2, Q3] $:: 0.0..200.0), % ograniczenie na
+                                                    % wielkość produkcji
+        my_instance: integers([Q3]), % możemy produkować tylko
+                                     % całkowitą liczbę czekoladek
+        my_instance: (R1 $= ...),
+        my_instance: (R2 $= ...),
+        my_instance: (Cost $= ...),
+        my_instance: ..., % ograniczenie na koszt
+        my_instance: (Income $= ...), % zysk
+        my_instance: eplex_solver_setup(max(Income)),
+        my_instance: eplex_solve(Income),
+        ...% pobranie wartości zmiennych Q1, Q2, Q3
+        ...% czyszczenie instancji
+        Loss $= -1.0 * Income.
+</code>
+W tym momencie większość pracy już za nami. Wystarczy wprowadzić kilka zmian do samego predykatu znajdującego rozwiązanie problemu fabryki (opis dla predykatu przykładowego; jeśli zrobiłeś własny, konieczne zmiany mogą wyglądać nieco inaczej). Przede wszystkim należy usunąć wszystkie linie, które rozwiązywały podzadanie programowania liniowego. Druga zmiana jest już bardzo drobna: cel minimalizacji strat (użycie predykatu ''minimize'') rozszerzamy o wywołanie pomocniczego predykatu ''solve3_lp'' (dla ułatwienia wszystkie nazwy zmiennych się zgadzają) oraz usuwamy zmienne ''Q1'', ''Q2'' i ''Q3'' z listy dla predykatu ''labeling'' (dlaczego?).
+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.1359977296.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry