1 Nawracanie i odcięcie Jakub Czoboda, Jezierski Aleksander, Skierkowski Paweł, Bembenista Kamil, Martynowski Witold

2 Generowanie wielu rozwiązańNajprościej jest wygenerować wiele rozwiązań na podstawie zbioru faktów wówczas, gdy wiele faktów pasuje do tego zapytania. Jeśli mamy w bazie następujące fakty „ojciec(X,Y)” oznaczające, że Y jest ojcem X: -ojciec(maria, jerzy). -ojciec(jan,jerzy). -ojciec(zuzanna,henryk). -ojciec(jerzy,edward).

3 Na zapytanie:. - ojciec(X,Y). Będzie istniało kilka odpowiedziNa zapytanie: ?- ojciec(X,Y). Będzie istniało kilka odpowiedzi. Jeśli będziemy żądali za pomocą średnika kolejnych rozwiązań, otrzymamy takie oto wyniki: X=maria, Y=jerzy; X=jan, Y=jerzy; X=zuzanna, Y=henryk; X=jerzy, Y=edward Dzięki nawracaniu znajdowane są wszystkie rozwiązania z bazy danych. Prolog nie analizuje zwracanych wyników i ich nie zapamiętuje.

4 Jeśli zadamy zapytanie:. - ojciec(_,X)Jeśli zadamy zapytanie: ?- ojciec(_,X). Otrzymamy: X=jerzy ; X=jerzy ; X=henryk ; X=edward; Jerzy pojawił się dwukrotnie, gdyż jest ojcem Marii i Jana. Jeśli prolog może pokazać to samo w dwojaki sposób, traktuje obie możliwości jako różne rozwiązania

5 Nawracanie ma miejsce także w sytuacji, kiedy istnieje więcej możliwych rozwiązań głębiej zagnieżdżonych. Przykładowa definicja reguły mówiącej, że „jednym z dzeci X jest Y, może wyglądać tak: Dziecko(X,Y) :- ojciec (Y,X). Wobec tego zapytanie: ?- dziecko(X,Y) da odpowiedzi: X=jerzy, Y=maria ; X=jerzy, Y=jan ; X=henryk, Y=zuzanna; X=edward, Y=jerzy

6 Działanie mechanizmu nawracania w ProloguPrzypuśćmy, że mamy pewien predykat: a określony w programie przez zdania i reguły. Zapiszmy ogólnie regułę dla a w postaci a() :- b(), c(), d(). Przy czym funkcje b, c, d są także definiowane zarówno przez fakty, jak i reguły oraz mogą być relacjami między jakimiś zmiennymi. Mechanizm nawracania (czyli schemat postępowania Prologu podczas „przeszukiwania” bazy wiedzy w celu udzielenia odpowiedzi na pytanie: ?- a()) można przedstawić następująco:

7 Przeszukiwanie linijka po linijce kodu programu w poszukiwaniu predykatu lub reguły o nazwie a. eśli jest to zdanie Prolog sprawdza, czy dla podanych zmiennych jest ono prawdziwe. Wówczas zwraca YES i sprawdza kolejną linijkę kodu. W pozostałych przypadkach (zdanie jest fałszywe lub nie da się określić jego wartości logicznej) Prolog przechodzi od razu do kolejnej linii kodu

8 Jeśli odnaleziona będzie reguła, Prolog zacznie przeszukiwanie bazy w celu znalezienia odpowiedzi na zapytanie ?-b(). Uwaga: Baza wiedzy jest przeszukiwana znów od pierwszej linii a nie od miejsca w którym wystąpiła reguła dla a. Po znalezieniu pierwszego zdania lub reguły dla B powtarza się schemat z poprzedniego punktu i tak aż do skonkretyzowania wszystkich argumentów b

9 Następnie powtarzane są kroki z poprzednich punktów dla c 0raz d i udzielana jest odpowiedź Yes/No lub zwracane są wartości zmiennych które spełniają zadaną regułę i da się je znaleźć w pierwszym kroku (np. jakiejś iteracji).

10 Prolog kontynuuje poszukiwania zdań/reguł określających d (przy ustalonych uprzednio zmiennych występujących w a, b, c) i po znalezieniu odpowiedzi lub kolejnej wartości zmiennej wypisuje odpowiedź. Dopiero wtedy, gdy wszystkie możliwości skonkretyzowania wolnych zmiennych w predykacie d zostaną wyczerpane, Prolog zaczyna poszukiwać kolejnych zdań/reguł dla c nie zmieniając zmiennych związanych przy określaniu b. Powtarzane są kroki z podpunktów 2 i dalszych aż do ponownego wypisania odpowiedzi lub wartości zmiennych.

11 Po wyczerpaniu możliwości określenia bPo wyczerpaniu możliwości określenia b. Prolog kontynuuje szukanie zdań/reguł dla a. Po znalezieniu każdej kolejnej powtarzane są znów wszystkie opisane już kroki aż do wypisania odpowiedzi.

12 Odcięcie Aby choć trochę kontrolować sposób realizacji programu w Prologu możemy używać operatora odcięcia „!”. Pozwala ono nakazać interpreterowi Prologa, by nie uwzględniał wcześniejszych możliwości wyboru podczas nawracania. Korzystanie z odcięcia jest bardzo istotne, ponieważ pozwala na pominięcie z góry znanych wyników, co w efekcie prowadzi do zwiększenia wydajności programu.

13 W celu dokładnego zrozumienia działania mechanizmu odcięcia, przyjrzyjmy się poniższemu programowi korzystającemu tylko z mechanizmu nawracania. a(X,Y) :- b(X), c(Y). b(d). b(e). b(f). c(g). c(h). c(i).

14 W wyniku działania programu otrzymujemy:?- a(X,Y). X = d Y = g ; X = d Y = h ; X = d Y = i ; X = e Y = g ; X = e Y = h ; X = e Y = i ; X = f Y = g ; X = f Y = h ; X = f Y = i ; No

15 Jak widać Prolog skonkretyzował dla zmiennej X wartość „d”, a następnie każdą kolejną wartość odpowiadającą zmiennej Y. Jako następne wartości, zmienna X przyjęła „e” oraz „f”, po czym Prolog powtózył poprzednie czynności dla każdej z nich. Często zachodzi jednak potrzeba ograniczenia działania programu i służy do tego właśnie mechanizm odcięcia.

16 Rozważmy ten sam przykład, tym razem wykorzystujący mechanizm odcięcia.a(X, Y) :- b(X), !, c(Y). b(d). b(e). b(f). c(g). c(h). c(i).

17 W odpowiedzi otrzymujemy poniższy wynik:?- a(X,Y). X = d Y = g ; X = d Y = h ; X = d Y = i ; No Jak można zauważyć, program zatrzymał się na etapie skonkretyzowania zmiennej X do wartości „d”.

18 Dzieje się to za sprawą zamieszczonego w kodzie operatora „Dzieje się to za sprawą zamieszczonego w kodzie operatora „!”, który przyjmuje pierwsze napotkane rozwiązanie dla wyrażenia b(X) jako jedyne. Jako że symbol odcięcia wystapił przed ukonkretyzowaniem zmiennej Y, wciąż można poszukiwać dla niej alternatyw.

19 Jako inny przypadek rozważmy poniższy kod:a(X) :- b(X), !, c(X). b(d). b(e). b(f). c(e). Możemy z góry założyć, że gdy X=e, wówczas spełnione jest zarówno „b” jak i „c”. Z powodu zastosowania odcięcia, program zatrzymuje się w momencie przypisania wyrażeniu b(X) wartości „d”, w efekcie zwracając wynik pusty.

20 Mechanizm odcięcia ma również znaczenia w przypadku, gdy dla jednego celu określone są dwie regułu. Dla przykładu, Prolog analizując poniższy kod: a(X) :- b(X), !, c(X). a(X) :- d(X). b(e). b(f). c(g). d(f). nie tylko odcina nawracanie podczas konkretyzowania zmiennej X, ale również odrzuca pozostałe regułydla a(X). Powoduje to zastosowany w kodzie symbol odcięcia, który blokuje możliwość korzystania z reguł innych niż te, które zostały zadeklarowane przed jego zastosowaniem.