Laboratorium sztucznej inteligencji Laboratorium nr 2 Podstawy programowania w Prologu. Rekurencja



Pobieranie 226,43 Kb.
Data26.02.2019
Rozmiar226,43 Kb.



Laboratorium sztucznej inteligencji

Laboratorium nr 2

Podstawy programowania w Prologu. Rekurencja



opracowanie: mgr. inż. Magdalena Wilkołazka

Podstawy teoretyczne

    1. Predykat odcięcia - ! i predykat – fail.

Automatyczne nawracanie jest jedną z cech charakterystycznych Prologa. Czasami są sytuacje, kiedy takie nawracanie powoduje stratę czasu, bo przeszukiwanie rozwiązań prowadzi donikąd. Wtedy można zastosować operator !, który pozwala na zablokowanie procesu nawrotu w wybranym miejscu. Jest to predykat bezargumentowy zawsze prawdziwy, który w czasie swojej weryfikacji powoduje zaniechanie badania innych, pozostałych jeszcze do weryfikacji definicji predykatów na bieżącym poziomie drzewa wnioskowania (uniemożliwia dokonanie nawrotu powyżej miejsca, w którym został wstawiony znak odcięcia (!)).

Zastosowanie operatora odcięcia zmienia logicznie (deklaratywnie) zdanie. np.:



p :- a, b.

p :- c.

jest równoważne zdaniu:



p ⇔ (a &b) ∨ c.

Natomiast:



p :- a, !, b.

p :- c.

co jest równoważne zapisowi:



p ⇔ (a &b) ∨ (~a & c).

Należy pamiętać, że negacje działają poprawnie tylko dla zunifikowanych (określonych jakąś wartością) zmiennych.

Wyróżniamy dwa rodzaje odcięć:

• odcięcia „czerwone” - to takie, które zmieniają interpretację deklaratywną programu*, utrudniają jego zrozumienie i powodują utratę pewnych rozwiązań.

• odcięcia „zielone” - takie, które nie wpływają na interpretację deklaratywną programu, nie zmniejszają jego czytelności i zachowują wszystkie rozwiązania (choć obcinają drzewo poszukiwań)
Przykład

Jest dany predykat funkcja/2, który nie zawiedzie, gdy pierwszy argument X i drugi argument Y przyjmą wartości opisane warunkami:



  • Jeżeli X <3, to Y = 0.

  • Jeżeli X ≥ 3 i X < 6, to Y = 2.

  • Jeżeli X ≥ 6, to Y = 4.

Rozwiązanie:

funkcja( X , 0) :- X < 3,!.

funkcja( X , 2) :- X >= 3, X < 6, !.

funkcja( X , 4) :- X >= 6.

Zadać pytanie:



funkcja(1,Y),Y > 2.

Aby zwiększyć optymalność kodu można zapisać źródło w postaci następujących reguł:



  • Jeżeli X<3, to Y = 0.

  • W przeciwnym przypadku jeżeli X < 6, to Y = 2.

  • W przeciwnym przypadku Y = 4.

Rozwiązanie:

funkcja( X , 0) :-X < 3,!.

funkcja( X , 2) :- X < 6, !.

funkcja( X , 4).

Przykład2



indian(curry).

indian(dahl).

indian(tandoori).

indian(kurma).

mild(dahl).

mild(tandoori).

mild(kurma).

chinese(chow_mein).

chinese(chop_suey).

chinese(sweet_and_sour).

italian(pizza).

italian(spaghetti).

szukaj(X):-indian(X),write(X),!.

Predykat fail służy do wymuszania nawrotów; zamiast wpisywać średnik, aby wyszukać kolejne rozwiązanie możemy użyć fail.

Oto przykład:

nazwa1(1) :- write('Jeden').

nazwa1(2) :- write('Dwa').

nazwa1(3) :- write('Trzy').

nazwa1(_) :- write(' Nie wiem!').

działanie Prologa:



?- nazwa1(2).

Dwa

Yes

?- nazwa1(2), fail.

Dwa Nie wiem!

No

?- nazwa1(X), fail.

JedenDwaTrzy Nie wiem!

No

W przypadku, gdy połączy się fail z predykatem odcięcia pojawią się takie wyniki:



nazwa2(1) :- !, write('Jeden').

nazwa2(2) :- !, write('Dwa').

nazwa2(3) :- !, write('Trzy').

nazwa2(_) :- write(' Nie wiem!').

Wyniki:


?- nazwa2(2).

Dwa

Yes

?- nazwa2(2), fail.

Dwa

No

?- nazwa2(X), fail.

Jeden

No

    1. If-else

Istnieje w prologu wbudowany predykat, który umożliwia wyrażenie konstrukcji if-then-else. W prologu if A then B else C można zapisać jako (A->B;C). Prolog to odczytuje, jako: spróbuj cel A, jesli jest on prawdziwy przejdź do celu B i zignoruj C. Jeżeli A zawiedzie, realizowany jest cel C i ignorowany B. Predykat max z wykorzystaniem konstrukcji if-then-else jest przedstawiony, jako:

max(X,Y,Z):-(X=Z=Y;Z=X).



  1. Rekurencja

Odwołanie reguły do samej siebie nazywamy rekurencją – rekurencja jest jedną z podstawowych operacji w prologu.



Uwaga! Poniżej podano cztery warianty tego samego programu - identyczne w sensie deklaratywnym, lecz różne w sensie proceduralnym.

przodek1(P,D):- rodzic(P,D).

przodek1(P,D):- rodzic(P,R),przodek1(R,D).
przodek2(P,D):- rodzic(P,R),przodek2(R,D).

przodek2(P,D):- rodzic(P,D).
przodek3(P,D):- rodzic(P,D).

przodek3(P,D):- przodek3(P,R),rodzic(R,D).
przodek4(P,D):- przodek4(P,R),rodzic(R,D).

przodek4(P,D):- rodzic(P,D).

Wyniki:


?-przodek1(tomek,ola).

Yes

?-przodek2(tomek,ola).

Yes

?-przodek3(tomek,ola).

Yes

?-przodek4(tomek,ola).

ERROR: out of local stack

Podsumowanie

przodek1 - najlepsza wersja

przodek2 - wersja o najgorszej efektywności, ale skuteczna

przodek3 - nie zawsze skuteczna, np. ?-przodek3(iza, jacek).



przodek4 - wersja nieskuteczna (nieskończona pętla!)

Uwaga!! W definicji klauzuli prologowej należy najpierw korzystać z klauzul, opisujących proste relacje między obiektami, zanim użyjemy relacji bardziej złożonych (rekurencyjnych).

  1. Realizacja ćwiczenia:

Laboratorium można wykonywać w parach. Zaliczenie danego laboratorium odbywa się na podstawie oddanego sprawozdania z wykonanych zadań. Sprawozdanie zawiera dane osób, które je wykonywały oraz rozwiazania problemów zadanych przez prowadzącą ćwiczenia.
Zad.1. Relacje rodzinne przedstawione sa na poniższym rysunku (strzałka X→Y symbolizuje, że X jest rodzicem Y.

Zdefiniuj predykat rodzic(X,Y), który jest prawdziwy kiedy X jest rodzicem Y i predykat: mężczyzna(X) (kobieta(X)), który jest prawdą kiedy X jest mężczyzną (kobietą). Sprawdź następujące zapytania:



    1. Czy tom jest mężczyzną?

    2. Kto jest mężczyzną?

Sprawdź następnie poniższe zapytania:

  1. Kto jest rodzicem Liz?

  2. Czy Bob jest rodzicem Pat?

  3. Znajdź wszystkie relacje rodzic-dziecko.

  4. Kto jest dziadkiem Jima?

  5. Kto jest wnukiem Toma?

Używając wcześniej zdefiniowanych predykatów utwórz predykaty: matka(X,Y) (ojciec(X,Y)), który jest prawdziwy kiedy X jest matką (ojcem) Y. Sprawdź, kto jest matką Jima i Joe.
W podobny sposób zdefiniuj predykaty: dziecko(X,Y), dziadek(X,Y), pradziadek(X,Y) i przetestuj je.
Aby uniknąć definiowania predykatów pra pra pra dziadków określ predykat przodek(X,Y), który jest prawdziwy, kiedy X jest przodkiem Y. (uzyj definicji rekursywnej czyli rekursji (rekurencji)). Przeanalizuj przykład w pomocy do ćwiczeń.

Sprawdź, kto jest przodkiem Pat.


Na koniec zmień kolejność klauzul w zdefiniowanej regule przodka i zobacz, co się stanie z zapytaniem.
Zad.2. Zdefiniuj następujący graf bez cykli.

Zdefiniuj predykat krawedz(p(x,y),p(x’,y’)) który jest prawdziwy, kiedy istnieje krawędź między punktem p(x,y) a punktem p(x’,y’). Przetestuj pewne zapytania dotyczące bezpośrednich krawędzi między odpowiadającymi punktami. Na końcu zdefiniuj predykat ścieżka(p(x,y),p(x’,y’)), który jest prawdziwy kiedy jest ścieżka bezpośrednia miedzy punktami p(x,y) i p(x’,y’). Sprawdź zapytania o istniejące ścieżki i nie istniejące. (np: sciezka(p(1,2),p(x,y)))

Co sie stanie kiedy krawędź (2,1)→(2,2) będzie zamknieta. Zanotuj, że wtedy nasz graph będzie miał cykl.
Zad.3 Korzystając z kombinacji predykatów !,fail napisz program dzielenia dwóch liczb reagujący na próbę dzielenia przez zero.

Zad.4.

Korzystając z predykatu odcięcia (!) napisz program kończący przeszukiwanie bazy wiedzy po znalezieniu pierwszego rozwiązania.




* Rozważmy klauzulę P postaci: P:-Q,R.

• Interpretacja deklaratywna klauzuli P: P jest prawdziwe wtedy, gdy Q i R są prawdziwe. albo: Z Q i R wynika P.

• Interpretacja proceduralna klauzuli P: żeby osiągnąć cel P, najpierw musisz osiągnąć podcel Q, a potem podcel R. albo: Spełnienie P wymaga najpierw spełnienia Q a potem R.

Rożnica: Interpretacja proceduralna określa nie tylko logiczny związek między nagłówkiem reguły i jej ciałem, ale również porządek w jakim mają być osiągane podcele. Deklaratywna interpretacja programu prologowego określa czy dany cel jest spełniony, jeśli tak, to dla jakich wartości zmiennych.





: files -> 146935 -> public
public -> Operacje arytmetyczne
public -> Kolejne kroki tej metody to
public -> Podstawy o czym będziemy mówić? Krótka historia C++
public -> Zadania z bramek logicznych I projektowania układów
public -> Liczby rzeczywiste, wprowadzane do komputera w zapisie dziesiętnym, podlegają automatycznemu przetworzeniu do jednej z postaci przewidzianych w standardzie ieee 754-2008
public -> Na dzisiejszych ćwiczeniach zostanie pokazany proces generowania kodu na podstawie przykładowego diagramu klas opisującego sklep inetrnetowy
public -> Przeliczanie liczb w systemie dziesiętnym na kod U2 I odwrotnie
public -> 1. Operacje arytmetyczne na liczbach w różnych systemach liczbowych dodawanie, odejmowanie, mnożenie i dzielenie
public -> Laboratorium nr 11
public -> Instrukcja switch I typ wyliczeniowy




©operacji.org 2019
wyślij wiadomość

    Strona główna