1 PROLOG NAWRACANIE I ODCIĘCIEWykonali: Piotr Wojnarski, Tomasz Kowalski, Rafał Zych, Arkadiusz Wiśniewski, Mateusz Zagórski

2 Generowanie wielu rozwiązańNajprościej jest wygenerować wiele rozwiązań zapytania na podstawie zbioru faktów wówczas, gdy wiele faktów pasuje do danego zapytania. Jeśli na przykład 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 taki oto wynik: X=maria, Y=jerzy ; X=jan, Y=jerzy ; X=zuzanna, Y=henryk ; X=jerzy, Y=edward

4 Dzięki nawracaniu znajdowane są wszystkie rozwiązania z bazy danychDzięki nawracaniu znajdowane są wszystkie rozwiązania z bazy danych. Prolog nie analizuje zwracanych wyników i ich nie zapamiętuje, wobec czego, jeśli zadamy zapytanie: ?- ojciec(_,X). Czyli kto jest ojcem? Otrzymamy: X=jerzy ; X=henryk ; X=edward

5 Jerzy pojawił się dwukrotnie, gdyż jest ojcem Marii i JanaJerzy 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. 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 dzieci X jest Y, może wyglądać tak: dziecko(X,Y) :- ojciec(Y,X).

6 Wobec tego zapytanie. - dziecko(X,Y)Wobec tego zapytanie ?- dziecko(X,Y). da odpowiedzi X=jerzy, Y=maria ; X=jerzy, Y=jan ; X=henryk, Y=zuzanna ; X=edward, Y=jerzy Jako, że ojciec(Y,X) ma cztery rozwiązania, tyleż rozwiązań ma dziecko(X,Y). Co więcej, rozwiązania generowane są w takiej samej kolejności.

7 Jedyna różnica polega na odwrotnej kolejności argumentów, co wynika z definicji predykatu dziecko. Analogicznie, jeśli zdefiniujemy: ojciec(X) :- ojciec(_,X). to zapytanie ?- ojciec(X). da w wyniku X=jerzy ; X=henryk ; X=edward

8 Jeśli mieszamy fakty i reguły, możliwe rozwiązanie pojawiają się w takiej kolejności w jakiej prezentowane są dane. Tak więc możemy zapisać, że adam jest osobą, że osobą jest wszystko posiadające matkę, i że ewa jest osobą. Poza tym różni ludzi mogą mieć różne matki: osoba(adam). osoba(X) :- matka(X,_). osoba(ewa). matka(kain,ewa). matka(abel,ewa). matka(jabal,ada). matka(tubilkain,sybilla).

9 Jeśli teraz zadamy zapytanie:. - osoba(X)Jeśli teraz zadamy zapytanie: ?- osoba(X). otrzymamy odpowiedzi: X=adam ; X=kain ; X=abel ; X=jabal ; X=tubilkain; X=ewa ;

10 Odcięcie Odcięcie pozwala nakazać interpreterowi Prologa, by nie uwzględniał wcześniejszych możliwości wyboru podczas nawracania. Może być to istotne z dwóch powodów: Program będzie działał szybciej gdyż nie będzie się niepotrzebnie starał spełniać cele, których wynik uzgadniania jest z góry znany, i które wobec tego nie wnoszą do rozwiązania niczego nowego Program zajmuje mniej pamięci komputera, gdyż pamięć jest zużywana oszczędniej.

11 Czasami użycie odcięcia spowoduje też, że program, który dotąd działał, działać przestanie, albo odwrotnie. Składniowo odcięcie w regule wygląda jak cel z predykatem bez argumentów. Cel ten zawsze jest natychmiast uzgadniany i nie może być ponownie uzgodniony. Jednak ma on też efekty uboczne polegające na zmianie sposobu nawracania. Miejsce tak zaznaczone jest niedostępne w tym sensie, że nie mogą być w nim umieszczane znaczniki.

12 Przykład praktyczny: Mamy w prologu bazę danych zawierającą dane o posiadanych książkach, osobach je wypożyczających i terminach zwrotu. Jednym z zagadnień, które trzeba uwzględnić jest dostępność poszczególnych usług bibliotecznych dla różnych grup ludzi.

13 Pewne usługi (podstawowe) powinny być dostępne dla wszystkichPewne usługi (podstawowe) powinny być dostępne dla wszystkich. Przykładami są korzystanie z katalogu czy czytelni. Inne usługi powinny być dostępne tylko dla wybranych osób czyli wypożyczanie książek, pożyczki międzybiblioteczne.

14 usluga(Osoba,Usluga) :-przetrzymana_ksiazka(Osoba,Ksiazka), !, usluga_podstawowa(Usluga). usluga(Osoba,Usluga) :- dowolna_usluga(Usluga). usluga_podstawowa(katalog). usluga_podstawowa(czytelnia). usluga_dodatkowa(wypozyczanie). usluga_dodatkowa(pozyczki_miedzybiblioteczne). dowolna_usluga(X) :- usluga_podstawowa(X). dowolna_usluga(X) :- usluga_dodatkowa(X).

15 Potrzebna jest baza danych klientów i informacji o korzystaniu z bibliotekiklient('A. Jones'). klient('W. Metesk'). przetrzymana_ksiazka('C. Watzer', book10089). przetrzymana_ksiazka('A. Jones', book29907). Po co użyto odcięcia i jakie ma ono znaczenie? Zakładamy, że chcemy przejrzeć wszystkich korzystających z biblioteki i sprawdzić jakie usługi są dla nich dostępne. ?- klient(X), usluga(X,Y).

16 Prolog najpierw odnajduje pierwszą osobę, ‘A. Jones’Prolog najpierw odnajduje pierwszą osobę, ‘A. Jones’. Załóżmy że ma kilka książek, których termin zwrotu dawno minął. Aby dowiedzieć się, jakie usługi dla tej osoby są dostępne, najpierw znajdowana jest pierwsza klauzula usluga. Wprowadzany jest nowy cel: sprawdzenie, czy osoba ma jakieś przetrzymane książki. Po krótkim przeszukiwaniu faktów przetrzymana_ksiazka znajdowany jest pierwszy fakt dotyczący A. Jonesa. Następny cel to odcięcie. Cel jest uzgadniany, jego efektem jest zatwierdzenie w systemie wszystkich decyzji od chwili wybrania klauzuli usluga.

17 Efektem odcięcia w regule usluga jest zatwierdzenie w systemie wszystkich wyborów dokonanych od chwili wybrania tej reguły. Ścieżka uzgadniania jest modyfikowana tak, aby pominąć wszystkie znaczniki między celem usluga a odcięciem, włącznie. Jeśli zatem nawracanie spowoduje wycofanie się poza ten punkt, cel usluga natychmiast zawiedzie.

18 Typowe zastosowania odcięciaPrzypadki kiedy chcemy poinformować system, że dla danego celu już została znaleziona odpowiednia reguła. Sytuacje kiedy chcemy poinformować Prologa, że dany cel ma natychmiast zawieść bez sprawdzania rozwiązań alternatywnych Przypadki kiedy należy zaprzestać generowania rozwiązań alternatywnych przez nawracanie.

19 Dziękujemy za uwagę