Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 4

Prolog rất thích hợp để giải quyết các bài toán liên quan tới các đối tượng và mối quan hệ giữa chúng. Prolog được ứng dụng chủ yếu trong lĩnh vực trí tuệ nhân tạo như công nghệ xử lý tri thức, hệ chuyên gia, máy móc, xử lý ngông ngữ, trò chơi
Nội dung trích xuất từ tài liệu:
Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 450 L p trình lôgic trong PrologIII.3. Sp t th t các m nh và các íchIII.3.1. Nguy cơ g p các vòng l p vô h n 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àntoàn úng n. Tuy nhiên, v m t th t c, m nh không dùng làm gì. TrongProlog, m nh này gây ra r c 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 ư cthay th b i p, và c th ti p t c. Prolog b rơi vào tình tr ng qu n 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í dcon kh và qu chu i trên ây, ta có th thay i th t các ích bên trong c a cácm nh . Ch ng h n các m nh thu c v quan h displacement ã ư c s px p như sau : grab, climbing, pushing, walking (ta có th b sung thêm m nh descending n u mu n tr n v n). Các m nh này nói r ng con kh có th n m l y qu chu i (grab), trèo lênh p (climbing), v.v... V m t ng nghĩa th t c, th t các m nh nói r ngtrư c con kh v i l y ư c qu chu i, nó ph i trèo lên h p, trư c khi trèo lênh p, nó ph i y cái h p, v.v... V i th t này, con kh l y ư c qu chu i (gi iquy t ư c bài toán). Bây gi n u ta thay i th t thì i u gì s x y ra ? Githi 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ư cũ (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 : 51Ng nghĩa c a chương trình Prolog (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 iclimbing 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, trcác bi n P2’, P2’’ và P2’’’. Như ta ã th y, s thành công c a m t íchkhô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 danhsá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 kh 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 ngtì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, d u 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 cũng hay g p nh ng vòng l p qu n vô h ntrong 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ácngôn ng l p trình khác là chương trình Prolog úng n v m t ng nghĩa khaibáo, nhưng l i không úng n v m t th t c, nghĩa là không có câu tr l i iv 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ì Prologc g ng ưa ra m t câu tr l i trong khi ang i theo m t con ư ng x u (khôngd n 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 i chương trìnhsao cho có th d phòng trư c nguy cơ b qu n ? Có ph i chúng ta luôn luôn bph thu c vào s s p t th t úng n c a các m nh và các ích ? Rõ ràngr 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 ib các vòng l p vô h n, t ng quát hơn và áng tin c y hơn so v i phương pháps p t th t . Sau ây, chúng ta s s d ng thư ng xuyên nh ng phương phápnà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 .III.3.2. Thay i th t m nh và ích trong chương trình 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 t 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ácchương trình là tương ương, nhưng v m t th t c, chúng s khác nhau. Thamkh 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 i như sau : Th t các m nh trong m t chương trình, và (1) Th t các ích bên trong thân c a các m nh . (2) 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ưsau : o th t các m nh , và (1) o th t các ích cho m i s p t th t các m nh . (2) Hình dư i ...