›
›

Bài giảng Mạng suy diễn, tính toán - Đỗ Văn Nhơn

pdf 88 trang Gia Huy 17/05/2022 2160
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng suy diễn, tính toán - Đỗ Văn Nhơn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_mang_suy_dien_tinh_toan_do_van_nhon.pdf

Nội dung text: Bài giảng Mạng suy diễn, tính toán - Đỗ Văn Nhơn

  1. MAÏNG SUY DIEÃN - TÍNH TOAÙN Ñoã Vaên Nhôn Ñaïi Hoïc Quoác Gia TPHCM Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  2. GIÔÙI THIEÄU „ Nghieân cöùu caùc phöông phaùp bieåu dieãn vaø xöû lyù tri thöùc laø coát loõi cho vieäc xaây döïng nhöõng chöông trình “thoâng minh”, ñaëc bieät laø caùc heä chuyeân gia vaø caùc heä giaûi toaùn döïa treân tri thöùc. „ Phaàn naøy seõ neâu leân moät moâ hình bieåu dieãn tri thöùc ñöôïc goïi laø Maïng Suy dieãn - Tính toaùn. Caùc thuaät giaûi cho caùc vaán ñeà cô baûn treân moâ hình ñöôïc thieát keá vaø aùp duïng trong moät soá chöông trình cuï theå. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  3. NOÄI DUNG I. Daãn nhaäp II. Moâ hình Maïng suy dieãn vaø vaán ñeà III. Tìm lôøi giaûi IV. Lôøi giaûi toái öu V. Taäp hôïp sinh VI. Maïng Suy dieãn - Tính toaùn Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  4. I. Daãn Nhaäp 1.1 Söï caàn thieát cuûa vieäc nghieân cöùu xaây döïng vaø phaùt trieån caùc moâ hình bieåu dieãn tri thöùc cho caùc chöông trình giaûi toaùn thoâng minh. 1.2 Caùc ví duï daãn tôùi söï ñeà xuaát moâ hình Maïng Suy dieãn - Tính toaùn vaø caùc vaán ñeà cô baûn treân moâ hình. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  5. 1.1 VAÁN ÑEÀ BIEÅU DIEÃN TRI THÖÙC ° Trong caáu truùc cuûa moät heä giaûi toaùn döïa treân tri thöùc, 2 thaønh phaàn trung taâm laø cô sôû tri thöùc vaø boä suy dieãn döïa treân tri thöùc. ° Ñaõ coù nhieàu phöông phaùp bieåu dieãn tri thöùc vaø suy dieãn ñaõ ñöôïc nghieân cöùu vaø ñeà xuaát. Tuy nhieân moãi phöông phaùp ñeàu chæ theå hieän ñöôïc moät khía caïnh naøo ñoù cuûa tri thöùc vaø coù nhöõng nhöôïc ñieåm nhaát ñònh. Caàn xaây döïng vaø phaùt trieån caùc moâ hình bieåu dieãn tri thöùc giuùp thieát keá vaø caøi ñaët phaàn tri thöùc cuõng nhö phaàn suy dieãn cuûa caùc heä giaûi toaùn döïa treân tri thöùc. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  6. 1.2 CAÙC VÍ DUÏ DAÃN TÔÙI MOÂ HÌNH Trong nhieàu chuû ñeà giaûi toaùn thöôøng gaëp nhöõng vaán ñeà ñaët ra döôùi daïng nhö sau: ° Caàn phaûi thöïc hieän nhöõng tính toaùn hay suy dieãn ra nhöõng yeáu toá caàn thieát naøo ñoù töø moät soá yeáu toá ñaõ ñöôïc bieát tröôùc. ° Ñeå giaûi quyeát vaán ñeà ngöôøi ta phaûi vaän duïng moät soá hieåu bieát (tri thöùc) naøo ñoù veà nhöõng lieân heä giöõa caùc yeáu toá ñang ñöôïc xem xeùt. Nhöõng lieân heä cho pheùp ta coù theå suy ra ñöôïc moät soá yeáu toá töø giaû thieát ñaõ bieát moät soá yeáu toá khaùc. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  7. Ví duï 1. „ Giaû söû chuùng ta ñang quan taâm ñeán moät soá yeáu toá trong moät tam giaùc, chaúng haïn : 3 caïnh a, b, c; 3 goùc töông öùng vôùi 3 caïnh : , , ; 3 ñöôøng cao töông öùng : ha, hb, hc; dieän tích S cuûa tam giaùc; nöûa chu vi p cuûa tam giaùc; baùn kính ñöôøng troøn noäi tieáp r cuûa tam giaùc. „ Giöõa 12 yeáu toá treân coù caùc coâng thöùc theå hieän nhöõng moái quan heä giuùp ta coù theå giaûi quyeát ñöôïc moät soá vaán ñeà tính toaùn ñaët ra nhö: Tính moät yeáu toá töø moät soá yeáu toá ñöôïc cho tröôùc. Chaúng haïn, tính S khi bieát a, b vaø p. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  8. Trong tam giaùc chuùng ta coù theå keå ra moät soá quan heä döôùi daïng coâng thöùc sau ñaây: „ Lieân heä giöõa 3 goùc : + + = „ Ñònh lyù cosin : a2 = b2 + c2 - 2.b.c.cos b2 = a2 + c2 - 2.a.c.cos c2 = a2 + b2 - 2.a.b.cos „ Ñònh lyù Sin: a b c sin sin sin Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  9. „ Lieân heä giöõa nöûa chu vi vaø 3 caïnh : „ 2.p = a + b + c „ Moät soá coâng thöùc tính dieän tích: „ S = a.ha/2; S = b.hb/2; S = c.hc/2; S = p.r „ Coâng thöùc tính dieän tích theo 3 caïnh (coâng thöùc Heron): S = p(p a)(p b)(p c) Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  10. Ví duï 2. „ Moät vaät theå coù khoái löôïng m chuyeån ñoäng thaúng vôùi gia toác khoâng thay ñoåi laø a trong moät khoaûng thôøi gian tính töø thôøi ñieåm t1 ñeán thôøi ñieåm t2. Vaän toáùc ban ñaàu cuûa vaät theå laø v1, vaän toác ôû thôøi ñieåm cuoái laø v2, vaø vaän toác trung bình laø v. Khoaûng caùch giöõa ñieåm ñaàu vaø ñieåm cuoái laø s. Löïc taùc ñoäng cuûa chuyeån ñoäng laø f. Ñoä bieán thieân vaän toác giöõa 2 thôøi ñieåm laø v, vaø ñoä bieán thieân thôøi gian laø t. Ngoaøi ra coøn coù moät soá yeáu toá khaùc nöõa cuûa chuyeån ñoäng vaät theå coù theå ñöôïc quan taâm. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  11. Ñeå giaûi nhöõng baøi toaùn veà chuyeån ñoäng naày chuùng ta phaûi söû duïng moät soá coâng thöùc lieân heä giöõa caùc yeáu toá cuûa chuyeån ñoäng, chaúng haïn nhö: „ f = m * a; „ v = a* t; „ s = v* t; „ 2*v = v1 + v2; „ v = v2 - v1; „ t = t2 - t1; Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  12. Ví duï 3. „ Trong hoùa hoïc chuùng ta thöôøng phaûi söû duïng caùc phaûn öùng hoùa hoïc ñeå ñieàu cheá caùc chaát naày töø caùc chaát khaùc. Loaïi vaán ñeà naày cuõng cho ta moät daïng töông töï nhö trong 2 ví duï treân : Cho tröôùc moät soá chaát hoùa hoïc, haõy tìm caùch ñieàu cheá ra moät hay moät soá chaát naøo ñoù. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  13. II. Moâ hình Maïng Suy dieãn 2.1 Moâ hình. „ ª Giôùi thieäu ª Ñònh nghóa ª Ví duï 2.2 Caùc vaán ñeà cô baûn. „ ª Tính giaûi ñöôïc ª Lôøi giaûi ª Söï boå sung giaû thieát 2.3 Moät soá khaùi nieäm vaø kyù hieäu Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  14. 2.1 Moâ hình ª Giôùi thieäu: „ Nhaän thaáy coù nhieàu vaán ñeà trong caùc lónh vöïc khaùc nhau ñaët ra döôùi daïng moät “maïng” caùc yeáu toá, trong ñoù giöõa caùc yeáu toá coù nhöõng moái lieân heä (hay quan heä) cho pheùp ta coù theå suy ra ñöôïc moät soá yeáu toá naày töø moät soá yeáu toá khaùc. „ Moâ hình maïng suy dieãn - tính toaùn laø moät söï khaùi quaùt daïng tri thöùc treân, vaø coù theå duøng bieåu dieãn tri thöùc vaø thieát keá caùc chöông trình giaûi toaùn töï ñoäng. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  15. ª Ñònh nghóa ° Quan heä suy dieãn: Cho M = x1,x2, ,xm laø moät taäp hôïp caùc bieán coù theå laáy giaù trò trong caùc mieàn xaùc ñònh D1, D2, ,Dm. Moãi quan heä suy dieãn R treân M ñöôïc xaùc ñònh bôûi moät (hay moät soá) aùnh xaï coù daïng: „ fR,u,v : Du Dv, „ trong ñoù u,v laø caùc boä bieán ñöôïc phaân chia töø boä bieán x = ; Du vaø Dv laø tích cuûa caùc mieàn xaùc ñònh töông öùng cuûa caùc bieán trong u vaø trong v. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  16. „ Quan heä suy dieãn R(x) coù theå ñöôïc bieåu dieãn bôûi moät (hay moät soá) aùnh xaï fR,u,v vaø ta vieát vaén taét laø: „ f : u v. „ Caùch kyù hieäu treân bao haøm yù nghóa nhö moät luaät suy dieãn: ta coù theå xaùc ñònh hay suy ra ñöôïc caùc bieán thuoäc v khi bieát caùc bieán thuoäc u. „ Quan heä laø ñoái xöùng vaø coù haïng k khi quan heä ñoù giuùp ta coù theå tính ñöôïc k bieán baát kyø töø m-k bieán kia (ôû ñaây x laø boä goàm m bieán ). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  17. Ví du 1ï: „ Quan heä f giöõa 3 goùc A, B, C trong tam giaùc ABC cho bôûi heä thöùc: A+B+C = . „ Quan heä f giöõa 3 goùc trong moät tam giaùc laø moät quan heä ñoái xöùng coù haïng 1. Quan heä naày bao haøm 3 luaät suy dieãn: „ A, B C „ A, C B „ C, B A Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  18. Ví du 2ï: „ Quan heä f giöõ a nöûa chu vi p vôùi caùc ñoä daøi cuûa 3 caïnh a, b, c: 2*p = a + b + c „ cho ta moät quan heä ñoái xöùng haïng 1 treân caùc bieán p, a, b, c. Ví du 3ï: „ Quan heä f giöõ a n bieán x1, x2, , xn ñöôïc cho döôùi daïng moät heä phöông trình tuyeán tính coù nghieäm. Trong tröôøng hôïp naày f laø moät quan heä ñoái xöùng coù haïng k baèng haïng cuûa ma traän heä soá cuûa heä phöông trình. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  19. ª Ñònh nghóa ° Maïng suy dieãn, vieát taét laø MSD, laø moät caáu truùc (M,F) goàm 2 taäp hôïp: ˜ M = x1,x2, ,xn , laø taäp hôïp caùc thuoäc tính hay caùc bieán laáy giaù trò trong caùc mieàn xaùc ñònh naøo ñoù. ˜ F = f1,f2, ,fm , laø taäp hôïp caùc luaät suy dieãn coù daïng: ˜ f : u(f) v(f) trong ñoù u(f) vaø v(f) laø caùc taäp hôïp con khaùc roãng cuûa M sao cho u(f) v(f) = .ø ˜ Kyù hieäu: M(f) = u(f) v(f). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  20. ª Ví duï: Maïng suy dieãn cho moät hình chöõ nhaät. „ Vieäc tính toaùn treân moät hình chöõ nhaät lieân quan ñeán moät soá giaù trò cuûa hình chöõ nhaät nhö sau : „ b1, b2 : hai caïnh cuûa hình chöõ nhaät; „ d : ñöôøng cheùo cuûa hình chöõ nhaät; „ S : dieän tích cuûa hình chöõ nhaät; „ p : chu vi cuûa hình chöõ nhaät; „ trong ñoù moãi bieán ñeàu coù giaù trò laø thuoäc taäp caùc soá thöïc döông. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  21. „ Giöõa caùc bieán ta ñaõ bieát coù caùc quan heä tính toaùn sau ñaây: f1 : S = b1 * b2; f2 : p = 2 * (b1 + b2); 2 2 2 f3 : d = b1 + b2 ; „ Veà maët suy luaän, caùc quan heä naày ñeàu coù theå xem laø caùc quan heä suy dieãn ñoái xöùng coù haïng laø 1. Nhö vaäy taäp bieán vaø taäp quan heä cuûa maïng naày laø : „ M = b1, b2, d, s, p , „ R = f1, f2, f3 . Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  22. „ Maïng (M,R) treân töông öùng vôùi maïng suy dieãn (M, F) vôùi F laø taäp caùc luaät suy dieãn sau ñaây: „ b1, b2 S „ S, b2 b1 S, b1 b2 b1, b2 p p, b2 b1 p, b1 b2 b1, b2 d d, b2 b1 d, b1 b2 Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  23. 2.2 Caùc vaán ñeà cô baûn Cho moät maïng suy dieãn (M,F) vôùi M laø taäp caùc thuoäc tính (hay caùc bieán) vaø F laø taäp caùc quan heä suy dieãn hay caùc luaät suy dieãn. Giaû söû coù moät taäp bieán A M ñaõ ñöôïc xaùc ñònh (töùc laø taäp goàm caùc bieán ñaõ bieát tröôùc), vaø B laø moät taäp bieán baát kyø trong M. ª Tính giaûi ñöôïc: „ Coù theå xaùc ñònh ñöôïc (hay suy ra) taäp B töø taäp A nhôø caùc quan heä trong F hay khoâng? Noùi caùch khaùc, ta coù theå tính ñöôïc giaù trò cuûa caùc bieán thuoäc B vôùi giaû thieát ñaõ bieát giaù trò cuûa caùc bieán thuoäc A hay khoâng? Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  24. ª Tìm lôøi giaûi: „ Neáu coù theå suy ra ñöôïc B töø A thì quaù trình suy dieãn nhö theá naøo? Trong tröôøng hôïp coù nhieàu caùch suy dieãn khaùc nhau thì caùch suy dieãn naøo laø toát nhaát? ª Boå sung giaû thieát: „ Trong tröôøng hôïp khoâng theå xaùc ñònh ñöôïc B, thì caàn cho theâm ñieàu kieän gì ñeå coù theå xaùc ñònh ñöôïc B. ° Kyù hieäu baøi toaùn xaùc ñònh B töø A laø: „ A B Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  25. 2.3 Moät soá khaùi nieäm vaø kyù hieäu ª Ñònh nghóa: „ Moät luaät suy dieãn u v ñöôïc ñöôïc goïi laø aùp duïng ñöôïc treân A khi u A. „ Moät quan heä suy dieãn ñöôïc goïi laø aùp duïng ñöôïc treân A khi noù xaùc ñònh moät luaät suy dieãn aùp duïng ñöôïc treân A. „ Daõy D = f1, f2, , fk caùc quan heä suy dieãn (hay luaät suy dieãn) cuûa maïng suy dieãn (M,F) ñöôïc noùi laø aùp duïng ñöôïc treân taäp A khi vaø chæ khi ta coù theå laàn löôït aùp duïng ñöôïc caùc quan heä f1, f2, , fk xuaát phaùt töø giaû thieát A. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  26. ª Kyù hieäu: „ Vôùi D = f1, f2, , fk , ñaët: „ A0 = A, A1 = A0 M(f1), . . . , Ak = Ak-1 M(fk), „ vaø kyù hieäu Ak laø D(A). „ Coù theå noùi raèng D(A) laø söï môû roäng cuûa taäp A nhôø aùp duïng daõy quan heä D. „ Ví duï: Trong maïng suy dieãn cho moät hình chöõ nhaät, vôùi A = b1, b2 vaø D = f1: S = b1 * b2; f2: p = 2*(b1+b2) ta coù D(A) = b1, b2, S, p . Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  27. ª Ñònh nghóa lôøi giaûi: „ D = f1, f2, , fk laø moät lôøi giaûi cuûa baøi toaùn A B khi laàn löôït aùp duïng caùc quan heä fi (i=1, ,k) xuaát phaùt töø giaû thieát A thì seõ suy ra ñöôïc caùc bieán thuoäc B. Noùi caùch khaùc D laø moät lôøi giaûi cuûa baøi toaùn khi D(A) B. „ Baøi toaùn A B laø giaûi ñöôïc khi noù coù moät lôøi giaûi. „ Lôøi giaûi f1, f2, , fk ñöôïc goïi laø lôøi giaûi toát neáu khoâng theå boû bôùt moät soá böôùc tính toaùn trong quaù trình giaûi, töùc laø khoâng theå boû bôùt moät soá quan heä trong lôøi giaûi. „ Lôøi giaûi ngaén nhaát:ù coù soá böôùc suy dieãn thaáp nhaát. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  28. III. Tìm lôøi giaûi 3.1 Tính giaûi ñöôïc 3.2 Thuaät toaùn tìm lôøi giaûi 3.3 Phaân tích quaù trình giaûi Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  29. 3.1 Tính giaûi ñöôïc ª Ñònh nghóa “bao ñoùng”: „ Cho maïng suy dieãn (M,F), vaø A laø moät taäp con cuûa M. Ta coù theå thaáy raèng coù duy nhaát moät taäp hôïp B lôùn nhaát M sao cho baøi toaùn A B laø giaûi ñöôïc, vaø taäp hôïp B naày ñöôïc goïi laø bao ñoùng cuûa A treân maïng (M,F). „ Kyù hieäu bao ñoùng cuûa A laø „ Closure(A). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  30. ª Ñònh lyù: „ Treân moät maïng suy dieãn (M,F), baøi toaùn A B laø giaûi ñöôïc khi vaø chæ khi B Closure(A). ª Meänh ñeà: „ Treân moät maïng suy dieãn (M,F), giaû söû A, B laø hai taäp con cuûa M. Ta coù caùc ñieàu sau ñaây laø töông ñöông: „ (1) B Closure(A). „ (2) Coù moät daõy quan heä D = f1, f2, , fk F thoûa caùc ñieàu kieän : (a) D aùp ñöôïc treân A. (b) D(A) B. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  31. ª Thuaät toaùn tìm bao ñoùng cuûa A treân maïng (M,F). „ 1. B A; 2. Repeat B1 B; for f F do if ( f ñoái xöùng and Card (M(f) \ B) r(f) ) or (f khoâng ñoái xöùng and M(f) \ B v(f) ) then begin B B M(f); F F \ f ; // loaïi f khoûi laàn xem xeùt sau end; Until B = B1; 3. Closure(A) B; Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  32. 3.2 Tìm lôøi giaûi ª Meänh ñeà: „ Daõy quan heä suy dieãn D laø moät lôøi giaûi cuûa baøi toaùn A B khi vaø chæ khi D aùp duïng ñöôïc treân A vaø D(A) B. Ñeå tìm moät lôøi giaûi ta coù theå laøm nhö sau: Xuaát phaùt töø giaû thieát A, ta thöû aùp duïng caùc quan heä ñeå môû roäng daàn taäp caùc bieán ñöôïc xaùc ñònh (ñöôïc bieát); vaø quaù trình naày taïo ra moät söï lan truyeàn tính xaùc ñònh treân taäp caùc bieán cho ñeán khi ñaït ñeán taäp bieán B. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  33. ª Thuaät toaùn tìm moät lôøi giaûi cuûa baøi toaùn A B . „ 1. Solution empty; // Solution laø daõy caùc quan heä seõ aùp duïng „ 2. if B A then begin Solution_found true; // bieán Solution_found = true khi // baøi toaùn laø giaûi ñöôïc goto böôùc 4; end else Solution_found false; Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  34. 3. Repeat Aold A; Choïn ra moät f F chöa xem xeùt; while not Solution_found and (choïn ñöôïc f) do begin if ( f ñoái xöùng and 0 < Card (M(f) \ A) r(f) ) or (f khoâng ñoái xöùng and M(f) \ A v(f)) then begin A A M(f); Solution Solution f ; end; if B A then Solution_found true; Choïn ra moät f F chöa xem xeùt; end; while Until Solution_found or (A = Aold); Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  35. 4. if not Solution_found then Baøi toaùn khoâng coù lôøi giaûi; else Solution laø moät lôøi giaûi; ° Nhaän xeùt: „ khi caàn trình baøy quaù trình giaûi (hay baøi giaûi) ta coù theå xuaát phaùt töø lôøi giaûi tìm ñöôïc döôùi daïng moät daõy caùc quan heä ñeå xaây döïng baøi giaûi. „ Lôøi giaûi (neáu coù) tìm ñöôïc trong thuaät toaùn treân chöa chaéc laø moät lôøi giaûi toát. Ta coù theå boå sung theâm cho thuaät toaùn ôû treân moät thuaät toaùn ñeå tìm moät lôøi giaûi toát töø moät lôøi giaûi ñaõ bieát nhöng chöa chaéc laø toát. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  36. ª Thuaät toaùn tìm moät lôøi giaûi toát cuûa baøi toaùn A B . „ Giaû söû f1, f2, , fm laø moät lôøi giaûi cuûa baøi toaùn A B. Tìm moät lôøi giaûi toát cho baøi toaùn. „ 1. D f1, f2, , fm ; 2. for i=m downto 1 do if D \ fi laø moät lôøi giaûi then D D \ fi ; 3. D laø moät lôøi giaûi toát. ° Löu yù: ta coù theå tìm moät lôøi giaûi toát töø moät lôøi giaûi bieát tröôùc baèng caùch laàn löôït xem xeùt caùc quan heä trong taäp lôøi giaûi ñaõ bieát vaø choïn ra caùc quan heä ñeå ñöa vaøo moät lôøi giaûi môùi sao cho trong lôøi giaûi môùi naày khoâng theå bôùt ra baát kyø moät quan heä naøo. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  37. Ví duï: „ Cho tam giaùc ABC coù caïnh a vaø 2 goùc keà laø , ñöôïc cho tröôùc. Haõy xaùc ñònh (hay suy ra) S cuûa tam giaùc. ° Ñeå tìm ra lôøi giaûi cho baøi toaùn tröôùc heát ta xeùt maïng suy dieãn cuûa tam giaùc. Maïng suy dieãn naày goàm : „ Taäp bieán M = a, b, c, , , , ha, hb, hc, S, p, R, r, , „ trong ñoù a,b,c laø 3 caïnh; , , laø 3 goùc töông öùng vôùi 3 caïnh; ha, hb, hc laø 3 ñöôøng cao; S laø dieän tích tam giaùc; p laø nöûa chu vi; R laø baùn kính ñöôøng troøn ngoaïi tieáp tam giaùc; r laø baùn kính ñöôøng troøn noäi tieáp tam giaùc, v.v Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  38. „ Caùc quan heä suy dieãn theå hieän bôûi caùc coâng thöùc sau ñaây: „ f1 : + + = a b „ f : 2 sin sin c b „ f3 : sin sin a c „ f4 : sin sin „ f5 : p = (a+b+c) /2 „ f6 : S = a.ha / 2 Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  39. „ f7 : S = b.hb / 2 „ f8 : S = c.hc / 2 „ f9 : S = a.b.sin / 2 „ f10 : S = b.c.sin / 2 „ f11 : S = c.a.sin / 2 p(p a)(p b)(p c) „ f12 : S = „ v.v „ Muïc tieâu cuûa baøi toaùn laø suy ra S (dieän tích cuûa tam giaùc). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  40. „ Theo ñeà baøi ta coù giaû thieát laø : A = a, , , vaø taäp bieán caàn xaùc ñònh laø B = S . „ Aùp duïng thuaät toaùn tìm lôøi giaûi ta coù moät lôøi giaûi cho baøi toaùn laø daõy quan heä suy dieãn sau: „ f1, f2, f3, f5, f9 . „ Xuaát phaùt töø taäp bieán A, laàn löôït aùp duïng caùc quan heä trong lôøi giaûi ta coù taäp caùc bieán ñöôïc xaùc ñònh môû roäng daàn ñeán khi S ñöôïc xaùc ñònh : „ a, , a, , , a, , , , b a, , , , b, c a, , , , b, c, p a, , , , b, c, p, S . Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  41. „ Coù theå nhaän thaáy raèng lôøi giaûi treân khoâng phaûi laø lôøi giaûi toát vì coù böôùc suy dieãn thöøa, chaúng haïn laø f5. Thuaät toaùn “tìm lôøi giaûi toát” seõ loïc ra töø lôøi giaûi treân moät lôøi giaûi toát laø f1, f2, f9 : „ a, , a, , , a, , , , b a, , , , b, S . „ Theo lôøi giaûi naày, ta coù quaù trình suy dieãn nhö sau : „ böôùc 1: Xaùc ñònh (aùp duïng f1). „ böôùc 2: Xaùc ñònh b (aùp duïng f2). „ böôùc 3: Xaùc ñònh S (aùp duïng f9). Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  42. 3.3 Phaân tích quaù trình giaûi ª Trong muïc naày ta neâu leân moät caùch xaây döïng quaù trình giaûi töø moät lôøi giaûi ñaõ bieát cuûa baøi toaùn A B treân maïng (M,F). „ Ñoái vôùi moät lôøi giaûi, raát coù khaû naêng moät quan heä naøo ñoù daãn tôùi vieäc tính toaùn moät soá bieán thöøa, töùc laø caùc bieán tính ra maø khoâng coù söû duïng cho caùc böôùc tính phía sau. Do ñoù, chuùng ta caàn xem xeùt quaù trình aùp duïng caùc quan heä trong lôøi giaûi vaø chæ tính toaùn caùc bieán thaät söï caàn thieát cho quaù trình giaûi theo lôøi giaûi. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  43. Ñònh lyù sau ñaây cho ta moät söï phaân tích taäp caùc bieán ñöôïc xaùc ñònh theo lôøi giaûi vaø treân cô sôû ñoù coù theå xaây döïng quaù trình suy dieãn ñeå giaûi quyeát baøi toaùn. „ Ñònh lyù: Cho f1, f2, , fm laø moät lôøi giaûi toát cho baøi toaùn A B treân moät maïng tính toaùn (M,F). Ñaët : A0 = A, Ai = f1, f2, , fi (A), vôùi moïi i=1, ,m. „ Khi ñoù coù moät daõy B0, B1, , Bm-1, Bm , thoûa caùc ñieàu kieän sau ñaây: (1) Bm = B. (2) Bi Ai , vôùi moïi i=0,1, ,m. (3) Vôùi moïi i=1, ,m, fi laø lôøi giaûi cuûa Bi-1 Bi nhöng khoâng laø lôøi giaûi cuûa G Bi , trong ñoù G laø moät taäp con thaät söï tuøy yù cuûa Bi-1. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  44. IV. Lôøi giaûi toái öu 4.1 Maïng Suy dieãn coù troïng soá 4.2 Ñònh nghóa lôøi giaûi toái öu 4.3 Tìm lôøi giaûi toái öu Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  45. 4.1 Maïng Suy dieãn coù troïng soá ª Daãn nhaäp „ trong nhieàu tröôøng hôïp aùp duïng cuï theå nhö heä suy dieãn tính toaùn hay heä suy dieãn treân caùc phaûn öùng hoùa hoïc, moãi luaät suy dieãn coù moät tham soá töông öùng ñaïi dieän cho ñoä phöùc taïp cuûa luaät suy dieãn hay chi phí. Nhöõng tham soá naày ñoùng vai troø quan troïng trong tính hieäu quaû cuûa lôøi giaûi. Ví duï, ñeå tính a, söû duïng (1) a + b + c = 2*p toát hôn söû duïng (2) a2 = b2 + c2 - 2*b*c*cos(A), vì coâng thöùc (1) tính ít hôn coâng thöùc (2). „ Moâ hình maïng suy dieãn coù troïng soá. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  46. ª Ñònh nghóa: „ Maïng suy dieãn coù troïng soá laø moät moâ hình (A,D,w) goàm: (1) moät taäp hôïp caùc thuoäc tính A, (2) moät taäp hôïp caùc luaät suy dieãn D, vaø (3) moät haøm troïng soá döông w : D R+ „ Moãi luaät daãn r thuoäc D coù daïng r : u v, vôùi u vaø v laø caùc taäp hôïp con khaùc roãng vaø rôøi nhau cuûa A. Ta goïi u laø phaàn giaû thieát cuûa luaät r vaø kyù hieäu laø hypothesis(r). Taäp v ñöôïc goïi laø phaàn keát luaän cuûa luaät r vaø kyù hieäu laø goal(r). Taäp hôïp attr(r) = hypothesis(r) goal(r) ñöôïc goïi laø taäp hôïp caùc thuoäc tính trong luaät r. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  47. Ví duï: „ Goïi A laø taäp hôïp goàm 3 caïnh cuûa moät tam giaùc (a, b, vaø c), 3 goùc trong (A, B, vaø C), nöûa chu vi p, dieän tích S, 3 ñöôøng cao (ha, hb, vaø hc), vaø caùc yeáu toá khaùc cuûa tam giaùc: „ A = A, B, C, a, b, c, p, S, ha, hb, hc, . „ Giöõa caùc thuoäc tính treân cuûa moät tam giaùc ta coù caùc luaät suy dieãn ñöôïc xaùc ñònh bôûi caùc quan heä suy dieãn theå hieän bôûi caùc coâng thöùc lieät keâ trong taäp hôïp sau ñaây: Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  48. D = f1: A + B + C = 180; f2: a/sin(A) = b/sin(B); f3: b/sin(B) = c/sin(C); f4: a/sin(A) = c/sin(C); f5: 2*p = a + b + c; f6: S = a*ha/2 f7: S = b * hb / 2; f8: S = c*hc/2; f9: S = sqrt(p*(p-a)*(p-b)*(p-c)); f10: ha = b*sin(C); f11: hb = a*sin(C); f12: hc = b*sin(A), . . . Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  49. „ Giaû söû caùc pheùp toaùn +, -, * vaø / ñöôïc ñaët cho troïng soá laø 1, pheùp tính caên baäc 2 coù troïng soá laø moät haèng soá döông c1, vaø caùc tính toaùn haøm löôïng giaùc coù troïng soá laø moät haèng soá döông c2. Nhö theá caùc quan heä suy dieãn coù troïng soá töông öùng nhö sau: „ w(f1) = 2; w(f2) = w(f3) = w(f4) = 2*c2 + 2; „ w(f5) = 3; w(f6) = w(f7) = w(f8) = 2; „ w(f9) = c1 + 6; „ w(f10) = w(f11) = w(f12) = c2 + 1; v.v . . . „ Khi ñoù ta coù (A, D, w) laø moät maïng suy dieãn coù troïng soá. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  50. 4.2 Ñònh nghóa lôøi giaûi toái öu ª Giaû söû (A, D, w) laø moät maïng suy dieãn coù troïng soá. Cho S = f1, ,fk laø moät daõy caùc luaät suy dieãn vaø A laø moät taäp hôïp caùc thuoäc tính. Ñaët „ S 1(A) = A goal(f1) neáu hypothesis(f1) A, = A neáu ngöôïc laïi. „ S i(A) = S i-1(A) goal(fi) neáu hypothesis (fi) S i-1(A), = S i-1(A) neáu ngöôïc laïi, (i=2, ,k). „ S (A) = S k(A). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  51. „ Ñaët: w(S) = w(f1) + w(f2) + + w(fk). „ Ta goïi w(S) laø troïng soá cuûa S. ª Cho moät baøi toaùn A B. daõy caùc luaät suy dieãn S ñöôïc goïi laø moät lôøi giaûi toái öu cuûa baøi toaùn khi noù thoûa maõn caùc ñieàu kieän sau ñaây: „ (1) S laø moät lôøi giaûi cuûa baøi toaùn A B. (2) Troïng soá cuûa S nhoû hôn hoaëc baèng troïng soá cuûa baát kyø moät lôøi giaûi naøo khaùc cuûa baøi toaùn. Noùi moät caùch khaùc laø w(S) = min w(S’) | S’ laø moät lôøi giaûi cuûa baøi toaùn A B Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  52. 4.3 Tìm lôøi giaûi toái öu ª Vaán ñeà: tìm lôøi giaûi toái öu cho baøi toaùn H G treân moät maïng suy dieãn coù troïng soá (A, D, w). ª Tieáp caän: thuaät giaûi A*. caàn coù moät bieåu dieãn thích hôïp cho khoâng gian traïng thaùi cuûa baøi toaùn cuõng nhö cho yeâu caàu cuûa baøi toaùn. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  53. ° Khoâng gian traïng thaùi: „ Vôùi moãi luaät r maø ta coù theå aùp duïng treân H ñeå suy ra nhöõng thuoäc tính môùi seõ daãn tôùi moät taäp thuoäc tính môùi H’ = H goal(r).Ta noùi raèng r laø moät caïnh noái töø ñænh H ñeán ñænh H’. „ Nhö theá, taäp hôïp goàm taát caû caùc taäp con (hay ñænh) H’ cuûa A sao cho coù moät daõy S goàm caùc luaät (hay caïnh) thoûa maõn ñieàu kieän H’ = S(H), cuøng vôùi caùc caïnh trong caùc daõy S seõ cho ta moät khoâng gian traïng thaùi cuûa baøi toaùn coù daïng ñoà thò. Hôn nöõa ñoà thò naày coù troïng soá ñöôïc ñònh nghóa bôûi: troïng soá cuûa caïnh r (töùc laø moät luaät suy dieãn) laø w(r). Ñoà thò coù troïng soá naày seõ ñöôïc kyù hieäu laø Graph(H G). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  54. ° Meänh ñeà: „ (1) Moät daõy S goàm caùc luaät laø moät lôøi giaûi cuûa baøi toaùn H G khi vaø chæ khi S laø moät loä trình treân ñoà thò Graph(H G) noái töø H ñeán S(H) vaø S(H) G. (2) Ñoä daøi cuûa moät loä trình S treân ñoà thò Graph(H G) laø w(S), troïng soá cuûa danh saùch luaät S treân maïng (A, D, w). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  55. „ Suy ra: vieäc tìm lôøi giaûi toái öu cho baøi toaùn H G töông ñöông vôùi vieäc tìm moät ñöôøng ñi ngaén nhaát treân ñoà thò Graph(H G) töø H ñeán moät ñænh muïc tieâu H’ thoûa ñieàu kieän H’ chöùa G. „ Ñoái vôùi moãi ñænh N treân ñoà thò, ñaët „ h(N) = min w(r) | hypothesis(r) N „ Giaù trò h(N) naày coù theå xem laø moät öôùc löôïng cho loä trình töø N ñeán moät ñænh muïc tieâu. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  56. Thuaät toaùn tìm lôøi giaûi toái öu: Böôùc 1: Khôûi taïo traïng thaùi xuaát phaùt. „ Open H ; // danh saùch ñænh môû ban ñaàu //chæ coù ñænh xuaát phaùt „ Close ; // danh saùch ñænh ñoùng „ g(H) 0; // ñoä daøi loä trình ñeán H laø 0 „ f(H) h(H); // ñoä daøi loä trình öôùc tính töø H //ñeán muïc tieâu laø h(H) „ found false; // bieán kieåm tra quaù trình tìm lôøi giaûi Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  57. Böôùc 2:Thöïc hieän quaù trình laëp ñeå tìm lôøi giaûi toái öu While (Open ) do begin Böôùc 2.1: Choïn moät ñænh N trong Open vôùi öôùc tính ñöôøng ñi f nhoû nhaát. Böôùc 2.2: Chuyeån N töø danh saùch Open sang danh saùch Close. Böôùc 2.3: if (N laø moät muïc tieâu) then begin Found true; Break; // Keát thuùc quaù trình laëp end Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  58. „ Böôùc 2.4: else // N khoâng laø moät muïc tieâu Begin Duyeät qua caùc ñænh keá S cuûa N (töùc laø coù cung r noái N vaø S) maø S Close, vaø xeùt caùc tröôøng hôïp sau: 1. S Open: Tính g(S) = g(N) + w(r); f(S) = g(S) + h(S); Boå sung S vao Open; 2. S Open: If g(N) + w(r) < g(S) then begin g(S) g(N) + w(r); f(S) g(S) + h(S); Caäp nhaät veà ñænh keá tröôùc cuûa S treân loä trình; end End „ End // // Keát thuùc voøng laëp while Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  59. Böôùc 3: Kieåm tra keát quaû vieäc tìm kieám. „ If Found then „ Keát quaû laø tìm ñöôïc lôøi giaûi toái öu vaø thieát laäp lôøi giaûi „ Else „ Keát quaû laø baøi toaùn khoâng coù lôøi giaûi. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  60. Ví duï: „ Giaû söû ta coù maïng suy dieãn coù troïng soá (A, D, w) nhö sau: „ A = A, B, C, a, b, c, p, S, ha, hb, hc „ D = „ f1: A + B + C = 180; „ f2: a/sin(A) = b/sin(B); „ f3: b/sin(B) = c/sin(C); „ f4: a/sin(A) = c/sin(C); Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  61. „ f5: 2*p = a + b + c; „ f6: S = a*ha/2; „ f7: S = b * hb / 2; „ f8: S = c*hc/2; „ f9: S = sqrt(p*(p-a)*(p-b)*(p-c)); „ f10: ha = b*sin(C); „ f11: hb = a*sin(C); „ f12: hc = b*sin(A) „ . Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  62. „ Caùc troïng soá: „ w(f1) = 2; „ w(f2) = w(f3) = w(f4) = 2*c2 + 2; „ w(f5) = 3; „ w(f6) = w(f7) = w(f8) = 2; „ w(f9) = c1 + 6; „ w(f10) = w(f11) = w(f12) = c2 + 1. „ Trong ñoù c1 vaø c2 laø caùc haèng soá döông vôùi c1 >> 1 vaø c2 >> 1. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  63. „ Xeùt baøi toaùn H G vôùi H = a, b, B vaø G = S . „ Treân maïng suy dieãn (A, D), neáu aùp duïng thuaät toaùn tìm lôøi giaûi ñaõ neâu ta coù theå tìm ñöôïc moät lôøi giaûi S = f2, f1, f3, f5, f9 . „ Treân maïng suy dieãn coù troïng soá (A, D, w) lôøi giaûi S coù troïng soá laø w(S) = 4*c2 + c1 + 15. „ Aùp duïng thuaät toaùn tìm lôøi giaûi toái öu treân maïng (A, D, w) ta coù theå tìm ñöôïc moät lôøi giaûi S’ = f2, f1, f10, f6 vôùi troïng soá laø w(S’) = 3*c2 + 7. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  64. V. Taäp hôïp sinh 5.1 Khaùi nieäm taäp hôïp sinh 5.2 Tìm taäp hôïp sinh 5.3 Boå sung giaû thieát Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  65. Giôùi thieäu: ° Vieäc khaûo saùt veà taäp hôïp sinh cuõng laø moät vaán ñeà ñöôïc ñaët ra moät caùch töï nhieân treân maïng suy dieãn nhaèm tìm ra moät taäp hôïp toái thieåu caùc thuoäc tính vaø caùc luaät suy dieãn sinh ra taát caû caùc thuoäc tính khaùc. ° Khaùi nieäm taäp hôïp sinh vaø phöông phaùp tìm moät taäp hôïp sinh treân moät maïng suy dieãn laø cô sôû cho vieäc phaùt trieån caùc thuaät toaùn giaûi quyeát vaán ñeà kieåm ñònh giaû thieát cuûa baøi toaùn suy dieãn. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  66. 5.1 Khaùi nieäm taäp hôïp sinh ª Ñònh nghóa: „ Cho (A, D) laø moät maïng suy dieãn. Moät taäp thuoäc tính S A ñöôïc goïi laø moät taäp hôïp sinh cuûa maïng suy dieãn khi ta coù bao ñoùng cuûa S treân maïng laø A, nghóa laø = A. „ Ví duï: „ Xeùt maïng suy dieãn (A, D) vôùi „ A = a, b, c, A, B, C, R, p, S „ goàm caùc bieán soá thöïc döông. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  67. „ D laø taäp hôïp caùc luaät suy dieãn töông öùng cuûa caùc quan heä suy dieãn theå hieän bôûi caùc coâng thöùc sau ñaây: „ f1: A + B + C = ; f2: a/sin(A) = 2*R ; „ f3: b/sin(B) = 2*R ; f4: c/sin(C) = 2*R ; „ f5: a + b + c = 2*p ; f6: a2 = b2 + c2 ‟ 2*b*c*cos(A) ; „ f7: b2 = a2 + c2 ‟ 2*a*c*cos(B) ; „ f8: c2 = b2 + a2 ‟ 2*b*a*cos(C) ; „ f9: S = sqrt(p*(p-a)*(p-b)*(p-c)) Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  68. „ Maïng suy dieãn naày coù moät taäp hôïp sinh laø „ T = a, A, B „ vaø töø T ta suy ra ñöôïc D nhôø caùc luaät suy dieãn sau: „ A, a R; „ A, B C; „ R, C c; „ R, B b; „ a, b, c p; „ a, b, c, p S Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  69. 5.2 Tìm taäp hôïp sinh ª Ta coù theå tìm moät taäp hôïp sinh baèng phöông phaùp thöû daàn. Tuy nhieân ôû ñaây seõ trình baøy caùch tìm moät taäp hôïp sinh khoâng taàm thöôøng vôùi soá phaàn töû caøng ít caøng toát. ª Phöông phaùp: „ thieát laäp moät “bieåu ñoà (hay ñoà thò) phaân caáp” cuûa moät maïng suy dieãn. „ Khoâng laøm maát tính toång quaùt ta coù theå giaû söû caùc luaät suy dieãn coù phaàn keát luaän goàm 1 phaàn töû. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  70. Ñònh nghóa: „ Cho moät maïng suy dieãn (A, D) maø moãi luaät suy dieãn coù phaàn keát luaän goàm 1 phaàn töû. Ta xaây döïng moät ñoà thò ñònh höôùng Graph(A, D) nhö sau: „ Taäp hôïp ñænh goàm taát caû caùc thuoäc tính vaø taát caû caùc luaät suy dieãn, töùc laø A D. „ ÖÙng vôùi moãi luaät r : hypothesis(r) goal(r), thieát laäp moät taäp hôïp edges(r) goàm taát caû caùc cung ñònh höôùng (x, r) vaø (r, y) thoûa x hypothesis(r) vaø y goal(r). Taäp hôïp caùc caïnh cuûa ñoà thò Graph(A, D) laø hôïp cuûa taát caû caùc taäp hôïp edges(r) vôùi r chaïy trong taäp D. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  71. „ Trong tröôøng hôïp treân ñoà thò Graph(A, D) ta coù degin(x) 1 vôùi moïi x A, thì ta coù theå hieåu ngaàm caùc ñænh thuoäc D vaø xeùt moät ñoà thò thu goïn GraphD (A) goàm: ° Taäp hôïp ñænh laø taäp hôïp caùc thuoäc tính A. ° Taäp hôïp caïnh goàm taát caû caùc cung (x,y) thoûa maõn ñieàu kieän: Coù (duy nhaát) moät luaät r sao cho goal(r) = y vaø x hypotheis(r). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  72. Ñònh nghóa: „ Ta goïi moät ñoà thò ñònh höôùng ñôn giaûn khoâng coù chu trình laø moät bieåu ñoà phaân caáp (hay moät ñoà thò phaân caáp). Ñænh x cuûa ñoà thò maø khoâng coù cung höôùng tôùi seõ ñöôïc goïi laø ñænh möùc 0, vaø ta vieát level(x) = 0. Ñoái vôùi caùc ñænh x khaùc, ta ñònh nghóa moät caùch qui naïp möùc cuûa noù vaø möùc cuûa ñænh naày coù theå ñöôïc cho bôûi: „ level(x) = max level(a) | coù cung noái a vôùi x + 1 „ taäp hôïp ñænh ñöôïc saép xeáp thaønh caùc möùc: möùc 0 cuûa laø taäp hôïp taát caû caùc ñænh möùc 0, möùc 1 laø taäp hôïp taát caû caùc ñænh möùc 1, v.v Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  73. Ví duï: „ Moät bieåu ñoà phaân caáp goàm 5 möùc Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  74. Meänh ñeà: „ Cho maïng suy dieãn (A, D). Giaû söû ñoà thò Graph(A, D) coù ñoà thò thu goïn GraphD(A). Khi aáy, neáu GraphD(A) laø moät ñoà thò phaân caáp thì taäp hôïp S = Level0 goàm taát caû caùc ñænh möùc 0 seõ cho ta moät taäp hôïp sinh cuûa maïng suy dieãn. „ Hôn nöõa trong tröôøng hôïp naày ta coøn coù: (1) S laø taäp hôïp sinh nhoû nhaát treân maïng suy dieãn. (2) Taäp D laø taäp hôïp luaät toái thieåu ñeå Level0 sinh ra A. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  75. Ñònh lyù: „ Cho maïng suy dieãn (A, D). ta coù: „ S A laø moät taäp hôïp sinh treân maïng suy dieãn khi vaø chæ khi coù moät taäp luaät D’ D sao cho Graph(A, D’) laø moät ñoà thò phaân caáp vaø S chöùa taäp hôïp caùc ñænh möùc 0 cuûa ñoà thò naày. „ Toàn taïi moät taäp luaät D’ D sao cho Graph(A, D’) laø moät ñoà thò phaân caáp. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  76. Thuaät toaùn: Tìm moät taäp hôïp sinh S trong maïng suy dieãn (A, D) baèng caùch xaây döïng moät maïng con (A’, D’) vôùi A’ = A vaø coù Graph(A’, D’) laø moät bieåu ñoà phaân caáp. „ Böôùc 1: A’ ; D’ ; S ; „ Böôùc 2: For r D do If not (attr(r) A’) then A’ A’ attr(r); D’ D’ r ; vaø Thöïc hieän vieäc caäp nhaät A’, D’ vaø S theo 2 tröôøng hôïp nhö sau: - Tröôøng hôïp 1: goal(r) A’ S S (hypothesis(r) - A’); Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  77. „ - Tröôøng hôïp 2: goal(r) A’ Loaïi r’ (neáu coù) trong D’ maø goal(r’) = goal(r); Loaïi moät soá luaät suy ra caùc x hypothesis(r) ñeå baûo ñaûm tính phaân caáp cuûa bieåu ñoà vaø caäp nhaät S. „ Böôùc 3: S S (A - A’); A’ A Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  78. 5.3 Boå sung giaû thieát ª xeùt vieäc boå sung giaû thieát cho baøi toaùn H G treân moät maïng suy dieãn (A, D) trong tröôøng hôïp baøi toaùn khoâng giaûi ñöôïc. ª YÙ töôûng chính ôû ñaây laø tieán haønh moät quaù trình xaây döïng moät bieåu ñoà phaân caáp vôùi taäp hôïp ñænh chöùa G vaø öu tieân cho vieäc ñaët caùc phaàn töû cuûa H ôû möùc 0. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  79. Thuaät toaùn: Cho maïng suy dieãn (A, D) vaø baøi toaùn H G khoâng giaûi ñöôïc (khoâng coù lôøi giaûi). Tìm H’ sao cho H H’ = vaø baøi toaùn (H H’) G laø giaûi ñöôïc. „ Böôùc 1: A’ H; D’ ; G G \ A’; „ Böôùc 2: while (G and D ) do 2.1: Laáy ra moät r töø D vaø caäp nhaät D. 2.2: if hypothesis(r) G or attr(r) A’ then Boû qua r 2.3: else Theâm r vaøo D’ vaø boå sung attr(r) vaøo A’vaø trong tröôøng hôïp goal(r) A’ thì loaïi ra r’ töø D’ (neáu coù) thoûa goal(r’) = goal(r) vaø loaïi moät soá luaät suy ra caùc x hypothesis(r) ñeå baûo ñaûm tính phaân caáp. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  80. „ 2.4: G G - A’ „ Böôùc 3: if G then Keát thuùc vôùi keát luaän:Vaán ñeà boå sung giaû thieát laø khoâng giaûi quyeát ñöôïc „ Böôùc 4: else (Trong tröôøng hôïp naày Graph(A’,D’) coù bieåu ñoà phaân caáp töông öùng laø GraphD’A’) Goïi L0 laø möùc 0 cuûa bieåu ñoà GraphD’A’. Ñaët: „ H’ L0 - H ª Thuaät toaùn tìm söï boå sung giaû thieát cho baøi suy dieãn ñöôïc neâu treân laø ñuùng vaø coù ñoä phöùc taïp laø O(|A|.|D|). Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  81. VI. Maïng Suy dieãn - Tính toaùn 6.1 Moâ hình 6.2 Giaûi baøi toaùn treân maïng suy dieãn-tính toaùn Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  82. 6.1 Moâ hình ª Ñònh nghóa: Moät maïng suy dieãn-tính toaùn goàm boán thaønh phaàn: ° Taäp hôïp A goàm caùc thuoäc tính. ° Taäp hôïp D goàm caùc luaät suy dieãn (hay caùc quan heä suy dieãn) treân caùc thuoäc tính. ° Taäp hôïp F goàm caùc coâng thöùc tính toaùn hay caùc thuû tuïc tính toaùn töông öùng vôùi caùc luaät suy dieãn. Söï töông öùng naày theå hieän bôûi moät aùnh xaï f : D F. ° Taäp hôïp R moät soá qui taéc hay ñieàu kieän raøng buoäc treân caùc thuoäc tính. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  83. „ Nhaän xeùt: „ Maïng suy dieãn tính toaùn goàm 4 taäp hôïp A, D, F vaø R nhö theá seõ ñöôïc kyù hieäu bôûi boä boán (A, D, F, R). Theo ñònh nghóa, ta coù (A, D) laø moät maïng suy dieãn vaø lôøi giaûi cho baøi toaùn H G treân maïng suy dieãn naày seõ xaùc ñònh caùc coâng thöùc hay caùc thuû tuïc tính toaùn caùc phaàn töû thuoäc G töø caùc phaàn töû thuoäc H. „ Ví duï: „ Kieán thöùc veà moät tam giaùc coù theå ñöôïc bieåu dieãn bôûi moät maïng suy dieãn tính toaùn (A, D, F, R) nhö sau: Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  84. „ A = A, B, C, a, b, c, R, S, p, laø taäp hôïp caùc yeáu toá cuûa moät tam giaùc goàm 3 goùc, 3 caïnh, baùn kính voøng troøn ngoaïi tieáp, dieän tích, nöûa chu vi, v.v „ D = r1: A, B C; r2: A, C B; r3: B, C A; r4: A, a R; r5: A, R a; r6: R, a A; r7: A, b, c a; „ F = f1: C = -A-B; f2: B = -A-C; f3: A = -B-C; f4: R = a/(2.sin(A)); f5: a = 2.R.sin(A); f6: A = arcsin(a/(2.R)); f7: a= b2+c2-2.b.c.cos(A); „ R = a+b > c; a+c > b; b+c > a; a > b A > B; a = b A = B; Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  85. 6.1 Giaûi toaùn treân Maïng Suy dieãn - Tính toaùn ª Treân moät maïng suy dieãn-tính toaùn ta coù theå giaûi quyeát caùc baøi toaùn suy dieãn tính toaùn chaúng haïn baøi toaùn giaûi tam giaùc hay baøi toaùn giaûi töù giaùc döïa treân vieäc giaûi baøi toaùn suy dieãn treân maïng suy dieãn. Hôn nöõa, caùc coâng thöùc hay thuû tuïc tính toaùn coù theå ñöôïc gaùn cho caùc troïng soá theå hieän ñoä phöùc taïp tính toaùn cuûa chuùng. Töø ñoù ta coù theå tìm ra ñöôïc nhöõng lôøi giaûi cho baøi toaùn suy dieãn tính toaùn vôùi chi phí tính toaùn thaáp nhaát döïa treân vieäc tìm lôøi giaûi toái öu treân maïng suy dieãn coù troïng soá. Ñaïi Hoïc Quoác Gia TP.HCM, 2001
  86. ª Ngoaøi ra, chuùng ta coù theå tìm ra ñöôïc caùc coâng thöùc töôøng minh qua caùc böôùc giaûi baøi toaùn vaø ruùt goïn caùc coâng thöùc döôùi daïng kyù hieäu. ª Keát hôïp ñieàu naày vôùi vieäc doø tìm nhöõng söï lieân heä suy dieãn giöõa caùc yeáu toá naøo ñoù maø ta quan taâm seõ cho ta moät phöông phaùp ñeå töï ñoäng tìm ra theâm nhöõng luaät suy dieãn vaø nhöõng coâng thöùc tính toaùn lieân quan ñeán caùc yeáu toá. Ñieàu naày coù yù nghóa nhö moät kyõ thuaät khaùm phaù tri thöùc. Ñaïi Hoïc Quoác Gia2001 TP.HCM,
  87. Söï Môû roäng & Phaùt trieån Moâ hình ª Moät söï môû roäng cuûa maïng suy dieãn tính toaùn laø cho pheùp xeùt theâm caùc quan heä khaùc vôùi caùc quan heä suy dieãn ‟ tính toaùn ôû ñaây, chaúng haïn caùc quan heä hình hoïc giöõa caùc ñoái töôïng hình hoïc ñieåm, ñoaïn, tia, goùc. Söï môû roäng naày seõ ñöôïc tích hôïp trong moät caáu truùc tröøu töôïng theo phöông phaùp laäp trình höôùng ñoái töôïng maø ta goïi laø moät ñoái töôïng tính toaùn. ª Khaùi nieäm veà ñoái töôïng tính toaùn seõ ñöôïc xaây döïng vaø ñöôïc xem xeùt trong moät moâ hình tri thöùc ñöôïc goïi laø moâ hình tri thöùc caùc ñoái töôïng tính toaùn. Ñaïi Hoïc Quoác Gia TP.HCM, 2001