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

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

Thêm vào BST

Báo xấu

79
lượt xem 15
download

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

Ưu điểm và nhược điểm của biểu diễn tri thức bằng luật: Ưu điểm : biểu diễn tri thức bằng luật đặc biệt hữu hiệu trong những tình huống hệ thống cần đưa ra những hành động dựa vào những sự kiện có thể quan sát được. Nó có những ưu điểm chính yếu sau đây:

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 10

N u A  V Trái(r) thì Lo i A ra kh i v ph i c a R. N u V Ph i(r) r ng thì lo i b r ra kh i h lu t d n : R = R – {r} B2 : Phân rã các lu t V i m i lu t r : X1  X2  …  Xn  Y trong R V im iit 1 n n R := R + { Xi  Y } R := R – {r} B3 : Lo i b lu t th a V i m i lu t r thu c R N u V Ph i(r)  Bao óng(V Trái(r), R-{r}) thì R := R – {r} B4 : Rút g n v trái V i m i lu t d n r : X : A1  A2, …, An  Y thu c R V im is ki n Ai thu c r G i lu t r1 : X – Ai  Y S = ( R – {r} )  {r1} N u Bao óng( X – Ai , S)  Bao óng(X, R) thì lo i s ki n A ra kh i X VIII.4. Ưu i m và như c i m c a bi u di n tri th c b ng lu t Ưu i m Bi u di n tri th c b ng lu t c bi t h u hi u trong nh ng tình hu ng h th ng c n ưa ra nh ng hành ng d a vào nh ng s ki n có th quan sát ư c. Nó có nh ng ưu i m chính y u sau ây : Các lu t r t d hi u nên có th d dàng dùng trao i v i ngư i dùng (vì nó là m t trong nh ng d ng t nhiên c a ngôn ng ). Có th d dàng xây d ng ư c cơ ch suy lu n và gi i thích t các lu t. Vi c hi u ch nh và b o trì h th ng là tương i d dàng. Có th c i ti n d dàng tích h p các lu t m . Các lu t thư ng ít ph thu c vào nhau. 64 Sưu t m b i: www.daihoc.com.vn
Như c i m Các tri th c ph c t p ôi lúc òi h i quá nhi u (hàng ngàn) lu t sinh. i u này s làm n y sinh nhi u v n liên quan nt c l n qu n tr h th ng. Th ng kê cho th y, ngư i xây d ng h th ng trí tu nhân t o thích s d ng lu t sinh hơn t t c phương pháp khác (d hi u, d cài t) nên h thư ng tìm m i cách bi u di n tri th c b ng lu t sinh cho dù có phương pháp khác thích h p hơn! ây là như c i m mang tính ch quan c a con ngư i. Cơ s tri th c lu t sinh l n s làm gi i h n kh năng tìm ki m c a chương trình i u khi n. Nhi u h th ng g p khó khăn trong vi c ánh giá các h d a trên lu t sinh cũng như g p khó khăn khi suy lu n trên lu t sinh. X. BI U DI N TRI TH C S D NG M NG NG NGHĨA X.1. Khái ni m M ng ng nghĩa là m t phương pháp bi u di n tri th c u tiên và cũng là phương pháp d hi u nh t i v i chúng ta. Phương pháp này s bi u di n tri th c dư i d ng m t th , trong ó nh là các i tư ng (khái ni m) còn các cung cho bi t m i quan h gi a các i tư ng (khái ni m) này. Ch ng h n : gi a các khái ni m chích chòe, chim, hót, cánh, t có m t s m i quan h như sau : Chích chòe là m t loài chim. Chim bi t hót Chim có cánh Chim s ng trong t Các m i quan h này s ư c bi u di n tr c quan b ng m t th như sau : 65 Sưu t m b i: www.daihoc.com.vn
Do m ng ng nghĩa là m t lo i th cho nên nó th a hư ng ư c t t c nh ng m t m nh c a công c này. Nghĩa là ta có th dùng nh ng thu t toán c a th trên m ng ng nghĩa như thu t toán tìm liên thông, tìm ư ng i ng n nh t,… th c hi n các cơ ch suy lu n. i m c bi t c a m ng ng nghĩa so v i th thông thư ng chính là vi c gán m t ý nghĩa (có, làm, là, bi t, ...) cho các cung. Trong th tiêu chu n, vi c có m t cung n i gi a hai nh ch cho bi t có s liên h gi a hai nh ó và t t c các cung trong th u bi u di n cho cùng m t lo i liên h . Trong m ng ng nghĩa, cung n i gi a hai nh còn cho bi t gi a hai khái ni m tương ng có s liên h như th nào. Vi c gán ng nghĩa vào các cung c a th ã giúp gi m b t ư c s lư ng th c n ph i dùng bi u di n các m i liên h gi a các khái ni m. Ch ng h n như trong ví d trên, n u s d ng th thông thư ng, ta ph i dùng n 4 lo i th cho 4 m i liên h : m t th bi u di n m i liên h "là", m t th cho m i liên h "làm", m t cho "bi t" và m t cho "có". M t i m khá thú v c a m ng ng nghĩa là tính k th a. B i vì ngay t trong khái ni m, m ng ng nghĩa ã hàm ý s phân c p (như các m i liên h "là") nên có nhi u nh trong m ng m c nhiên s có nh ng thu c tính c a nh ng nh khác. Ch ng h n theo m ng ng nghĩa trên, ta có th d dàng tr l i "có" cho câu h i : "Chích chòe có làm t không?". Ta có th kh ng nh ư c i u này vì nh "chích chòe" có liên k t "là" v i nh "chim" và nh "chim" l i liên k t "bi t" v i nh "làm t " nên suy ra nh "chích chòe" cũng có liên k t lo i "bi t" v i nh "làm t ". (N u ý, b n s nh n ra ư c ki u "suy lu n" mà ta v a th c hi n b t ngu n t thu t toán "loang" hay "tìm liên thông" trên th !). Chính c tính k th a c a m ng ng nghĩa ã cho phép ta có th th c hi n ư c r t nhi u phép suy di n t nh ng thông tin s n có trên m ng. Tuy m ng ng nghĩa là m t ki u bi u di n tr c quan i v i con ngư i nhưng khi ưa vào máy tính, các i tư ng và m i liên h gi a chúng thư ng ư c bi u di n dư i d ng nh ng phát bi u ng t (như v t ). Hơn n a, các thao tác tìm ki m trên m ng ng nghĩa thư ng khó khăn ( c bi t i v i nh ng m ng có kích thư c l n). Do ó, mô hình m ng ng nghĩa ư c dùng ch y u phân tích v n . Sau ó, nó s ư c chuy n i sang d ng lu t ho c frame thi hành ho c m ng ng nghĩa s ư c dùng k t h p v i m t s phương pháp bi u di n khác. 66 Sưu t m b i: www.daihoc.com.vn
X.2. Ưu i m và như c i m c a m ng ng nghĩa Ưu i m M ng ng nghĩa r t linh ng, ta có th d dàng thêm vào m ng các nh ho c cung m i b sung các tri th c c n thi t. M ng ng nghĩa có tính tr c quan cao nên r t d hi u. M ng ng nghĩa cho phép các nh có th th a k các tính ch t t các nh khác thông qua các cung lo i "là", t ó, có th t o ra các liên k t "ng m" gi a nh ng nh không có liên k t tr c ti p v i nhau. M ng ng nghĩa ho t ng khá t nhiên theo cách th c con ngư i ghi nh n thông tin. Như c i m Cho n nay, v n chưa có m t chu n nào quy nh các gi i h n cho các nh và cung c a m ng. Nghĩa là b n có th gán ghép b t kỳ khái ni m nào cho nh ho c cung! Tính th a k (v n là m t ưu i m) trên m ng s có th d n n nguy cơ mâu thu n trong tri th c. Ch ng h n, n u b sung thêm nút "Gà" vào m ng như hình sau thì ta có th k t lu n r ng "Gà" bi t "bay"!. S dĩ có i u này là vì có s không rõ ràng trong ng nghĩa gán cho m t nút c a m ng. B n c có th ph n i quan i m vì cho r ng, vi c sinh ra mâu thu n là do ta thi t k m ng d ch không ph i do khuy t i m c a m ng!. Tuy nhiên, xin lưu ý r ng, tính th a k sinh ra r t nhi u m i liên "ng m" nên kh năng n y sinh ra m t m i liên h không h p l là r t l n! H u như không th bi n di n các tri th c d ng th t c b ng m ng ng nghĩa vì các khái ni m v th i gian và trình t không ư c th hi n tư ng minh trên m ng ng nghĩa. X.3. M t ví d tiêu bi u Dù là m t phương pháp tương i cũ và có nh ng y u i m nhưng m ng ng nghĩav n có nh ng ng d ng vô cùng c áo. Hai lo i ng d ng tiêu bi u c a m ng ng nghĩa là ng d ng x lý ngôn ng t nhiên và ng d ng gi i bài toán t ng. Ví d 1 : Trong ng d ng x lý ngôn ng t nhiên, m ng ng nghĩa có th giúp máy tính phân tích ư c c u trúc c a câu t ó có th ph n nào "hi u" ư c ý nghĩa c a câu. Ch ng h n, câu "Châu ang c m t cu n sách dày và cư i khoái trá" có th ư c bi u di n b ng m t m ng ng nghĩa như sau : 67 Sưu t m b i: www.daihoc.com.vn
Ví d 2 : Gi i bài toán tam giác t ng quát Chúng ta s không i sâu vào ví d 1 vì ây là m t v n quá ph c t p có th trình bày trong cu n sách này. Trong ví d này, chúng ta s kh o sát m t v n ơn gi n hơn nhưng cũng không kém ph n c áo. Khi m i h c l p trình, b n thư ng ư c giáo viên cho nh ng bài t p nh p môn i lo i như "Cho 3 c nh c a tam giác, tính chi u dài các ư ng cao", "Cho góc a, b và c nh AC. Tính chi u dài trung tuy n", ... V i m i bài t p này, vi c b n c n làm là l y gi y bút ra tìm cách tính, sau khi ã xác nh các bư c tính toán, b n chuy n nó thành chương trình. N u có 10 bài, b n ph i làm l i vi c tính toán r i l p trình 10 l n. N u có 100 bài, b n ph i làm 100 l n. Và tin bu n cho b n là s lư ng bài toán thu c lo i này là r t nhi u! B i vì m t tam giác có t t c 22 y u t khác nhau!. Không l m i l n g p m t bài toán m i, b n u ph i l p trình l i? Li u có m t chương trình t ng quát có th t ng gi i ư c t t c (vài ngàn!) nh ng bài toán tam giác thu c lo i này không? Câu tr l i là CÓ ! Và ng c nhiên hơn n a, chương trình này l i khá ơn gi n. Bài toán này s ư c gi i b ng m ng ng nghĩa. Có 22 y u t liên quan n c nh và góc c a tam giác. xác nh m t tam giác hay xây d ng m t 1 tam giác ta c n có 3 y u t trong ó ph i có y u t c nh. Như v y có kho ng C322 -1 (kho ng vài ngàn) cách xây d ng hay xác nh m t tam giác. Theo th ng kê, có kho ng 200 công th c liên quan n c nh và góc 1 tam giác. gi i bài toán này b ng công c m ng ng nghĩa, ta ph i s d ng kho ng 200 nh ch a công th c và kho ng 22 nh ch a các y u t c a tam giác. M ng ng nghĩa cho bài toán này có c u trúc như sau : nh c a th bao g m hai lo i :  nh ch a công th c (ký hi u b ng hình ch nh t)  nh ch a y u t c a tam giác (ký hi u b ng hình tròn) Cung : ch n i t nh hình tròn n nh hình ch nh t cho bi t y u t tam giác xu t hi n trong công th c nào (không có trư ng h p cung n i gi a hai nh hình tròn ho c cung n i gi a hai nh hình ch nh t). * Lưu ý : trong m t công th c liên h gi a n y u t c a tam giác, ta gi nh r ng n u ã bi t giá tr c a n-1 y u t thì s tính ư c giá tr c a y u t còn l i. Ch ng h n như trong công th c t ng 3 góc c a tam giác b ng 1800 thì khi bi t ư c hai góc, ta s tính ư c góc còn l i. 68 Sưu t m b i: www.daihoc.com.vn
Cơ ch suy di n th c hi n theo thu t toán "loang" ơn gi n sau : B1 : Kích ho t nh ng nh hình tròn ã cho ban u (nh ng y u t ã có giá tr ) B2 : L p l i bư c sau cho n khi kích ho t ư c t t c nh ng nh ng v i nh ng y u t c n tính ho c không th kích ho t ư c b t kỳ nh nào n a. N u m t nh hình ch nh t có cung n i v i n nh hình tròn mà n-1 nh hình tròn ã ư c kích ho t thì kích ho t nh hình tròn còn l i (và tính giá tr nh còn l i này thông qua công th c nh hình ch nh t). Gi s ta có m ng ng nghĩa gi i bài toán tam giác như hình sau Ví d : "Cho hai góc  và chi u dài c nh a c a tam giác. Tính chi u dài ư ng cao hC". V i m ng ng nghĩa ã cho trong hình trên. Các bư c thi hành c a thu t toán như sau : B t u: nh ac a th ư c kích ho t. Công th c (1) ư c kích ho t (vìa ư c kích ho t). T công th c (1) tính ư c c nh b. nh b ư c kích ho t. 69 Sưu t m b i: www.daihoc.com.vn
Công th c (4) ư c kích ho t (vì ). T công th c (4) tính ư c góc  Công th c (2) ư c kích ho t (vì 3 nh b ư c kích ho t). T công th c (2) tính ư c c nh c. nh c ư c kích ho t. Công th c (3) ư c kích ho t (vì 3 nh a, b, c ư c kích ho t) . T công th c (3) tính ư c di n tích S. nh S ư c kích ho t. Công th c (5) ư c kích ho t (vì 2 nh S, c ư c kích ho t). T công th c (5) tính ư c hC. nh hC ư c kích ho t. Giá tr hC ã ư c tính. Thu t toán k t thúc. V m t chương trình, ta có th cài t m ng ng nghĩa gi i bài toán tam giác b ng m t m ng hai chi u A trong ó : C t : ng v i công th c. M i c t ng v i m t công th c tam giác khác nhau ( nh hình ch nh t). Dòng : ng v i y u t tam giác. M i dòng ng v i m t y u t tam giác khác nhau ( nh hình tròn). Ph n t A[i, j] = -1 nghĩa là trong công th c ng v i c t j có y u t tam giác ng v i c t i. Ngư c l i A[i,j] = 0. th c hi n thao tác "kích ho t" m t nh hình tròn, ta t giá tr c a toàn dòng ng v i y u t tam giác b ng 1. ki m tra xem m t công th c ã có n-1 y u t hay chưa (nghĩa là ki m tra i u ki n " nh hình ch nh t có cung n i v i n nh hình tròn mà n-1 nh hình tròn ã ư c kích ho t"), ta ch vi c l y hi u gi a t ng s ô có giá tr b ng 1 và t ng s ô có giá tr -1 trên c t ng v i công th c c n ki m tra. N u k t qu b ng n, thì công th c ã có n-1 y u t . Tr l i m ng ng nghĩa ã cho. Quá trình thi hành kích ho t ư c di n ra như sau : M ng bi u di n m ng ng nghĩa ban u (1) (2) (3) (4) (5)  -1 0 0 -1 0  -1 -1 0 -1 0  0 -1 0 -1 0 a -1 0 -1 0 0 b -1 -1 -1 0 0 70 Sưu t m b i: www.daihoc.com.vn