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

Cú pháp và ngữ nghĩa của Prolog đơn giản và sáng sủa, nó được người Nhật coi là một trong những nền tảng để xây dựng máy tính thế hệ thứ năm mà ở đó, thay vì phải mô tả cách giải quyết một bài toán trên máy tính, con người chỉ cần mô tả bài toán và máy tính sẽ hỗ trợ họ nốt phần còn lạ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 9 L p trình lägich trong Prolog148 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 • 1 2 3 4 5 6 7 8 Hình II.7. M t l i gi i c a bài toán tám quân h u,bi u di n b i danh sách [ 1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1 ]. ây, phép toán / không ph i là phép chia, mà ch là cách t h p hai toc a m t ô bàn c . Hình 5.6 trên ây là m t l i gi i khác c a bài toán tám quânh u ư c bi u di n dư i d ng m t danh sách như sau : [ 1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1 ] T cách bi u di n danh sách, ta c n tìm l i gi i có d ng : [ X1/Y1, X2/Y2, X3/Y3, ... , X8/Y8 ] Ta c n tìm các giá tr c a các bi n X1, Y1, X2, Y2, X3, Y3, ... , X8, Y8. Docác quân h u ph i n m trên các c t khác nhau không th ăn l n nhau, nên tacó ngay giá tr c a các to X, và l i gi i lúc này có d ng : [ 1/Y1, 2/Y2, 3/Y3, ... , 8/Y8 ] Cho n lúc này, bài toán tám quân h u ch t ra i v i bàn c 8 × 8. Tuynhiên, l i gi i ph i d ki n ư c cho trư ng h p t ng quát khi l p trình. ây,ta s th y r ng chính trư ng h p t ng quát l i ơn gi n hơn bài toán ban u. Bànc 8 × 8 ch là m t trư ng h p riêng. gi i quy t cho trư ng h p t ng quát, ta chuy n kích thư c 8 quân h uthành m t s quân h u b t kỳ nào ó (m i c t m t quân h u), k c s c t b ngkhông. Ta xây d ng quan h solution t hai tình hu ng sau : 1. Danh sách các quân h u là r ng : danh sách r ng cũng là m t l i gi i vì không x y ra s t n công nào. solution( [ ] ). 2. Danh sách các quân h u khác r ng và có d ng như sau : [ X/Y | Others ] 149K thu t l p trình Prolog Trong trư ng h p th hai, quân h u th nh t n m trên ô X/Y, còn nh ng quânh u khác n m trong danh sách Others. N u danh sách này là m t l i gi i, thình ng i u ki n sau ây ph i ư c tho mãn : 1. Nh ng quân h u trong danh sách Others không th t n công l n nhau, i u này nói lên r ng Others cũng là m t l i gi i. 2. V trí X và Y c a nh ng quân h u ph i n m gi a 1 và 8. 3. M t quân h u t i v trí X/Y không th t n công m t quân h u nào khác trong danh sách Others. i v i i u ki n th nh t, quan h solution ph i ư c g i m t cáchquy. i u ki n th hai nói lên r ng Y ph i thu c v danh sách [ 1, 2, 3, 4,5, 6, 7, 8 ]. ây, ta không c n quan tâm n v trí X, vì nó ph i tương h pv i danh sách k t qu tr v như ta ã xác nh ngay t u. Nghĩa là X ph ithu c v nh ng giá tr ã ư c n nh tương ng. Gi s i u ki n th ba ư c gi i quy t nh quan h noattack, chương trìnhProlog cho quan h solution như sau : solution( [ X/Y | Others ] ) :- solution( Others ), member( Y, [ 1, 2, 3, 4, 5, 6, 7, 8 ] ), noattack( X/Y, Others ). Bây gi ta c n tìm quan h noattack. Ta th y : 1. N u danh sách Rlist r ng, khi ó noattack là úng, vì không có quân h u nào t n công quân h u t i X/Y nào ó. noattack( _, [ ] ). 2. N u danh sách Rlist khác r ng, khi ó có d ng [ R1 | Rlist1 ] và hai i u ki n sau ây ph i ư c tho mãn : (a) Quân h u t i ô R không th t n công quân h u t i ô R1, và (b) Quân h u t i ô R không th t n công quân h u nào trong Rlist1. m t quân h u không th t n công quân h u khác, thì chúng không th n mtrên cùng hàng, cùng c t và cùng ư ng chéo chính ho c ph . Ta bi t ch c ch nr ng các quân h u ã n m trên các c t phân bi t nhau do mô hình l i gi i ã n nh. Bây gi ta c n ch ra r ng : • Các to Y c a các quân h u ph i phân bi t nhau, và • Các quân h u không th n m trên cùng ư ng chéo chính ho c ph . nghĩa là kho ng cách gi a các ô trên tr c X ph i khác v i các ô trên tr c Y. L p trình lägich trong Prolog150 noattack( X/Y, [ X1/Y2 | Others ] ) :- Y =\= Y1, Y1 - Y =\= X1 - X, Y1 - Y =\= X - X1, noattack( X/Y, Others ). Dư i ây là chương trình Prolog y th nh t có ch a danh sách l i gi i làquan h model. Mô hình làm cho vi c tìm l i gi i cho bài toán tám quân h u trnên ơn gi n hơn. % chương trình th nh t gi i bài toán tám quân h u % The problem of the eight queens - Program 1 % −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− solution( [ ] ). solution( [ X/Y | Others ] ) :- solution( Others ), ismember( Y, [ 1, 2, 3, 4, 5, 6, 7, 8 ] ), noattack( X/Y, Others ). noattack( _ , [ ] ). noattack( X/Y, [ X1/Y1 | Others ] ) :- Y =\= Y1, Y1 – Y =\= X1 - X, Y1 – Y =\= X - X1, noattack( X/Y, Others ). ismember( X , [ X | L ] ). ismember( X, [ Y | L ] ) :- ismember( X, L ). model( [ 1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8 ] ). ). ?- model( S ), solution( S S = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1] ; S = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1] ; S = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1] ; S = [1/3, 2/6, 3/4, 4/2, 5/8, 6/5, 7/7, 8/1] ; S = [1/5, 2/7, 3/1, 4/3, 5/8, 6/6, 7/4, 8/2] ; S = [1/4, 2/6, 3/8, 4/3, 5/1, 6/7, 7/5, 8/2] Yes S d ng v t not, ta vi t l i chương trình như sau : solution( ...