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

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

Thêm vào BST

Báo xấu

140
lượt xem 31
download

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

Thuật giải Robinson thuật giải này hoạt động dựa trên phương pháp chứng minh phản chứng chứng minh phép suy luận là đúng ( với a là giả thuyết và b là kết luậ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 9

 p, q, r,  p  s   q,  s B4 : N u GTi có phép  thì tách thành hai dòng con. N u KLi có phép  thì tách thành hai dòng con. Ví d : p,  p  q  q p,  p  q p, q  q B5 : M t dòng ư c ch ng minh n u t n t i chung m t m nh c hai phía. Ví d : p, q  q ư c ch ng minh p,  p  q  p p, q B6 : a) N u m t dòng không còn phép n i  ho c  c hai v và 2 v không có chung m t bi n m nh thì dòng ó không ư c ch ng minh. b) M t v n ư c ch ng minh n u t t c dòng d n xu t t d ng chu n ban u u ư c ch ng minh. VII.2 Thu t gi i Robinson Thu t gi i này ho t ng d a trên phương pháp ch ng minh ph n ch ng. Phương pháp ch ng minh ph n ch ng Ch ng minh phép suy lu n (a  b) là úng (v i a là gi thi t, b là k t lu n). Ph n ch ng : gi s b sai suy ra  b là úng. Bài toán ư c ch ng minh n u a úng và  b úng sinh ra m t mâu thu n. B1 : Phát bi u l i gi thi t và k t lu n c a v n dư i d ng chu n như sau : GT1, GT2, ...,GTn  KL1, KL2, .., KLm Trong ó : GTi và KLj ư c xây d ng t các bi n m nh và các phép toán :  ,  ,  B2 : N u GTi có phép  thì thay b ng d u "," 57 Sưu t m b i: www.daihoc.com.vn
N u KLi có phép  thì thay b ng d u "," B3 : Bi n i dòng chu n B1 v thành danh sách m nh như sau : { GT1, GT2, ..., GTn ,  KL1,  KL2, ...,  KLm } B4 : N u trong danh sách m nh bư c 2 có 2 m nh i ng u nhau thì bài toán ư c ch ng minh. Ngư c l i thì chuy n sang B4. (a và  a g i là hai m nh i ng u nhau) B5 : Xây d ng m t m nh m i b ng cách tuy n m t c p m nh trong danh sách m nh bư c 2. N u m nh m i có các bi n m nh i ng u nhau thì các bi n ó ư c lo i b . Ví d : &#p   q   r  s  q Hai m nh  q, q là i ng u nên s ư c lo i b prs B6 : Thay th hai m nh v a tuy n trong danh sách m nh b ng m nh m i. Ví d : { p   q ,  r  s  q , w  r, s  q }  { p   r  s , w  r, s  q } B7 : N u không xây d ng ư c thêm m t m nh m i nào và trong danh sách m nh không có 2 m nh nào i ng u nhau thì v n không ư c ch ng minh. Ví d : Ch ng minh r ng  p  q,  q  r,  r  s,  u   s   p,  u B3: {  p  q,  q  r,  r  s,  u   s, p, u } B4 : Có t t c 6 m nh nhưng chưa có m nh nào i ng u nhau. B5 :  tuy n m t c p m nh (ch n hai m nh có bi n i ng u). Ch n hai m nh u: pqqrpr Danh sách m nh thành : { p  r ,  r  s,  u   s, p, u } V n chưa có m nh i ng u. 58 Sưu t m b i: www.daihoc.com.vn
Tuy n hai c p m nh u tiên prrsps Danh sách m nh thành { p  s,  u   s, p, u } V n chưa có hai m nh i ng u Tuy n hai c p m nh u tiên  p  s  u   s   p   u Danh sách m nh thành : { p   u, p, u } V n chưa có hai m nh i ng u Tuy n hai c p m nh : puup Danh sách m nh tr thành : { p, p } Có hai m nh i ng u nên bi u th c ban u ã ư c ch ng minh. VIII. BI U DI N TRI TH C S D NG LU T D N XU T (LU T SINH) VIII.1. Khái ni m Phương pháp bi u di n tri th c b ng lu t sinh ư c phát minh b i Newell và Simon trong lúc hai ông ang c g ng xây d ng m t h gi i bài toán t ng quát. ây là m t ki u bi u di n tri th c có c u trúc. Ý tư ng cơ b n là tri th c có th ư c c u trúc b ng m t c p i u ki n – hành ng : "N U i u ki n x y ra THÌ hành ng s ư c thi hành". Ch ng h n : N U èn giao thông là THÌ b n không ư c i th ng, N U máy tính ã m mà không kh i ng ư c THÌ ki m tra ngu n i n, … Ngày nay, các lu t sinh ã tr nên ph bi n và ư c áp d ng r ng rãi trong nhi u h th ng trí tu nhân t o khác nhau. Lu t sinh có th là m t công c mô t gi i quy t các v n th c t thay cho các ki u phân tích v n truy n th ng. Trong trư ng h p này, các lu t ư c dùng như là nh ng ch d n (tuy có th không hoàn ch nh) nhưng r t h u ích tr giúp cho các quy t nh trong quá trình tìm ki m, t ó làm gi m không gian tìm ki m. M t ví d khác là lu t sinh có th ư c dùng b t chư c hành vi c a nh ng chuyên gia. Theo cách này, lu t sinh không ch ơn thu n là m t ki u bi u di n tri th c trong máy tính mà là m t ki u bi u di n các hành vi c a con ngư i. M t cách t ng quát lu t sinh có d ng như sau : P1  P2  ...  Pn  Q 59 Sưu t m b i: www.daihoc.com.vn
Tùy vào các v n ang quan tâm mà lu t sinh có nh ng ng nghĩa hay c u t o khác nhau : Trong logic v t : P1, P2, ..., Pn, Q là nh ng bi u th c logic. Trong ngôn ng l p trình, m i m t lu t sinh là m t câu l nh. IF (P1 AND P2 AND .. AND Pn) THEN Q. Trong lý thuy t hi u ngôn ng t nhiên, m i lu t sinh là m t phép d ch : ONE  m t. TWO  hai. JANUARY  tháng m t bi u di n m t t p lu t sinh, ngư i ta thư ng ph i ch rõ hai thành ph n chính sau : (1) T p các s ki n F(Facts) F = { f1, f2, ... fn } (2) T p các quy t c R (Rules) áp d ng trên các s ki n d ng như sau : f1 ^ f2 ^ ... ^ fi  q Trong ó, các fi , q u thu c F Ví d : Cho 1 cơ s tri th c ư c xác nh như sau : Các s ki n : A, B, C, D, E, F, G, H, K T p các quy t c hay lu t sinh (rule) R1 : A  E R2 : B  D R3 : H  A R4 : E  G  C R5 : E  K  B R6 : D  E  K  C R7 : G  K  F  A 60 Sưu t m b i: www.daihoc.com.vn
VIII.2. Cơ ch suy lu n trên các lu t sinh Suy di n ti n : là quá trình suy lu n xu t phát t m t s s ki n ban u, xác nh các s ki n có th ư c "sinh" ra t s ki n này. S ki n ban u : H, K R3 : H  A {A, H. K } R1 : A  E { A, E, H, H } R5 : E  K  B { A, B, E, H, K } R2 : B  D { A, B, D, E, H, K } R6 : D  E  K  C { A, B, C, D, E, H, K } Suy di n lùi : là quá trình suy lu n ngư c xu t phát t m t s s ki n ban u, ta tìm ki m các s ki n ã "sinh" ra s ki n này. M t ví d thư ng g p trong th c t là xu t phát t các tình tr ng c a máy tính, ch n oán xem máy tính ã b h ng hóc âu. Ví d : T p các s ki n : • c ng là "h ng" hay "ho t ng bình thư ng" • H ng màn hình. • L ng cáp màn hình. • Tình tr ng èn c ng là "t t" ho c "sáng" • Có âm thanh c c ng. • Tình tr ng èn màn hình "xanh" ho c "ch p " • Không s d ng ư c máy tính. • i n vào máy tính "có" hay "không" T p các lu t : R1. N u ( ( c ng "h ng") ho c (cáp màn hình "l ng")) thì không s d ng ư c máy tính. R2. N u ( i n vào máy là "có") và ( (âm thanh c c ng là "không") ho c tình tr ng èn c ng là "t t")) thì ( c ng "h ng"). R3. N u ( i n vào máy là "có") và (tình tr ng èn màn hình là "ch p ") thì (cáp màn hình "l ng"). xác nh ư c các nguyên nhân gây ra s ki n "không s d ng ư c máy tính", ta ph i xây d ng m t c u trúc th g i là th AND/OR như sau : 61 Sưu t m b i: www.daihoc.com.vn
Như v y là xác nh ư c nguyên nhân gây ra h ng hóc là do c ng h ng hay cáp màn hình l ng, h th ng ph i l n lư t i vào các nhánh ki m tra các i u ki n như i n vào máy "có", âm thanh c ng "không"…T i m t bư c, n u giá tr c n xác nh không th ư c suy ra t b t kỳ m t lu t nào, h th ng s yêu c u ngư i dùng tr c ti p nh p vào. Ch ng h n như bi t máy tính có i n không, h th ng s hi n ra màn hình câu h i "B n ki m tra xem có i n vào máy tính không (ki m tra èn ngu n)? (C/K)". th c hi n ư c cơ ch suy lu n lùi, ngư i ta thư ng s d ng ngăn x p ( ghi nh n l i nh ng nhánh chưa ki m tra). VIII.3. V n t i ưu lu t T p các lu t trong m t cơ s tri th c r t có kh năng th a, trùng l p ho c mâu thu n. Dĩ nhiên là h th ng có th l i cho ngư i dùng v vi c ưa vào h th ng nh ng tri th c như v y. Tuy vi c t i ưu m t cơ s tri th c v m t t ng quát là m t thao tác khó (vì gi a các tri th c thư ng có quan h không tư ng minh), nhưng trong gi i h n cơ s tri th c dư i d ng lu t, ta v n có m t s thu t toán ơn gi n lo i b các v n này. VIII.3.1. Rút g n bên ph i Lu t sau hi n nhiên úng : A  B  A (1) Do ó lu t ABAC Là hoàn toàn tương ương v i ABC 62 Sưu t m b i: www.daihoc.com.vn
Quy t c rút g n : Có th lo i b nh ng s ki n bên v ph i n u nh ng s ki n ó ã xu t hi n bên v trái. N u sau khi rút g n mà v ph i tr thành r ng thì lu t ó là lu t hi n nhiên. Ta có th lo i b các lu t hi n nhiên ra kh i tri th c. VIII.3.2. Rút g n bên trái Xét các lu t : (L1) A, B  C (L2) A  X (L3) X  C Rõ ràng là lu t A, B  C có th ư c thay th b ng lu t A  C mà không làm nh hư ng n các k t lu n trong m i trư ng h p. Ta nói r ng s ki n B trong lu t (1) là dư th a và có th ư c lo i b kh i lu t d n trên. VIII.3.3. Phân rã và k t h p lu t Lu t A  B  C Tương ương v i hai lu t AC BC V i quy t c này, ta có th lo i b hoàn toàn các lu t có phép n i HO C. Các lu t có phép n i này thư ng làm cho thao tác x lý tr nên ph c t p. VIII.3.4. Lu t th a M t lu t d n A  B ư c g i là th a n u có th suy ra lu t này t nh ng lu t còn l i. Ví d : trong t p các lu t g m {A  B, B  C, A  C} thì lu t th 3 là lu t th a vì nó có th ư c suy ra t 2 lu t còn l i. VIII.3.5. Thu t toán t i ưu t p lu t d n Thu t toán này s t i ưu hóa t p lu t ã cho b ng cách lo i i các lu t có phép n i HO C, các lu t hi n nhiên ho c các lu t th a. Thu t toán bao g m các bư c chính B1 : Rút g n v ph i V i m i lu t r trong R V im is ki n A  V Ph i(r) 63 Sưu t m b i: www.daihoc.com.vn