Sztuczna inteligencja
Jan Kazimirski
Sztuczna inteligencja
wykład 6
Sztuczna inteligencja
Jan Kazimirski
Sztuczna inteligencja
wykład 6
Sztuczna inteligencja
Jan Kazimirski
2
PROLOG
Sztuczna inteligencja
Jan Kazimirski
3
Literatura
●
W. F. Clocksin, C. S. Mellish, „Prolog.
Programowanie”, Helion 2003
●
I. Bratko, „Prolog Programming for Artificial
Intelligence”, Addison-Wesley 1986
●
M. Bramer, „Logic Programming with Prolog”,
Springer 2005
●
L. Sterling, E. Shapiro, „The Art of Prolog”, MIT
1999
Sztuczna inteligencja
Jan Kazimirski
4
Oprogramowanie
●
GNU Prolog
–
Strona domowa:
–
Źródła do pobrania: gprolog-1.3.1.tar.gz
–
Instalacja: po rozpakowaniu: ./configure; make;
make install
●
SWI Prolog
–
Strona domowa:
–
Instalacja: pakiet RPM (Open SUSE)
Sztuczna inteligencja
Jan Kazimirski
5
Prolog
●
Prolog – „Programowanie w Logice”
●
Alain Colmerauer and Phillipe Roussel – 1972 r
●
Deklaratywny język programowania
●
Dziedziny zastosowań:
–
Analiza języka naturalnego
–
Dowodzenie twierdzeń, obliczenia symboliczne
–
Systemy eksperckie, inteligentne bazy danych
–
Sztuczna inteligencja
Sztuczna inteligencja
Jan Kazimirski
6
Język proceduralny vs. deklaratywny
●
Język proceduralny
–
Programista określa sekwencję instrukcji do
wykonania – algorytm.
●
Język deklaratywny
–
Programista opisuje znane fakty i relacje
dotyczące problemu
–
Programista zadaje pytania prowadzące do
rozwiązania problemu
Sztuczna inteligencja
Jan Kazimirski
7
SWI Prolog
●
Rozwijane od 1987 r.
●
Autor: Jan Wielemaker
●
Platformy: Linux, Windows, MacOS
●
Typ licencji: Open Source
●
Łatwe łączenie z językami proceduralnymi ( m.in.
C, C++, Java)
●
Interfejs graficzny za pośrednictwem XPCE
Sztuczna inteligencja
Jan Kazimirski
8
Uruchomienie programu
Sztuczna inteligencja
Jan Kazimirski
9
Praca z programem
●
Przygotowanie programu
–
Dowolny edytor tekstowy. Treść programu w
zewnętrznym pliku (rozszerzenie .pl)
–
Wczytanie programu - consult(plik). lub [plik].
●
Realizacja zapytań
–
Załadowanie programu
–
Tryb interaktywny - konwersacyjny
Sztuczna inteligencja
Jan Kazimirski
10
Obiekty i relacje
●
Zdanie: „Jan ma książkę”
●
Obiekty: „Jan”, „książka”
●
Relacja „ma”
●
Zdanie określa relację między obiektami.
●
UWAGA! Obiekt ma zupełnie inny sens niż w
językach obiektowych (Java,C++)
Sztuczna inteligencja
Jan Kazimirski
11
Reguły
●
Reguły – służą do zapisu relacji
●
Przykład: „Dwoje ludzi jest siostrami jeżeli są
kobietami i mają tych samych rodziców”
●
Reguły wyjaśniają relację i pozwalają znaleźć
obiekty znajdujące się w tej relacji
Sztuczna inteligencja
Jan Kazimirski
12
Programowanie w PROLOG-u
●
Zdefiniowanie faktów określających obiekty i
związki między nimi
●
Zdefiniowanie reguł dotyczących obiektów i
związków między nimi
●
Zadawanie zapytań o obiekty i związki między
nimi.
Sztuczna inteligencja
Jan Kazimirski
13
Fakty
●
Zdanie: „Jan lubi Marię”
–
Obiekty: Jan, Maria
–
Relacja: lubi
●
Składnia w PROLOG-u:
lubi(jan,maria).
Sztuczna inteligencja
Jan Kazimirski
14
Fakty c.d.
●
Składnia c.d.
–
Nazwy obiektów muszą zaczynać się od małej
litery. Nie używamy polskich znaków
–
Nazwy obiektów zapisuje się za nazwą relacji w
nawiasach okrągłych i oddziela przecinkami
–
Na końcu zapisu faktu musi znaleźć się kropka
Sztuczna inteligencja
Jan Kazimirski
15
Fakty c.d.
●
Kolejność obiektów
–
Kolejność obiektów jest dowolna, ale istotna, tzn.
musi być stosowana konsekwentnie w
programie
–
Dwa poniższe zapisy
NIE
są równoważne:
lubi(jan,maria).
lubi(maria,jan).
Sztuczna inteligencja
Jan Kazimirski
16
Fakty c.d.
●
Obiekty w zapisie faktu – argumenty
●
Relacja w zapisie faktu – predykat
●
Nazwy obiektów i relacji mogą być dowolne np.
a(b,c).
●
Relacja może mieć dowolną liczbę argumentów.
●
Zbiór faktów – baza danych
Sztuczna inteligencja
Jan Kazimirski
17
Zapytania
●
Po zdefiniowaniu bazy danych można realizować
zapytania, które ich dotyczą
●
Zapytanie zaczyna się od ?-
●
Składnia zapytania jest podobna do składni faktu.
●
Proste zapytanie o fakt pozwala sprawdzić czy
dany fakt znajduje się w bazie danych
Sztuczna inteligencja
Jan Kazimirski
18
Przykład 1
prog1.pl
owoc(jablko).
owoc(gruszka).
owoc(malina).
?- [prog1].
% prog1 compiled 0.00 sec, 680 bytes
true.
?- owoc(malina).
true.
?- owoc(ziemniak).
false.
?- warzywo(malina).
ERROR: toplevel: Undefined procedure: warzywo/1
(DWIM could not correct goal)
?-
Sztuczna inteligencja
Jan Kazimirski
19
Zmienne
●
Zmienne pozwala odpowiadać na pytania o to jaki
obiekt występuje w relacji
●
Zmienne zaczynają się od wielkiej litery
●
Zmienna nieukonkretniona – nie wiadomo
jakiemu obiektowi odpowiada
●
Zmienna ukonkretniona – odpowiada
określonemu obiektowi
Sztuczna inteligencja
Jan Kazimirski
20
Przykład 2
prog1.pl
owoc(jablko).
owoc(gruszka).
owoc(malina).
?- [prog1].
% prog1 compiled 0.00 sec, 400 bytes
true.
?- owoc(X).
X = jablko .
<ENTER>
?- owoc(X).
X = jablko ;
<;>
X = gruszka ;
<;>
X = malina.
?-
Sztuczna inteligencja
Jan Kazimirski
21
Przykład 3
prog2.pl
lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).
?- consult(prog2).
% prog2 compiled 0.00 sec, 424 bytes
true.
?- lubi(X,kwiaty).
X = maria ;
<;>
false.
?- lubi(jan,X).
X = ksiazki ;
<;>
X = maria.
?-
Sztuczna inteligencja
Jan Kazimirski
22
Koniunkcja
●
Koniunkcja pozwala na łączenie celów które
muszą być spełnione aby odpowiedzieć na
pytanie.
●
Przykład:
–
„Czy Jan i Maria lubią się nawzajem”
–
Z użyciem koniunkcji: „Czy Jan lubi Marię i czy
Maria lubi Jana”
●
W PROLOG-u koniunkcję zapisuje się za pomocą
przecinka.
Sztuczna inteligencja
Jan Kazimirski
23
Przykład 4
prog2.pl
lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).
?- consult(prog2).
% prog2 compiled 0.00 sec, 968 bytes
true.
?- lubi(jan,maria),lubi(maria,jan).
false.
?- lubi(jan,ksiazki),lubi(jan,maria).
true ;
false.
?-
Sztuczna inteligencja
Jan Kazimirski
24
Przykład 5
prog3.pl
lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).
lubi(maria,ksiazki).
?- consult(prog3).
% prog3 compiled 0.00 sec, 1,072 bytes
true.
?- lubi(maria,X),lubi(jan,X).
X = ksiazki ;
false.
?-
Sztuczna inteligencja
Jan Kazimirski
25
Poszukiwanie z nawracaniem
●
Poszukiwanie w przypadku koniunkcji:
–
Poszukiwany jest pierwszy cel
–
Po jego znalezieniu zaznaczana jest pozycja w bazie,
zmienna jest ukonkretniana
–
Poszukiwany jest drugi cel – z ukonkretnioną zmienną
–
W przypadku braku rozwiązania – powrót do pozycji
pierwszego celu i dalsze poszukiwanie pierwszego
celu – zmienna jest ponownie nieukonkretniona
Sztuczna inteligencja
Jan Kazimirski
26
Reguły
●
Reguły opisują relacje.
●
Reguła określa, że jakiś fakt zależy od innych
faktów.
●
Przykład: „Jan lubi wszystkich, którzy lubią
książki”
●
Zapis z użyciem zmiennej: „Jan lubi X, jeżeli X
lubi książki”
Sztuczna inteligencja
Jan Kazimirski
27
Reguły c.d.
●
Definicja reguły w prologu składa się z głowy i
treści oddzielonych znakami :-
●
Przykład:
lubi(jan,X) :- lubi(X,ksiazki).
Sztuczna inteligencja
Jan Kazimirski
28
Przykład 6
prog4.pl
lubi(jan,ksiazki).
lubi(maria,kwiaty).
lubi(jan,maria).
lubi(maria,ksiazki).
lubi(piotr,ksiazki).
lubi(jan,X) :- lubi(X,ksiazki).
?- consult(prog4).
% prog4 compiled 0.00 sec, 1,332 bytes
true.
?- lubi(jan,X).
X = ksiazki ;
X = maria ;
X = jan ;
X = maria ;
X = piotr ;
false.
?-
Sztuczna inteligencja
Jan Kazimirski
29
Reguły c.d.
●
W treści reguły można stosować koniunkcję
●
Zmienne użyte i w głowie i w treści reguły będą
ukonkretniane w całym zakresie reguły
●
Zmienne można również zastosować tylko w
treści reguły.
Sztuczna inteligencja
Jan Kazimirski
30
Przykład 7
prog5.pl
mezczyzna(albert).
mezczyzna(edward).
kobieta(alicja).
kobieta(wiktoria).
rodzice(edward,wiktoria,albert).
rodzice(alicja,wiktoria,albert).
siostra(X,Y) :-
kobieta(X),
rodzice(X,M,O),
rodzice(Y,M,O).
?- consult(prog5).
% prog5 compiled 0.00 sec, 844 bytes
true.
?- siostra(alicja,edward).
true.
?- siostra(edward,alicja).
false.
?- siostra(alicja,albert).
false.
?- siostra(alicja,wiktoria).
false.
?-
Sztuczna inteligencja
Jan Kazimirski
31
PROLOG - składnia
●
Program w PROLOG-u składa się z termów
●
Term – stała, zmienna lub struktura
●
Stała – nazywa konkretny obiekt lub relację
●
Dwa rodzaje stałych: atomy i liczby
●
Atomy mogą składać się z liter i cyfr – zaczynając
się od małej litery np. jan, marta, lubi
●
Atomy mogą składać się z symboli, np. :-
Sztuczna inteligencja
Jan Kazimirski
32
PROLOG – składnia c.d.
●
Atomy o nazwach zawartych w apostrofy mogą
zawierać dowolne znaki.
●
PROLOG rozpoznaje liczby całkowite i
rzeczywiste
●
Zmienne mają postać atomów ale zaczynają się
od wielkiej litery lub znaku podkreślenia
●
Pojedynczy znak podkreślenia - zmienna
anonimowa (jej nazwa nie ma znaczenia)
Sztuczna inteligencja
Jan Kazimirski
33
PROLOG – składnia c.d.
●
Struktury – termy złożone
●
Obiekt złożony z atomów, liczb, zmiennych i
innych termów złożonych.
●
Strukturę zapisuje się jako f(arg1,arg2,...), gdzie f
to funktor (nazwa relacji) a arg1... to składniki.
Sztuczna inteligencja
Jan Kazimirski
34
Przykład 8
prog6.pl
posiada(marcin,auto(fiat,bialy)).
posiada(piotr,auto(ford,czerwony)).
posiada(pawel,auto(opel,bialy)).
?- consult(prog6).
% prog6 compiled 0.00 sec, 496 bytes
true.
?- posiada(pawel,auto(_,_)).
true.
?- posiada(X,auto(fiat,_)).
X = marcin ;
false.
?-
Wykorzystanie zmiennej
anonimowej oraz struktury.
! Poszczególne wystąpienia
zmiennej anonimowej nie
muszą być ukonkretnione do tej
samej wartości
Sztuczna inteligencja
Jan Kazimirski
35
Operatory
●
Niektóre operacje wygodniej zapisywać za
pomocą operatorów, np. działania matematyczne
●
Zapis a+b to inna forma zapisu termu w postaci
+(a,b)
●
Charakterystyka operatorów:
–
Operatory infiksowe, prefiksowe, postfiksowe
–
Priorytet operatora
–
Łączność operatorów – lewo-, prawostronna
Sztuczna inteligencja
Jan Kazimirski
36
Predykat równości
●
Wbudowany predykat infiksowy zapisywany jako
X = Y
●
Celem jest próba dopasowania X z Y.
●
Przykłady:
–
jan = pawel. /* zawodzi */
–
jan = jan. /* OK */
–
auto(fiat,bialy) = auto(X,Y). /* OK, ukonkretnienie */
Sztuczna inteligencja
Jan Kazimirski
37
Arytmetyka
●
Wbudowane predykaty porównania
–
X =:= Y - X i Y są tą samą liczbą
–
X =/= Y – X i Y są różnymi liczbami
–
X > Y – X jest większe niż Y
–
X < Y – X jest mniejsze niż Y
–
X =< Y – X jest mniejsze lub równe Y
–
X >= Y – X jest większe lub równe Y
Sztuczna inteligencja
Jan Kazimirski
38
Arytmetyka c.d.
●
Obliczenia
–
Do obliczeń wykorzystuje się operatora
infiksowego is
–
Operator is wylicza term występujący po prawej
stronie a następnie próbuje dopasować go do
termu po lewej stronie
–
Wbudowane operatory arytmetyczne obejmują:
dodawanie(+), odejmowanie(-), mnożenie(*),
dzielenie(/), dzielenie całkowite (//), dzielenie
modulo (mod)
Sztuczna inteligencja
Jan Kazimirski
39
Przykład 9
?- 2 < 3.
true.
?- 2 > 3.
false.
?- X is 2*3.
X = 6.
?- X is 8 mod 3.
X = 2.
?-
Sztuczna inteligencja
Jan Kazimirski
40
Przykład 10
prog7.pl
cena(fiat,5).
cena(ford,10).
cena(bmw,80).
cena(audi,40).
tanszy(X,Y) :-
cena(X,A),
cena(Y,B),
A<B.
drozszy(X,Y) :-
cena(X,A),
cena(Y,B),
A>B.
?- tanszy(fiat,ford).
true.
?- tanszy(bmw,ford).
false.
?- tanszy(X,ford).
X = fiat ;
false.
?- tanszy(X,bmw).
X = fiat ;
X = ford ;
X = audi.
Sztuczna inteligencja
Jan Kazimirski
41
Przykład 11
prog8.pl
/* populacja - mln mieszk.*/
populacja(usa,203).
populacja(indie,548).
populacja(chiny,800).
/* obszar - mln mil kw. */
obszar(usa,3).
obszar(indie,1).
obszar(chiny,4).
/* gstosc zaludnienia */
gestosc(X,Y) :-
populacja(X,P),
obszar(X,O),
Y is P/O.
?- consult(prog8).
% prog8 compiled 0.00 sec, 888 bytes
true.
?- gestosc(chiny,X).
X = 200.
?- gestosc(usa,X).
X = 67.6667.
?- gestosc(polska,X).
false.
?-
Sztuczna inteligencja
Jan Kazimirski
42
Struktury a drzewa
●
Struktury mogą być reprezentowane w postaci
drzew.
●
Przykład: a+b*c – tzn. +(a,*(b,c))
+
a
*
b
c
Sztuczna inteligencja
Jan Kazimirski
43
Lista
●
Ciąg uporządkowanych elementów
●
Lista może być dowolnej długości
●
Elementami listy mogą być dowolne termy: stałe,
zmienne, struktury, a także inne listy
●
Z listy można korzystać jeżeli nie wiadomo z góry
ile będzie elementów
Sztuczna inteligencja
Jan Kazimirski
44
Lista c.d.
●
Szczególny rodzaj listy nie zawierającej
elementów – lista pusta – zapisywana jako [].
●
Lista składa się z głowy i ogona.
●
Koniec listy zwyczajowo zapisywany jest jako
lista pusta.
●
Wewnętrzna reprezentacja listy opiera się o
funktor dwuargumentowy - kropkę
Sztuczna inteligencja
Jan Kazimirski
45
Lista c.d.
●
Lista zawierająca 1 element (a)
.(a.[])
●
Lista zawierająca 3 elementy (a,b,c)
.(a,.(b,.(c,[])))
●
Notacja alternatywna – elementy listy zapisane w
nawiasach kwadratowych np. [a,b,c]
Sztuczna inteligencja
Jan Kazimirski
46
Lista a drzewo
●
Listę można
zapisać w
postaci
drzewa, np.
Lista [a,b,c]
będzie miała
postać:
a
.
b
.
.
c
[]
Sztuczna inteligencja
Jan Kazimirski
47
Głowa i ogon listy
●
Podział na głowę i ogon listy wykorzystuje się do
jej przetwarzania.
●
Do dzielenia listy na głowę i ogon służy symbol
pionowej kreski (|).
●
Wzorzec H|T ukonkretnia H głową listy a T jej
ogonem.
Sztuczna inteligencja
Jan Kazimirski
48
Przykład 12
?- [] = [H|T].
false.
?- [a] = [H|T].
H = a,
T = [].
?- [a,b,c] = [H|T].
H = a,
T = [b, c].
?- [[a,b],c] = [H|T].
H = [a, b],
T = [c].
?- [a,[b,c]] = [H|T].
H = a,
T = [[b, c]].
?- [a,b,c] = [H1,H2|T].
H1 = a,
H2 = b,
T = [c].
?- [[1,2,3],4] = [[H1|T1]|T2].
H1 = 1,
T1 = [2, 3],
T2 = [4].
Sztuczna inteligencja
Jan Kazimirski
49
Listy i rekurencja
●
Listy są praktycznie głównym elementem
PROLOG-u (w sensie wykorzystania)
●
Efektywne korzystanie z list wymaga specjalnego
podejścia do ich przetwarzania – rekurencji.
●
Połączenie list i rekurencji pozwala na efektywne
i eleganckie rozwiązywanie w PROLOG-u bardzo
złożonych problemów
Sztuczna inteligencja
Jan Kazimirski
50
Listy i rekurencja – przykład 1
●
Problem: Chcemy stworzyć predykat isList(X)
sprawdzający czy dany term jest listą
●
Rozwiązanie:
–
Lista pusta jest listą. A więc:
isList([]).
–
Każda inna lista da się rozłożyć na głowę i ogon
będący listą.
isList([H|T]) :- isList(T).
Sztuczna inteligencja
Jan Kazimirski
51
Listy i rekurencja – przykład 2
●
Problem: Predykat isMember(X,Y) sprawdzający
czy X jest elementem listy Y.
●
Rozwiązanie:
–
X należy do listy jeżeli jest jej głową
isMember(X,[X|_]).
–
Jeżeli X nie jest głową listy to może należeć do jej
ogona
isMember(X,[_,Y]) :- isMember(X,Y).
Sztuczna inteligencja
Jan Kazimirski
52
Odcięcie
●
Szukając rozwiązań PROLOG stosuje
nawracanie
●
Aby uniknąć nawracania można użyć w regule
tzw. odcięcia
●
Odcięcie oznacza się symbolem !
Sztuczna inteligencja
Jan Kazimirski
53
Odcięcie c.d.
●
Przykład reguły z odcięciem:
a(X) :- b(X),
!
, c(X).
b(d).
b(e).
b(f).
c(e).
●
Zapytanie
?- a(X).
da odpowiedź
false
●
Bez odcięcia rezultatem byłoby
X = e
Sztuczna inteligencja
Jan Kazimirski
54
Wejście/wyjście
●
Wbudowane predykaty PROLOG-u pozwalają na
bardziej rozbudowaną komunikację z
użytkownikiem.
●
Predykat wbudowany
read
pozwala na
wczytywanie termów ze standardowego wejścia
●
Predykat wbudowany
write
– wypisywanie
termów na standardowe wyjście
Sztuczna inteligencja
Jan Kazimirski
55
Czytanie termów
●
Do czytania termów można użyć predykatu read
●
Wpisywany term należy zakończyć znakiem
kropki
●
Predykat read uzgadnia zmienną tylko raz.
●
Nawracania w przypadku read można wymusić
predykatem repeat.
Sztuczna inteligencja
Jan Kazimirski
56
Przykład 12
prog9.pl
a(1,b).
a(1,c).
a(2,d).
a(2,e).
e(X) :- read(Y),a(Y,X).
?- consult(prog9).
% prog9 compiled 0.00 sec, 1,236 bytes
true.
?- e(X).
|:
1.
X = b ;
X = c.
?-
Sztuczna inteligencja
Jan Kazimirski
57
Przykład 13
prog10.pl
a(1,b).
a(1,c).
a(2,d).
a(2,e).
e(X) :- repeat,read(Y),a(Y,X).
?- consult(prog10).
% prog10 compiled 0.00 sec, 1,316 bytes
true.
?- e(X).
|:
1.
X = b ;
X = c ;
|:
2.
X = d ;
X = e ;
|: |
Sztuczna inteligencja
Jan Kazimirski
58
Pisanie termów
●
Do pisania termów służy predykat write
●
W predykacie write zmienna uzgadniana jest
tylko raz
●
Predykat nl służy do wypisywania znaku nowej
linii
Sztuczna inteligencja
Jan Kazimirski
59
Przykład 14
prog11.pl
kwadrat :- read(X), licz(X).
licz(stop) :- !.
licz(X) :- C is X * X,
write(C),kwadrat.
?- consult(prog11).
% prog11 compiled 0.00 sec, 492 bytes
true.
?- kwadrat.
|:
3.
9
|:
5.
25
|:
stop.
true.
?-
Sztuczna inteligencja
Jan Kazimirski
60
Reguły bez głowy
●
Reguła bez głowy pozwala na definiowanie
obiektu na etapie kompilacji
●
Przykład:
:- write('Witaj!').
●
Rezultat kompilacji:
?- consult(prog12).
Witaj!
% prog12 compiled 0.00 sec, 404 bytes
true.
?-
Sztuczna inteligencja
Jan Kazimirski
61
Przykład 15 - silnia
prog13.pl
silnia(0,F) :- F is 1.
silnia(N1,F1) :- N1>0,
N2 is N1-1,
silnia(N2,F2),
F1 is N1*F2.
?- consult(prog13).
% prog13 compiled 0.00 sec, 832 bytes
true.
?- silnia(5,X).
X = 120 ;
false.
?- silnia(10,X).
X = 3628800 ;
false.
?- silnia(3,X).
X = 6 ;
false.
Sztuczna inteligencja
Jan Kazimirski
62
Przykład 16 - Fibonacci
prog14.pl
fib(0,F) :- F is 1.
fib(1,F) :- F is 1.
fib(N,F):- N>1,
N1 is N-1,
N2 is N-2,
fib(N1,F1),
fib(N2,F2),
F is (F1 + F2).
?- consult(prog14).
% prog14 compiled 0.00 sec, 968 bytes
true.
?- fib(2,X).
X = 2
?- fib(3,X).
X = 3 .
?- fib(4,X).
X = 5 .
?- fib(5,X).
X = 8 .
Sztuczna inteligencja
Jan Kazimirski
63
Przykład 17 – Bubble sort
prog15.pl
bSort(List,Sorted) :-
swap(List,List1),
!,
bSort(List1,Sorted).
bSort(Sorted,Sorted).
swap([X,Y|Rest],[Y,X|Rest]) :-
X > Y.
swap([Z|Rest],[Z|Rest1]) :-
swap(Rest,Rest1).
?- consult(prog15).
% prog15 compiled 0.00 sec, 1,072 bytes
true.
?- bSort([1,8,4,7,2,3],Sorted).
Sorted = [1, 2, 3, 4, 7, 8].
?-