Lập Trình Logic ProLog: Phần 4 - PGS.TS. PHAN HUY KHÁNH (Hướng Dẫn Chi Tiết)

50 Lp trình lôgic trong Prolog

( <UVM1!$!L!$!)!

( Iy!ơV!$!WVG

Xét mnh ! sau ây :

p :- p

Ngha ca mnh ! là « p úng nu p úng». V! mt khai báo, mnh ! hoàn

toàn úng 6n. Tuy nhiên, v! mt th tc, mnh ! không dùng  làm gì. Trong

Prolog, mnh ! này gây ra r6c ri. Ta xét câu h=i :

?- p.

S dng mnh ! trên, ích p ưc thay th bi chính ích p, r>i li ưc

thay th bi p, và c th tip tc. Prolog b rơi vào tình trng quGn vô hn.

Ví d này làm phương tin thc hin các vòng lp ca Prolog. Tr li ví d

con khD và qu chui trên ây, ta có th thay 1i th t các ích bên trong ca các

mnh !. Ch?ng hn các mnh ! thuc v! quan h displacement ã ưc s6p

xp như sau :

grab, climbing, pushing, walking

(ta có th b1 sung thêm mnh ! descending nu mun trn vFn).

Các mnh ! này nói r*ng con khD có th n6m ly qu chui (grab), trèo lên

hp (climbing), v.v... V! mt ng ngha th tc, th t các mnh ! nói r*ng

trưc con khD vi ly ưc qu chui, nó phi trèo lên hp, trưc khi trèo lên

hp, nó phi Gy cái hp, v.v... Vi th t này, con khD ly ưc qu chui (gii

quyt ưc bài toán). Bây gi nu ta thay 1i th t thì i!u gì s@ xy ra ? Gi

thit r*ng mnh ! walking xut hin u tiên. Lúc này, vic thc hin ích ã

t ra trên ây :

?- couldtake(state(tothedoor, onthefloor, tothewindow,

nothave)).

s@ to ra mt quá trình thc thi khác.

Bn danh sách ích u tiên như cB (các tên bin ưc t li) :

(1) couldtake(state(tothedoor, onthefloor,

tothewindow, nothave))

Sau khi mnh ! th hai ưc áp dng, ta có :

(2) displacement(state(tothedoor, onthefloor,

tothewindow, nothave), M’, S2’),

couldtake(S2’)

Vi chuyn ng walking(tothedoor, P2’), ta nhn ưc :

Ng ngha ca chưng trình Prolog 51

(3) couldtake(state(P2’, onthefloor, tothewindow,

nothave))

Áp dng ln na mnh ! th hai ca couldtake :

(4) displacement(state(P2’, onthefloor, tothewindow,

nothave), M’’, S2’’), couldtake(S2’’)

T thi im này, s khác nhau xut hin. Mnh ! u tiên có phn u có

th so khp vi ích u tiên trên ây bây gi s@ là walking (mà không phi

climbing như trưc).

Ràng buc là S2’’ = state(P2’’, onthefloor, tothewindow,

nothave). Danh sách các ích tr thành :

(5) couldtake(state(P2’’, onthefloor, tothewindow,

nothave))

B*ng cách áp dng mnh ! th hai couldtake, ta nhn ưc

(6) displacement(state(P2’’, onthefloor, tothewindow,

nothave), M’’’, S2’’’), couldtake(S2’’’)

Tip tc áp dng mnh ! walking cho mnh ! th nht và ta có :

(7) couldtake(state(P2’’’, onthefloor, tothewindow,

nothave))

Bây gi ta so sánh các ích (3), (5) và (7). Chúng gn như ging ht nhau, tr

các bin P2’, P2’’ và P2’’’. Như ta ã thy, s thành công ca mt ích

không ph thuc vào tên các bin trong ích. i!u này có ngha r*ng k t danh

sách các ích (3), quá trình thc hin không có s tin trin nào.

Thc t, ta nhn thy r*ng mnh ! th hai ca couldtake và walking ã

ưc s dng qua li. Con khD i loanh quanh trong phòng mà không bao gi có

ý nh s dng cái hp. Do không có s tin trin nào, nên v! mt lý thuyt, quá

trình tìm n qu chui s@ din ra mt cách vô hn. Prolog s@ không x lý nhng

tình hung vô ích như vy.

Ví d này minh ho Prolog ang th gii mt bài toán mà không bao gi t

ưc li gii, dHu r*ng li gii t>n ti. Nhng tình hung như vy không phi là

him khi lp trình Prolog. Ngưi ta cBng hay gp nhng vòng lp quGn vô hn

trong các ngôn ng lp trình khác. Tuy nhiên, i!u không bình thưng so vi các

ngôn ng lp trình khác là chương trình Prolog úng 6n v! mt ng ngha khai

báo, nhưng li không úng 6n v! mt th tc, ngha là không có câu tr li i

vi câu h=i cho trưc.

Trong nhng trưng hp như vy, Prolog không th xoá mt ích vì Prolog

c g6ng ưa ra mt câu tr li trong khi ang i theo mt con ưng xu (không

dHn n thành công).

52 Lp trình lôgic trong Prolog

Câu h=i chúng ta mun t ra là : liu chúng ta có th thay 1i chương trình

sao cho có th d phòng trưc nguy cơ b quGn ? Có phi chúng ta luôn luôn b

ph thuc vào s s6p t th t úng 6n ca các mnh ! và các ích ? Rõ ràng

r*ng các chương trình ln s@ tr nên d sai sót nu phi da trên mt th t nào

ó ca các mnh ! và các ích. T>n ti nhi!u phương pháp khác cho phép loi

b= các vòng lp vô hn, t1ng quát hơn và áng tin cy hơn so vi phương pháp

s6p t th t. Sau ây, chúng ta s@ s dng thưng xuyên nhng phương pháp

này trong vic tìm kim các con ưng, hp gii các bài toán và duyt các > th.

( PayQM1L)!!ươ

 

Ngay các ví d  u chương, ta ã thy nguy c xy ra các vòng lp vô hn.

Chương trình mô t quan h t1 tiên :

ancestor(X, Z) :-

parent(X, Z).

ancestor(X, Z) :-

parent(X, Y),

ancestor(Y, Z).

Ta hãy xét mt s bin th ca chương trình này. V! mt khai báo, tt c các

chương trình là tương ương, nhưng v! mt th tc, chúng s@ khác nhau. Tham

kho ng ngha khai báo ca Prolog, không nh hưng n ngha khai báo, ta có

th thay 1i như sau :

(1) Th t các mnh ! trong mt chương trình, và

(2) Th t các ích bên trong thân ca các mnh !.

Th tc ancestor trên ây g>m hai mnh !, uôi mnh ! th nht có mt

ích con và uôi mnh ! th hai có hai ích con. Như vy chương trình s@ có

bn bin th (=1×2×2) mà c bn !u có cùng ngha khai báo. Ta nhn ưc như

(1) o th t các mnh !, và

(2) o th t các ích cho mAi s6p t th t các mnh !.

Hình dưi ây mô t bn th tc anc1, anc2, anc3, anc4 :

% Th tc gc

anc1(X, Z) :-

parent(X, Z).

anc1 (X, Z) :-

parent(X, Y),

anc1 (Y, Z).

% Bin th a : hoán 1i các mnh !

Ng ngha ca chưng trình Prolog 53

anc2 (X, Z) :-

parent(X, Y),

anc2 (Y, Z).

anc2(X, Z) :-

parent(X, Z).

% Bin th b : hoán 1i các ích ca mnh ! th hai

anc3(X, Z) :-

parent(X, Z).

anc3 (X, Z) :-

anc3 (X, Y),

parent(Y, Z).

% Bin th c : hoán 1i các ích và các mnh !

anc4 (X, Z) :-

anc4 (X, Y),

parent(Y, Z).

anc4(X, Z) :-

parent(X, Z).

% Các câu h=i ưc t ra ln lưt như sau :

?- anc1(tom, sue).

-> Yes

?- anc2(tom, sue).

-> Yes

?- anc3(tom, sue).

-> Yes

?- anc4(tom, sue).

ERR 211 Not enough local stack

54 Lp trình lôgic trong Prolog

Hình III.6. Bin th! a ca quan h t tiên tr li câu h"i

“Tom có phi là mt t tiên ca Sue ?”

Trong trưng hp cui cùng, Prolog không th tìm ra câu tr li. Do b quGn

vô hn nên Prolog thông báo “không  b nh”. Hình 2.4. mô t quá trình thc

hin ca anc1 (trưc ây là ancestor) cho cùng mt câu h=i.

Hình 2.13 (a, b, c) mô t quá trình thc hin ca anc2, anc3 và anc4. Ta

thy anc4 không có hy vng và anc2 kém hiu qu hơn so vi anc1 do thc

hin nhi!u ln tìm kim và quay lui hơn trong cây.

So sánh các quá trình so khp trong các hình v@, ta thy r*ng cn khai báo các

mnh !  ơn gin khi gii các bài toán. i vi bài toán quan h t1 tiên, c

bn bin th !u da trên hai ý :

Y’’ = sue

tht bi

anc2(X, Z)

parent (X, Y),

anc2 (Y, Z),

anc2(X , Z) :-

parent (X, Z).

anc2(tom, sue)

parent (tom, Y’)

anc2(Y’, sue)

Y’ = bill

anc2(bill, sue)

parent (bill, Y’’)

anc2 (Y’’, sue)

parent (bill, sue)

thành công

Y” = ann

anc2(ann, sue)

parent(ann, Y’’’)

anc2(Y’’’, sue)

parent (ann, sue)

parent(jim, Y’’’)

anc2(Y’’’, sue)

anc2(sue, sue)

parent (sue, Y’’’)

anc2(Y’’’, sue)

parent (sue, sue)

t bi

Y’’’ = jim

anc2 (jim, sue)

parent (jim, sue)

t bi

tht bi

Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 4

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi