|
|
pl:prolog:prolog_lab:reprezentacja_wiedzy [2009/03/17 20:03] holownia |
pl:prolog:prolog_lab:reprezentacja_wiedzy [2019/06/27 15:50] |
====== LAB: Reprezentacja wiedzy w Prologu, szukanie rozwiązań ====== | |
| |
FIXME Przemyśleć całość i poprawić cut. | |
| |
===== -. Reprezentacja wiedzy ===== | |
==== Rodzina - reprezentacja bazy danych ==== | |
| |
Program prezentuje realizację prostej bazy danych. | |
| |
Baza jest opisywana przy pomocy predykatu ''rodzina/3''. Osoby w rodzinie są opisywane przy pomocy termu ''osoba/4''. | |
| |
Rekord: | |
| |
<code prolog> | |
rodzina( | |
osoba(jan, kowalski, data(5,kwiecien,1946), pracuje(tpsa,3000)), | |
osoba(anna, kowalski, data(8,luty,1949), pracuje(szkola,1500)), | |
[ | |
osoba(maria, kowalski, data(20,maj,1973), pracuje(argo_turist,4000)), | |
osoba(pawel, kowalski, data(15,listopad,1979), zasilek)], | |
). | |
</code> | |
| |
Do bazy dostarczony jest interfejs, pozwalający na wyszukiwanie osób o pewnych własnościach. Przykładowe własności - elementy interfejsu: | |
| |
<code prolog> | |
zona(X) :- | |
rodzina(_,X,_). | |
| |
dziecko(X) :- | |
rodzina(_,_,Dzieci), | |
nalezy(X,Dzieci). | |
</code> | |
| |
Pełny program {{repr-fam.pl}} | |
| |
| |
**Ćwiczenie** | |
| |
Pobrać program {{repr-fam.pl}} | |
| |
Przeglądnąć całość. | |
| |
Zadać pytania: | |
| |
* jakie są osoby w bazie? | |
* jakie są dzieci w bazie? | |
* pokazać pensje wszystkich osób, | |
* jakie dzieci urodziły się w 1979r.? | |
* znaleźć wszystkie żony, które pracują, | |
* znaleźć osoby urodzone przed 1950 r, których pensja jest mniejsza niż 3000, | |
* itd. | |
| |
Korzystając z wiedzy zdobytej na [[listy2#przechwytywanie_wynikow|poprzednim laboratorium]], proszę policzyć zarobki wszystkich osób: | |
| |
?- bagof(X,istnieje(X),L),zarobki(L,Z). | |
| |
| |
Dopisać kolejne 2 rodziny. | |
| |
Powtórzyć pytania, kreatywnie... | |
| |
| |
==== Planowanie lotów ==== | |
Program {{flight_planner-1.pl}} pozwala na znalezienie trasy przelotu. | |
| |
Uwaga: w kodzie powyżej znajduje się ciekawe użycie operatora / /2. Proszę zwrócić uwagę na poniższy kod. | |
Prolog nie wylicza wyniku działania [[http://gollem.science.uva.nl/SWI-Prolog/Manual/operators.html#tab:operators|operatora]] (nie ma nigdzie ''is'') ale uzgadnia jego argumenty, gdyż operator po prawej i po lewej stronie ''='' jest taki sam. | |
| |
<code prolog> | |
?- a/b = X/Y. | |
| |
X = a | |
Y = b | |
| |
?- a/b = Z. | |
| |
Z = a/b | |
</code> | |
| |
**Ćwiczenie** | |
| |
Pobrać program {{flight_planner-1.pl}} | |
| |
Przetestować, np.: | |
<code prolog> | |
?- flight(ljubljana,london,Dzien,_,Wylot:_,_),Wylot >=18. | |
| |
Dzien = mo | |
Wylot = 20 ; | |
| |
Dzien = we | |
Wylot = 20 ; | |
| |
Dzien = th | |
Wylot = 20 ; | |
| |
Dzien = sa | |
Wylot = 20 ; | |
</code> | |
Czyli w które dni tygodnia mamy bezpośredni lot z Ljubljany do Londynu, po 18. | |
| |
Albo: jak można dostać się z Ljubljany do Edynburga w czwartek? | |
<code prolog> | |
?- route(ljubljana,edinburgh,th,R). | |
| |
R = [ljubljana/zurich/jp322/11:30, zurich/london/sr806/16:10, london/edinburgh/ba4822/18:40] | |
</code> | |
| |
Rozbudować - dodać własne trasy. | |
| |
Uwaga: wyrażenie | |
| |
:- op( 50, xfy, :). | |
| |
definiuje nowy operator (omówione na [[prolog_lab_metaprog#tematdefiniowanie_operatorow|kolejnym laboratorium]]). | |
W uproszczeniu: chcemy móc pisać ''g:m,'' zamiast '':(g,m)''. | |
| |
===== -. Wewnętrzna reprezentacja ===== | |
| |
Predykaty ''display'', ''write_canonical'' wypisują Prologową reprezentację termów. | |
| |
Np. | |
<code prolog> | |
?- A=1, display(A). | |
1 | |
| |
?- A=[1], display(A). | |
.(1, []) | |
| |
?- A=[1,a], display(A). | |
.(1, .(a, [])) | |
| |
?- A=[1,a,[ala,ma,[kota]]], display(A). | |
.(1, .(a, .(.(ala, .(ma, .(.(kota, []), []))), []))) | |
</code> | |
| |
W przypadku długich list może przydać się ''print/1''. | |
<code prolog> | |
?- X=[1,2,3,45,6,7,8,9,32,4,6,ff,7,d],print(X). | |
[1, 2, 3, 45, 6, 7, 8, 9, 32, 4, 6, ff, 7, d] | |
| |
X = [1, 2, 3, 45, 6, 7, 8, 9, 32|...] | |
</code> | |
| |
===== -. Sterowanie wnioskowaniem ===== | |
| |
Operator cut, pisany przy pomocy ''!'' pozwala na zablokowanie procesu nawrotu w wybranym miejscu. Te zmienne logiczne, które zostały zunifikowane przed napotkaniem ''!'', nie mogą ulec zmianie. | |
W efekcie można uniknąć wyszukiwania niechcianych, zbędnych, a czasem wręcz niepoprawnych rozwiązań. | |
| |
__Przykład 1__:\\ | |
Baza wiedzy: | |
<code prolog> | |
c(1). | |
c(2). | |
| |
a(X) :- c(X), !. | |
</code> | |
| |
Proszę zadać cel: | |
<code prolog> | |
?- a(X), write(X), fail. | |
</code> | |
| |
X zostaje zunifikowany z 1 - c(1). Cut uniemożliwia dalsze nawroty. | |
| |
__Przykład 2__:\\ | |
Baza wiedzy: | |
<code prolog> | |
c(1). | |
c(2). | |
d(2). | |
| |
a(X) :- c(X), !, d(X). | |
</code> | |
| |
Proszę zadać cel: | |
<code prolog> | |
?- a(1). | |
?- a(2). | |
?- a(X). | |
</code> | |
| |
Dla celu a(X) X zostaje zunifikowany z 1 - c(1). Reguła jest prawdziwa dla X=2, ale Prolog nie znajdzie takiego rozwiązania, bo uniemożliwiony został nawrót. d(1) przy takiej bazie wiedzy nie jest prawdziwe. | |
| |
__Przykład 3__:\\ | |
Baza wiedzy: | |
<code prolog> | |
c(1). | |
c(2). | |
c(3). | |
d(1). | |
d(2). | |
d(3). | |
| |
a(X,Y) :- c(X), !, d(Y). | |
</code> | |
| |
Proszę zadać cel: | |
<code prolog> | |
?- a(X,Y), write('X = '), write(X), write(', Y = '), writeln(Y), fail. | |
</code> | |
| |
Proszę zauważyć, że dla zmiennej logicznej Y, której unifikacja przebiega po wykonaniu odcięcia, nawroty są możliwe. | |
| |
| |
__Przykład 4__:\\ | |
Baza wiedzy: | |
<code prolog> | |
b(1). | |
b(2). | |
c(2). | |
c(3). | |
| |
a(X) :- b(X), !, c(X). | |
a(X) :- c(X). | |
</code> | |
| |
Proszę zadać cel: | |
<code prolog> | |
?- a(X). | |
?- a(3). | |
</code> | |
| |
Po napotkaniu cut odcinane są także pozostałe reguły predykatu. Dlaczego wobec tego a(3) jednak zwraca prawdę? | |
| |
Przykłady inspirowane [[http://en.wikibooks.org/wiki/Programming:Prolog_Cuts_and_Negation|Prolog Cuts and Negation]] | |
| |
**Ćwiczenie** | |
| |
Proszę dopisać do bazy wiedzy znany już predykat ''należy/2'': | |
| |
<code prolog> | |
nalezy1(X,[X|_]) :- write(X). | |
nalezy1(X,[_|O]) :- | |
nalezy1(X,O). | |
</code> | |
| |
Sprawdzić działanie dla list: | |
| |
?- nalezy1(a,[a,b,c]),fail. | |
| |
?- nalezy1(a,[a,b,a,c]),fail. | |
| |
Zmodyfikować: | |
| |
<code prolog> | |
nalezy2(X,[X|_]) :- !, write(X). | |
nalezy2(X,[_|O]) :- | |
nalezy2(X,O). | |
</code> | |
| |
Przetestować: | |
| |
?- nalezy2(a,[a,b,c]),fail. | |
| |
?- nalezy2(a,[a,b,a,c]),fail. | |
| |
A nastęnie sprawdzić działanie predykatu once/1. | |
| |
?- once((nalezy1(a,[a,b,a,c]))),fail. | |
| |
Wpisać predykat: | |
| |
<code prolog> | |
max1(X,Y,X) :- X >= Y. | |
max1(X,Y,Y) :- X < Y. | |
</code> | |
| |
a następnie prześledzić jego działanie: | |
| |
<code prolog> | |
?- spy(max1). | |
% Spy point on max1/3 | |
| |
[debug] ?- trace. | |
| |
[trace] ?- max1(2,3,X). | |
</code> | |
| |
Następnie dopisać: | |
| |
<code prolog> | |
max2(X,Y,X) :- X >= Y, !. | |
max2(_,Y,Y). | |
</code> | |
| |
i sprawdzić: | |
| |
<code prolog> | |
?- spy(max2). | |
% Spy point on max2/3 | |
| |
[debug] ?- trace. | |
| |
[trace] ?- max2(2,3,X). | |
</code> | |
| |
| |
===== -. Użycie predykatu not ===== | |
| |
Poza predykatem fail/0 mamy do dyspozycji predykat true/0. | |
Przy ich użyciu można skonstruować odpowiednik operatora \+ (negacja) - predykat not/0, który z logicznego punktu widzenia mógłby wyglądać tak: | |
| |
not(P) :- P,!,fail;true. | |
| |
| |
**Ćwiczenie** | |
| |
<code prolog> | |
?- true. | |
| |
?- fail. | |
| |
?- not(true). | |
| |
?- not(fail). | |
| |
?- \+ true. | |
| |
?- \+ fail. | |
</code> | |
| |
| |
===== -. Ciekawe problemy ===== | |
Proszę przeanalizować poniższe problemy, w miarę czasu i możliwości. | |
| |
| |
==== Zaawansowana Mapa ==== | |
| |
Rozważmy problem [[programy#tematkolorowanie_mapy|kolorowania mapy]]. | |
| |
W jaki sposób policzyć ile jest rozwiązań problemu? | |
| |
Napisz odpowiednie zapytanie albo predykat. | |
Podpowiedź: utwórz listę rozwiązań, policz elementy listy. | |
| |
Powyższy problem można przedstawić w sposób ogólny definiując predykaty: ''panstwo/1'', ''kolor/1'', ''sasiad/2'' określające odpowiednio: nazwy państw, kolory, oraz państwa sąsiadujące ze sobą. | |
| |
**Ćwiczenie** | |
| |
Zaimplementuj powyższą bazę wiedzy korzystając z tematu Kolorowanie Mapy. | |
Napisz klauzule predykatu ''koloruj/1'', który znajduje odpowiednie pokolorowanie w formie listy: ''[ [panstwo1,kolor1], [panstwo2,kolor2], ... ]''. | |
| |
Podpowiedź: | |
- wygeneruj listę państw, | |
- wygeneruj: ''[panstwo1,kolor1]'' dla każdego państwa, rekurencyjnie przegladajac listę państw, w rezultacie otrzymując kandydata na rozwiązanie: ''[ [panstwo1,kolor1], [panstwo2,kolor2], ... ]'' | |
- sprawdź czy w wygenerowanym kandydacie na rozwiązanie sąsiadujące państwa nie mają tego samego koloru; uwaga: przydatne będzie użycie ''forall/2''. | |
| |
==== Zagadka Einsteina ==== | |
Jedna z możliwych postaci zagadki Einstein'a: | |
| |
5 ludzi różnych narodowości zamieszkuje 5 domów w 5 różnych kolorach. Wszyscy palą papierosy 5 różnych marek i piją 5 różnych napojów. Hodują zwierzęta 5 różnych gatunków. Który z nich hoduje rybki? | |
| |
- Norweg zamieszkuje pierwszy dom. | |
- Anglik mieszka w czerwonym domu. | |
- Zielony dom znajduje się bezpośrednio po lewej stronie domu białego. | |
- Duńczyk pije herbatkę. | |
- Palacz Rothmansów mieszka obok hodowcy kotów. | |
- Mieszkaniec żółtego domu pali Dunhille. | |
- Niemiec pali Marlboro. | |
- Mieszkaniec środkowego domu pija mleko. | |
- Palacz Rothmansów ma sąsiada, który pija wodę. | |
- Palacz Pall Malli hoduje ptaki. | |
- Szwed hoduje psy. | |
- Norweg mieszka obok niebieskiego domu. | |
- Hodowca koni mieszka obok żółtego domu. | |
- Palacz Philip Morris pija piwo. | |
- W zielonym domu pija się kawę. | |
| |
| |
**Ćwiczenie** | |
| |
Proszę pobrać kod {{einstein.pl}} i zastanowić się na jego działaniem. | |
| |
Uzyskanie poprawnego rozwiązania: | |
<code prolog> | |
1 ?- rozwiazanie(Hodowca_rybek). | |
Hodowca_rybek = niemiec ; | |
fail. | |
</code> | |
| |
W przytoczonej wyżej wersji zagadki pytamy o hodowcę rybek. | |
Proszę wykonać odpowiednią modyfikację, aby dowiedzieć się, jakie papierosy palą mieszkańcy poszczególnych narodowości. | |
| |
Uzyskanie poprawnego rozwiązania: | |
<code prolog> | |
1 ?- rozwiazanie(S). | |
S = [norweg, dunhill] ; | |
S = [dunczyk, rothmans] ; | |
S = [anglik, pall_mall] ; | |
S = [niemiec, marlboro] ; | |
S = [szwed, phillip_morris] ; | |
fail. | |
</code> | |
| |
Proszę wrócić do oryginalnej wersji i sprawdzić, jak usunięcie któregoś z ograniczeń (ze wskazówek zagadki) wpływa na rozwiązanie. Proszę usunąć np. ograniczenie nr 13. | |
| |
Pojawia się alternatywne rozwiązanie. | |
| |
<code prolog> | |
1 ?- rozwiazanie(Hodowca_rybek). | |
Hodowca_rybek = dunczyk ; | |
Hodowca_rybek = niemiec ; | |
fail. | |
</code> | |
| |
| |
==== Sortowanie ==== | |
Pliki poniżej zawierają niektóre klasyczne algorytmy sortowania w Prologu. Patrz również: http://en.wikipedia.org/wiki/Sorting_algorithm oraz po polsku: http://pl.wikipedia.org/wiki/Sortowanie | |
| |
**Ćwiczenie** | |
| |
Pobrać kod algorytmów i prześledzić ich działanie: | |
| |
* {{bubblesort.pl}} | |
* {{insertsort.pl}} | |
* {{mergesort.pl}} | |
* {{quicksort.pl}} | |
| |
Przypomnienie z podstaw informatyki: jaką złożoność obliczeniową mają te algorytmy? | |
| |
Porównać ich wydajność, sortując losową listę liczb (np. z zakresu od 0 do 100) o zadanej długości (np. 30), wygenerowaną przy pomocy {{mkrandom.pl}} | |
| |
<code prolog> | |
?- mkrandom(100,30,X), time(bubblesort(X,B)), time(quicksort(X,Q)). | |
% 19,749 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips) | |
% 701 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips) | |
</code> | |
| |
===== Komentarze ==== | |
| |
* ciężko zdażyć zrealizować całe laboratorium: rodzina + flight planner zajmuje 70 min --- //[[wojnicki@agh.edu.pl|Igor Wojnicki]] 2008/11/05 15:41// | |