Thuật toán và giải thuật - Hoàng Kiếm Part 8

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

97
lượt xem 21
download

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

Mộ số thuật giải liên quan đến mệnh đề một trong những vấn đề khá quan trọng của logic mệnh đề là chứng minh đúng đắng phép suy diễn . Đây cũng là bài toán chứng minh thường gặp trong toán học

Chủ đề:

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

Lưu

Nội dung Text: Thuật toán và giải thuật - Hoàng Kiếm Part 8

END; END; CONST SO_LUAT = 3; BEGIN WHILE (xz) AND (yz) DO BEGIN FOR i:=1 TO SO_LUAT DO IF DK(L) THEN ThiHanh(L); END; END. o n chương trình chính cũng thi hành b ng cách l n lư t xét qua 3 l nh IF như chương trình u tiên. Tuy nhiên, ây, bi u th c i u ki n ư c thay th b ng hàm DK và các hành ng ng v i i u ki n ã ư c thay th b ng th t c ThiHanh. Tính ch t "m m" hơn c a chương trình này th hi n ch , n u mu n b sung "tri th c", ta ch ph i i u ch nh l i các hàm DK và ThiHanh mà không c n ph i s a l i chương trình chính. Bây gi hãy gi s r ng ta ã có hàm và th t c c bi t sau : FUNCTION GiaTriBool(DK : String) : BOOLEAN; PROCEDURE ThucHien(ThaoTac : String) ; hàm GiaTriBool nh n vào m t chu i i u ki n, nó s phân tích chu i, tính toán r i tr ra giá tr BOOLEAN c a bi u th c này. Ví d : GiaTriBoolean(‘6
END; DSLuat ARRAY [1..SO_LUAT] OF Luat; 9; VAR CacLuat DSLuat; PROCEDURE KhoiDong; BEGIN CacLuat[1].DK := ‘x = Vx’; CacLuat[2].DK := ‘y = 0’; CacLuat[3].DK := ‘y>0’; 9; CacLuat[1].ThaoTac := ‘x:=0’; CacLuat[2].ThaoTac:= ‘y:=Vy’; CacLuat[3].ThaoTac:= ‘k:=min(Vx-x,y), x:=x+k, y:=y-k’; END; BEGIN WHILE (xz) AND (yz) DO BEGIN FOR i:=1 TO SO_LUAT DO IF GiaTriBoolean(CacLuat[i].DK) THEN ThucHien(CacLuat[i].ThaoTac); END; END. Chúng ta t m cho r ng trong quá trình chương trình thi hành, ta có th d dàng thay i s ph n t m ng CacLuat (các ngôn ng l p trình sau này như Visual C++, Delphi u cho phép i u này). V i chương trình này, khi mu n s a i "tri th c", b n ch c n thay i giá tr m ng Luat là xong. Tuy nhiên, ngư i dùng v n g p khó khăn khi mu n b sung ho c hi u ch nh tri th c. H c n ph i nh p các chu i i lo i như ‘x=0’ ho c ‘k:=min(Vx-x,y)’ ...Các chu i này, tuy có ý nghĩa i v i chương trình nhưng v n còn khá xa l i v i ngư i dùng bình thư ng. Chúng ta c n gi m b t "kho ng cách" này l i b ng cách ưa ra nh ng chu i i u ki n ho c thao tác có ý nghĩa tr c ti p i v i ngư i dùng. Chương trình 51 Sưu t m b i: www.daihoc.com.vn
s có chuy n i l i các i u ki n và thao tác này sang d ng phù h p v i chương trình. làm ư c i u trên. Chúng ta c n ph i li t kê ư c các tr ng thái và thao tác cơ b n c a bài toán này. Sau ây là m t s tr ng thái và thao tác cơ b n. Tr ng thái cơ b n : Bình X y, Bình X r ng, Bình X không r ng, Bình X có n lít nư c. Thao tác h t nư c trong bình, y nư c trong bình, nư c t bình A sang bình B cho n khi B y ho c A r ng. Lưu ý r ng ta không th có thao tác " n lít nư c t A sang B" vì bài toán ã gi nh r ng các bình u không có v ch chia, hơn n a n u ta bi t cách n lít nư c t A sang B thì l i gi i bài toán tr thành quá ơn gi n. "Múc y X" " z lít nư c t X sang Y" Vì ây là m t bài toán ơn gi n nên b n có th d nh n th y r ng, các tr ng thái cơ b n và thao tác ch ng có gì khác so v i các i u ki n mà chúng ta ã ưa ra. K ti p, ta s vi t các o n chương trình cho phép ngư i dùng nh p vào các lu t (d ng n u ... thì ...) ư c hình thành t các tr ng thái và i u ki n cơ b n này, ng th i ti n hành chuy n sang d ng máy tính có th x lý ư c như ví d trên. Chúng ta s không bàn n vi c cài t các o n chương trình giao ti p v i ngư i dùng ây. Như v y, so v i chương trình truy n th ng ( ư c c u t o t hai "ch t li u" cơ b n là d li u và thu t toán), chương trình trí tu nhân t o ư c c u t o t hai thành ph n là cơ s tri th c (knowledge base) và ng cơ suy di n (inference engine). Cơ s tri th c : là t p h p các tri th c liên quan nv n mà chương trình quan tâm gi i quy t. ng cơ suy di n : là phương pháp v n d ng tri th c trong cơ s tri th c gi i quy t v n . 52 Sưu t m b i: www.daihoc.com.vn
N u xét theo quan ni m bi u di n tri th c mà ta v a bàn lu n trên thì cơ s tri th c ch là m t d ng d li u c bi t và ng cơ suy di n cũng ch là m t d ng c a thu t toán c bi t mà thôi. Tuy v y, có th nói r ng, cơ s tri th c và ng cơ suy di n là m t bư c ti n hóa m i c a d li u và thu t toán c a chương trình! B n có th hình dung ng cơ suy di n gi ng như m t lo i ng cơ t ng quát, ư c chu n hóa có th dùng v n hành nhi u lo i xe máy khác nhau và cơ s tri th c chính là lo i nhiên li u c bi t v n hành lo i ng cơ này ! Cơ s tri th c cũng g p ph i nh ng v n tương t như nh ng cơ s d li u khác như s trùng l p, th a, mâu thu n. Khi xây d ng cơ s tri th c, ta cũng ph i chú ý n nh ng y u t này. Như v y, bên c nh v n bi u di n tri th c, ta còn ph i ra các phương pháp lo i b nh ng tri th c trùng l p, th a ho c mâu thu n. Nh ng thao tác này s ư c th c hi n trong quá trình ghi nh n tri th c vào h th ng. Chúng ta s c p n nh ng phương pháp này trong ph n tìm hi u v các lu t d n. Hình nh trên tóm t t cho chúng ta th y c u trúc chung nh t c a m t chương trình trí tu nhân t o. B. CÁC PHƯƠNG PHÁP BI U DI N TRI TH C TRÊN MÁY TÍNH V. LOGIC M NH 53 Sưu t m b i: www.daihoc.com.vn
ây có l là ki u bi u di n tri th c ơn gi n nh t và g n gũi nh t i v i chúng ta. M nh là m t kh ng nh, m t phát bi u mà giá tr c a nó ch có th ho c là úng ho c là sai. Ví d : phát bi u "1+1=2" có giá tr úng. phát bi u "M i lo i cá có th s ng trên b " có giá tr sai. Giá tr c a m nh không ch ph thu c vào b n thân m nh ó. Có nh ng m nh mà giá tr c a nó luôn úng ho c sai b t ch p th i gian nhưng cũng có nh ng m nh mà giá tr c a nó l i ph thu c vào th i gian, không gian và nhi u y u t khác quan khác. Ch ng h n như m nh : "Con ngư i không th nh y cao hơn 5m v i chân tr n" là úng khi trái t , còn nh ng hành tinh có l c h p d n y u thì có th sai. Ta ký hi u m nh b ng nh ng ch cái la tinh như a, b, c, ... Có 3 phép n i cơ b n t o ra nh ng m nh m i t nh ng m nh cơ s là phép h i ( ), giao( ) và ph nh ( ) B n c ch n h n ã t ng s d ng logic m nh trong chương trình r t nhi u l n (như trong c u trúc l nh IF ... THEN ... ELSE) bi u di n các tri th c "c ng" trong máy tính ! Bên c nh các thao tác tính ra giá tr các m nh ph c t giá tr nh ng m nh con, chúng ta có ư c m t cơ ch suy di n như sau : Modus Ponens : N u m nh A là úng và m nh A B là úng thì giá tr c a B s là úng. Modus Tollens : N u m nh A B là úng và m nh B là sai thì giá tr c a A s là sai. Các phép toán và suy lu n trên m nh ã ư c c p nhi u n trong các tài li u v toán nên chúng ta s không i vào chi ti t ây. VI. LOGIC V T Bi u di n tri th c b ng m nh g p ph i m t tr ng i cơ b n là ta không th can thi p vào c u trúc c a m t m nh . Hay nói m t cách khác là m nh không có c u trúc . i u này làm h n ch r t nhi u thao tác suy lu n . Do ó, ngư i ta ã ưa vào khái ni m v t và lư ng t ( - v i m i,  - t n t i) tăng cư ng tính c u trúc c a m t m nh . Trong logic v t , m t m nh ư c c u t o b i hai thành ph n là các i tư ng tri th c và m i liên h gi a chúng (g i là v t ). Các m nh s ư c bi u di n dư i d ng : V t (< i tư ng 1>, < i tư ng 2>, …, < i tư ng n>) 54 Sưu t m b i: www.daihoc.com.vn
Như v y bi u di n v c a các trái cây, các m nh s ư c vi t l i thành : Cam có v Ng t  V (Cam, Ng t) Cam có màu Xanh  Màu (Cam, Xanh) ... Ki u bi u di n này có hình th c tương t như hàm trong các ngôn ng l p trình, các i tư ng tri th c chính là các tham s c a hàm, giá tr m nh chính là k t qu c a hàm (thu c ki u BOOLEAN). V i v t , ta có th bi u di n các tri th c dư i d ng các m nh t ng quát, là nh ng m nh mà giá tr c a nó ư c xác nh thông qua các i tư ng tri th c c u t o nên nó. Ch ng h n tri th c : "A là b c a B n u B là anh ho c em c a m t ngư i con c a A" có th ư c bi u di n dư i d ng v t như sau : B (A, B) = T n t i Z sao cho : B (A, Z) và (Anh(Z, B) ho c Anh(B,Z)) Trong trư ng h p này, m nh B (A,B) là m t m nh t ng quát Như v y n u ta có các m nh cơ s là : a) B ("An", "Bình") có giá tr úng (Anh là b c a Bình) b) Anh("Tú", "Bình") có giá tr úng (Tú là anh c a Bình) thì m nh c) B ("An", "Tú") s có giá tr là úng. (An là b c a Tú). Rõ ràng là n u ch s d ng logic m nh thông thư ng thì ta s không th tìm ư c m t m i liên h nào gi a c và a,b b ng các phép n i m nh ,,.T ó, ta cũng không th tính ra ư c giá tr c a m nh c. S dĩ như v y vì ta không th th hi n tư ng minh tri th c "(A là b c a B) n u có Z sao cho (A là b c a Z) và (Z anh ho c em C)" dư i d ng các m nh thông thư ng. Chính c trưng c a v t ã cho phép chúng ta th hi n ư c các tri th c d ng t ng quát như trên. Thêm m t s ví d n a các b n th y rõ hơn kh năng c a v t : Câu cách ngôn "Không có v t gì là l n nh t và không có v t gì là bé nh t!" có th ư c bi u di n dư i d ng v t như sau : L nHơn(x,y) = x>y Nh Hơn(x,y) = x
Câu châm ngôn "G n m c thì en, g n èn thì sáng" ư c hi u là "chơi v i b n x u nào thì ta cũng s thành ngư i x u" có th ư c bi u di n b ng v t như sau : Ngư iX u (x) =  y : B n(x,y) và Ngư iX u(y) Công c v t ã ư c nghiên c u và phát tri n thành m t ngôn ng l p trình c trưng cho trí tu nhân t o. ó là ngôn ng PROLOG. Ph n c thêm c a chương s gi i thi u t ng quan v i các b n v ngôn ng này. VII. M T S THU T GI I LIÊN QUAN N LOGIC M NH M t trong nh ng v n khá quan tr ng c a logic m nh là ch ng minh tính úng n c a phép suy di n (a  b). ây cũng chính là bài toán ch ng minh thư ng g p trong toán h c. Rõ ràng r ng v i hai phép suy lu n cơ b n c a logic m nh (Modus Ponens, Modus Tollens) c ng v i các phép bi n i hình th c, ta cũng có th ch ng minh ư c phép suy di n. Tuy nhiên, thao tác bi n i hình th c là r t khó cài t ư c trên máy tính. Th m chí i u này còn khó khăn v i c con ngư i! V i công c máy tính, b n có th cho r ng ta s d dàng ch ng minh ư c m i bài toán b ng m t phương pháp "thô b o" là l p b ng chân tr . Tuy v lý thuy t, phương pháp l p b ng chân tr luôn cho ư c k t qu cu i cùng nhưng ph c t p c a phương pháp này là quá l n, O(2n) v i n là s bi n m nh . Sau ây chúng ta s nghiên c u hai phương pháp ch ng minh m nh v i ph c t p ch có O(n). VII.1. Thu t gi i Vương H o B1 : Phát bi u l i gi thi t và k t lu n c a v n theo d ng chu n sau : GT1, GT2, ..., GTn  KL1, KL2, ..., KLm Trong ó các GTi và KLi là các m nh ư c xây d ng t các bi n m nh và 3 phép n i cơ b n :  ,  ,  B2 : Chuy n v các GTi và KLi có d ng ph nh. Ví d : p  q,  (r  s),  g, p  r  s,  p  p  q, p  r, p  (r  s), g, s B3 : N u GTi có phép  thì thay th phép  b ng d u "," N u KLi có phép  thì thay th phép  b ng d u "," Ví d : p  q, r  ( p  s)   q,  s 56 Sưu t m b i: www.daihoc.com.vn