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

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

Thêm vào BST

Báo xấu

77
lượt xem 11
download

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

Biểu diễn tri thức bằng script Script là một cách biểu diễn tri thức tương tự như frame nhưng mà thay vì đặc tả một đối tượng, nó mô tả một chuỗi các sự kiện. Để mô tả chuỗi sự kiện, script sử dụng một dãy các slot chưa thông tin về cac con người, đối tượng hành động liên quan đến sự kiện đó

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 12

D th y r ng, di n tích ph n tô en chính là hi u gi a di n tích hình vuông và di n tích hình tròn n i ti p. Dĩ nhiên là b n cũng có th vi t m t chương trình bình thư ng tính toán, nhưng khi ã "tích h p" các tri th c v tính di n tích bên trong bi u di n, chương trình c a chúng ta tr nên r t g n nh . B n hãy lưu ý 3 l nh ư c in m trong ví d dư i. L nh u tiên s " c t " l i gi thi t "hình vuông có c nh v i chi u dài x", l nh k ti p c t gi thi t "hình tròn n i ti p", còn l nh th 3 mô t vi c tính di n tích b ng cách l y di n tích hình vuông tr cho di n tích hình tròn. VAR x, s : numeric; k : square; c : circle; BEGIN ; k.b1 := x; c.d := x; s := k.s – c.s; END. Như v y, chương trình máy tính c a chúng ta ã ho t ng khá gi ng như vi c "mô t " các gi i bài toán b ng ngôn ng t nhiên. Hãy nghĩ xa hơn m t tí. Các bài toán hình h c thư ng ư c mô t b ng các ngôn t khá chính xác (ch ng h n như : cho m t tam giác v i chi u cao xu t phát t nh A là 5, chi u dài c nh áy là 6, ....). Do ó, v m t nguyên tác, chúng ta v n có th xây d ng m t chương trình "hi u" nh ng bài này (theo như cách mà chúng ta v a làm). Sau ó, ngư i dùng có th hoàn toàn nh máy tính gi i giúp bài toán cho mình b ng cách mô t l i gi i cho máy tính (ch không c n ph i l p trình). B n có c m giác i u này th t thú v không? ây chính là bư c i u tiên trong vi c t o ra m t chương trình tr giúp cho vi c gi i các bài toán hình h c trên máy tính v i giao ti p b ng ngôn ng t nhiên! tăng thêm s c m nh cho h th ng này, ngư i ta thư ng cài t m t m ng ng nghĩa ngay bên trong m i frame. Ch ng h n, ta có th có m t frame TRIANGLE, trong ó cài t m t m ng ng nghĩa (gi ng như ví d trong ph n m ng ng nghĩa) c t m i liên h gi a các y u t tam giác (thay vì s d ng các công th c liên h ơn gi n như ví d trên). XII. BI U DI N TRI TH C B NG SCRIPT 78 Sưu t m b i: www.daihoc.com.vn
Script là m t cách bi u di n tri th c tương t như frame nhưng thay vì ct m t i tư ng, nó mô t m t chu i các s ki n. mô t chu i s ki n, script s d ng m t dãy các slot ch a thông tin v các con ngư i, i tư ng và hành ng liên quan n s ki n ó. Tuy c u trúc c a các script là r t khác nhau tùy theo bài toán, nhưng nhìn chung m t script thư ng bao g m các thành ph n sau : i u ki n vào (entry condition): mô t nh ng tình hu ng ho c i u ki n c n ư c th a mãn trư c khi các s ki n trong script có th di n ra. Role (di n viên): là nh ng con ngư i có liên quan trong script. Prop (tác t ): là t t c nh ng i tư ng ư c s d ng trong các chu i s ki n s di n ra. Scene(Tình hu ng) : là chu i s ki n th c s di n ra. Result (K t qu ) : tr ng thái c a các Role sau khi script ã thi hành xong. Track (phiên b n) : mô t m t bi n th (ho c trư ng h p c bi t) có th x y ra trong o n script. Sau ây là m t ví d tiêu bi u cho script. Ví d này là m t bi n th c a ví d n i ti ng v nhà hàng bán th c ăn nhanh (các nhà hàng bán gà rán mà ta thư ng g p trong các siêu th !) thư ng ư c s d ng minh h a cách bi u di n tri th c b ng script trong cách sách nói v trí tu nhân t o. i ăn trong m t nhà hàng là m t tình hu ng thư ng g p trong cu c s ng v i nh ng i u ki n vào, di n viên, tác t , hoàn c nh, k t qu khá "chu n". Và qua script ví d , b n s th y phương pháp này có th ư c dùng mô t chính xác nh ng tình hu ng di n ra hàng ngày c a nh ng nhà hàng bán th c ăn nhanh. Các tình hu ng là nh ng o n script con trong o n script chính mô t nh ng tình hu ng nh trong toàn b quá trình. Lưu ý r ng trong o n script này có tình hu ng tùy ch n trong ó mô t vi c khách hàng mua th c ăn v thay vì vào nhà hàng ăn. Script "nhà hàng" Phiên b n : Nhà hàng bán th c ăn nhanh. Di n viên : Khách hàng Ngư i ph c v . Tác t : Bàn ph c v . Ch ng i. Khay ng th c ăn Th c ăn 79 Sưu t m b i: www.daihoc.com.vn
Ti n Các lo i gia v như mu i, tương, t, tiêu, ... i u ki n vào : Khách hàng ói Khách hàng có ti n tr . Tình hu ng 1 : Vào nhà hàng Khách hàng u xe vào bãi u xe. Khách hàng bư c vào nhà hàng. Khách hàng x p hàng trư c bàn ph c v . Khách hàng c th c ơn trên tư ng và quy t nh s kêu món ăn gì. Tình hu ng 2: Kêu món ăn. Khách hàng kêu món ăn v i ngư i ph c v ( ang ng qu y ph c v ) Ngư i ph c v t th c ăn lên khay và ưa hóa ơn tính ti n cho khách. Khách hàng tr ti n cho ngư i ph c v . Tình hu ng 3: Khách hàng dùng món ăn Khách hàng l y thêm các gia v Khách hàng c m khay n m t bàn còn tr ng. Khách hàng ăn th c ăn. Tình hu ng 3A (tùy ch n) : Khách hàng mua th c ăn em v Khách hàng mang th c ăn v nhà. Tình hu ng 4 : Ra v Khách hàng thu d n bàn Khách hàng b rác (th c ăn th a, xương, m ng v n, ...) vào thùng rác. Khách hàng ra kh i nhà hàng. Khách hàng lái xe i. 80 Sưu t m b i: www.daihoc.com.vn
K t qu : Khách hàng không còn ói. Khách hàng còn ít ti n hơn ban u. Khách hàng vui v * Khách hàng b c mình * Khách hàng quá no. * Tùy ch n. Script r t h u d ng trong vi c d oán i u gì s x y n trong nh ng tình hu ng xác nh. Th m chí trong nh ng tình hu ng chưa di n ra, script còn cho phép máy tính d oán ư c vi c gì s x y ra và x y ra i v i ai và vào th i i m nào. N u máy tính kích ho t m t script, ngư i dùng có th t câu h i và h th ng có th suy ra ư c nh ng câu tr l i chính xác mà không c n ngư i dùng cung c p thêm nhi u thông tin (trong m t s trư ng h p có th không c n thêm thông tin). Do ó, cũng gi ng như frame, script là m t d ng bi u di n tri th c tương i h u d ng vì nó cho phép ta mô t chính xác nh ng tình hu ng "chu n" mà con ngư i v n th c hi n m i ngày ho c ã n m b t chính xác. cài t script trong máy tính, b n ph i tìm cách lưu tr các tri th c dư i d ng hình th c. LISP là ngôn ng l p trình phù h p nh t làm i u này. Sau khi ã cài t xong script, b n (ngư i dùng) có th t câu h i v nh ng con ngư i ho c i u ki n có liên quan trong script. H th ng sau ó s ti n hành thao tác tìm ki m ho c thao tác so m u tìm câu tr l i. Ch ng h n b n có th t câu h i "Khách hàng làm gì trư c tiên?". H th ng s tìm th y câu tr l i trong scene 1 và ưa ra áp án " u xe và bư c vào nhà hàng". XIII. PH I H P NHI U CÁCH BI U DI N TRI TH C M c tiêu chính bi u di n tri th c trong máy tính là ph c v cho vi c thu nh n tri th c vào máy tính, truy xu t tri th c và th c hi n các phép suy lu n d a trên nh ng tri th c ã lưu tr . Do ó, th a mãn ư c 3 m c tiêu trên, khi ch n phương pháp bi u di n tri th c, chúng ta ph i cân nh c m t s y u t cơ b n sau ây : Tính t nhiên, ng b và d hi u c a bi u di n tri th c. M c tr u tư ng c a tri th c : tri th c ư c khai báo c th hay nhúng vào h th ng dư i d ng các mã th t c? Tính ơn th và linh ng c a cơ s tri th c (có cho phép d dàng b sung tri th c, m c ph thu c gi a các tri th c, ...) Tính hi u qu trong vi c truy xu t tri th c và s c m nh c a các phép suy lu n (theo ki u heuristic) . 81 Sưu t m b i: www.daihoc.com.vn
B ng sau cho chúng ta m t s ưu và khuy t i m c a các phương pháp bi u di n tri th c ã ư c trình bày. P.Pháp Ưu i m Như c i m Lu t sinh Cú pháp ơn gi n, d R t khó theo dõi s phân c p, hi u, di n d ch ơn gi n, không hi u qu trong nh ng tính ơn th cao, linh h th ng l n, không th bi u ng (d i u ch nh). di n ư c m i lo i tri th c, r t y u trong vi c bi u di n các tri th c d ng mô t , có c u trúc. M ng ng D theo dõi s phân c p, Ng nghĩa g n li n v i m i nghĩa s dò theo các m i liên nh có th nh p nh ng, khó h , linh ng x lý các ngo i l , khó l p trình. Frame Có s c m nh di n t Khó l p trình, khó suy di n, t t, d cài t các thu c thi u ph n m m h tr . tính cho các slot cũng như các m i liên h , d dàng t o ra các th t c chuyên bi t hóa, d ưa vào các thông tin m c nh và d th c hi n các thao tác phát hi n các giá tr b thi u sót. Logic hình Cơ ch suy lu n chính Tách r i vi c bi u di n và x th c xác ( ư c ch ng minh lý, không hi u qu v i lư ng b i toán h c). d li u l n, quá ch m khi cơ s d li u l n. Tuy v y, như chúng ta ã bi t, hi n nay v n chưa có m t ki u bi u di n tri th c nào phù h p v i m i tình hu ng. Do ó, khi ph i làm vi c v i nhi u ngu n tri th c khác nhau (khác lo i, khác tính ch t), chúng ta nhi u lúc ph i hy sinh tính ng b b ng cách s d ng cùng lúc nhi u ki u bi u di n tri th c, m i ki u bi u di n ng v i m t nhi m v con. Nhưng như v y, chúng ta l i n y sinh ra v n "d ch" m t tri th c t ki u bi u di n này sang ki u bi u di n khác. Tuy th nhưng m t s h chương trình trí tu g n ây v n dùng cùng lúc nhi u ki u bi u di n d li u khác nhau. M t trong nh ng ví d k t h p nhi u ki u bi u di n tri th c mà chúng ta ã t ng làm quen là ki u k t h p gi a frame và m ng ng nghĩa trong vi c tr giúp gi i bài toán hình h c. M t trong nh ng s ph i h p tương i thành công là s k t h p gi a lu t sinh và frame. Lu t sinh không hi u qu trong nhi u ng d ng, c bi t là trong các tác v nh nghĩa, mô t các i tư ng ho c nh ng m i liên k t tĩnh gi a các i tư ng. Nhưng nh ng y u i m này l i chính là ưu i m c a frame. Ngày nay, ã có r t nhi u h th ng ã t o ra m t ki u bi u di n lai gi a lu t sinh và frame có ư c ưu i m c a hai cách bi u di n. S thành công c a các h th ng n i ti ng như KEE, 82 Sưu t m b i: www.daihoc.com.vn
Level5 Object và Nexpert Object ã minh ch ng cho i u này. Frame cung c p m t ngôn ng c u trúc hi u qu c t nh ng i tư ng xu t hi n trong các lu t. Frame còn óng vai trò như m t l p h tr cho thao tác suy di n cơ b n trên nh ng i tư ng không c n ph i tương tác m t cách tư ng minh trong các lu t. Kh năng phân l p c a frame còn có th ư c dùng phân ho ch, t o ch m c và s p x p các lu t sinh trong h th ng. Kh năng này r t thích h p cho ngư i dùng trong vi c xây d ng và hi u các lu t, cũng như cũng có th theo dõi ư c các lu t ư c s d ng khi nào và cho m c gì. Hình sau cho th y m t ki u k t h p gi a lu t sinh và frame. S k t h p này ã cho phép t o ra các lu t so m u nh m tăng t c tìm ki m c a h th ng. K t qu c a s k t h p này cho phép t o ra các bi u di n ph c t p hơn r t nhi u so v i vi c ch dùng frame, th m chí ph c t p hơn c vi c l p trình tr c ti p b ng ngôn ng C++ !!. * Suy lu n không ch c ch n (Hypothetical reasoning) : là k thu t suy lu n d a trên các i u ki n có th có mâu thu n ho c không ch c ch n. Ví d k t h p bi u di n tri th c b ng lu t sinh và frame trong bài toán i u ch ch t hóa h c V n : Cho trư c m t s ch t hóa h c. Hãy xây d ng chu i các ph n ng hóa h c i u ch m t s ch t hóa h c khác. u tiên, ây là m t ng d ng h t s c t nhiên c a tri th c bi u di n dư i d ng lu t. Lý do là vì b n thân các ph n ng hóa h c tiêu chu n u ư c th hi n dư i d ng lu t. Ch ng h n ta có các phương trình ph n ng sau : Na + Cl2  NaCl 83 Sưu t m b i: www.daihoc.com.vn
Fe + Cl2  FeCl2 Cu + Cl2  CuCl2 Cl2 + H2O  HCl + HClO MnO2 + 4HCl  MnCl2 + Cl2 + H2O HCl + KMnO4  KCl + MnCl2 + H2O + Cl2 NaCl + H2O  Cl2 + H2 + NaOH ... Như v y, n u xem m t ch t hóa h c là m t s ki n và m t phương trình ph n ng như là m t lu t d n thì bài toán i u ch ch t hóa h c, m t cách r t t nhiên, tr thành bài toán suy lu n ti n trong cơ s tri th c d ng lu t d n. Tuy nhiên, s lư ng các ph n ng là r t l n, nên ta không th s d ng các lu t d a trên các ph n ng c th như v y mà ph i s d ng các ph n ng t ng quát hơn như : Axit + Bazơ  Mu i + Nư c Ki m + Nư c  Xút + H2 (trong hóa h c cũng có nhi u ph n ng r t c bi t không th t ng quát ư c, trong trư ng h p này, ta s xem ph n ng ó như là m t lu t riêng!). mô t ư c các ph n ng t ng quát như trên, ta s s d ng các frame. Ch ng h n c t Acid Sulfuric H2SO4 ta s d ng các frame t ng quát sau. 84 Sưu t m b i: www.daihoc.com.vn