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

Chia sẻ: Dwefershrdth Vrthrtj | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST

Báo xấu

155
lượt xem 55
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Prolog được sử dụng nhiều trong các ứng dụng của trí tuệ nhân tạo và ngôn ngữ học trong khoa học máy tính (đặc biệt là trong ngành xử lý ngôn ngữ tự nhiên vì đây là mục tiêu thiết kế ban đầu của nó).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 8

129 K thu t l p trình Prolog hơn, thay vì s d ng c p ôi cut-fail, ngư i ta s d ng not. Tuy nhiên, phép ph nh not cũng không ph i không gây ra nh ng phi n ph c cho ngư i dùng. Nhi u khi s d ng not không hoàn toàn chính xác v i phép ph nh trong Toán h c. Ch ng h n n u trong chương trình có nh nghĩa quan h man, mà ta ưa ra m t câu h i i lo i như : ?- not( man( marie)). Khi ó, Prolog s tr l i No n u ã có nh nghĩa man( marie), tr l i Yes n u chưa có nh nghĩa như v y. Tuy nhiên, khi tr l i No, không ph i Prolog nói r ng «Marie không ph i là m t ngư i», mà nói r ng «Không tìm th y trong chương trình thông tin ch ng minh Marie là m t ngư i». Khi th c hi n phép not, Prolog không ch ng minh tr c ti p mà tìm cách ch ng minh i u ngư c l i. N u ch ng minh ư c, Prolog suy ra r ng ích not thành công. Cách l p lu n như v y ư c g i là gi thuy t v th gi i khép kín (hypothesis of the enclosed world). Theo gi thuy t này, th gi i khép kín có nghĩa là nh ng gi t n t i ( úng) u n m trong chương trình ho c ư c suy ra t chương trình. Nh ng gì không n m trong chương trình, ho c không th suy ra t chương trình, thì s là không úng (sai), hay i u ph nh là úng. Vì v y, c n chú ý khi s d ng ph nh do thông thư ng, ngư i ta ã không gi thi t r ng th gi i là khép kín. Trong chương trình, do thi u khai báo m nh : man( marie). nên Prolog không ch ng minh ư c r ng Marie là m t ngư i. Sau ây là m t ví d khác s d ng phép ph nh not : r( a). q( b). p( X ) :- not( r( X )). Nu t câu h i : ?- q( X ), p( X ). thì Prolog s tr l i : X=b Yes Nhưng n u t câu h i : ?- p( X ), q( X ). thì Prolog s tr l i : No hi u ư c vì sao cùng m t chương trình nhưng v i hai cách t câu h i khác nhau l i có hai cách tr l i khác nhau, ta c n tìm hi u cách Prolog l p lu n.
L p trình lägich trong Prolog 130 Trong trư ng h p th nh t, bi n X ư c ràng bu c giá tr là b khi th c hi n ích q( X ). Ti p t c th c hi n ích con p( X ), nh ràng bu c X=b, ích not( r( X )) tho mãn vì ích r( b ) không tho mãn, Prolog tr l i Yes. Trái l i trong trư ng h p th hai, do Prolog th c hi n ích con p( X ) trư c nên s th t b i c a not( r( X )), t c r( X ) thành công v i ràng bu c X=a, d n n câu tr l i No. II. S d ng các c u trúc Ki u d li u c u trúc, danh sách, k thu t so kh p, quay lui và nhát c t là nh ng i m m nh trong l p trình Prolog. Chương này s ti p t c trình bày m t s ví d tiêu bi u v : Truy c p thông tin c u trúc t m t cơ s d li u. Mô ph ng m t ôtômat h u h n không ơn nh và máy Turing. L p k ho ch i du l ch Bài toán tám quân h u ng th i, ta cũng trình bày cách Prolog tr u tư ng hoá d li u. II.1. Truy c p thông tin c u trúc t m t cơ s d li u Sau ây là m t ví d cho phép bi u di n và thao tác các d li u c u trúc. T ó, ta cũng hi u cách s d ng Prolog như m t ngôn ng truy v n cơ s d li u. Trong Prolog, m t cơ s ư c bi u di n dư i d ng m t t p h p các s ki n. Ch ng h n, m t cơ s d li u v các gia ình s mô t m i gia ình (family) như m t m nh . M i gia ình s g m ba ph n t l n lư t : ch ng, v (individual) và các con (children). Do các ph n t này thay i tuy theo t ng gia ình, nên các con s ư c bi u di n b i m t danh sách có th nh n ư c m t s lư ng tuỳ ý s con. M i ngư i trong gia ình ư c bi u di n b i b n thành ph n : tên, h , ngày tháng năm sinh và vi c làm. Thành ph n vi c làm có th có giá tr “th t nghi p” (inactive), ho c ch rõ tên cơ quan công tác và thu nh p theo năm. Gi s cơ s d li u ch a m nh u tiên như sau : family( individual( tom, smith, date(7, may, 1960), work(microsoft, 30000) ), individual( ann, smith, date(9, avril, 1962), inactive), [ individual( roze, smith, date(16, june, 1991), inactive), individual( eric, smith, date(23, march, 1993), inactive) ] ).
131 K thu t l p trình Prolog D li u v nh ng gia ình khác ti p t c ư c b sung dư i d ng các m nh tương t . Hình 5.1 dư i ây minh ho cách t ch c cơ s d li u. Prolog là m t ngôn ng r t thích h p cho vi c khôi ph c thông tin : ngư i s d ng có th g i các i tư ng mà không nh t thi t ch rõ t t c các thành ph n. Ngư i s d ng ch c n ch ra c u trúc c a các i tư ng mà h quan tâm m t cách t ơng trưng, không c n ph i ch ra h t. Hình 1.2 minh ho nh ng c u trúc như v y. Ví d , bi u di n nh ng gia ình dòng h Smith, trong Prolog vi t : family( individual( _ , smith, _ , _ ), _ , _ ) family individual individual . tom smith date work ann smith date inactive children . 7 may 1960 microsoft 30000 9 avril 1962 roze smith date inactive children [ ] 16 june 1991 eric smith date inactive Hình II.1. C u trúc cây bi u di n thông tin v m t gia ình (a) family (b) family _ _ . individual _ _ . _ _ bob _ _ . _ (c) family _ [] _ individual . . Firstname Lastname _ _ _ . _ _ _ Hình II.2. tính ch t c u trúc c a các i tư ng Prolog cho phép bi u di n : (a) m t gia ình Smith nào ó ; (b) nh ng gia ình có úng ba con ; (c) nh ng gia ình
L p trình lägich trong Prolog 132 có ít nh t ba con. Riêng trư ng h p (c) còn cho phép bi u di n tên c a ngư i v nh s ràng bu c các bi n Firstname và Lastname. Nh ng d u g ch dư i dòng như ã bi t là các bi n n c danh, ngư i s d n g không c n quan tâm n giá tr c a chúng. M t cách tương t , nh ng gia ình có ba con ư c bi u di n b i : family( _ , _ , [ _ , _ , _ ] ) Ta cũng có th t câu h i tìm nh ng ngư i v trong nh ng gia ình có ít nh t ba con : ?- family( _ , individual( Firstname, Lastname, _ , _ ), [ _ , _ , _ | _ ] ). Nh ng ví d trên ây ch ra r ng ta có th bi u di n các i tư ng b i c u trúc c a chúng mà không c n quan tâm n n i dung, b ng cách b qua nh ng tham i vô nh. Sau ây là m t s m nh ư c ưa thêm vào cơ s d li u các gia ình có th t các câu h i v n tin khác nhau (có th b sung thêm các gia ình m i b i m nh family) : % X là m t ngư i ch ng husban( X ) :- family( X , _ , _ ). % X là m t ngư i v wife( X ) :- family( _, X , _ ). % X là m t ngư i con, chú ý các tên bi n ch hoa chidren( X ) :- family( _, _ , Chidren ), ismember( X, Chidren ). ismember( X, [ X | L ] ). % có th s d ng m nh member c a Prolog ismember( X, [ Y | L ] ) :- ismember( X, L ). % m i thành viên c a gia ình exist( Individual ) :- husban( Individual ) ; wife( Individual ) ; chidren( Individual ). dateofbirth( individual( _ , _, Date , _ ), Date ). salary( individual( _ , _, _ , work( _ , S ) ), S ). % thu nh p c a ngư i lao ng salary( individual( _ , _, _ , inactive ), 0 ). % ngư i không có ngu n thu nh p Bây gi ta có th t các câu h i như sau : 1. Tìm tên h c a nh ng ngư i có m t trong cơ s d li u :
133 K thu t l p trình Prolog ?- exist( individual( Firstname, Lastname, _ , _ ) ). 2. Tìm nh ng ngư i con sinh năm 1991 : ?- chidren( X ), dateofbirth( X, date( _ , _ , 1991 ) ). 3. Tìm nh ng ngư i v có vi c làm : ?- wife( individual( Firstname, Lastname, _ , work( _ , _ ) ) ). 4. Tìm nh ng ngư i không có vi c làm sinh trư c năm 1975 : ?- exist( individual( Firstname, Lastname, date( _ , _ , Year ), inactive ) ), Year < 1975. 5. Tìm nh ng ngư i sinh trư c năm 1975 có thu nh p dư i 10000 : ?- exist( Individual ), dateofbirth( Individual, date( _ , _ , Year ) ), Year < 1975, salary( Individual, Salary ), Salary < 10000. 6. Tìm nh ng gia ình có ít nh t ba con : ?- family( individual( _, Name, _ , _ ), _, [ _, _, _ | _ ] ). tính t ng thu nh p c a m t gia ình, ta có th nh nghĩa m t quan h nh phân cho phép tính t ng các thu nh p c a m t danh sách nh ng ngư i ang có vi c làm d ng : total( List_of_ individual, Sum_of_ salary ) Ta vi t trong Prolog như sau : % danh sách r ng total( [ ], 0 ) total( [ Individual | List ], Sum ) :- % S là thu nh p c a ngư i u tiên salary( Individual, S ), % Remain là thu nh p c a t t c nh ng total( List, Remain ), ngư i còn l i Sum is S + Remain. Như v y, t ng thu nh p c a m t gia ình ư c tính b i câu h i : ?- family( Husban, Wife, Chidren ), total( [ Husban, Wife | Chidren ], Income ). Các phiên b n Prolog u có th tính dài (length) c a m t danh sách (xem m c III chương 1 trư c ây, ta cũng ã tìm cách xây d ng quan h này).
L p trình lägich trong Prolog 134 Bây gi ta có th áp d ng tìm nh ng gia ình có ngu n thu nh p nh hơn 5000 tính theo u ngư i : ?- family( Husban, Wife, Chidren ), total( [ Husban, Wife | Chidren ], Income ) length( [ Husban, Wife | Chidren ], N ), % N là s ngư i trong m t gia ình Income / N < 5000. II.2. Tr u tư ng hoá d li u Tr u tư ng hoá d li u (data abstraction) ư c xem là cách t ch c t nhiên (m t cách có th c p) nh ng thành ph n khác nhau trong cùng nh ng ơn v thông tin, sao cho v m t ý ni m, ngư i s d ng có th hi u ư c c u trúc bên trong. Chương trình ph i d dàng truy c p ư c vào t ng thành ph n d li u. M t cách lý tư ng thì ngư i s d ng không nhìn th y ư c nh ng chi ti t cài t các c u trúc này, ngư i s d ng ch quan tâm n nh ng i tư ng và quan h gi a chúng. V i m c ích ó, Prolog ph i có cách bi u di n thông tin phù h p. tìm hi u cách Prolog gi i quy t, ta quay l i ví d cơ s d li u gia ình trong m c trư c ây. M i gia ình là m t nhóm các thông tin khác nhau v b n ch t, m i ngư i hay m i gia ình ư c x lý như m t i tư ng c l p. Gi thi t r ng m i gia ình ư c bi u di n như Hình II.1. Bây gi ta ti p t c nh nghĩa các quan h có th ti p c n n các thành ph n c a gia ình mà không c n bi t chi ti t. Nh ng quan h này ư c g i là các b ch n (selector), vì chúng ch n nh ng thành ph n nào ó. M i b ch n s có tên là tên thành ph n mà nó ch n ra, và có hai tham i : i tư ng ch a thành ph n ư c ch n và b n thân thành ph n ó : selector_relation( Object, Selected_component ) Sau ây là m t s ví d v các b ch n : husban( family( Husban, _ , _ ), Husban ). wife( family( _ , Wife, _ ), Wife ). chidren( family( _ , _ , ChidrenList ), ChidrenList ). Ta cũng có th nh nghĩa nh ng b ch n ch n ra nh ng ngư i con c bi t như con trư ng, con út và con th N trong gia ình : % ngư i con trư ng eldest( Family, Eldest ) :- chidren(Family, [ Eldest | _ ] ). % ngư i con út cadet( Family, Eldest ) :- chidren( Family, [ Eldest | _ ] ). Ch n ra m t ngư i con b t kỳ nào ó : % ngư i con th N trong gia ình
135 K thu t l p trình Prolog nth_child( N, Family, Chidren ) :- chidren( Family, ChidrenList ), % ph n t th N c a m t danh sách nth_member( N, ChidrenList, Chidren ). T bi u di n c u trúc minh ho trong Hình II.1, sau ây là m t s b ch n nh n tham i là m t thành viên trong gia ình (individual) : lastname( individual( _ , Lastname, _ , _ ), Lastname ). % tên gia ình (h ) firstname( individual( Firstname, _ , Wife, _ ), % tên riêng Firstname ). % ngày sinh born( individual( _ , _ , Date, _ ), Date ). Làm cách nào có th áp d ng các b ch n ? M i khi các b ch n ã ư c nh nghĩa, ta không c n quan tâm n cách bi u di n nh ng thông tin có c u trúc. t o ra và thao tác trên nh ng thông tin c u trúc, ch c n bi t tên các b ch n và s d ng chúng trong chương trình. V i phương pháp này, các bi u di n ph c t p c u trúc d li u s d dàng hơn so v i phương pháp mô t ã xét. Ví d , ngư i s d ng không c n bi t nh ng ngư i con trong gia ình ư c lưu gi trong m t danh sách. Gi s r ng ta mu n hai ngư i con Johan Smith và Eric Smith cùng thu c m t gia ình, và Eric là em th hai c a Johan. Ta có th s d n g b ch n nh nghĩa hai cá th , ư c g i là Individual1 và Individual2, và nh nghĩa gia ình như sau : % Johan Smith lastname( Individual1, smith ), firstname( Individual1, johan ). % Eric Smith lastname( Individual2, smith ), firstname( Individual1, eric ), husban( Family, Individual1 ). nth_child( 2, Family, Individual2 ). Vi c s d ng các b ch n làm thay i d dàng m t chương trình Prolog. Gi s ta mu n thay i d li u c a m t chương trình, ta ch c n nh nghĩa l i các b ch n, ph n còn l i c a chương trình v n ho t ng như cũ.
L p trình lägich trong Prolog 136 II.3. Mô ph ng ôtômat h u h n Ví d sau ây minh ho cách Prolog bi u di n các mô hình toán h c tr u tư ng. II.3.1. Mô ph ng ôtômat h u h n không ơn nh M t o tômat h u h n không ơn nh (Non-deterministic Finite Automaton, vi t t t NFA) là m t máy tr u tư ng có th c m t câu vào (input string) là m t xâu (hay chu i) ký t nào ó và có th quy t nh có th a nh n (accept) hay không th a nh n (rejecting). Ôtômat có m t s h u h n tr ng thái (state) và luôn m t tr ng thái nào ó có th chuy n ti p (transition) qua m t tr ng thái khác sau khi c (th a nh n) m t ký hi u (symbol) hay ký t thu c m t b ng ký t (alphabet hay set of characters) h u h n nào ó. M t xâu ã cho ư c g i là ư c th a nh n b i ôtômat, n u sau khi c h t câu vào, ôtômat rơi vào m t trong các tr ng thái th a nh n. Ngư i ta thư ng bi u di n o tômat h u h n b i m t th nh hư ng mô t các chuy n ti p tr ng thái có th . M i cung nh hư ng c a th ư c g n nhãn là ký t s c. M i nút c a th là m t tr ng thái, trong ó, tr ng thái u (initial state) ư c ánh d u b i >, và các tr ng thái th a nh n (accepted state) ư c ánh d u b i ư ng kép. a a s1 s2 b e b e a s4 s3 Hình II.3. M t o tômat h u h n không ơn nh b n tr ng thái. Hình 5.3 minh ho m t ôtômat h u h n không ơn nh có b n tr ng thái s1, s2, s3 và s4, trong ó, s1 là tr ng thái u và ôtômat ch có m t tr ng thái th a nh n duy nh t là s3. Chú ý ôtômat có hai chuy n ti p n i vòng (chu kỳ) t i tr ng thái s1 (nghĩa là ôtômat không thay i tr ng thái sau khi c xong ho c ký t a, ho c ký t b). M i chuy n ti p c a ôtômat ư c xác nh b i m t quan h gi a tr ng thái hi n hành, ký t s c và tr ng thái s t t i. Chú ý r ng m i chuy n ti p có th không ơn nh. Trong Hình II.3, t tr ng thái s1, sau khi c ký t a, ôtômat có
137 K thu t l p trình Prolog th rơi vào ho c tr ng thái s1, ho c tr ng thái s2. Ta cũng th y m t s cung có nhãn e (câu r ng), tương ng v i “chuy n ti p epsilon”, ký hi u e-chuy n ti p. Nh ng cung này mô t s chuy n ti p “không nhìn th y ư c” c a ôtômat : ôtômat chuy n qua m t tr ng thái m i khác mà không h c m t ký t nào. Nghĩa là ph n câu vào v n không thay i, nhưng ôtômat ã thay i tr ng thái. Ngư i ta nói ôtômat th a nh n câu vào n u t n t i m t dãy các chuy n ti p trong th sao cho : 1. Lúc u, ôtômat tr ng thái u (ví d s1). 2. Ôtômat k t thúc vi c oán nh n câu vào và tr ng thái th a nh n (s3). 3. Các nhãn trên các cung c a con ư ng chuy n ti p t tr ng thái u n tr ng thái th a nh n tương ng v i câu vào là xâu ã c. Trong quá trình oán nh n câu vào, ôtômat quy t nh l a ch n m t trong s các chuy n ti p có th ti p t c. c bi t, ôtômat có th th c hi n hay không th c hi n m t e-chuy n ti p, n u tr ng thái hi n hành cho phép. Ôtômat không th a nh n câu vào n u nó không rơi vào tr ng thái th a nh n dù ã c h t câu vào, ho c không còn kh năng ti p t c chuy n ti p mà câu vào chưa k t thúc, ho c có th b qu n vô h n. Như ã bi t, các ôtômat h u h n không ơn nh tr u tư ng có m t tính ch t thú v : t i m i th i i m, ôtômat có kh năng l a ch n, trong s các chuy n ti p có th , m t chuy n ti p “t t nh t” th a nh n câu vào. Ch ng h n, ôtômat cho Hình II.3 s th a nh n các xâu ab và aabaab, nhưng không th a nh n các xâu abb và abba. M t cáct t ng quát, ôtômat th a nh n m i xâu k t thúc b i ab, nhưng không th a nh n các xâu khác. Trong Prolog, m t ôtômat ư c nh nghĩa b i ba quan h : 1. M t quan h m t ngôi satisfaction cho phép xác nh các tr ng thái th a nh n c a ôtômat. 2. M t quan h ba ngôi trans cho phép xác nh các tr ng thái chuy n ti p, ch ng h n : trans( S1, X, S2 ). có nghĩa là ôtômat chuy n ti p t tr ng thái S1 qua tr ng thái S2 sau khi c ký t X. 3. M t quan h hai ngôi epsilon ch ra phép chuy n ti p r ng t tr ng thái S1 qua tr ng thái S2 : epsilon( S1, S2 ). Ôtômat ã cho Hình II.3 ư c mô t b i các m nh Prolog như sau : satisfaction( s3 ).
L p trình lägich trong Prolog 138 trans( s1, a, s1 ). trans( s1, a, s2 ). trans( s1, b, s1 ). trans( s2, b, s3 ). trans( s3, b, s4 ). epsilon( s2, s4 ). epsilon( s3, s1 ). bi u di n các xâu ký t trong Prolog, ta s s d ng ki u danh sách. Ch ng h n xâu aab ư c bi u di n b i [ a, b, a ]. Xu t phát t m t câu vào, ôtômat v a mô t trên ây s mô ph ng quá trình oán nh n, b ng cách c l n lư t các ph n t c a danh sách, th a nh n hay không th a nh n. Theo nh nghĩa, ôtômat h u h n không ơn nh s th a nh n câu vào n u, xu t phát t tr ng thái u, sau khi c h t câu (x lý h t m i ph n t c a danh sách), ôtômat rơi vào tr ng thái th a nh n. Quan h hai ngôi accept sau ây cho phép mô ph ng quá trình oán nh n m t câu vào t m t tr ng thái ã cho : accept( State, InputString ) Quan h accept là úng n u State là tr ng thái u và InputString là m t câu vào. ký t u tiên ph n còn l i c a câu vào X S S1 (a) câu vào e S S1 (b) Hình II.4. O tômat th a nh n câu vào : (a) c ký t u tiên X ; (b) th c hi n m t e-chuy n ti p. Ba m nh cho phép nh nghĩa quan h này, tương ng v i ba trư ng h p như sau : 1. Xâu r ng [ ] ư c th a nh n t i tr ng thái S n u ôtômat ang t i tr ng thái S và S là m t tr ng thái th a nh n. 2. M t xâu khác r ng ư c th a nh n t i tr ng thái S n u u c ang t i v trí c ký t u tiên c a xâu sau khi c, ôtômat chuy n qua tr n g thái S1 và xu t phát t tr ng thái S1 này, ôtômat th a nh n toàn b ph n còn l i c a câu vào (xem minh ho Hình II.4 (a) ).
139 K thu t l p trình Prolog 3. M t xâu khác r ng ư c th a nh n t i tr ng thái S n u ôtômat có th th c hi n m t e-chuy n ti p t tr ng thái S qua tr ng thái S1 và xu t phát t tr ng thái S1 này, ôtômat th a nh n toàn b ph n còn l i c a câu vào (xem minh ho Hình II.4 (b) ). Ta có th vi t trong Prolog như sau : % th a nh n xâu r ng accept( S, [ ] ) :- satisfaction( S ). % th a nh n sau khi c ký accept( S, [ X | Remainder ] ) :- t u tiên trans( S, X, S1 ), accept( S1, Remainder). accept( S, InputString ) :- % th a nh n b i e-chuy n t i p epsilon( S, S1 ), accept( S1, Remainder). Bây gi , ta có th yêu c u ôtômat nh n bi t xâu aaab b i câu h i sau : ?- accept( s1, [ a, a, a, b ] ). Yes Tuy nhiên, ôtômat không th a nh n xâu abbb : ?- accept( s1, [ a, b, b, b ] ). ERROR: Out of local stack Ta cũng th y r ng các chương trình Prolog thư ng gi i quy t các bài toán t ng quát hơn nh ng gì mà NLT t o ra chúng. Ví d , yêu c u Prolog cho bi t tr ng thái u nào thì xâu ab ư c th a nh n : ?- accept( S, [ a, b ] ). S = s1 Yes Thú v hơn n a, ta có th yêu c u Prolog cho bi t nh ng xâu ba ký t nào thì ư c th a nh n b i ôtômat : ?- accept( s1, [ X1, X2, X3 ] ). X1 = a X2 = a X3 = b Yes N u ta mu n k t qu tr v là m t xâu, ta ch c n t câu h i : ?- InputString = [ _ , _ , _ ], accept( s1, InputString ). InputString = [a, a, b]
L p trình lägich trong Prolog 140 Yes i xa hơn, t i sao ta không th yêu c u Prolog cho bi t nh ng tr ng thái u nào c a ôtômat cho phép nh n bi t nh ng xâu có b y ký t , v.v... ? C n ph i có nh ng thay i trên các quan h satisfaction, trans và epsilon n u ta mu n ôtômat th c hi n nh ng x lý t ng quát hơn. Ôtômat ã cho Hình II.4 hông ch a các n i vòng e-chuy n ti p. Bây gi n u ta thêm m t chuy n ti p : epsilon( s1, s3 ). thì ta ã t o ra m t n i vòng trên xâu r ng e làm r i lo n ch c năng oán nh n c a ôtômat. Lúc này v i câu h i : ?- accept( s1, [ a ] ). s gây ra m t vòng l p qu n vô h n t i tr ng thái s1, trong khi ôtômat c g ng tìm m t con ư ng n tr ng thái th a nh n s3. II.3.2. Mô ph ng ôtômat h u h n ơn nh M t ô tômat h u h n là ơn nh (Deterministic Finite Automaton, vi t t t DFA) n u chuy n ti p c a ôtômat ư c xác nh ơn nh : ôtômat ch có th chuy n qua m t và ch m t tr ng thái ti p theo sau khi c m t ký t và không có các « chuy n ti p epsilon». Thay vì s d ng thu t ng quan h ba ngôi, ngư i ta thư ng s d ng thu t ng hàm chuy n ti p delta d(s, a) = s’ mô t các ho t ng oán nh n câu c a ôtômat ơn nh. DFA ư c vi t trong Prolog như sau : parse(L) :- start(S), trans(S,L). trans(X,[A|B]) :- delta(X,A,Y), % X ---A---> Y write(X), write(' '), write([A|B]), nl, trans(Y,B). trans(X,[]) :- final(X), write(X), write(' '), write([]), nl. DFA sau ây th a nh n ngôn ng (a,b)*ab(a,b)* :
141 K thu t l p trình Prolog start(0). final(2). delta(0,a,1). delta(0,b,0). delta(1,a,1). delta(1,b,2). delta(2,a,2). delta(2,b,2). Sơ bi u di n ôtômat như sau : A a, b b a 0 2 1 b Hình II.5. Ôtômat h u h n ơn nh có ba tr ng thái. Sau ây là m t s ho t ng oán nh n c a ôtômat : ?- parse([b,b,a,a,b,a,b]). 0 [b, b, a, a, b, a, b] 0 [b, a, a, b, a, b] 0 [a, a, b, a, b] 1 [a, b, a, b] 1 [b, a, b] 2 [a, b] 2 [b] 2 [] Yes ?- parse([b,b,a]). 0 [b, b, a] 0 [b, a] 0 [a] No II.4. Ví d : l p k ho ch i du l ch b ng máy bay Trong m c này, ta s xây d ng m t chương trình Prolog cho phép l p k ho ch i du l ch b ng máy bay. D u r ng ơn gi n, nh ng ví d này tr l i ư c nh ng câu h i mang tính th c ti n sau ây : Nh ng ngày nào trong tu n có chuy n bay tr c ti p t Paris i Ljubljana ? •
L p trình lägich trong Prolog 142 Làm cách nào i t Ljubljana n Grenoble ngày th Năm ? • Tôi ph i i du l ch Milan, Ljubljana và Zurich xu t phát t Paris ngày th • Ba và ph i quay v trong ngày th Sáu. Làm sao có th s p x p các chuy n i c a tôi sao cho m i ngày không i máy bay quá m t l n ? Chương trình Prolog ư c d a trên m t cơ s d li u ch a nh ng thông tin v các chuy n bay. M i chuy n bay là m t quan h ba ngôi cho bi t l ch trình bay timetable như sau : timetable( Place1, Place2, Fly_List). Danh sách các chuy n bay có d ng như sau : Departure_hour / Arrival_hour / Fly_Number / Day_List Danh sách các ngày có chuy n bay ho c là m t danh sách các ngày th trong tu n, ho c là m t nguyên t all (cho t t c các ngày). Ch ng h n, sau ây là m t quan h timetable : timetable( paris , grenoble , [ 9:40 / 10:50 / ba4732 / all , 11:40 / 12:50 / ba4752 / all , 18:40 / 19:50 / ba4822 / [ mo , tu , we , th , fr ] ] ). L ch trình bay ư c bi u di n b i các c u trúc hai thành ph n là gi và phút phân cách nhau b i phép toán : (d u hai ch m). Bài toán chính t ra là tìm nh ng l trình chính xác gi a hai thành ph (nơi i và nơi n) và m t ngày nào ó ã cho. l p trình, ta s d ng m t quan h có b n tham i như sau : path( Place1 , Place2 , Day, Path ) trong ó, là m t dãy các chuy n bay tho mãn các tiêu chu n sau : (1) Nơi i là Place1. (2) Nơi n là Place2. (3) T t c nh ng chuy n bay cùng ngày Day trong tu n. (4) T t c nh ng chuy n bay c a l trình Path thu c v quan h timetable. (5) Có th i gian di chuy n gi a các chuy n bay. L trình ư c bi u di n b i m t danh sách các i tư ng như sau : Departure - Arrival : Fly_number : Departure_hour Ta cũng s d ng các v t b tr sau ây :
143 K thu t l p trình Prolog (1) fly( Place1, Place2 , Day , Fly_number , Departure_hour, Arrival_hour ) Có nghĩa là t n t i m t chuy n bay s hi u Fly_number gi a Place1 và Place2 trong ngày Day, tương ng v i ngày i và ngày n ã cho. (2) dephour( Path , Hour ) Gi xu t phát c a l trình Path là Hour. (3) connecting( Hour1, Hour2 ) Có ít nh t 40 phút gi a Hour1và Hour2, cho phép th c hi n vi c di chuy n (n i ti p gi a hai chuy n bay. Vn tìm m t l trình gi a hai thành ph tương t bài toán oán nh n xâu c a m t ôtômat h u h n không ơn nh ã xét trong m c trư c. Nh ng i m chung là : Các tr ng thái c a ôtômat tương ng v i các thành ph . • M t chuy n ti p gi a hai tr ng thái tương ng v i các chuy n bay gi a hai • thành ph . Quan h trans c a ôtômat tương ng v i quan h timetable. • mô ph ng quá trình oán nh n câu, ôtômat tìm ư c m t l trình gi a • tr ng thái u và m t tr ng thái th a nh n. Còn mô ph ng vi c l p k ho ch i du l ch, chương trình tìm ư c m t l ch trình bay gi a thành ph xu t phát và thành ph n. Chính vì v y, ta có th nh nghĩa m t quan h v l trình path tương t v i quan h accept, ch có khác là quan h path không ch a chuy n ti p r ng. X y ra hai trư ng h p như sau : N u có m t chuy n bay tr c ti p gi a P1 và P2 thì l trình ư c rút (1) g n thành : path( P1 , P2 , Day, [ P1 - P2 : FlyNum : DepH ] ) :- fly( P1 , P2 , Day , FlyNum , Dep , Arr ). N u không có m t chuy n bay tr c ti p gi a P1 và P2 thì l trình s (2) ph i bao g m m t chuy n bay gi a P1 và m t thành ph trung gian P3, r i m t chuy n bay gi a P3 và P2. Lúc này c n có th i gian di chuy n gi a hai chuy n bay, t nơi n c a chuy n bay th nh t n nơi xu t phát c a chuy n bay th hai : path( P1 , P2 , Day , [ P1 - P3 : FlyNum : Dep1 | Path ] ) :- path( P3 , P2 , Day , Path ),
L p trình lägich trong Prolog 144 fly( P1 , P3 , Day , FlyNum1 , Dep1 , Arr1 ), dephour( Path , Dep2 ) , connecting( Arr1 , Dep2 ). Các quan h fly, connecting và dephour ư c xây d ng tương i d dàng. Dư i ây là chương trình y bao g m cơ s d li u v l ch trình bay. Ví d này ơn gi n, không x y ra trư ng h p có l trình vô ích, nghĩa là m t l trình không d n n âu. Ta cũng th y r ng cơ s d li u v l ch trình bay còn nh . có th qu n lý m t cơ s d li u l n hơn, nh t thi t ph i s d ng m t chương trình l p k ho ch thông minh hơn. % Chương trình l p k ho ch i du l ch :- op( 50 , xfy , : ). fly( Place1, Place2 , Day , FlyNum , DepH , ArrH ) :- timetable( Place1 , Place2 , FlyList ) , ismember( DepH / ArrH / FlyNum / DayList , FlyList ) , flyday( Day , DayList ). ismember( X , [ X | L ] ). ismember( X , [ Y | L ] ) :- ismember( X , L ). flyday( Day , DayList ) :- ismember( Day , DayList ). flyday( Day , all ) :- ismember( Day , [ mo , tu , we , th , fr , sa , su ] ). % Chuy n bay tr c ti p path( P1 , P2 , Day, [ P1 - P2 : FlyNum : DepH ] ) :- fly( P1 , P2 , Day , FlyNum , DepH , _ ). % Chuy n bay không tr c ti p path( P1 , P2 , Day , [ P1 - P3 : FlyNum : Dep1 | Path ] ) :- path( P3 , P2 , Day , Path ), fly( P1 , P3 , Day , FlyNum1 , Dep1 , Arr1 ), dephour( Path , Dep2 ) , connecting( Arr1 , Dep2 ). dephour( [ P1 - P2 : FlyNum : Dep | _ ] , Dep ). connecting( Hour1 : Mins1 , Hour2 : Mins2 ) :- 60 *( Hour2 - Hour1 ) + Mins2 - Mins1 >= 40. % M t cơ s d li u v l ch trình các chuy n bay timetable( grenoble , paris , [ 9 :40 / 10:50 / ba4733 / all , 13 :40 / 14:50 / ba4773 / all , 19:40 / 20:50 / ba4833 / [ mo , tu , we , th , fr , su ] ] ). timetable( paris , grenoble , [ 9:40 / 10:50 / ba4732 / all ,
145 K thu t l p trình Prolog 11:40 / 12:50 / ba4752 / all , 18:40 / 19:50 / ba4822 / [ mo , tu , we , th , fr ] ] ). timetable( paris , ljubljana , [ 13:20 / 16:20 / ju201 / [ fr ] , 13:20 / 16:20 / ju213 / [ su ] ] ). timetable( paris , zurich , [ 9:10 / 11:45 / ba614 / all , 14:45 / 17:20 / sr805 / all ] ). timetable( paris , milan , [ 8:30 / 11:20 / ba510 / all , 11:00 / 13:50 / az459 / all ] ). timetable( ljubljana , zurich , [ 11:30 / 12:40 / ju322 / [ tu , fr ] ] ). timetable( ljubljana , paris , [ 11:10 / 12:20 / yu200 / [ fr ] , 11:25 / 12:20 / yu212 / [ su ] ] ). timetable( milan , paris , [ 9:10 / 10 :00 / az458 / all , 12:20 / 13:10 / ba511 / all ] ). timetable( milan , zurich , [ 9:25 / 10:15 / sr621 / all , 12:45 / 13:35 / sr623 / all ] ). timetable( zurich , ljubljana , [ 13:30 / 14:40 / yu323 / [ tu , th ] ] ). timetable( zurich , paris , [ 9:00 / 9:40 / ba613 / [ mo , tu , we, th, fr, sa ], 16:10 /16:55 / sr806 / [ mo , tu , we, th, fr, su ] ] ). timetable( zurich , milan , [ 7:55 / 8:45 / sr620 / all ] ). Sau ây là m t s câu h i trên cơ s d li u v l ch trình hàng không : • Nh ng ngày nào trong tu n có m t chuy n bay tr c ti p gi a Paris và Ljubljana ? ?- fly( paris , ljubljana , Day , _ , _ , _ ). Day = fr; Day = su; No Làm cách nào có th i t Ljubljana n Grenoble ngày th năm ? • ?- path( ljubljana , grenoble , th, C ). C = [ ljubljana-paris:yu200:11:10, paris- grenoble:ba4822:18:40 ] ; C = [ ljubljana-paris:yu212:11:25, paris-
L p trình lägich trong Prolog 146 grenoble:ba4822:18:40 ] ; C = [ ljubljana-zurich:ju322:11:30, zurich- paris:sr806:16:10, paris-grenoble:ba4822:18:40 ] Làm cách nào xu t phát t Paris, có th du l ch Milan, Ljubljana và • Zurich trong ngày th Ba, tr v trong ngày th Sáu, sao cho m i ngày ch th c hi n không quá m t chuy n bay ? ây là m t câu h i tương i l ng c ng. tr l i, ta c n s d ng quan h permutation ã trình bày trong chương 1, m c 3. Quan h này cho phép hoán v t t c các thành ph Milan, Ljubljana và Zurich sao cho t n t i nh ng chuy n bay thích h p m i ngày : ?- permutation( [ milan , ljubljana , zurich ] , [ V1, V2, V3 ] ), fly( paris, V1, tu, FN1, Dep1, Arr1 ), fly( V1, V2, tu, FN2, Dep2, Arr2 ), fly( V2, V3, tu, FN3, Dep3, Arr3 ), fly( V3, paris, fr, FN4, Dep4, Arr4 ). -> V1 = milan K t qu -> V1 = ljubljana V2 = zurich V2 = zurich V3 = ljubljana V3 = milan FN1 = ba510 FN1 = ju213 Dep1 = 8:30 Dep1 = 13:20 Arr1 = 11:20 Arr1 = 16:20 FN2 = sr621 FN2 = ju322 Dep2 = 9:25 Dep2 = 11:30 Arr2 = 10:15 Arr2 = 12:40 FN3 = yu323 FN3 = sr620 Dep3 = 13:30 Dep3 = 7:55 Arr3 = 14:40 Arr3 = 8:45 FN4 = yu200 FN4 = az458 Dep4 = 11:10 Dep4 = 9:10 Arr4 = 12:20 Arr4 = 10:0 ; II.5. Bài toán tám quân h u Bài toán tám quân h u do Call Friedrich Gauss ưa ra vào năm 1850 nhưng không có l i gi i hoàn toàn theo phương pháp gi i tích. Sau ó bài toán này ư c nhi u ngư i gi i tr n v n trên MT T, theo nhi u cách khác nhau. Bài toán phát bi u như sau : Hãy tìm cách t tám quân h u lên m t bàn c vua (có 8 x 8 ô, lúc u không ch a quân nào) sao cho không có quân nào ăn ư c quân nào ? M t quân h u có th ăn ư c b t c quân nào n m trên cùng c t, hay cùng hàng, hay cùng ư n g chéo thu n, hay cùng ư ng chéo ngh ch v i nó. Niclaus Wirth trình bày phương pháp th -sai (trial-and-error) như sau :
147 K thu t l p trình Prolog t m t quân h u vào c t 1 (trên m t hàng tuỳ ý); − t ti p m t quân h u th hai sao cho 2 quân không ăn nhau; − − Ti p t c t quân th 3, v.v... Hình II.6. M t l i gi i c a bài toán tám quân h u L i gi i có d ng m t vòng l p theo gi ng Pascal như sau : Xét-c t- u ; repeat Th _c t ; if An_toàn then begin t_quân_h u_vào ; Xét_c t_k _ti p; end else Quay_l i ; until ã_xong_v i_c t_cu i or ã_quay_l i_quá_c t_ u ; V i Prolog, chương trình s có d ng m t v t : solution( Pos ) V t này ch tho mãn khi và ch khi Pos bi u di n m t cách b trí tám quân h u sao cho không có quân nào ăn ư c quân nào. Sau ây ta s trình bày ba cách ti p c n l p trình Prolog d a trên các cách bi u di n khác nhau. II.5.1. S d ng danh sách to theo hàng và c t Ta c n tìm cách bi u di n các v trí trên bàn c . Gi i pháp tr c ti p nh t là s d ng m t danh sách tám ph n t mà m i ph n t tương ng v i ô t quân h u. M i ph n t là m t c p s nguyên gi a 1 và 8 ch to c a quân h u : X/Y