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

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi