Trí tuệ nhân tạo - Chương 2: Biểu diễn tri thức

99 trang vanle 1820

Download

Bạn đang xem 20 trang mẫu của tài liệu "Trí tuệ nhân tạo - Chương 2: Biểu diễn tri thức", để 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:

tri_tue_nhan_tao_chuong_2_bieu_dien_tri_thuc.pdf

Nội dung text: Trí tuệ nhân tạo - Chương 2: Biểu diễn tri thức

Chöông 2 BIEÅU DIEÃN TRI THÖÙC A. TOÅNG QUAN TRÍ TUEÄ NHAÂN TAÏO I. MÔÛ ÑAÀU Cheá taïo ñöôïc nhöõng coã maùy thoâng minh nhö con ngöôøi (thaäm chí thoâng minh hôn con ngöôøi) laø moät öôùc mô chaùy boûng cuûa loaøi ngöôøi töø haøng ngaøn naêm nay. Haún baïn ñoïc coøn nhôù ñeán nhaø khoa hoïc Alan Turing cuøng nhöõng ñoùng goùp to lôùn cuûa oâng trong lónh vöïc trí tueä nhaân taïo. Naêng löïc maùy tính ngaøy caøng maïnh meõ laø moät ñieàu kieän heát söùc thuaän lôïi cho trí tueä nhaân taïo. Ñieàu naøy cho pheùp nhöõng chöông trình maùy tính aùp duïng caùc thuaät giaûi trí tueä nhaân taïo coù khaû naêng phaûn öùng nhanh vaø hieäu quaû hôn tröôùc. Söï kieän maùy tính Deep Blue ñaùnh baïi ñaïi kieän töôùng côø vua theá giôùi Casparov laø moät minh chöùng huøng hoàn cho moät böôùc tieán daøi trong coâng cuoäc nghieân cöùu veà trí tueä nhaân taïo. Tuy coù theå ñaùnh baïi ñöôïc Casparov nhöng Deep Blue laø moät coã maùy chæ bieát ñaùnh côø ! Noù thaäm chí khoâng coù ñöôïc trí thoâng minh sô ñaúng cuûa moät ñöùa beù bieát leân ba nhö nhaän dieän ñöôïc nhöõng ngöôøi thaân, khaû naêng quan saùt - - 75
nhaän bieát theá giôùi, tình caûm thöông, gheùt Ngaønh trí tueä nhaân taïo ñaõ coù nhöõng böôùc tieán ñaùng keå, nhöng moät trí tueä nhaân taïo thöïc söï vaãn chæ coù trong nhöõng boä phim khoa hoïc giaû töôûng cuûa Hollywood. Vaäy thì taïi sao chuùng ta vaãn nghieân cöùu veà trí tueä nhaân taïo? Ñieàu naøy cuõng töông töï nhö öôùc mô cheá taïo vaøng cuûa caùc nhaø giaû kim thuaät thôøi Trung coå, tuy chöa thaønh coâng nhöng chính quaù trình nghieân cöùu ñaõ laøm saùng toû nhieàu vaán ñeà. Maëc duø muïc tieâu toái thöôïng cuûa ngaønh TTNT laø xaây döïng moät chieác maùy coù naêng löïc tö duy töông töï nhö con ngöôøi nhöng khaû naêng hieän taïi cuûa taát caû caùc saûn phaåm TTNT vaãn coøn raát khieâm toán so vôùi muïc tieâu ñaõ ñeà ra. Tuy vaäy, ngaønh khoa hoïc môùi meû naøy vaãn ñang tieán boä moãi ngaøy vaø ñang toû ra ngaøy caøng höõu duïng trong moät soá coâng vieäc ñoøi hoûi trí thoâng minh cuûa con ngöôøi. Hình aûnh sau seõ giuùp baïn hình dung ñöôïc tình hình cuûa ngaønh trí tueä nhaân taïo. Caùc maïch ñieän töû Maùy tính trí tueä luaän lyù ñôn giaûn nhaân taïo ngaøy nay Thaáp Cao Baät/Taét caùc Maùy tính tieâu Maùy tính trí Con coâng taéc chuaån tueä nhaân taïo ngöôøi Hình 2.1 trong töông lai 76 - -
Tröôùc khi böôùc vaøo tìm hieåu veà trí tueä nhaân taïo, chuùng ta haõy nhaéc laïi moät ñònh nghóa ñöôïc nhieàu nhaø khoa hoïc chaáp nhaän. Muïc tieâu cuûa ngaønh khoa hoïc trí tueä nhaân taïo ? Taïo ra nhöõng chieác maùy tính coù khaû naêng nhaän thöùc, suy luaän vaø phaûn öùng. Nhaän thöùc ñöôïc hieåu laø khaû naêng quan saùt, hoïc hoûi, hieåu bieát cuõng nhö nhöõng kinh nghieäm veà theá giôùi xung quanh. Quaù trình nhaän thöùc giuùp con ngöôøi coù tri thöùc. Suy luaän laø khaû naêng vaän duïng nhöõng tri thöùc saün coù ñeå phaûn öùng vôùi nhöõng tình huoáng hay nhöõng vaán ñeà - baøi toaùn gaëp phaûi trong cuoäc soáng. Nhaän thöùc vaø suy luaän ñeå töø ñoù ñöa ra nhöõng phaûn öùng thích hôïp laø ba haønh vi coù theå noùi laø ñaëc tröng cho trí tueä cuûa con ngöôøi. (Dó nhieân coøn moät yeáu toá nöõa laø tình caûm. Nhöng chuùng ta seõ khoâng ñeà caäp ñeán ôû ñaây!). Do ñoù, cuõng khoâng coù gì ngaïc nhieân khi muoán taïo ra moät chieác maùy tính thoâng minh, ta caàn phaûi trang bò cho noù nhöõng khaû naêng naøy. Caû ba khaû naêng naøy ñeàu caàn ñeán moät yeáu toá cô baûn laø tri thöùc. Döôùi goùc nhìn cuûa taäp saùch naøy, xaây döïng trí tueä nhaân taïo laø tìm caùch bieåu dieãn tri thöùc, tìm caùch vaän duïng tri thöùc ñeå giaûi quyeát vaán ñeà vaø tìm caùch boå sung tri - - 77
thöùc baèng caùch “phaùt hieän” tri thöùc töø caùc thoâng tin saün coù (maùy hoïc). II. THOÂNG TIN, DÖÕ LIEÄU VAØ TRI THÖÙC Tri thöùc laø moät khaùi nieäm raát tröøu töôïng. Do ñoù, chuùng ta seõ khoâng coá gaéng ñöa ra moät ñònh nghóa hình thöùc chính xaùc ôû ñaây. Thay vaøo ñoù, chuùng ta haõy cuøng nhau caûm nhaän khaùi nieäm “tri thöùc” baèng caùch so saùnh noù vôùi hai khaùi nieäm khaùc laø thoâng tin vaø döõ lieäu. Nhaø baùc hoïc noåi tieáng Karan Sing ñaõ töøng noùi raèng “Chuùng ta ñang ngaäp chìm trong bieån thoâng tin nhöng laïi ñang khaùt tri thöùc”. Caâu noùi naøy laøm noåi baät söï khaùc bieät veà löôïng laãn veà chaát giöõa hai khaùi nieäm thoâng tin vaø tri thöùc. Trong ngöõ caûnh cuûa ngaønh khoa hoïc maùy tính, ngöôøi ta quan nieäm raèng döõ lieäu laø caùc con soá, chöõ caùi, hình aûnh, aâm thanh maø maùy tính coù theå tieáp nhaän vaø xöû lyù. Baûn thaân döõ lieäu thöôøng khoâng coù yù nghóa ñoái vôùi con ngöôøi. Coøn thoâng tin laø taát caû nhöõng gì maø con ngöôøi coù theå caûm nhaän ñöôïc moät caùch tröïc tieáp thoâng qua caùc giaùc quan cuûa mình (khöùu giaùc, vò giaùc, thính giaùc, xuùc giaùc, thò giaùc vaø giaùc quan thöù 6) hoaëc giaùn tieáp thoâng qua caùc phöông tieän kyõ thuaät nhö tivi, radio, cassette, Thoâng tin ñoái vôùi con ngöôøi luoân coù moät yù nghóa nhaát ñònh naøo ñoù. Vôùi phöông tieän maùy tính (maø cuï theå laø caùc thieát bò ñaàu ra), con ngöôøi 78 - -
seõ tieáp thu ñöôïc moät phaàn döõ lieäu coù yù nghóa ñoái vôùi mình. Neáu so veà löôïng, döõ lieäu thöôøng nhieàu hôn thoâng tin. TRI THÖÙC Möùc ñoä tröøu töôïng THOÂNG TIN DÖÕ LIEÄU Soá löôïng Hình 2.2 Cuõng coù theå quan nieäm thoâng tin laø quan heä giöõa caùc döõ lieäu. Caùc döõ lieäu ñöôïc saép xeáp theo moät thöù töï hoaëc ñöôïc taäp hôïp laïi theo moät quan heä naøo ñoù seõ chöùa ñöïng thoâng tin. Neáu nhöõng quan heä naøy ñöôïc chæ ra moät caùch roõ raøng thì ñoù laø caùc tri thöùc. Chaúng haïn : Trong toaùn hoïc : Baûn thaân töøng con soá rieâng leû nhö 1, 1, 3, 5, 2, 7, 11 laø caùc döõ lieäu. Tuy nhieân, khi ñaët chuùng laïi vôùi nhau theo traät töï nhö döôùi ñaây thì giöõa chuùng ñaõ baét ñaàu coù moät moái lieân heä Döõ lieäu : 1, 1, 2, 3, 5, 8, 13, 21, 34 - - 79
Moái lieân heä naøy coù theå ñöôïc bieåu dieãn baèng coâng thöùc sau : Un = Un-1 + Un-2. Coâng thöùc neâu treân chính laø tri thöùc. Trong vaät lyù : Baûn sau ñaây cho chuùng ta bieát soá ño veà ñieän trôû (R), ñieän theá (U) vaø cöôøng ñoä doøng ñieän (I) trong moät maïch ñieän. I U R 5 10 2 2.5 20 8 4 12 3 7.3 14.6 2 Baûn thaân nhöõng con soá trong caùc coät cuûa baûn treân khoâng coù maáy yù nghóa neáu ta taùch rôøi chuùng ta. Nhöng khi ñaët keá nhau, chuùng ñaõ cho thaáy coù moät söï lieân heä naøo ñoù. Vaø moái lieân heä naøy coù theå ñöôïc dieãn taû baèng coâng thöùc ñôn giaûn sau : U I R Coâng thöùc naøy laø tri thöùc. 80 - -
Trong cuoäc soáng haøng ngaøy : Haèng ngaøy, ngöôøi noâng daân vaãn quan saùt thaáy caùc hieän töôïng naéng, möa, raâm vaø chuoàn chuoàn bay. Raát nhieàu laàn quan saùt, hoï ñaõ coù nhaän xeùt nhö sau : Chuoàn chuoàn bay thaáp thì möa, Bay cao thì naéng, bay vöøa thì raâm. Lôøi nhaän xeùt treân laø tri thöùc. Coù quan ñieåm treân cho raèng chæ nhöõng moái lieân heä töôøng minh (coù theå chöùng minh ñöôïc) giöõa caùc döõ lieäu môùi ñöôïc xem laø tri thöùc. Coøn nhöõng moái quan heä khoâng töôøng minh thì khoâng ñöôïc coâng nhaän. ÔÛ ñaây, ta cuõng coù theå quan nieäm raèng, moïi moái lieân heä giöõa caùc döõ lieäu ñeàu coù theå ñöôïc xem laø tri thöùc, bôûi vì, nhöõng moái lieân heä naøy thöïc söï toàn taïi. Ñieåm khaùc bieät laø chuùng ta chöa phaùt hieän ra noù maø thoâi. Roõ raøng raèng “duø sao thì traùi ñaát cuõng vaãn xoay quanh maët trôøi” duø tri thöùc naøy coù ñöôïc Galileâ phaùt hieän ra hay khoâng! Nhö vaäy, so vôùi döõ lieäu thì tri thöùc coù soá löôïng ít hôn raát nhieàu. Thuaät ngöõ ít ôû ñaây khoâng chæ ñôn giaûn laø moät daáu nhoû hôn bình thöôøng maø laø söï keát tinh hoaëc coâ ñoïng laïi. Baïn haõy hình dung döõ lieäu nhö laø nhöõng ñieåm treân maët phaúng coøn tri thöùc chính laø phöông trình cuûa ñöôøng cong noái taát caû nhöõng ñieåm naøy laïi. Chæ caàn moät phöông trình ñöôøng cong ta coù theå bieåu dieãn ñöôïc voâ soá ñieåm! Cuõng vaäy, chuùng ta caàn coù nhöõng kinh nghieäm, nhaän xeùt töø haøng ñoáng soá lieäu thoáng keâ, neáu khoâng, chuùng ta seõ - - 81
ngaäp chìm trong bieån thoâng tin nhö nhaø baùc hoïc Karan Sing ñaõ caûnh baùo! Ngöôøi ta thöôøng phaân loaïi tri thöùc ra laøm caùc daïng nhö sau. Tri thöùc söï kieän : laø caùc khaúng ñònh veà moät söï kieän, khaùi nieäm naøo ñoù (trong moät phaïm vi xaùc ñònh). Caùc ñònh luaät vaät lyù, toaùn hoïc thöôøng ñöôïc xeáp vaøo loaïi naøy. (Chaúng haïn : maët trôøi moïc ôû ñaèng ñoâng, tam giaùc ñeàu coù ba goùc 600 ) Tri thöùc thuû tuïc : thöôøng duøng ñeå dieãn taû phöông phaùp, caùc böôùc caàn tieán haønh, trình töø hay ngaén goïn laø caùch giaûi quyeát moät vaán ñeà. Thuaät toaùn, thuaät giaûi laø moät daïng cuûa tri thöùc thuû tuïc. Tri thöùc moâ taû : cho bieát moät ñoái töôïng, söï kieän, vaán ñeà, khaùi nieäm ñöôïc thaáy, caûm nhaän, caáu taïo nhö theá naøo (moät caùi baøn thöôøng coù boán chaân, con ngöôøi coù hai tay, hai maét ) Tri thöùc heuristic : laø moät daïng tri thöùc caûm tính. Caùc tri thöùc thuoäc loaïi naøy thöôøng coù daïng öôùc löôïng, phoûng ñoaùn, vaø thöôøng ñöôïc hình thaønh thoâng qua kinh nghieäm. 82 - -
Treân thöïc teá, raát hieám coù moät trí tueä maø khoâng caàn ñeán tri thöùc (lieäu coù theå coù moät ñaïi kieän töôùng côø vua maø khoâng bieát ñaùnh côø hoaëc khoâng bieát caùc theá côø quan troïng khoâng?). Tuy tri thöùc khoâng quyeát ñònh söï thoâng minh (ngöôøi bieát nhieàu ñònh lyù toaùn hôn chöa chaéc ñaõ giaûi toaùn gioûi hôn!) nhöng noù laø moät yeáu toá cô baûn caáu thaønh trí thoâng minh. Chính vì vaäy, muoán xaây döïng moät trí thoâng minh nhaân taïo, ta caàn phaûi coù yeáu toá cô baûn naøy. Töø ñaây ñaët ra vaán ñeà ñaàu tieân laø Caùc phöông phaùp ñöa tri thöùc vaøo maùy tính ñöôïc goïi laø bieåu dieãn tri thöùc. III. THUAÄT TOAÙN – MOÄT PHÖÔNG PHAÙP BIEÅU DIEÃN TRI THÖÙC? Tröôùc khi traû lôøi caâu hoûi treân, baïn haõy thöû nghó xem, lieäu moät chöông trình giaûi phöông trình baäc hai coù theå ñöôïc xem laø moät chöông trình coù tri thöùc hay khoâng? Coù chöù ! Vaäy thì tri thöùc naèm ôû ñaâu? Tri thöùc veà giaûi phöông trình baäc hai thöïc chaát ñaõ ñöôïc maõ hoùa döôùi daïng caùc caâu leänh if then else trong chöông trình. Moät caùch toång quaùt, coù theå khaúng ñònh laø taát caû caùc chöông trình maùy tính ít nhieàu ñeàu ñaõ coù tri thöùc. Ñoù chính laø tri thöùc cuûa laäp trình vieân ñöôïc chuyeån thaønh caùc caâu leänh cuûa chöông trình. Baïn seõ thaéc maéc “nhö vaäy taïi sao ñöa tri thöùc vaøo maùy tính laïi laø moät vaán ñeà ? (vì töø tröôùc tôùi giôø chuùng ta ñaõ, ñang vaø seõ tieáp tuïc laøm nhö theá maø?)”. Ñuùng nhö theá thaät, nhöng vaán ñeà naèm ôû choã, caùc tri thöùc trong nhöõng chöông - - 83
trình truyeàn thoáng laø nhöõng tri thöùc “cöùng”, nghóa laø noù khoâng theå ñöôïc theâm vaøo hay ñieàu chænh moät khi chöông trình ñaõ ñöôïc bieân dòch. Muoán ñieàu chænh thì chuùng ta phaûi tieán haønh söûa laïi maõ nguoàn cuûa chöông trình (roài sau ñoù bieân dòch laïi). Maø thao taùc söûa chöông trình thì chæ coù nhöõng laäp trình vieân môùi coù theå laøm ñöôïc. Ñieàu naøy seõ laøm giaûm khaû naêng öùng duïng chöông trình (vì ña soá ngöôøi duøng bình thöôøng ñeàu khoâng bieát laäp trình). Baïn thöû nghó xem, vôùi moät chöông trình hoã trôï ra quyeát ñònh (nhö ñaàu tö coå phieáu, ñaàu tö baát ñoäng saûn chaúng haïn), lieäu ngöôøi duøng coù caûm thaáy thoaûi maùi khoâng khi muoán ñöa vaøo chöông trình nhöõng kieán thöùc cuûa mình thì anh ta phaûi choïn moät trong hai caùch laø (1) töï söûa laïi maõ chöông trình!? (2) tìm taùc giaû cuûa chöông trình ñeå nhôø ngöôøi naøy söûa laïi!?. Caû hai thao taùc treân ñeàu khoâng theå chaáp nhaän ñöôïc ñoái vôùi baát kyø ngöôøi duøng bình thöôøng naøo. Hoï caàn coù moät caùch naøo ñoù ñeå chính hoï coù theå ñöa tri thöùc vaøo maùy tính moät caùch deã daøng, thuaän tieän gioáng nhö hoï ñang ñoái thoaïi vôùi moät con ngöôøi. Ñeå laøm ñöôïc ñieàu naøy, chuùng ta caàn phaûi “meàm” hoùa caùc tri thöùc ñöôïc bieåu dieãn trong maùy tính. Xeùt cho cuøng, moïi chöông trình maùy tính ñeàu goàm hai thaønh phaàn laø caùc maõ leänh vaø döõ lieäu. Maõ leänh ñöôïc ví nhö laø phaàn cöùng cuûa chöông trình coøn döõ lieäu ñöôïc xem laø phaàn meàm (vì noù coù theå ñöôïc thay ñoåi bôûi ngöôøi duøng). Do ñoù, “meàm” hoùa tri 84 - -
thöùc cuõng ñoàng nghóa vôùi vieäc tìm caùc phöông phaùp ñeå coù theå bieåu dieãn caùc loaïi tri thöùc cuûa con ngöôøi baèng caùc caáu truùc döõ lieäu maø maùy tính coù theå xöû lyù ñöôïc. Ñaây cuõng chính laø yù nghóa cuûa thuaät ngöõ “bieåu dieãn tri thöùc”. Baïn caàn phaûi bieát raèng, ít ra laø cho ñeán thôøi ñieåm baïn ñang ñoïc cuoán saùch naøy, con ngöôøi vaãn chöa theå tìm ra moät kieåu bieåu dieãn toång quaùt cho moïi loaïi tri thöùc! Ñeåå laøm vaán ñeà maø chuùng ta ñang baøn luaän trôû neân saùng toû hôn. Chuùng ta haõy xem xeùt moät soá baøi toaùn trong phaàn tieáp theo. IV. LAØM QUEN VÔÙI CAÙCH GIAÛI QUYEÁT VAÁN ÑEÀ BAÈNG CAÙCH CHUYEÅN GIAO TRI THÖÙC CHO MAÙY TÍNH Baøi toaùn 1 : Cho hai bình roãng X vaø Y coù theå tích laàn löôït laø VX vaø VY, haõy duøng hai bình naøy ñeå ñong ra z lít nöôùc (z <= min(VX,VY)). Baøi toaùn 2 : Cho bieát moät soá yeáu toá cuûa tam giaùc (nhö chieàu daøi caïnh vaø goùc ). Haõy tính caùc yeáu toá coøn laïi. Baøi toaùn 3 : Tính dieän tích phaàn giao cuûa caùc hình hình hoïc cô baûn. - - 85
Hai baøi toaùn ñaàu laø hai baøi toaùn khaù tieâu bieåu, thöôøng ñöôïc duøng ñeå minh hoïa cho neùt ñeïp cuûa phöông phaùp giaûi quyeát vaán ñeà baøi toaùn baèng caùch chuyeån giao tri thöùc cho maùy tính. Neáu söû duïng thuaät toaùn thoâng thöôøng, chuùng ta thöôøng chæ giaûi ñöôïc moät soá tröôøng hôïp cuï theå cuûa caùc baøi toaùn naøy. Thaäm chí, nhieàu ngöôøi khi môùi tieáp caän vôùi hai baøi toaùn naøy coøn khoâng tin laø noù coù theå hoaøn toaøn ñöôïc giaûi moät caùch toång quaùt bôûi maùy tính! Baøi toaùn soá 3 laø moät minh hoïa ñeïp maét cho kyõ thuaät giaûi quyeát vaán ñeà “vó moâ”, nghóa laø ta chæ caàn moâ taû caùc böôùc giaûi quyeát ôû möùc toång quaùt cho maùy tính maø khoâng caàn ñi vaøo caøi ñaët cuï theå. Baøi toaùn 1 seõ ñöôïc giaûi quyeát baèng caùch söû duïng caùc luaät daãn xuaát (luaät sinh). Baøi toaùn 2 seõ ñöôïc giaûi quyeát baèng maïng ngöõ nghóa vaø baøi toaùn 3 seõ giaûi quyeát baèng coâng cuï frame. ÔÛ ñaây chuùng ta cuøng nhau tìm hieåu caùch giaûi baøi toaùn ñaàu tieân. Hai baøi toaùn keá tieáp seõ ñöôïc giaûi quyeát laàn löôït ôû caùc muïc sau. Vôùi moät tröôøng hôïp cuï theå cuûa baøi toaùn 1, nhö VX = 5 vaø VY = 7 vaø z = 4. Sau moät thôøi gian tính toaùn, baïn coù theå seõ ñöa ra moät quy trình ñoå nöôùc ñaïi loaïi nhö : - Muùc ñaày bình 7 - Truùt heát qua bình 5 cho ñeán khi 5 ñaày. - Ñoå heát nöôùc trong bình 5 - Ñoå heát nöôùc coøn laïi töø bình 7 sang bình 5 86 - -
- Muùc ñaày bình 7 - Truùt heát qua bình 5 cho ñeán khi bình 5 ñaày. - Phaàn coøn laïi chính laø soá nöôùc caàn ñong. Tuy nhieân, vôùi nhöõng soá lieäu khaùc, baïn phaûi “maøy moø” laïi töø ñaàu ñeå tìm ra quy trình ñoå nöôùc. Cöù theá, moãi moät tröôøng hôïp seõ coù moät caùch ñoå nöôùc hoaøn toaøn khaùc nhau. Nhö vaäy, neáu coù moät ai ñoù yeâu caàu baïn ñöa ra moät caùch laøm toång quaùt thì chính baïn cuõng seõ luùng tuùng (dó nhieân, ngoaïi tröø tröôøng hôïp baïn ñaõ bieát tröôùc caùch giaûi theo tri thöùc maø chuùng ta saép söûa tìm hieåu ôû ñaây!). Ñeán ñaây, baïn haõy bình taâm kieåm laïi caùch thöùc baïn tìm kieám lôøi giaûi cho moät tröôøng hôïp cuï theå. Vì chöa tìm ra moät quy taéc cuï theå naøo, baïn seõ thöïc hieän moät loaït caùc thao taùc “caûm tính” nhö ñong ñaày moät bình, truùt moät bình naøy sang bình kia, ñoå heát nöôùc trong moät bình ra vöøa laøm vöøa nhaåm tính xem caùch laøm naøy coù theå ñi ñeán keát quaû hay khoâng. Sau nhieàu laàn thí nghieäm, raát coù theå baïn seõ ruùt ra ñöôïc moät soá kinh nghieäm nhö “khi bình 7 ñaày nöôùc maø bình 5 chöa ñaày thì haõy ñoå noù sang bình 5 cho ñeán khi bình 5 ñaày” Vaäy thì taïi sao baïn laïi khoâng thöû “truyeàn” nhöõng kinh nghieäm naøy cho maùy tính vaø ñeå cho maùy tính “maøy moø” tìm caùc thao taùc cho chuùng ta? Ñieàu naøy hoaøn toaøn coù lôïi, vì maùy tính coù khaû naêng “maøy moø” hôn haún chuùng ta! Neáu nhöõng “kinh nghieäm” maø chuùng ta cung caáp cho maùy tính khoâng giuùp chuùng ta tìm ñöôïc lôøi giaûi, chuùng - - 87
ta seõ thay theá noù baèng nhöõng kinh nghieäm khaùc vaø laïi tieáp tuïc ñeå maùy tính tìm kieám lôøi giaûi! Chuùng ta haõy phaùt bieåu laïi baøi toaùn moät caùch hình thöùc hôn. Khoâng laøm maát tính toång quaùt, ta luoân coù theå giaû söû raèng VX < VY. Goïi löôïng nöôùc chöùa trong bình X laø x (0<=x<=VX) Goïi löôïng nöôùc chöùa trong bình Y laø y (0<=y<=VY) Nhö vaäy, ñieàu kieän keát thuùc cuûa baøi toaùn seõ laø : x = z hoaëc y = z Ñieàu kieän ñaàu cuûa baøi toaùn laø : x = 0 vaø y = 0 Quaù trình giaûi ñöôïc thöïc hieän baèng caùch xeùt laàn löôït caùc luaät sau, luaät naøo thoûa maõn thì seõ ñöôïc aùp duïng. Luùc naøy, caùc luaät chính laø caùc “kinh nghieäm” hay tri thöùc maø ta ñaõ chuyeån giao cho maùy tính. Sau khi aùp duïng luaät, traïng thaùi cuûa baøi toaùn seõ thay ñoåi, ta laïi tieáp tuïc xeùt caùc luaät keá tieáp, neáu heát luaät, quay trôû laïi luaät ñaàu tieân. Quaù trình tieáp dieãn cho ñeán khi ñaït ñöôïc ñieàu kieän keát thuùc cuûa baøi toaùn. Ba luaät naøy ñöôïc moâ taû nhö sau : 88 - -
(L1) Neáu bình X ñaày thì ñoå heát nöôùc trong bình X ñi. (L2) Neáu bình Y roãng thì ñoå ñaày nöôùc vaøo bình Y. (L3) Neáu bình X khoâng ñaày vaø bình Y khoâng roãng thì haõy truùt nöôùc từ bình Y sang bình X (cho ñeán khi bình X ñaày hoaëc bình Y heát nöôùc). Treân thöïc teá, luùc ñaàu ñeå giaûi tröôøng hôïp toång quaùt cuûa baøi toaùn naøy, ngöôøi ta ñaõ duøng ñeán hôn 15 luaät (kinh nghieäm) khaùc nhau. Tuy nhieân, sau naøy, ngöôøi ta ñaõ ruùt goïn laïi chæ coøn ba luaät nhö treân. Baïn coù theå deã daøng chuyeån ñoåi caùch giaûi naøy thaønh chöông trình nhö sau : x := 0; y := 0; WHILE ( (x z) ) DO BEGIN IF (x = Vx) THEN x := 0; IF (y = 0) THEN (y:= Vy); IF (y > 0) THEN BEGIN k:= min(Vx - x, y); x := x + k; y := y - k; END; END; Thöû “chaïy” chöông trình treân vôùi soá lieäu cuï theå laø : VX = 3, VY = 4 vaø z = 2 Ban ñaàu : x = 0, y = 0 Luaät (L2) -> x = 0, y = 4 Luaät (L3) -> x = 3, y = 1 - - 89
Luaät (L1) -> x = 0, y = 1 Luaät (L3) -> x = 1, y = 0 Luaät (L2) -> x = 1, y = 4 Luaät (L3) -> x = 3, y = 2 Ba luaät maø chuùng ta ñaõ caøi ñaët trong chöông trình ôû treân ñöôïc goïi laø cô sôû tri thöùc. Coøn caùch thöùc tìm kieám lôøi giaûi baèng caùch duyeät tuaàn töï töøng luaät vaø aùp duïng noù ñöôïc goïi laø ñoäng cô suy dieãn. Chuùng ta seõ ñònh nghóa chính xaùc hai thuaät ngöõ naøy ôû cuoái muïc. Ngöôøi ta ñaõ chöùng minh ñöôïc raèng, baøi toaùn ñong nöôùc chæ coù lôøi giaûi khi soá nöôùc caàn ñong laø moät boäi soá cuûa öôùc soá chung lôùn nhaát cuûa theå tích hai bình. z = n USCLN(VX,VY) (vôùi n nguyeân döông) Caùch giaûi quyeát vaán ñeà theo kieåu naøy khaùc so vôùi caùch giaûi baèng thuaät toaùn thoâng thöôøng laø chuùng ta khoâng ñöa ra moät trình töï giaûi quyeát vaán ñeà cuï theå maø chæ ñöa ra caùc quy taéc chung chung (döôùi daïng caùc luaät), maùy tính seõ döïa vaøo ñoù (aùp duïng caùc luaät) ñeå töï xaây döïng moät quy trình giaûi quyeát vaán ñeà. Ñieàu naøy cuõng gioáng nhö vieäc chuùng ta giaûi toaùn baèng caùch ñöa ra caùc ñònh lyù, quy taéc lieân quan ñeán baøi toaùn maø khoâng caàn phaûi chæ ra caùch giaûi cuï theå. Vaäy thì ñieåm thuù vò naèm ôû ñieåm naøo? Baïn seõ coù theå caûm thaáy raèng chuùng ta vaãn ñang duøng tri thöùc “cöùng” ! (vì caùc tri thöùc vaãn laø caùc caâu leänh IF ñöôïc caøi saün trong chöông trình). Thöïc ra thì chöông trình cuûa chuùng ta ñaõ 90 - -
“meàm” hôn moät tí roài ñaáy. Neáu khoâng tin, caùc baïn haõy quan saùt phieân baûn keá tieáp cuûa chöông trình naøy. FUNCTION DK(L INTEGER):BOOLEAN; BEGIN CASE L OF 1 : DK := (x = Vx); 2: DK :=(y= 0); 3 : DK := (y>0); END; END; PROCEDURE ThiHanh(L INTEGER):BOOLEAN; BEGIN CASE L OF 1 : x := 0; 2: y := Vy; 3 : BEGIN k := min(Vx-x,y); x := x+k; y := y-k; END; END; END; CONST SO_LUAT = 3; BEGIN WHILE (x z) DO BEGIN FOR i:=1 TO SO_LUAT DO IF DK(L) THEN ThiHanh(L); END; END. Ñoaïn chöông trình chính cuõng thi haønh baèng caùch laàn löôït xeùt qua ba leänh IF nhö chöông trình ñaàu tieân. Tuy nhieân, ôû ñaây, bieåu thöùc ñieàu kieän ñöôïc thay theá baèng haøm DK vaø caùc haønh ñoäng öùng vôùi ñieàu kieän ñaõ ñöôïc thay theá - - 91
baèng thuû tuïc ThiHanh. Tính chaát “meàm” hôn cuûa chöông trình naøy theå hieän ôû choã, neáu muoán boå sung “tri thöùc”, ta chæ phaûi ñieàu chænh laïi caùc haøm DK vaø ThiHanh maø khoâng caàn phaûi söûa laïi chöông trình chính. Baây giôø haõy giaû söû raèng ta ñaõ coù haøm vaø thuû tuïc ñaëc bieät sau : FUNCTION GiaTriBool(DK : String) : BOOLEAN; PROCEDURE ThucHien(ThaoTac : String) ; Haøm GiaTriBool nhaän vaøo moät chuoãi ñieàu kieän, noù seõ phaân tích chuoãi, tính toaùn roài traû ra giaù trò BOOLEAN cuûa bieåu thöùc naøy. Ví duï : GiaTriBoolean(‘6<7’) seõ traû ra FALSE Thuû tuïc ThucHien cuõng nhaän vaøo moät chuoãi, noù cuõng seõ phaân tích chuoãi roài tieán haønh thöïc hieän nhöõng haønh ñoäng ñöôïc mieâu taû trong chuoãi naøy. Vôùi haøm vaø thuû tuïc naøy, chöông trình cuûa chuùng ta seõ nhö sau : CONST SO_LUAT = 3; TYPE Luat RECORD DK : String; ThiHanh : String; END; 92 - -
DSLuat ARRAY [1 SO_LUAT] OF Luat; VAR CacLuat DSLuat; PROCEDURE KhoiDong; BEGIN CacLuat[1].DK := ‘x = Vx’; CacLuat[2].DK := ‘y = 0’; CacLuat[3].DK := ‘y>0’; 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 (x z) DO BEGIN FOR i:=1 TO SO_LUAT DO IF GiaTriBoolean(CacLuat[i].DK) THEN ThucHien(CacLuat[i].ThaoTac); END; END. Chuùng ta taïm cho raèng trong quaù trình chöông trình thi haønh, ta coù theå deã daøng thay ñoåi soá phaàn töû maûng CacLuat (caùc ngoân ngöõ laäp trình sau naøy nhö Visual C++, Delphi ñeàu cho pheùp ñieàu naøy). Vôùi chöông trình naøy, khi muoán söûa ñoåi “tri thöùc”, baïn chæ caàn thay ñoåi giaù trò maûng Luat laø xong. Tuy nhieân, ngöôøi duøng vaãn gaëp khoù khaên khi muoán boå sung hoaëc hieäu chænh tri thöùc. Hoï caàn phaûi nhaäp caùc chuoãi ñaïi loaïi nhö ‘x=0’ hoaëc ‘k:=min(Vx-x,y)’ Caùc chuoãi naøy, - - 93
tuy coù yù nghóa ñoái vôùi chöông trình nhöng vaãn coøn khaù xa laï ñoái vôùi ngöôøi duøng bình thöôøng. Chuùng ta caàn giaûm bôùt “khoaûng caùch” naøy laïi baèng caùch ñöa ra nhöõng chuoãi ñieàu kieän hoaëc thao taùc coù yù nghóa tröïc tieáp ñoái vôùi ngöôøi duøng. Chöông trình seõ coù chuyeån ñoåi laïi caùc ñieàu kieän vaø thao taùc naøy sang daïng phuø hôïp vôùi chöông trình. Ñeå laøm ñöôïc ñieàu treân. Chuùng ta caàn phaûi lieät keâ ñöôïc caùc traïng thaùi vaø thao taùc cô baûn cuûa baøi toaùn naøy. Sau ñaây laø moät soá traïng thaùi vaø thao taùc cô baûn. Traïng thaùi cô baûn Bình X ñaày, Bình X roãng, Bình X khoâng roãng, Bình X coù n lít nöôùc. Thao taùc Ñoå heát nöôùc trong bình, Ñoå ñaày nöôùc trong bình, Ñoå nöôùc töø bình A sang bình B cho ñeán khi B ñaày hoaëc A roãng. Löu yù raèng ta khoâng theå coù thao taùc “Ñoå n lít nöôùc töø A sang B” vì baøi toaùn ñaõ giaû ñònh raèng caùc bình ñeàu khoâng coù vaïch chia, hôn nöõa neáu ta bieát caùch ñoå n lít nöôùc töø A sang B thì lôøi giaûi baøi toaùn trôû thaønh quaù ñôn giaûn. “Muùc ñaày X” “Ñoå z lít nöôùc töø X sang Y” 94 - -
Vì ñaây laø moät baøi toaùn ñôn giaûn neân baïn coù theå deã nhaän thaáy raèng, caùc traïng thaùi cô baûn vaø thao taùc chaúng coù gì khaùc so vôùi caùc ñieàu kieän maø chuùng ta ñaõ ñöa ra. Keá tieáp, ta seõ vieát caùc ñoaïn chöông trình cho pheùp ngöôøi duøng nhaäp vaøo caùc luaät (daïng neáu thì ) ñöôïc hình thaønh töø caùc traïng thaùi vaø ñieàu kieän cô baûn naøy, ñoàng thôøi tieán haønh chuyeån sang daïng maùy tính coù theå xöû lyù ñöôïc nhö ôû ví duï treân. Chuùng ta seõ khoâng baøn ñeán vieäc caøi ñaët caùc ñoaïn chöông trình giao tieáp vôùi ngöôøi duøng ôû ñaây. Nhö vaäy, so vôùi chöông trình truyeàn thoáng (ñöôïc caáu taïo töø hai “chaát lieäu” cô baûn laø döõ lieäu vaø thuaät toaùn), chöông trình trí tueä nhaân taïo ñöôïc caáu taïo töø hai thaønh phaàn laø cô sôû tri thöùc (knowledge base) vaø ñoäng cô suy dieãn (inference engine). Cô sôû tri thöùc : laø taäp hôïp caùc tri thöùc lieân quan ñeán vaán ñeà maø chöông trình quan taâm giaûi quyeát. Ñoäng cô suy dieãn : laø phöông phaùp vaän duïng tri thöùc trong cô sôû tri thöùc ñeå giaûi quyeát vaán ñeà. - - 95
DÖÕ LIEÄU DÖÕ LIEÄU CÔ SÔÛ TRI THÖÙC THUAÄT ÑOÄNG CÔ SUY TOAÙN DIEÃN Neáu xeùt theo quan nieäm bieåu dieãn tri thöùc maø ta vöøa baøn luaän ôû treân thì cô sôû tri thöùc chæ laø moät daïng döõ lieäu ñaëc bieät vaø ñoäng cô suy dieãn cuõng chæ laø moät daïng cuûa thuaät toaùn ñaëc bieät maø thoâi. Tuy vaäy, coù theå noùi raèng, cô sôû tri thöùc vaø ñoäng cô suy dieãn laø moät böôùc tieán hoùa môùi cuûa döõ lieäu vaø thuaät toaùn cuûa chöông trình! Baïn coù theå hình dung ñoäng cô suy dieãn gioáng nhö moät loaïi ñoäng cô toång quaùt, ñöôïc chuaån hoùa coù theå duøng ñeå vaän haønh nhieàu loaïi xe maùy khaùc nhau vaø cô sôû tri thöùc chính laø loaïi nhieân lieäu ñaëc bieät ñeå vaän haønh loaïi ñoäng cô naøy ! 96 - -
NGÖÔØI DUØNG HEÄ THOÁNG GIAO TIEÁP NGÖÔØI DUØNG HEÄ THOÁNG THU NHAÄN & ÑOÄNG CÔ SUY TOÁI ÖU TRI THÖÙC DIEÃN CÔ SÔÛ TRI THÖÙC Cô sôû tri thöùc cuõng gaëp phaûi nhöõng vaán ñeà töông töï nhö nhöõng cô sôû döõ lieäu khaùc nhö söï truøng laép, thöøa, maâu thuaãn. Khi xaây döïng cô sôû tri thöùc, ta cuõng phaûi chuù yù ñeán nhöõng yeáu toá naøy. Nhö vaäy, beân caïnh vaán ñeà bieåu dieãn tri thöùc, ta coøn phaûi ñeà ra caùc phöông phaùp ñeå loaïi boû nhöõng tri thöùc truøng laép, thöøa hoaëc maâu thuaãn. Nhöõng thao taùc naøy seõ ñöôïc thöïc hieän trong quaù trình ghi nhaän tri thöùc vaøo heä thoáng. Chuùng ta seõ ñeà caäp ñeán nhöõng phöông phaùp naøy trong phaàn tìm hieåu veà caùc luaät daãn. Hình aûnh treân toùm taét cho chuùng ta thaáy caáu truùc chung nhaát cuûa moät chöông trình trí tueä nhaân taïo. - - 97
B. CAÙC PHÖÔNG PHAÙP BIEÅU DIEÃN TRI THÖÙC TREÂN MAÙY TÍNH V. LOGIC MEÄNH ÑEÀ Ñaây coù leõ laø kieåu bieåu dieãn tri thöùc ñôn giaûn nhaát vaø gaàn guõi nhaát ñoái vôùi chuùng ta. Meänh ñeà laø moät khaúng ñònh, moät phaùt bieåu maø giaù trò cuûa noù chæ coù theå hoaëc laø ñuùng hoaëc laø sai. Ví duï : phaùt bieåu “1 + 1 = 2” coù giaù trò ñuùng. phaùt bieåu “Moïi loaïi caù coù theå soáng treân bôø” coù giaù trò sai. Giaù trò cuûa meänh ñeà khoâng chæ phuï thuoäc vaøo baûn thaân meänh ñeà ñoù. Coù nhöõng meänh ñeà maø giaù trò cuûa noù luoân ñuùng hoaëc sai baát chaáp thôøi gian nhöng cuõng coù nhöõng meänh ñeà maø giaù trò cuûa noù laïi phuï thuoäc vaøo thôøi gian, khoâng gian vaø nhieàu yeáu toá khaùc quan khaùc. Chaúng haïn nhö meänh ñeà : “Con ngöôøi khoâng theå nhaûy cao hôn 5m vôùi chaân traàn” laø ñuùng khi ôû traùi ñaát, coøn ôû nhöõng haønh tinh coù löïc haáp daãn yeáu thì coù theå sai. Ta kyù hieäu meänh ñeà baèng nhöõng chöõ caùi latinh nhö a, b, c, Coù ba pheùp noái cô baûn ñeå taïo ra nhöõng meänh ñeà môùi töø nhöõng meänh ñeà cô sôû laø pheùp hoäi (), giao() vaø phuû ñònh (). 98 - -
Baïn ñoïc chaén haún ñaõ töøng söû duïng logic meänh ñeà trong chöông trình raát nhieàu laàn (nhö trong caáu truùc leänh IF THEN ELSE) ñeå bieåu dieãn caùc tri thöùc “cöùng” trong maùy tính ! Beân caïnh caùc thao taùc tính ra giaù trò caùc meänh ñeà phöùc töø giaù trò nhöõng meänh ñeà con, chuùng ta coù ñöôïc moät cô cheá suy dieãn nhö sau : Modus Ponens : Neáu meänh ñeà A laø ñuùng vaø meänh ñeà A B laø ñuùng thì giaù trò cuûa B seõ laø ñuùng. Modus Tollens : Neáu meänh ñeà A B laø ñuùng vaø meänh ñeà B laø sai thì giaù trò cuûa A seõ laø sai. Caùc pheùp toaùn vaø suy luaän treân meänh ñeà ñaõ ñöôïc ñeà caäp nhieàu ñeán trong caùc taøi lieäu veà toaùn neân chuùng ta seõ khoâng ñi vaøo chi tieát ôû ñaây. VI. LOGIC VÒ TÖØ Bieåu dieãn tri thöùc baèng meänh ñeà gaëp phaûi moät trôû ngaïi cô baûn laø ta khoâng theå can thieäp vaøo caáu truùc cuûa moät meänh ñeà. Hay noùi moät caùch khaùc laø meänh ñeà khoâng coù caáu truùc. Ñieàu naøy laøm haïn cheá raát nhieàu thao taùc suy luaän. Do ñoù, ngöôøi ta ñaõ ñöa vaøo khaùi nieäm vò töø vaø löôïng töø ( - vôùi moïi,  - toàn taïi) ñeå taêng cöôøng tính caáu truùc cuûa moät meänh ñeà. - - 99
Trong logic vò töø, moät meänh ñeà ñöôïc caáu taïo bôûi hai thaønh phaàn laø caùc ñoái töôïng tri thöùc vaø moái lieân heä giöõa chuùng (goïi laø vò töø). Caùc meänh ñeà seõ ñöôïc bieåu dieãn döôùi daïng : Vò töø ( , , , ) Nhö vaäy ñeå bieåu dieãn vò cuûa caùc traùi caây, caùc meänh ñeà seõ ñöôïc vieát laïi thaønh : Cam coù vò Ngoït Vò (Cam, Ngoït) Cam coù maøu Xanh  Maøu (Cam, Xanh) Kieåu bieåu dieãn naøy coù hình thöùc töông töï nhö haøm trong caùc ngoân ngöõ laäp trình, caùc ñoái töôïng tri thöùc chính laø caùc tham soá cuûa haøm, giaù trò meänh ñeà chính laø keát quaû cuûa haøm (thuoäc kieåu BOOLEAN). Vôùi vò töø, ta coù theå bieåu dieãn caùc tri thöùc döôùi daïng caùc meänh ñeà toång quaùt, laø nhöõng meänh ñeà maø giaù trò cuûa noù ñöôïc xaùc ñònh thoâng qua caùc ñoái töôïng tri thöùc caáu taïo neân noù. Chaúng haïn tri thöùc: “A laø boá cuûa B neáu B laø anh hoaëc em cuûa moät ngöôøi con cuûa A” coù theå ñöôïc bieåu dieãn döôùi daïng vò töø nhö sau : Boá (A, B) = Toàn taïi Z sao cho : Boá (A, Z) vaø (Anh(Z, B) hoaëc Anh(B,Z)) 100 - -
Trong tröôøng hôïp naøy, meänh ñeà Boá(A,B) laø moät meänh ñeà toång quaùt Nhö vaäy neáu ta coù caùc meänh ñeà cô sôû laø : a) Boá (“An”, “Bình”) coù giaù trò ñuùng (Anh laø boá cuûa Bình) b) Anh(“Tuù”, “Bình”) coù giaù trò ñuùng (Tuù laø anh cuûa Bình) thì meänh ñeà c) Boá (“An”, “Tuù”) seõ coù giaù trò laø ñuùng. (An laø boá cuûa Tuù). Roõ raøng laø neáu chæ söû duïng logic meänh ñeà thoâng thöôøng thì ta seõ khoâng theå tìm ñöôïc moät moái lieân heä naøo giöõa c vaø a, b baèng caùc pheùp noái meänh ñeà , , . Töø ñoù, ta cuõng khoâng theå tính ra ñöôïc giaù trò cuûa meänh ñeà c. Sôû dó nhö vaäy vì ta khoâng theå theå hieän töôøng minh tri thöùc “(A laø boá cuûa B) neáu coù Z sao cho (A laø boá cuûa Z) vaø (Z anh hoaëc em C)” döôùi daïng caùc meänh ñeà thoâng thöôøng. Chính ñaëc tröng cuûa vò töø ñaõ cho pheùp chuùng ta theå hieän ñöôïc caùc tri thöùc daïng toång quaùt nhö treân. Theâm moät soá ví duï nöõa ñeå caùc baïn thaáy roõ hôn khaû naêng cuûa vò töø : Caâu caùch ngoân “Khoâng coù vaät gì laø lôùn nhaát vaø khoâng coù vaät gì laø beù nhaát!” coù theå ñöôïc bieåu dieãn döôùi daïng vò töø nhö sau : LôùnHôn(x,y) = x>y NhoûHôn(x,y) = x<y - - 101
x, y : LôùnHôn(y,x) vaø x, y : NhoûHôn(y,x) Caâu chaâm ngoân “Gaàn möïc thì ñen, gaàn ñeøn thì saùng” ñöôïc hieåu laø “chôi vôùi baïn xaáu naøo thì ta cuõng seõ thaønh ngöôøi xaáu” coù theå ñöôïc bieåu dieãn baèng vò töø nhö sau : NgöôøiXaáu (x) = y : Baïn(x,y) vaø NgöôøiXaáu(y) Coâng cuï vò töø ñaõ ñöôïc nghieân cöùu vaø phaùt trieån thaønh moät ngoân ngöõ laäp trình ñaëc tröng cho trí tueä nhaân taïo. Ñoù laø ngoân ngöõ PROLOG. Phaàn ñoïc theâm cuûa chöông seõ giôùi thieäu toång quan vôùi caùc baïn veà ngoân ngöõ naøy. VII. MOÄT SOÁ THUAÄT GIAÛI LIEÂN QUAN ÑEÁN LOGIC MEÄNH ÑEÀ Moät trong nhöõng vaán ñeà khaù quan troïng cuûa logic meänh ñeà laø chöùng minh tính ñuùng ñaén cuûa pheùp suy dieãn (a b). Ñaây cuõng chính laø baøi toaùn chöùng minh thöôøng gaëp trong toaùn hoïc. Roõ raøng raèng vôùi hai pheùp suy luaän cô baûn cuûa logic meänh ñeà (Modus Ponens, Modus Tollens) coäng vôùi caùc pheùp bieán ñoåi hình thöùc, ta cuõng coù theå chöùng minh ñöôïc pheùp suy dieãn. Tuy nhieân, thao taùc bieán ñoái hình thöùc laø raát khoù caøi ñaët ñöôïc treân maùy tính, thaäm chí ñieàu naøy coøn khoù khaên vôùi caû con ngöôøi! 102 - -
Vôùi coâng cuï maùy tính, baïn coù theå cho raèng ta seõ deã daøng chöùng minh ñöôïc moïi baøi toaùn baèng moät phöông phaùp “thoâ baïo” laø laäp baûng chaân trò . Tuy veà lyù thuyeát, phöông phaùp laäp baûng chaân trò luoân cho ñöôïc keát quaû cuoái cuøng nhöng ñoä phöùc taïp cuûa phöông phaùp naøy laø quaù lôùn, O(2n) vôùi n laø soá bieán meänh ñeà. Sau ñaây chuùng ta seõ nghieân cöùu hai phöông phaùp chöùng minh meänh ñeà vôùi ñoä phöùc taïp chæ coù O(n). B1 : Phaùt bieåu laïi giaû thieát vaø keát luaän cuûa vaán ñeà theo daïng chuaån sau : GT1, GT2, , GTn KL1, KL2, , KLm trong ñoù caùc GTi vaø KLi laø caùc meänh ñeà ñöôïc xaây döïng töø caùc bieán meänh ñeà vaø ba pheùp noái cô baûn : , ,  B2 : Chuyeån veá caùc GTi vaø KLi coù daïng phuû ñònh. Ví duï p  q,  (r  s), g, p  r s, p p  q, p  r, p (r  s), g, s B3 : Neáu GTi coù pheùp  thì thay theá pheùp  baèng daáu “,” Neáu KLi coù pheùp  thì thay theá pheùp  baèng daáu “,” Ví duï - - 103
p  q, r  (p  s) q, s p, q, r, p  s q, s B4 : Neáu GTi coù pheùp  thì taùch thaønh hai doøng con. Neáu ôû KLi coù pheùp  thì taùch thaønh hai doøng con. Ví duï p, p  q q p, p q p, q q B5 : Moät doøng ñöôïc chöùng minh neáu toàn taïi chung moät meänh ñeà ôû caû hai phía. Ví duï p, q q ñöôïc chöùng minh p, p q p p, q B6 : a) Neáu moät doøng khoâng coøn pheùp noái  hoaëc  ôû caû hai veá vaø ôû hai veá khoâng coù chung moät bieán meänh ñeà thì doøng ñoù khoâng ñöôïc chöùng minh. b) Moät vaán ñeà ñöôïc chöùng minh neáu taát caû doøng daãn xuaát töø daïng chuaån ban ñaàu ñeàu ñöôïc chöùng minh. 104 - -
Thuaät giaûi naøy hoaït ñoäng döïa treân phöông phaùp chöùng minh phaûn chöùng. Phöông phaùp chöùng minh phaûn chöùng Chöùng minh pheùp suy luaän (a b) laø ñuùng (vôùi a laø giaû thieát, b laø keát luaän). Phaûn chöùng : giaû söû b sai suy ra b laø ñuùng. Baøi toaùn ñöôïc chöùng minh neáu a ñuùng vaø b ñuùng sinh ra moät maâu thuaãn. B1 : Phaùt bieåu laïi giaû thieát vaø keát luaän cuûa vaán ñeà döôùi daïng chuaån nhö sau : GT1, GT2, ,GTn KL1, KL2, , KLm trong ñoù : GTi vaø KLj ñöôïc xaây döïng töø caùc bieán meänh ñeà vaø caùc pheùp toaùn : , ,  B2 : Neáu GTi coù pheùp  thì thay baèng daáu “,” Neáu KLi coù pheùp  thì thay baèng daáu “,” B3 : Bieán ñoåi doøng chuaån ôû B1 veà thaønh danh saùch meänh ñeà nhö sau : { GT1, GT2, , GTn ,  KL1,  KL2, ,  KLm } - - 105
B4 : Neáu trong danh saùch meänh ñeà ôû böôùc 2 coù hai meänh ñeà ñoái ngaãu nhau thì baøi toaùn ñöôïc chöùng minh. Ngöôïc laïi thì chuyeån sang B4. (a vaø a goïi laø hai meänh ñeà ñoái ngaãu nhau) B5 : Xaây döïng moät meänh ñeà môùi baèng caùch tuyeån moät caëp meänh ñeà trong danh saùch meänh ñeà ôû böôùc 2. Neáu meänh ñeà môùi coù caùc bieán meänh ñeà ñoái ngaãu nhau thì caùc bieán ñoù ñöôïc loaïi boû. Ví duï : p  q  r  s  q Hai meänh ñeà q, q laø ñoái ngaãu neân seõ ñöôïc loaïi boû p  r  s B5 : Thay theá hai meänh ñeà vöøa tuyeån trong danh saùch meänh ñeà baèng meänh ñeà môùi. Ví duï : { p  q , r  s  q , w  r, s  q } { p  r  s , w  r, s  q } B6 : Neáu khoâng xaây döïng ñöôïc theâm moät meänh ñeà môùi naøo vaø trong danh saùch meänh ñeà khoâng coù hai meänh ñeà naøo ñoái ngaãu nhau thì vaán ñeà khoâng ñöôïc chöùng minh. Ví duï : Chöùng minh raèng p  q, q  r, r  s, u  s p, u 106 - -
B3: { p  q, q  r, r  s, u  s, p, u } B4 : Coù taát caû saùu meänh ñeà nhöng chöa coù meänh ñeà naøo ñoái ngaãu nhau. B5 : tuyeån moät caëp meänh ñeà (choïn hai meänh ñeà coù bieán ñoái ngaãu). Choïn hai meänh ñeà ñaàu : p  q  q  r p  r Danh saùch meänh ñeà thaønh : {p  r , r  s, u  s, p, u } Vaãn chöa coù meänh ñeà ñoái ngaãu. Tuyeån hai caëp meänh ñeà ñaàu tieân p  r  r  s p  s Danh saùch meänh ñeà thaønh {p  s, u  s, p, u } Vaãn chöa coù hai meänh ñeà ñoái ngaãu Tuyeån hai caëp meänh ñeà ñaàu tieân p  s  u  s p  u Danh saùch meänh ñeà thaønh : {p  u, p, u } Vaãn chöa coù hai meänh ñeà ñoái ngaãu - - 107
Tuyeån hai caëp meänh ñeà : p  u  u p Danh saùch meänh ñeà trôû thaønh : {p, p } Coù hai meänh ñeà ñoái ngaãu neân bieåu thöùc ban ñaàu ñaõ ñöôïc chöùng minh. VIII. BIEÅU DIEÃN TRI THÖÙC SÖÛ DUÏNG LUAÄT DẪN XUẤT (LUẬT SINH) Phöông phaùp bieåu dieãn tri thöùc baèng luaät sinh ñöôïc phaùt minh bôûi Newell vaø Simon trong luùc hai oâng ñang coá gaéng xaây döïng moät heä giaûi baøi toaùn toång quaùt. Ñaây laø moät kieåu bieåu dieãn tri thöùc coù caáu truùc. YÙ töôûng cô baûn laø tri thöùc coù theå ñöôïc caáu truùc baèng moät caëp ñieàu kieän – haønh ñoäng : “NEÁU ñieàu kieän xaûy ra THÌ haønh ñoäng seõ ñöôïc thi haønh”. Chaúng haïn : NEÁU ñeøn giao thoâng laø ñoû THÌ baïn khoâng ñöôïc ñi thaúng; NEÁU maùy tính ñaõ môû maø khoâng khôûi ñoäng ñöôïc THÌ kieåm tra nguoàn ñieän Ngaøy nay, caùc luaät sinh ñaõ trôû neân phoå bieán vaø ñöôïc aùp duïng roäng raõi trong nhieàu heä thoáng trí tueä nhaân taïo khaùc nhau. Luaät sinh coù theå laø moät coâng cuï moâ taû ñeå giaûi quyeát caùc vaán ñeà thöïc teá thay cho caùc kieåu phaân tích vaán ñeà 108 - -
truyeàn thoáng. Trong tröôøng hôïp naøy, caùc luaät ñöôïc duøng nhö laø nhöõng chæ daãn (tuy coù theå khoâng hoaøn chænh) nhöng raát höõu ích ñeå trôï giuùp cho caùc quyeát ñònh trong quaù trình tìm kieám, töø ñoù laøm giaûm khoâng gian tìm kieám. Moät ví duï khaùc laø luaät sinh coù theå ñöôïc duøng ñeå baét chöôùc haønh vi cuûa nhöõng chuyeân gia. Theo caùch naøy, luaät sinh khoâng chæ ñôn thuaàn laø moät kieåu bieåu dieãn tri thöùc trong maùy tính maø laø moät kieåu bieåu dieãn caùc haønh vi cuûa con ngöôøi. Moät caùch toång quaùt luaät sinh coù daïng nhö sau : P1  P2   Pn Q Tuøy vaøo caùc vaán ñeà ñang quan taâm maø luaät sinh coù nhöõng ngöõ nghóa hay caáu taïo khaùc nhau : Trong logic vò töø : P1,P2, , Pn, Q laø nhöõng bieåu thöùc logic. Trong ngoân ngöõ laäp trình, moãi moät luaät sinh laø moät caâu leänh. IF (P1 AND P2 AND AND Pn) THEN Q. Trong lyù thuyeát hieåu ngoân ngöõ töï nhieân, moãi luaät sinh laø moät pheùp dòch : ONE moät - - 109
TWO hai JANUARY thaùng moät Ñeå bieåu dieãn moät taäp luaät sinh, ngöôøi ta thöôøng phaûi chæ roõ hai thaønh phaàn chính sau : (1) Taäp caùc söï kieän F(Facts) F = { f1, f2, fn } (2) Taäp caùc quy taéc R (Rules) aùp duïng treân caùc söï kieän daïng nhö sau : f1 ^ f2 ^ ^ fi q Trong ñoù, caùc fi , q ñeàu thuoäc F Ví duï : Cho moät cô sôû tri thöùc ñöôïc xaùc ñònh nhö sau : Caùc söï kieän : A, B, C, D, E, F, G, H, K Taäp caùc quy taéc hay luaät sinh (rule) R1 : A E R2 : B D R3 : H A R4 : E  G C 110 - -
R5 : E  K B R6 : D  E  K C R7 : G  K  F A Suy dieãn tieán : laø quaù trình suy luaän xuaát phaùt töø moät soá söï kieän ban ñaàu, xaùc ñònh caùc söï kieän coù theå ñöôïc “sinh” ra töø söï kieän naøy. Söï kieän ban ñaà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 dieãn luøi : laø quaù trình suy luaän ngöôïc xuaát phaùt töø moät soá söï kieän ban ñaàu, ta tìm kieám caùc söï kieän ñaõ “sinh” ra söï kieän naøy. Moät ví duï thöôøng gaëp trong thöïc teá laø xuaát phaùt töø caùc tình traïng cuûa maùy tính, chaån ñoaùn xem maùy tính ñaõ bò hoûng hoùc ôû ñaâu. Ví duï Taäp caùc söï kieän : o OÅ cöùng laø “hoûng” hay “hoaït ñoäng bình thöôøng” o Hoûng maøn hình. - - 111
o Loûng caùp maøn hình. o Tình traïng ñeøn oå cöùng laø “taét” hoaëc “saùng” o Coù aâm thanh ñoïc oå cöùng. o Tình traïng ñeøn maøn hình “xanh” hoaëc “chôùp ñoû” o Khoâng söû duïng ñöôïc maùy tính. o Ñieän vaøo maùy tính “coù” hay “khoâng” Taäp caùc luaät : R1. Neáu ( (oå cöùng “hoûng”) hoaëc (caùp maøn hình “loûng”)) thì khoâng söû duïng ñöôïc maùy tính. R2. Neáu (ñieän vaøo maùy laø “coù”) vaø ( (aâm thanh ñoïc oå cöùng laø “khoâng”) hoaëc tình traïng ñeøn oå cöùng laø “taét”)) thì (oå cöùng “hoûng”). R3. Neáu (ñieän vaøo maùy laø “coù”) vaø (tình traïng ñeøn maøn hình laø “chôùp ñoû”) thì (caùp maøn hình “loûng”). Ñeå xaùc ñònh ñöôïc caùc nguyeân nhaân gaây ra söï kieän “khoâng söû duïng ñöôïc maùy tính”, ta phaûi xaây döïng moät caáu truùc ñoà thò goïi laø ñoà thò AND/OR nhö sau : 112 - -
Khoâng söû duïng ñöôïc maùy tính OR OÅ cöùng Caùp maøn hình “hoûng” “loûng” AND AND Tình traïng OR Ñieän vaøo maùy “coù” ñeøn maøn hình “chôùp” AÂm Ñeøn oå thanh oå cöùng cöùng “taét” “khoâng” Hình 2.3 Nhö vaäy laø ñeå xaùc ñònh ñöôïc nguyeân nhaân gaây ra hoûng hoùc laø do oå cöùng hoûng hay caùp maøn hình loûng, heä thoáng phaûi laàn löôït ñi vaøo caùc nhaùnh ñeå kieåm tra caùc ñieàu kieän nhö ñieän vaøo maùy “coù”, aâm thanh oå cöùng “khoâng” Taïi moät böôùc, neáu giaù trò caàn xaùc ñònh khoâng theå ñöôïc suy ra töø baát kyø moät luaät naøo, heä thoáng seõ yeâu caàu ngöôøi duøng tröïc tieáp nhaäp vaøo. Chaúng haïn nhö ñeå bieát maùy tính coù ñieän khoâng, heä thoáng seõ hieän ra maøn hình caâu hoûi “Baïn kieåm tra xem coù ñieän vaøo maùy tính khoâng (kieåm tra ñeøn nguoàn)? (C/K)”. Ñeå thöïc hieän ñöôïc cô cheá suy luaän luøi, ngöôøi ta thöôøng söû - - 113
duïng ngaên xeáp (ñeå ghi nhaän laïi nhöõng nhaùnh chöa kieåm tra). VIII.3 Vaán ñeà toái öu luaät Taäp caùc luaät trong moät cô sôû tri thöùc raát coù khaû naêng thöøa, truøng laép hoaëc maâu thuaãn. Dó nhieân laø heä thoáng coù theå ñoå loãi cho ngöôøi duøng veà vieäc ñöa vaøo heä thoáng nhöõng tri thöùc nhö vaäy. Tuy vieäc toái öu moät cô sôû tri thöùc veà maët toång quaùt laø moät thao taùc khoù (vì giöõa caùc tri thöùc thöôøng coù quan heä khoâng töôøng minh), nhöng trong giôùi haïn cô sôû tri thöùc döôùi daïng luaät, ta vaãn coù moät soá thuaät toaùn ñôn giaûn ñeå loaïi boû caùc vaán ñeà naøy. VIII.3.1. Ruùt goïn beân phaûi Luaät sau hieån nhieân ñuùng : A  B A (1) Do ñoù luaät A  B A  C Laø hoaøn toaøn töông ñöông vôùi A  B C Quy taéc ruùt goïn : Coù theå loaïi boû nhöõng söï kieän beân veá phaûi neáu nhöõng söï kieän ñoù ñaõ xuaát hieän beân veá traùi. Neáu 114 - -
sau khi ruùt goïn maø veá phaûi trôû thaønh roãng thì luaät ñoù laø luaät hieån nhieân. Ta coù theå loaïi boû caùc luaät hieån nhieân ra khoûi tri thöùc. VIII.3.2. Ruùt goïn beân traùi Xeùt caùc luaät : (L1) A, B C (L2) A X (L3) X C Roõ raøng laø luaät A, B C coù theå ñöôïc thay theá baèng luaät A C maø khoâng laøm aûnh höôûng ñeán caùc keát luaän trong moïi tröôøng hôïp. Ta noùi raèng söï kieän B trong luaät (1) laø dö thöøa vaø coù theå ñöôïc loaïi boû khoûi luaät daãn treân. VIII.3.3. Phaân raõ vaø keát hôïp luaät Luaät A  B C Töông ñöông vôùi hai luaät A C B C Vôùi quy taéc naøy, ta coù theå loaïi boû hoaøn toaøn caùc luaät coù pheùp noái HOAËC. Caùc luaät coù pheùp noái naøy thöôøng laøm cho thao taùc xöû lyù trôû neân phöùc taïp. - - 115
VIII.3.4. Luaät thöøa Moät luaät daãn A B ñöôïc goïi laø thöøa neáu coù theå suy ra luaät naøy töø nhöõng luaät coøn laïi. Ví duï : trong taäp caùc luaät goàm {A B, B C, A C} thì luaät thöù ba laø luaät thöøa vì noù coù theå ñöôïc suy ra töø hai luaät coøn laïi. VIII.3.5. Thuaät toaùn toái öu taäp luaät daãn Thuaät toaùn naøy seõ toái öu hoùa taäp luaät ñaõ cho baèng caùch loaïi ñi caùc luaät coù pheùp noái HOAËC, caùc luaät hieån nhieân hoaëc caùc luaät thöøa. Thuaät toaùn bao goàm ba böôùc chính B1 : Ruùt goïn veá phaûi Vôùi moãi luaät r trong R Vôùi moãi söï kieän A VeáPhaûi(r) Neáu A VeáTraùi(r) thì Loaïi A ra khoûi veá phaûi cuûa R. Neáu VeáPhaûi(r) roãng thì loaïi boû r ra khoûi heä luaät daãn : R = R – {r} B2 : Phaân raõ caùc luaät Vôùi moãi luaät r : X1  X2   Xn Y trong R Vôùi moãi i töø 1 ñeán n R := R + { Xi Y} R := R – {r} B3 : Loaïi boû luaät thöøa Vôùi moãi luaät r thuoäc R 116 - -
Neáu VeáPhaûi(r) BaoÑoùng(VeáTraùi(r), R-{r}) thì R := R – {r} B4 : Ruùt goïn veá traùi Vôùi moãi luaät daãn r : X:A1  A2, ,An Y thuoäc R Vôùi moãi söï kieän Ai thuoäc r Goïi luaät r1 :X – Ai Y S = ( R – {r} )  {r1} Neáu BaoÑoùng( X – Ai , S)  BaoÑoùng(X, R) thì loaïi söï kieän A ra khoûi X Öu ñieåm Bieåu dieãn tri thöùc baèng luaät ñaëc bieät höõu hieäu trong nhöõng tình huoáng heä thoáng caàn ñöa ra nhöõng haønh ñoäng döïa vaøo nhöõng söï kieän coù theå quan saùt ñöôïc. Noù coù nhöõng öu ñieåm chính yeáu sau ñaây : o Caùc luaät raát deã hieåu neân coù theå deã daøng duøng ñeå trao ñoåi vôùi ngöôøi duøng (vì noù laø moät trong nhöõng daïng töï nhieân cuûa ngoân ngöõ). o Coù theå deã daøng xaây döïng ñöôïc cô cheá suy luaän vaø giaûi thích töø caùc luaät. o Vieäc hieäu chænh vaø baûo trì heä thoáng laø töông ñoái deã daøng. o Coù theå caûi tieán deã daøng ñeå tích hôïp caùc luaät môø. o Caùc luaät thöôøng ít phuï thuoäc vaøo nhau. - - 117
Nhöôïc ñieåm o Caùc tri thöùc phöùc taïp ñoâi luùc ñoøi hoûi quaù nhieàu (haøng ngaøn) luaät sinh. Ñieàu naøy seõ laøm naûy sinh nhieàu vaán ñeà lieân quan ñeán toác ñoä laãn quaûn trò heä thoáng. o Thoáng keâ cho thaáy, ngöôøi xaây döïng heä thoáng trí tueä nhaân taïo thích söû duïng luaät sinh hôn taát caû phöông phaùp khaùc (deã hieåu, deã caøi ñaët) neân hoï thöôøng tìm moïi caùch ñeå bieåu dieãn tri thöùc baèng luaät sinh cho duø coù phöông phaùp khaùc thích hôïp hôn! Ñaây laø nhöôïc ñieåm mang tính chuû quan cuûa con ngöôøi. o Cô sôû tri thöùc luaät sinh lôùn seõ laøm giôùi haïn khaû naêng tìm kieám cuûa chöông trình ñieàu khieån. Nhieàu heä thoáng gaëp khoù khaên trong vieäc ñaùnh giaù caùc heä döïa treân luaät sinh cuõng nhö gaëp khoù khaên khi suy luaän treân luaät sinh. X. BIEÅU DIEÃN TRI THÖÙC SÖÛ DUÏNG MAÏNG NGÖÕ NGHÓA X.1. Khaùi nieäm Maïng ngöõ nghóa laø moät phöông phaùp bieåu dieãn tri thöùc ñaàu tieân vaø cuõng laø phöông phaùp deã hieåu nhaát ñoái vôùi chuùng ta. Phöông phaùp naøy seõ bieåu dieãn tri thöùc döôùi daïng moät ñoà thò, trong ñoù ñænh laø caùc ñoái töôïng (khaùi nieäm) coøn caùc cung cho bieát moái quan heä giöõa caùc ñoái töôïng (khaùi nieäm) naøy. Chaúng haïn, giöõa caùc khaùi nieäm chích choøe, chim, hoùt, caùnh, toå coù moät soá moái quan heä nhö sau : 118 - -
o Chích choøe laø moät loaøi chim. o Chim bieát hoùt o Chim coù caùnh o Chim soáng trong toå Caùc moái quan heä naøy seõ ñöôïc bieåu dieãn tröïc quan baèng moät ñoà thò nhö sau : Chích Hoùt laø bieát choøe Chim coù laøm Toå Caùnh Do maïng ngöõ nghóa laø moät loaïi ñoà thò cho neân noù thöøa höôûng ñöôïc taát caû nhöõng maët maïnh cuûa coâng cuï naøy; nghóa laø ta coù theå duøng nhöõng thuaät toaùn cuûa ñoà thò treân maïng ngöõ nghóa nhö thuaät toaùn tìm lieân thoâng, tìm ñöôøng ñi ngaén nhaát, ñeå thöïc hieän caùc cô cheá suy luaän. Ñieåm ñaëc bieät cuûa maïng ngöõ nghóa so vôùi ñoà thò thoâng thöôøng chính laø vieäc gaùn moät yù nghóa (coù, laøm, laø, bieát, ) cho caùc cung. Trong ñoà thò tieâu chuaån, vieäc coù moät cung noái giöõa hai ñænh chæ cho bieát coù söï lieân heä giöõa hai ñænh ñoù vaø taát caû caùc cung trong ñoà thò ñeàu bieåu dieãn cho cuøng moät loaïi lieân - - 119
heä. Trong maïng ngöõ nghóa, cung noái giöõa hai ñænh coøn cho bieát giöõa hai khaùi nieäm töông öùng coù söï lieân heä nhö theá naøo. Vieäc gaùn ngöõ nghóa vaøo caùc cung cuûa ñoà thò ñaõ giuùp giaûm bôùt ñöôïc soá löôïng ñoà thò caàn phaûi duøng ñeå bieåu dieãn caùc moái lieân heä giöõa caùc khaùi nieäm. Chaúng haïn nhö trong ví duï treân, neáu söû duïng ñoà thò thoâng thöôøng, ta phaûi duøng ñeán boán loaïi ñoà thò cho boán moái lieân heä: moät ñoà thò ñeå bieåu dieãn moái lieân heä “laø”, moät ñoà thò cho moái lieân heä “laøm”, moät cho “bieát” vaø moät cho “coù”. Moät ñieåm khaù thuù vò cuûa maïng ngöõ nghóa laø tính keá thöøa. Bôûi vì ngay töø trong khaùi nieäm, maïng ngöõ nghóa ñaõ haøm yù söï phaân caáp (nhö caùc moái lieân heä “laø”) neân coù nhieàu ñænh trong maïng maëc nhieân seõ coù nhöõng thuoäc tính cuûa nhöõng ñænh khaùc. Chaúng haïn theo maïng ngöõ nghóa ôû treân, ta coù theå deã daøng traû lôøi “coù” cho caâu hoûi : “Chích choøe coù laøm toå khoâng?”. Ta coù theå khaúng ñònh ñöôïc ñieàu naøy vì ñænh “chích choøe” coù lieân keát “laø” vôùi ñænh “chim” vaø ñænh “chim” laïi lieân keát “bieát” vôùi ñænh “laøm toå” neân suy ra ñænh “chích choøe” cuõng coù lieân keát loaïi “bieát” vôùi ñænh “laøm toå”. (Neáu ñeå yù, baïn seõ nhaän ra ñöôïc kieåu “suy luaän” maø ta vöøa thöïc hieän baét nguoàn töø thuaät toaùn “loang” hay “tìm lieân thoâng” treân ñoà thò!). Chính ñaëc tính keá thöøa cuûa maïng ngöõ nghóa ñaõ cho pheùp ta coù theå thöïc hieän ñöôïc raát nhieàu pheùp suy dieãn töø nhöõng thoâng tin saün coù treân maïng. 120 - -
Tuy maïng ngöõ nghóa laø moät kieåu bieåu dieãn tröïc quan ñoái vôùi con ngöôøi nhöng khi ñöa vaøo maùy tính, caùc ñoái töôïng vaø moái lieân heä giöõa chuùng thöôøng ñöôïc bieåu dieãn döôùi daïng nhöõng phaùt bieåu ñoäng töø (nhö vò töø). Hôn nöõa, caùc thao taùc tìm kieám treân maïng ngöõ nghóa thöôøng khoù khaên (ñaëc bieät ñoái vôùi nhöõng maïng coù kích thöôùc lôùn). Do ñoù, moâ hình maïng ngöõ nghóa ñöôïc duøng chuû yeáu ñeå phaân tích vaán ñeà. Sau ñoù, noù seõ ñöôïc chuyeån ñoåi sang daïng luaät hoaëc frame ñeå thi haønh hoaëc maïng ngöõ nghóa seõ ñöôïc duøng keát hôïp vôùi moät soá phöông phaùp bieåu dieãn khaùc. X.2. Öu ñieåm vaø nhöôïc ñieåm cuûa maïng ngöõ nghóa Öu ñieåm o Maïng ngöõ nghóa raát linh ñoäng, ta coù theå deã daøng theâm vaøo maïng caùc ñænh hoaëc cung môùi ñeå boå sung caùc tri thöùc caàn thieát. o Maïng ngöõ nghóa coù tính tröïc quan cao neân raát deã hieåu. o Maïng ngöõ nghóa cho pheùp caùc ñænh coù theå thöøa keá caùc tính chaát töø caùc ñænh khaùc thoâng qua caùc cung loaïi “laø”, töø ñoù, coù theå taïo ra caùc lieân keát “ngaàm” giöõa nhöõng ñænh khoâng coù lieân keát tröïc tieáp vôùi nhau. o Maïng ngöõ nghóa hoaït ñoäng khaù töï nhieân theo caùch thöùc con ngöôøi ghi nhaän thoâng tin. - - 121
Nhöôïc ñieåm o Cho ñeán nay, vaãn chöa coù moät chuaån naøo quy ñònh caùc giôùi haïn cho caùc ñænh vaø cung cuûa maïng. Nghóa laø baïn coù theå gaùn gheùp baát kyø khaùi nieäm naøo cho ñænh hoaëc cung! o Tính thöøa keá (voán laø moät öu ñieåm) treân maïng seõ coù theå daãn ñeán nguy cô maâu thuaãn trong tri thöùc. Chaúng haïn, neáu boå sung theâm nuùt “Gaø” vaøo maïng nhö hình sau thì ta coù theå keát luaän raèng “Gaø” bieát “bay”!. Sôû dó coù ñieàu naøy laø vì coù söï khoâng roõ raøng trong ngöõ nghóa gaùn cho moät nuùt cuûa maïng. Baïn ñoïc coù theå phaûn ñoái quan ñieåm vì cho raèng, vieäc sinh ra maâu thuaãn laø do ta thieát keá maïng dôû chöù khoâng phaûi do khuyeát ñieåm cuûa maïng! Tuy nhieân, xin löu yù raèng, tính thöøa keá sinh ra raát nhieàu moái lieân “ngaàm” neân khaû naêng naûy sinh ra moät moái lieân heä khoâng hôïp leä laø raát lôùn! Gaø Hoùt laø bieát Chích laø Chim coù laøm Toå Caùnh Haàu nhö khoâng theå bieån dieãn caùc tri thöùc daïng thuû tuïc baèng maïng ngöõ nghóa vì caùc khaùi nieäm veà thôøi gian vaø trình töï khoâng ñöôïc theå hieän töôøng minh treân maïng ngöõ nghóa. X.3. Moät ví duï tieâu bieåu 122 - -
Duø laø moät phöông phaùp töông ñoái cuõ vaø coù nhöõng yeáu ñieåm nhöng maïng ngöõ nghóa vaãn coù nhöõng öùng duïng voâ cuøng ñoäc ñaùo. Hai loaïi öùng duïng tieâu bieåu cuûa maïng ngöõ nghóa laø öùng duïng xöû lyù ngoân ngöõ töï nhieân vaø öùng duïng giaûi baøi toaùn töï ñoäng. Ví duï 1 : Trong öùng duïng xöû lyù ngoân ngöõ töï nhieân, maïng ngöõ nghóa coù theå giuùp maùy tính phaân tích ñöôïc caáu truùc cuûa caâu ñeå töø ñoù coù theå phaàn naøo “hieåu” ñöôïc yù nghóa cuûa caâu. Chaúng haïn, caâu “Chaâu ñang ñoïc moät cuoán saùch daøy vaø cöôøi khoaùi traù” coù theå ñöôïc bieåu dieãn baèng moät maïng ngöõ nghóa nhö sau : ai Chaâ ai u Ñoïc Cöôøi caùi gì nhö theá naøo ra Saùch Daøy Khoaùi traù Ví duï 2 : Giaûi baøi toaùn tam giaùc toång quaùt Chuùng ta seõ khoâng ñi saâu vaøo ví duï 1 vì ñaây laø moät vaán ñeà quaù phöùc taïp ñeå coù theå trình baøy trong cuoán saùch naøy. Trong ví duï naøy, chuùng ta seõ khaûo saùt moät vaán ñeà ñôn giaûn hôn nhöng cuõng khoâng keùm phaàn ñoäc ñaùo. Khi môùi hoïc laäp trình, baïn thöôøng ñöôïc giaùo vieân cho nhöõng baøi taäp nhaäp moân ñaïi loaïi nhö “Cho ba caïnh cuûa tam giaùc, - - 123
tính chieàu daøi caùc ñöôøng cao”, “Cho goùc a, b vaø caïnh AC. Tính chieàu daøi trung tuyeán”, Vôùi moãi baøi taäp naøy, vieäc baïn caàn laøm laø laáy giaáy buùt ra tìm caùch tính, sau khi ñaõ xaùc ñònh caùc böôùc tính toaùn, baïn chuyeån noù thaønh chöông trình. Neáu coù 10 baøi, baïn phaûi laøm laïi vieäc tính toaùn roài laäp trình 10 laàn. Neáu coù 100 baøi, baïn phaûi laøm 100 laàn. Vaø tin buoàn cho baïn laø soá löôïng baøi toaùn thuoäc loaïi naøy laø raát nhieàu! Bôûi vì moät tam giaùc coù taát caû 22 yeáu toá khaùc nhau!. Khoâng leõ moãi laàn gaëp moät baøi toaùn môùi, baïn ñeàu phaûi laäp trình laïi? Lieäu coù moät chöông trình toång quaùt coù theå töï ñoäng giaûi ñöôïc taát caû (vaøi ngaøn!) nhöõng baøi toaùn tam giaùc thuoäc loaïi naøy khoâng? Caâu traû lôøi laø COÙ ! Vaø ngaïc nhieân hôn nöõa, chöông trình naøy laïi khaù ñôn giaûn. Baøi toaùn naøy seõ ñöôïc giaûi baèng maïng ngöõ nghóa. Coù 22 yeáu toá lieân quan ñeán caïnh vaø goùc cuûa tam giaùc. Ñeå xaùc ñònh moät tam giaùc hay ñeå xaây döïng moät tam giaùc ta caàn coù ba yeáu toá trong ñoù phaûi coù yeáu toá caïnh. Nhö vaäy 3 coù khoaûng C 22 -1 (khoaûng vaøi ngaøn) caùch ñeå xaây döïng hay xaùc ñònh moät tam giaùc. Theo thoáng keâ, coù khoaûng 200 coâng thöùc lieân quan ñeán caïnh vaø goùc moät tam giaùc. Ñeå giaûi baøi toaùn naøy baèng coâng cuï maïng ngöõ nghóa, ta phaûi söû duïng khoaûng 200 ñænh ñeå chöùa coâng thöùc vaø khoaûng 22 ñænh ñeå chöùa caùc yeáu toá cuûa tam giaùc. Maïng ngöõ nghóa cho baøi toaùn naøy coù caáu truùc nhö sau. Ñænh cuûa ñoà thò bao goàm hai loaïi : o Ñænh chöùa coâng thöùc (kyù hieäu baèng hình chöõ nhaät) o Ñænh chöùa yeáu toá cuûa tam giaùc (kyù hieäu baèng hình troøn) 124 - -
Cung : chæ noái töø ñænh hình troøn ñeán ñænh hình chöõ nhaät cho bieát yeáu toá tam giaùc xuaát hieän trong coâng thöùc naøo (khoâng coù tröôøng hôïp cung noái giöõa hai ñænh hình troøn hoaëc cung noái giöõa hai ñænh hình chöõ nhaät). * Löu yù : trong moät coâng thöùc lieân heä giöõa n yeáu toá cuûa tam giaùc, ta giaû ñònh raèng neáu ñaõ bieát giaù trò cuûa n-1 yeáu toá thì seõ tính ñöôïc giaù trò cuûa yeáu toá coøn laïi. Chaúng haïn nhö trong coâng thöùc toång ba goùc cuûa tam giaùc baèng 1800 thì khi bieát ñöôïc hai goùc, ta seõ tính ñöôïc goùc coøn laïi. Cô cheá suy dieãn thöïc hieän theo thuaät toaùn “loang” ñôn giaûn sau : B1 : Kích hoaït nhöõng ñænh hình troøn ñaõ cho ban ñaàu (nhöõng yeáu toá ñaõ coù giaù trò) B2 : Laëp laïi böôùc sau cho ñeán khi kích hoaït ñöôïc taát caû nhöõng ñænh öùng vôùi nhöõng yeáu toá caàn tính hoaëc khoâng theå kích hoaït ñöôïc baát kyø ñænh naøo nöõa. Neáu moät ñænh hình chöõ nhaät coù cung noái vôùi n ñænh hình troøn maø n-1 ñænh hình troøn ñaõ ñöôïc kích hoaït thì kích hoaït ñænh hình troøn coøn laïi (vaø tính giaù trò ñænh coøn laïi naøy thoâng qua coâng thöùc ôû ñænh hình chöõ nhaät). Giaû söû ta coù maïng ngöõ nghóa ñeå giaûi baøi toaùn tam giaùc nhö hình 2.4 - - 125
+  +  - = 0 (4)    a b c b (1) (2) sin sin sin sin a b h c (3) S p p-a p-b p-c S – ½ hc.c = 0 (5) S Ví duï : “Cho hai goùc ,  vaø chieàu daøi caïnh a cuûa tam giaùc. Tính chieàu daøi ñöôøng cao hC”. Vôùi maïng ngöõ nghóa ñaõ cho trong hình 2.4. Caùc böôùc thi haønh cuûa thuaät toaùn nhö sau : 126 - -
Baét ñaàu : ñænh , a cuûa ñoà thò ñöôïc kích hoaït. o Coâng thöùc (1) ñöôïc kích hoaït (vì , a ñöôïc kích hoaït). Töø coâng thöùc (1) tính ñöôïc caïnh b. Ñænh b ñöôïc kích hoaït. o Coâng thöùc (4) ñöôïc kích hoaït (vì ). Töø coâng thöùc (4) tính ñöôïc goùc  o Coâng thöùc (2) ñöôïc kích hoaït (vì ba ñænh , , b ñöôïc kích hoaït). Töø coâng thöùc (2) tính ñöôïc caïnh c. Ñænh c ñöôïc kích hoaït. o Coâng thöùc (3) ñöôïc kích hoaït (vì ba ñænh a, b, c ñöôïc kích hoaït) . Töø coâng thöùc (3) tính ñöôïc dieän tích S. Ñænh S ñöôïc kích hoaït. o Coâng thöùc (5) ñöôïc kích hoaït (vì hai ñænh S, c ñöôïc kích hoaït). Töø coâng thöùc (5) tính ñöôïc hC. Ñænh hC ñöôïc kích hoaït. o Giaù trò hC ñaõ ñöôïc tính. Thuaät toaùn keát thuùc. Veà maët chöông trình, ta coù theå caøi ñaët maïng ngöõ nghóa giaûi baøi toaùn tam giaùc baèng moät maûng hai chieàu A trong ñoù : - - 127
o Coät : öùng vôùi coâng thöùc. Moãi coät öùng vôùi moät coâng thöùc tam giaùc khaùc nhau (ñænh hình chöõ nhaät). o Doøng : öùng vôùi yeáu toá tam giaùc. Moãi doøng öùng vôùi moät yeáu toá tam giaùc khaùc nhau (ñænh hình troøn). o Phaàn töû A[i, j] = -1 nghóa laø trong coâng thöùc öùng vôùi coät j coù yeáu toá tam giaùc öùng vôùi coät i. Ngöôïc laïi A[i,j] = 0. Ñeå thöïc hieän thao taùc “kích hoaït” moät ñænh hình troøn, ta ñaët giaù trò cuûa toaøn doøng öùng vôùi yeáu toá tam giaùc baèng 1. Ñeå kieåm tra xem moät coâng thöùc ñaõ coù ñuû n-1 yeáu toá hay chöa (nghóa laø kieåm tra ñieàu kieän “ñænh hình chöõ nhaät coù cung noái vôùi n ñænh hình troøn maø n-1 ñænh hình troøn ñaõ ñöôïc kích hoaït”), ta chæ vieäc laáy hieäu giöõa toång soá oâ coù giaù trò baèng 1 vaø toång soá oâ coù giaù trò -1 treân coät öùng vôùi coâng thöùc caàn kieåm tra. Neáu keát quaû baèng n, thì coâng thöùc ñaõ coù ñuû n-1 yeáu toá. Trôû laïi maïng ngöõ nghóa ñaõ cho. Quaù trình thi haønh kích hoaït ñöôïc dieãn ra nhö sau : Maûng bieåu dieãn maïng ngöõ nghóa ban ñaàu 128 - -
(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 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Khôûi ñaàu : ñænh , a cuûa ñoà thò ñöôïc kích hoaït. (1) (2) (3) (4) (5) 1 0 0 1 0  1 1 0 1 0  0 -1 0 -1 0 a 1 0 1 1 0 b -1 -1 -1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Treân coät (1), hieäu (1 + 1 + 1 – (-1)) = 4 neân doøng b seõ ñöôïc kích hoaït. - - 129
(1) (2) (3) (4) (5) 1 0 0 1 0  1 1 0 1 0  0 -1 0 -1 0 a 1 0 1 1 0 b 1 1 1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Treân coät (4), hieäu (1 + 1 + 1 – (-1)) = 4 neân doøng  seõ ñöôïc kích hoaït. (1) (2) (3) (4) (5) 1 0 0 1 0  1 1 0 1 0  0 1 0 1 0 a 1 0 1 1 0 b 1 1 1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Treân coät (2), hieäu (1 + 1 + 1 – (1)) = 4 neân doøng c ñöôïc kích hoaït. 130 - -
(1) (2) (3) (4) (5) 1 0 0 1 0  1 1 0 1 0  0 1 0 1 0 A 1 0 1 1 0 B 1 1 1 0 0 C 0 1 1 0 1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Treân coät (3), hieäu (1 + 1 + 1 – (-1)) = 4 neân doøng S ñöôïc kích hoaït. (1) (2) (3) (4) (5) 1 0 0 1 0  1 1 0 1 0  0 1 0 1 0 a 1 0 1 1 0 b 1 1 1 0 0 c 0 1 1 0 1 S 0 0 1 0 1 hC 0 0 0 0 -1 Treân coät (5), hieäu (1 + 1 – (1)) = 3 neân doøng hC ñöôïc kích hoaït. Khaû naêng cuûa heä thoáng naøy khoâng chæ döøng laïi ôû vieäc tính ra giaù trò caùc yeáu toá caàn thieát, vôùi moät chuùt söûa ñoåi, chöông trình naøy coøn coù theå ñöa ra caùch giaûi hình thöùc cuûa - - 131
baøi toaùn vaø thaäm chí coøn coù theå choïn ñöôïc caùch giaûi hình thöùc toái öu (toái öu hieåu theo nghóa laø caùch giaûi söû duïng nhöõng coâng thöùc ñôn giaûn nhaát). Sôû dó coù theå noùi nhö vaäy vì caùch suy luaän cuûa ta trong baøi toaùn naøy laø tìm kieám theo chieàu roäng. Do ñoù, khi ñaït ñeán keát quaû, ta coù theå coù raát nhieàu caùch khaùc nhau. Ñeå coù theå choïn ñöôïc giaûi phaùp toái öu, baïn caàn phaûi ñònh nghóa ñöôïc ñoä “phöùc taïp” cuûa moät coâng thöùc. Moät trong nhöõng tieâu chuaån thöôøng ñöôïc duøng laø soá löôïng pheùp nhaân, chia, coäng, tröø, ruùt caên, tính sin, cos, ñöôïc aùp duïng trong coâng thöùc. Caùc pheùp tính sin, cos vaø ruùt caên coù ñoä phöùc taïp cao nhaát, keá ñeán laø nhaân chia vaø cuoái cuøng laø coäng tröø. Cuoái cuøng baïn coù theå caûi tieán laïi phöông phaùp suy luaän baèng caùch vaän duïng thuaät toaùn A vôùi öôùc löôïng h = 0 ñeå coù theå choïn ra ñöôïc “ñöôøng ñi” toái öu. Ta choïn öôùc löôïng h = 0 vì hai lyù do sau (1) khoâng gian baøi toaùn nhoû neân ta khoâng caàn phaûi giôùi haïn ñoä roäng tìm kieám (2) xaây döïng moät öôùc löôïng nhö vaäy laø töông ñoái khoù khaên, ñaëc bieät laø laøm sao ñeå heä thoáng khoâng ñaùnh giaù quaù cao h. XI. BIEÅU DIEÃN TRI THÖÙC BAÈNG FRAME XI.1 Khaùi nieäm Frame laø moät caáu truùc döõ lieäu chöùa ñöïng taát caû nhöõng tri thöùc lieân quan ñeán moät ñoái töôïng cuï theå naøo ñoù. Frame coù lieân heä chaët cheõ ñeán khaùi nieäm höôùng ñoái töôïng (thöïc ra frame laø nguoàn goác cuûa laäp trình höôùng ñoái töôïng). 132 - -
Ngöôïc laïi vôùi caùc phöông phaùp bieåu dieãn tri thöùc ñaõ ñöôïc ñeà caäp ñeán, frame “ñoùng goùi” toaøn boä moät ñoái töôïng, tình huoáng hoaëc caû moät vaán ñeà phöùc taïp thaønh moät thöïc theå duy nhaát coù caáu truùc. Moät frame bao haøm trong noù moät khoái löôïng töông ñoái lôùn tri thöùc veà moät ñoái töôïng, söï kieän, vò trí, tình huoáng hoaëc nhöõng yeáu toá khaùc. Do ñoù, frame coù theå giuùp ta moâ taû khaù chi tieát moät ñoái töôïng. Döôùi moät khía caïnh naøo ñoù, ngöôøi ta coù theå xem phöông phaùp bieåu dieãn tri thöùc baèng frame chính laø nguoàn goác cuûa ngoân ngöõ laäp trình höôùng ñoái töôïng. YÙ töôûng cuûa phöông phaùp naøy laø “thay vì baét ngöôøi duøng söû duïng caùc coâng cuï phuï nhö dao môû ñeå ñoà hoäp, ngaøy nay caùc haõng saûn xuaát ñoà hoäp thöôøng gaén keøm caùc naép môû ñoà hoäp ngay beân treân voû lon. Nhö vaäy, ngöôøi duøng seõ khoâng bao giôø phaûi lo laéng ñeán vieäc tìm moät thieát bò ñeå môû ñoà hoäp nöõa!”. Cuõng vaäy, yù töôûng chính cuûa frame (hay cuûa phöông phaùp laäp trình höôùng ñoái töôïng) laø khi bieåu dieãn moät tri thöùc, ta seõ “gaén keøm” nhöõng thao taùc thöôøng gaëp treân tri thöùc naøy. Chaúng haïn nhö khi moâ taû khaùi nieäm veà hình chöõ nhaät, ta seõ gaén keøm caùch tính chu vi, dieän tích. Frame thöôøng ñöôïc duøng ñeå bieåu dieãn nhöõng tri thöùc “chuaån” hoaëc nhöõng tri thöùc ñöôïc xaây döïng döïa treân nhöõng kinh nghieäm hoaëc caùc ñaëc ñieåm ñaõ ñöôïc hieåu bieát caën keõ. Boä naõo cuûa con ngöôøi chuùng ta vaãn luoân “löu tröõ” raát nhieàu caùc tri thöùc chung maø khi caàn, chuùng ta coù theå “laáy ra” ñeå vaän duïng noù trong nhöõng vaán ñeà caàn phaûi giaûi quyeát. Frame laø moät coâng cuï thích hôïp ñeå bieåu dieãn nhöõng kieåu tri thöùc naøy. - - 133
XI.2 Caáu truùc cuûa frame Moãi moät frame moâ taû moät ñoái töôïng (object). Moät frame bao goàm hai thaønh phaàn cô baûn laø slot vaø facet. Moät slot laø moät thuoäc tính ñaëc taû ñoái töôïng ñöôïc bieåu dieãn bôûi frame. Ví duï : trong frame moâ taû xe hôi, coù hai slot laø troïng löôïng vaø loaïi maùy. Moãi slot coù theå chöùa moät hoaëc nhieàu facet. Caùc facet (ñoâi luùc ñöôïc goïi laø slot “con”) ñaëc taû moät soá thoâng tin hoaëc thuû tuïc lieân quan ñeán thuoäc tính ñöôïc moâ taû bôûi slot. Facet coù nhieàu loaïi khaùc nhau, sau ñaây laø moät soá facet thöôøng gaëp. o Value (giaù trò) : cho bieát giaù trò cuûa thuoäc tính ñoù (nhö xanh, ñoû, tím vaøng neáu slot laø maøu xe). o Default (giaù trò maëc ñònh) : heä thoáng seõ töï ñoäng söû duïng giaù trò trong facet naøy neáu slot laø roãng (nghóa laø chaúng coù ñaëc taû naøo!). Chaúng haïn trong frame veà xe, xeùt slot veà soá löôïng baùnh. Slot naøy seõ coù giaù trò 4. Nghóa laø, maëc ñònh moät chieác xe hôi seõ coù 4 baùnh! o Range (mieàn giaù trò) : (töông töï nhö kieåu bieán), cho bieát giaù trò slot coù theå nhaän nhöõng loaïi giaù trò gì (nhö soá nguyeân, soá thöïc, chöõ caùi, ) o If added : moâ taû moät haønh ñoäng seõ ñöôïc thi haønh khi moät giaù trò trong slot ñöôïc theâm vaøo (hoaëc ñöôïc hieäu chænh). Thuû tuïc thöôøng ñöôïc vieát döôùi daïng moät script. o If needed : ñöôïc söû duïng khi slot khoâng coù giaù trò naøo. Facet moâ taû moät haøm ñeå tính ra giaù trò cuûa slot. 134 - -
Frame : XE HÔI Thuoäc lôùp : phöông tieän vaän chuyeån. Teân nhaø saûn xuaát : Audi Quoác gia cuûa nhaø saûn xuaát : Ñöùc Model : 5000 Turbo Frame MAÙY Loaïi xe : Sedan Xy-lanh : 3.19 inch Troïng löôïng : 3300lb Tyû leä neùn : 3.4 inche Soá löôïng cöûa : 4 (default) Xaêng : TurboCharger Hoäp soá : 3 soá töï ñoäng Maõ löïc : 140 hp Soá löôïng baùnh : 4 (default) Maùy (tham chieáu ñeán frame Maùy) Kieåu : In-line, overhead cam Soá xy-lanh : 5 Khaû naêng taêng toác 0-60 : 10.4 giaây ¼ daëm : 17.1 giaây, 85 mph. - - 135
XI.3 Tính keá thöøa Trong thöïc teá, moät heä thoáng trí tueä nhaân taïo thöôøng söû duïng nhieàu frame ñöôïc lieân keát vôùi nhau theo moät caùch naøo ñoù. Moät trong nhöõng ñieåm thuù vò cuûa frame laø tính phaân caáp. Ñaëc tính naøy cho pheùp keá thöøa caùc tính chaát giöõa caùc frame. Hình sau ñaây cho thaáy caáu truùc phaân caáp cuûa caùc loaïi hình hình hoïc cô baûn. Goác cuûa caây ôû treân cuøng töông öùng vôùi möùc ñoä tröøu töôïng cao nhaát. Caùc frame naèm ôû döôùi cuøng (khoâng coù frame con naøo) goïi laø laù. Nhöõng frame naèm ôû möùc thaáp hôn coù theå thöøa keá taát caû nhöõng tính chaát cuûa nhöõng frame cao hôn. Caùc frame cha seõ cung caáp nhöõng moâ taû toång quaùt veà thöïc theå. Frame coù caáp caøng cao thì möùc ñoä toång quaùt caøng cao. Thoâng thöôøng, frame cha seõ bao goàm caùc ñònh nghóa cuûa caùc thuoäc tính. Coøn caùc frame con seõ chöùa ñöïng giaù trò thöïc söï cuûa caùc thuoäc tính naøy. 136 - -
Ñoái töôïng hình hoïc Tam Töù Hình giaùc giaùc troøn Caân Vuoâng Thang Bình haønh Ñeàu Vuoâng- Thoi Chöõ Caân nhaät Vuoâng Hình 2.5 Moät ví duï bieåu dieãn caùc ñoái töôïng hình hoïc baèng frame Caùc kieåu döõ lieäu cô baûn : Area : numeric; // dieän tích Height : numeric; //chieàu cao Perimeter : numberic; //chu vi Side : numeric; //caïnh Diagonal : numeric; //ñöôøng cheùo - - 137
Radius : numeric; //baùn kính Angle : numeric; //goùc Diameter : numeric; //ñöôøng kính pi : (val:numeric = 3.14159) Frame : CIRCLE (hình troøn) r : radius; s : area; d p : perimeter; d : diameter; r d = 2 r; s = pi r2; p = 2 pi r; Frame RECTANGLE (hình chöõ nhaät) b1 : side; b1 b2 : side; s : area; p : perimeter; d2 b2 s = b1 b2; p = 2 (b1+b2); 2 2 2 d = b1 + b2 ; Frame SQUARE (hình vuoâng) Laø : RECTANGLE 138 - -
b1 = b2; Frame RHOMBUS (hình thoi) b : side; d1 : diagonal; d2 : diagonal; s : area; p : perimeter; d d alpha1 : angle; b h alpha2 : angle; h : height; alpha1 alpha2 cos (alpha2/2) d1 = h; s = d1 d2 / 2; p = 4 b; s = b h; cos (alpha2/2)/(2 b) = d2; Chuùng ta coù theå deã daøng khai baùo caùc ñoái töôïng hình hoïc khaùc theo caùch naøy. Sau khi ñaõ bieåu dieãn caùc tri thöùc veà caùc hình hình hoïc cô baûn xong, ta coù theå vaän duïng noù ñeå giaûi caùc baøi toaùn hình hoïc, chaúng haïn baøi toaùn tính dieän tích. Ví duï, cho hình vuoâng k vaø voøng troøn noäi tieáp c, bieát caïnh hình vuoâng coù chieàu daøi laø x, haõy vieát chöông trình ñeå tính dieän tích phaàn toâ ñen. - - 139
x Deã thaáy raèng, dieän tích phaàn toâ ñen chính laø hieäu giöõa dieän tích hình vuoâng vaø dieän tích hình troøn noäi tieáp. Dó nhieân laø baïn cuõng coù theå vieát moät chöông trình bình thöôøng ñeå tính toaùn, nhöng khi ñaõ “tích hôïp” caùc tri thöùc veà tính dieän tích beân trong bieåu dieãn, chöông trình cuûa chuùng ta trôû neân raát goïn nheï. Baïn haõy löu yù ba leänh ñöôïc in ñaäm trong ví duï döôùi. Leänh ñaàu tieân seõ “ñaëc taû” laïi giaû thieát “hình vuoâng coù caïnh vôùi chieàu daøi x”, leänh keá tieáp ñaëc taû giaû thieát “hình troøn noäi tieáp”, coøn leänh thöù ba moâ taû vieäc tính dieän tích baèng caùch laáy dieän tích hình vuoâng tröø cho dieän tích hình troøn. VAR x, s : numeric; k : square; c : circle; BEGIN ; k.b1 := x; c.d := x; s := k.s – c.s; END. 140 - -
Nhö vaäy, chöông trình maùy tính cuûa chuùng ta ñaõ hoaït ñoäng khaù gioáng nhö vieäc “moâ taû” caùc giaûi baøi toaùn baèng ngoân ngöõ töï nhieân. Haõy nghó xa hôn moät tí. Caùc baøi toaùn hình hoïc thöôøng ñöôïc moâ taû baèng caùc ngoân töø khaù chính xaùc (chaúng haïn nhö : cho moät tam giaùc vôùi chieàu cao xuaát phaùt töø ñænh A laø 5, chieàu daøi caïnh ñaùy laø 6 ). Do ñoù, veà maët nguyeân taùc, chuùng ta vaãn coù theå xaây döïng moät chöông trình ñeå “hieåu” nhöõng ñeà baøi naøy (theo nhö caùch maø chuùng ta vöøa laøm). Sau ñoù, ngöôøi duøng coù theå hoaøn toaøn nhôø maùy tính giaûi giuùp baøi toaùn cho mình baèng caùch moâ taû lôøi giaûi cho maùy tính (chöù khoâng caàn phaûi laäp trình). Baïn coù caûm giaùc ñieàu naøy thaät thuù vò khoâng? Ñaây chính laø böôùc ñi ñaàu tieân trong vieäc taïo ra moät chöông trình trôï giuùp cho vieäc giaûi caùc baøi toaùn hình hoïc treân maùy tính vôùi giao tieáp baèng ngoân ngöõ töï nhieân! Ñeå taêng theâm söùc maïnh cho heä thoáng naøy, ngöôøi ta thöôøng caøi ñaët moät maïng ngöõ nghóa ngay beân trong moãi frame. Chaúng haïn, ta coù theå coù moät frame TRIANGLE, trong ñoù caøi ñaët moät maïng ngöõ nghóa (gioáng nhö ôû ví duï trong phaàn maïng ngöõ nghóa) ñeå ñaëc taû moái lieân heä giöõa caùc yeáu toá tam giaùc (thay vì söû duïng caùc coâng thöùc lieân heä ñôn giaûn nhö ví duï treân). - - 141
XII. BIEÅU DIEÃN TRI THÖÙC BAÈNG SCRIPT Script laø moät caùch bieåu dieãn tri thöùc töông töï nhö frame nhöng thay vì ñaëc taû moät ñoái töôïng, noù moâ taû moät chuoãi caùc söï kieän. Ñeå moâ taû chuoãi söï kieän, script söû duïng moät daõy caùc slot chöùa thoâng tin veà caùc con ngöôøi, ñoái töôïng vaø haønh ñoäng lieân quan ñeán söï kieän ñoù. Tuy caáu truùc cuûa caùc script laø raát khaùc nhau tuøy theo baøi toaùn, nhöng nhìn chung moät script thöôøng bao goàm caùc thaønh phaàn sau : o Ñieàu kieän vaøo (entry condition): moâ taû nhöõng tình huoáng hoaëc ñieàu kieän caàn ñöôïc thoûa maõn tröôùc khi caùc söï kieän trong script coù theå dieãn ra. o Role (dieãn vieân): laø nhöõng con ngöôøi coù lieân quan trong script. o Prop (taùc toá): laø taát caû nhöõng ñoái töôïng ñöôïc söû duïng trong caùc chuoãi söï kieän seõ dieãn ra. o Scene(Tình huoáng) : laø chuoãi söï kieän thöïc söï dieãn ra. o Result (Keát quaû) : traïng thaùi cuûa caùc Role sau khi script ñaõ thi haønh xong. o Track (phieân baûn) : moâ taû moät bieán theå (hoaëc tröôøng hôïp ñaëc bieät) coù theå xaûy ra trong ñoaïn script. Sau ñaây laø moät ví duï tieâu bieåu cho script. Ví duï naøy laø moät bieán theå cuûa ví duï noåi tieáng veà nhaø haøng baùn thöùc aên nhanh (caùc nhaø haøng baùn gaø raùn maø ta thöôøng gaëp trong caùc sieâu thò!) thöôøng ñöôïc söû duïng ñeå minh hoïa caùch bieåu 142 - -
dieãn tri thöùc baèng script trong caùch saùch noùi veà trí tueä nhaân taïo. Ñi aên trong moät nhaø haøng laø moät tình huoáng thöôøng gaëp trong cuoäc soáng vôùi nhöõng ñieàu kieän vaøo, dieãn vieân, taùc toá, hoaøn caûnh, keát quaû khaù “chuaån”. Vaø qua script ôû ví duï, baïn seõ thaáy phöông phaùp naøy coù theå ñöôïc duøng ñeå moâ taû chính xaùc nhöõng tình huoáng dieãn ra haøng ngaøy cuûa nhöõng nhaø haøng baùn thöùc aên nhanh. Caùc tình huoáng laø nhöõng ñoaïn script con trong ñoaïn script chính ñeå moâ taû nhöõng tình huoáng nhoû trong toaøn boä quaù trình. Löu yù raèng trong ñoaïn script naøy coù tình huoáng tuøy choïn trong ñoù moâ taû vieäc khaùch haøng mua thöùc aên veà thay vì vaøo nhaø haøng aên. Script “nhaø haøng” Phieân baûn : Nhaø haøng baùn thöùc aên nhanh Dieãn vieân : Khaùch haøng Ngöôøi phuïc vuï Taùc toá : Baøn phuïc vuï Choã ngoài Khay ñöïng thöùc aên Thöùc aên Tieàn Caùc loaïi gia vò nhö muoái, töông, ôùt, tieâu, Ñieàu kieän vaøo : Khaùch haøng ñoùi Khaùch haøng coù ñuû tieàn ñeå traû. Tình huoáng 1 : Vaøo nhaø haøng Khaùch haøng ñaäu xe vaøo baõi ñaäu xe. - - 143
Khaùch haøng böôùc vaøo nhaø haøng. Khaùch haøng xeáp haøng tröôùc baøn phuïc vuï. Khaùch haøng ñoïc thöïc ñôn treân töôøng vaø quyeát ñònh seõ keâu moùn aên gì. Tình huoáng 2: Keâu moùn aên. Khaùch haøng keâu moùn aên vôùi ngöôøi phuïc vuï (ñang ñöùng ôû quaày phuïc vuï) Ngöôøi phuïc vuï ñaët thöùc aên leân khay vaø ñöa hoùa ñôn tính tieàn cho khaùch. Khaùch haøng traû tieàn cho ngöôøi phuïc vuï. Tình huoáng 3: Khaùch haøng duøng moùn aên Khaùch haøng laáy theâm caùc gia vò Khaùch haøng caàm khay ñeán moät baøn coøn troáng. Khaùch haøng aên thöùc aên. Tình huoáng 3A (tuøy choïn) : Khaùch haøng mua thöùc aên ñem veà Khaùch haøng mang thöùc aên veà nhaø. Tình huoáng 4 : Ra veà Khaùch haøng thu doïn baøn Khaùch haøng boû raùc (thöùc aên thöøa, xöông, maûng vuïn ) vaøo thuøng raùc. Khaùch haøng ra khoûi nhaø haøng. Khaùch haøng laùi xe ñi. Keát quaû : Khaùch haøng khoâng coøn ñoùi. Khaùch haøng coøn ít tieàn hôn ban ñaàu. Khaùch haøng vui veû * Khaùch haøng böïc mình * Khaùch haøng quaù no. * Tuøy choïn. 144 - -
Script raát höõu duïng trong vieäc döï ñoaùn ñieàu gì seõ xaûy ñeán trong nhöõng tình huoáng xaùc ñònh. Thaäm chí trong nhöõng tình huoáng chöa dieãn ra, script coøn cho pheùp maùy tính döï ñoaùn ñöôïc vieäc gì seõ xaûy ra vaø xaûy ra ñoái vôùi ai vaø vaøo thôøi ñieåm naøo. Neáu maùy tính kích hoaït moät script, ngöôøi duøng coù theå ñaët caâu hoûi vaø heä thoáng coù theå suy ra ñöôïc nhöõng caâu traû lôøi chính xaùc maø khoâng caàn ngöôøi duøng cung caáp theâm nhieàu thoâng tin (trong moät soá tröôøng hôïp coù theå khoâng caàn theâm thoâng tin). Do ñoù, cuõng gioáng nhö frame, script laø moät daïng bieåu dieãn tri thöùc töông ñoái höõu duïng vì noù cho pheùp ta moâ taû chính xaùc nhöõng tình huoáng “chuaån” maø con ngöôøi vaãn thöïc hieän moãi ngaøy hoaëc ñaõ naém baét chính xaùc. Ñeå caøi ñaët script trong maùy tính, baïn phaûi tìm caùch löu tröõ caùc tri thöùc döôùi daïng hình thöùc. LISP laø ngoân ngöõ laäp trình phuø hôïp nhaát ñeå laøm ñieàu naøy. Sau khi ñaõ caøi ñaët xong script, baïn (ngöôøi duøng) coù theå ñaët caâu hoûi veà nhöõng con ngöôøi hoaëc ñieàu kieän coù lieân quan trong script. Heä thoáng sau ñoù seõ tieán haønh thao taùc tìm kieám hoaëc thao taùc so maãu ñeå tìm caâu traû lôøi. Chaúng haïn baïn coù theå ñaët caâu hoûi “Khaùch haøng laøm gì tröôùc tieân?”. Heä thoáng seõ tìm thaáy caâu traû lôøi trong scene 1 vaø ñöa ra ñaùp aùn “Ñaäu xe vaø böôùc vaøo nhaø haøng”. - - 145
XIII. PHOÁI HÔÏP NHIEÀU CAÙCH BIEÅU DIEÃN TRI THÖÙC Muïc tieâu chính bieåu dieãn tri thöùc trong maùy tính laø phuïc vuï cho vieäc thu nhaän tri thöùc vaøo maùy tính, truy xuaát tri thöùc vaø thöïc hieän caùc pheùp suy luaän döïa treân nhöõng tri thöùc ñaõ löu tröõ. Do ñoù, ñeå thoûa maõn ñöôïc ba muïc tieâu treân, khi choïn phöông phaùp bieåu dieãn tri thöùc, chuùng ta phaûi caân nhaéc moät soá yeáu toá cô baûn sau ñaây : o Tính töï nhieân, ñoàng boä vaø deã hieåu cuûa bieåu dieãn tri thöùc. o Möùc ñoä tröøu töôïng cuûa tri thöùc : tri thöùc ñöôïc khai baùo cuï theå hay nhuùng vaøo heä thoáng döôùi daïng caùc maõ thuû tuïc? o Tính ñôn theå vaø linh ñoäng cuûa cô sôû tri thöùc (coù cho pheùp deã daøng boå sung tri thöùc, möùc ñoä phuï thuoäc giöõa caùc tri thöùc, ) o Tính hieäu quaû trong vieäc truy xuaát tri thöùc vaø söùc maïnh cuûa caùc pheùp suy luaän (theo kieåu heuristic) . Baûng sau cho chuùng ta moät soá öu vaø khuyeát ñieåm cuûa caùc phöông phaùp bieåu dieãn tri thöùc ñaõ ñöôïc trình baøy. Baûng 2.1 P.Phaùp Öu ñieåm Nhöôïc ñieåm Luaät sinh Cuù phaùp ñôn giaûn, deã hieåu, dieãn Raát khoù theo doõi söï dòch ñôn giaûn, tính ñôn theå cao, phaân caáp, khoâng hieäu linh ñoäng (deã ñieàu chænh). quaû trong nhöõng heä thoáng lôùn, khoâng theå bieåu dieãn ñöôïc moïi loaïi tri thöùc, raát yeáu 146 - -
trong vieäc bieåu dieãn caùc tri thöùc daïng moâ taû, coù caáu truùc. Maïng ngöõ Deã theo doõi söï phaân caáp, seõ doø Ngöõ nghóa gaén lieàn nghóa theo caùc moái lieân heä, linh ñoäng vôùi moãi ñænh coù theå nhaäp nhaèng, khoù xöû lyù caùc ngoaïi leä, khoù laäp trình. Frame Coù söùc maïnh dieãn ñaït toát, deã caøi Khoù laäp trình, khoù suy ñaët caùc thuoäc tính cho caùc slot dieãn, thieáu phaàn meàm cuõng nhö caùc moái lieân heä, deã hoã trôï. daøng taïo ra caùc thuû tuïc chuyeân bieät hoùa, deã ñöa vaøo caùc thoâng tin maëc ñònh vaø deã thöïc hieän caùc thao taùc phaùt hieän caùc giaù trò bò thieáu soùt. Logic hình Cô cheá suy luaän chính xaùc (ñöôïc Taùch rôøi vieäc bieåu thöùc chöùng minh bôûi toaùn hoïc). dieãn vaø xöû lyù, khoâng hieäu quaû vôùi löôïng döõ lieäu lôùn, quaù chaäm khi cô sôû döõ lieäu lôùn. Tuy vaäy, nhö chuùng ta ñaõ bieát, hieän nay vaãn chöa coù moät kieåu bieåu dieãn tri thöùc naøo phuø hôïp vôùi moïi tình huoáng. Do ñoù, khi phaûi laøm vieäc vôùi nhieàu nguoàn tri thöùc khaùc nhau (khaùc loaïi, khaùc tính chaát), chuùng ta nhieàu luùc phaûi hy sinh tính ñoàng boä baèng caùch söû duïng cuøng luùc nhieàu kieåu bieåu dieãn tri thöùc, moãi kieåu bieåu dieãn öùng vôùi moät nhieäm vuï con. Nhöng nhö vaäy, chuùng ta laïi naûy sinh ra vaán ñeà “dòch” moät tri thöùc töø kieåu bieåu dieãn naøy sang kieåu bieåu dieãn khaùc. Tuy theá nhöng moät soá heä chöông - - 147
trình trí tueä gaàn ñaây vaãn duøng cuøng luùc nhieàu kieåu bieåu dieãn döõ lieäu khaùc nhau. Moät trong nhöõng ví duï keát hôïp nhieàu kieåu bieåu dieãn tri thöùc maø chuùng ta ñaõ töøng laøm quen laø kieåu keát hôïp giöõa frame vaø maïng ngöõ nghóa trong vieäc trôï giuùp giaûi baøi toaùn hình hoïc. Moät trong nhöõng söï phoái hôïp töông ñoái thaønh coâng laø söï keát hôïp giöõa luaät sinh vaø frame. Luaät sinh khoâng ñuû hieäu quaû trong nhieàu öùng duïng, ñaëc bieät laø trong caùc taùc vuï ñònh nghóa, moâ taû caùc ñoái töôïng hoaëc nhöõng moái lieân keát tónh giöõa caùc ñoái töôïng. Tuy vaäy, nhöõng yeáu ñieåm naøy laïi chính laø öu ñieåm cuûa frame. Ngaøy nay, ñaõ coù raát nhieàu heä thoáng ñaõ taïo ra moät kieåu bieåu dieãn lai giöõa luaät sinh vaø frame coù ñöôïc öu ñieåm cuûa hai caùch bieåu dieãn. Söï thaønh coâng cuûa caùc heä thoáng noåi tieáng nhö KEE, Level5 Object vaø Nexpert Object ñaõ minh chöùng cho ñieàu naøy. Frame cung caáp moät ngoân ngöõ caáu truùc hieäu quaû ñeå ñaëc taû nhöõng ñoái töôïng xuaát hieän trong caùc luaät. Frame coøn ñoùng vai troø nhö moät lôùp hoã trôï cho thao taùc suy dieãn cô baûn treân nhöõng ñoái töôïng khoâng caàn phaûi töông taùc moät caùch töôøng minh trong caùc luaät. Khaû naêng phaân lôùp cuûa frame coøn coù theå ñöôïc duøng ñeå phaân hoaïch, taïo chæ muïc vaø saép xeáp caùc luaät sinh trong heä thoáng. Khaû naêng naøy raát thích hôïp cho ngöôøi duøng trong vieäc xaây döïng vaø hieåu caùc luaät, cuõng nhö cuõng coù theå theo doõi ñöôïc caùc luaät ñöôïc söû duïng khi naøo vaø cho muïc gì. 148 - -
Hình sau cho thaáy moät kieåu keát hôïp giöõa luaät sinh vaø frame. Söï keát hôïp naøy ñaõ cho pheùp taïo ra caùc luaät so maãu nhaèm taêng toác ñoä tìm kieám cuûa heä thoáng. Keát quaû cuûa söï keát hôïp naøy cho pheùp taïo ra caùc bieåu dieãn phöùc taïp hôn raát nhieàu so vôùi vieäc chæ duøng frame, thaäm chí phöùc taïp hôn caû vieäc laäp trình tröïc tieáp baèng ngoân ngöõ C++ !!. CAÙC KYÕ THUAÄT CUÛA LUAÄT SINH Caùc luaät Suy luaän luøi Suy luaän tieán Caùc luaät so maãu Demon Suy luaän khoâng chaéc chaén * Caùc kyõ thuaät veà raøng buoäc. Ñoái töôïng Thöøa keá vaø chuyeân bieät hoùa Caùc cô cheá truyeàn thoâng ñieäp FRAME (KYÕ THUAÄT HÖÔÙNG ÑOÁI TÖÔÏNG) * Suy luaän khoâng chaéc chaén (Hypothetical reasoning) laø kyõ thuaät suy luaän döïa treân caùc ñieàu kieän coù theå coù maâu thuaãn hoaëc khoâng chaéc chaén. Ví duï keát hôïp bieåu dieãn tri thöùc baèng luaät sinh vaø frame trong baøi toaùn ñieàu cheá chaát hoùa hoïc - - 149
Vaán ñeà : Cho tröôùc moät soá chaát hoùa hoïc. Haõy xaây döïng chuoãi caùc phaûn öùng hoùa hoïc ñeå ñieàu cheá moät soá chaát hoùa hoïc khaùc. Ñaàu tieân, ñaây laø moät öùng duïng heát söùc töï nhieân cuûa tri thöùc bieåu dieãn döôùi daïng luaät. Lyù do laø vì baûn thaân caùc phaûn öùng hoùa hoïc tieâu chuaån ñeàu ñöôïc theå hieän döôùi daïng luaät. Chaúng haïn ta coù caùc phöông trình phaûn öùng sau : Na + Cl2 NaCl 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ö vaäy, neáu xem moät chaát hoùa hoïc laø moät söï kieän vaø moät phöông trình phaûn öùng nhö laø moät luaät daãn thì baøi toaùn ñieàu cheá chaát hoùa hoïc, moät caùch raát töï nhieân, trôû thaønh baøi toaùn suy luaän tieán trong cô sôû tri thöùc daïng luaät daãn. Tuy nhieân, soá löôïng caùc phaûn öùng laø raát lôùn, neân ta khoâng theå söû duïng caùc luaät döïa treân caùc phaûn öùng cuï theå 150 - -
nhö vaäy maø phaûi söû duïng caùc phaûn öùng toång quaùt hôn nhö : Axit + Bazô Muoái + Nöôùc Kieàm + Nöôùc Xuùt + H2 (trong hoùa hoïc cuõng coù nhieàu phaûn öùng raát ñaëc bieät khoâng theå toång quaùt ñöôïc, trong tröôøng hôïp naøy, ta seõ xem phaûn öùng ñoù nhö laø moät luaät rieâng!). Ñeå moâ taû ñöôïc caùc phaûn öùng toång quaùt nhö treân, ta seõ söû duïng caùc frame. Chaúng haïn ñeå ñaëc taû acid sulfuric H2SO4 ta söû duïng caùc frame toång quaùt sau. FRAME : ACID Teân : xaùc ñònh bôûi frame con. Caáu taïo #1 : H2 #2 : laø moät goác acid. FRAME : ACID SULFURIC FRAME : GOÁC ACID SO4 Teân : Acid Sulfuric Caáu taïo Caáu taïo #1 : S04 #1 : H2 #2 : goác acid S04 Laø : ACID Dó nhieân laø trong caùc frame ôû treân coøn raát nhieàu thuoäc tính hoùa hoïc khaùc. ÔÛ ñaây chuùng toâi chæ trình baøy sô löôïc veà maët yù töôûng ñeå baïn ñoïc coù cô sôû baét ñaàu. YÙ töôûng naøy - - 151
ñaõ ñöôïc moät soá sinh vieân naêm 4 cuûa khoa Coâng ngheä Thoâng tin Ñaïi hoïc Khoa hoïc Töï nhieân - Ñaïi hoïc Quoác gia TP. Hoà Chí Minh caøi ñaët thaønh coâng. Chöông trình chaïy toát trong phaïm vi caùc phaûn öùng trong saùch giaùo khoa lôùp 10, 11 vaø 12. 152 - -
Chöông 3 MÔÛ ÑAÀU VEÀ MAÙY HOÏC Trong chöông tröôùc, chuùng ta ñaõ tìm hieåu caùch thöùc chuyeån giao tri thöùc moät caùch tröïc tieáp cho maùy tính. Ñeán ñaây, maùy tính cuõng vaãn coøn thuï ñoäng. Trong chöông naøy chuùng ta seõ tìm hieåu caùc phöông phaùp giuùp maùy tính coù theå chuû ñoäng ruùt ra ñöôïc tri thöùc baèng caùch “quan saùt” caùc döõ lieäu do con ngöôøi cung caáp. I. THEÁ NAØO LAØ MAÙY HOÏC ? Thuaät ngöõ “hoïc” theo nghóa thoâng thöôøng laø tieáp thu tri thöùc ñeå bieát caùch vaän duïng. ÔÛ ngoaøi ñôøi, quaù trình hoïc dieãn ra döôùi nhieàu hình thöùc khaùc nhau nhö hoïc thuoäc loøng (hoïc veït), hoïc theo kinh nghieäm (hoïc döïa theo tröôøng hôïp), hoïc theo kieåu nghe nhìn Treân maùy tính cuõng coù nhieàu thuaät toaùn hoïc khaùc nhau. Tuy nhieân, trong phaïm vi cuûa giaùo trình naøy, chuùng ta chæ khaûo saùt phöông phaùp hoïc döïa theo tröôøng hôïp. Theo phöông phaùp naøy, heä thoáng seõ ñöôïc cung caáp moät soá caùc tröôøng hôïp “maãu”, döïa treân taäp maãu naøy, heä thoáng seõ tieán haønh phaân tích vaø ruùt ra caùc quy luaät (bieåu dieãn baèng luaät sinh). Sau ñoù, heä thoáng seõ döïa treân caùc luaät naøy ñeå “ñaùnh giaù” caùc tröôøng hôïp khaùc (thöôøng khoâng gioáng nhö caùc tröôøng hôïp “maãu”). Ngay caû chæ vôùi kieåu hoïc naøy, chuùng ta cuõng ñaõ coù nhieàu thuaät toaùn hoïc khaùc nhau. Moät laàn nöõa, vôùi muïc ñích giôùi thieäu, chuùng ta chæ khaûo saùt moät tröôøng hôïp ñôn giaûn. Coù theå - - 153
khaùi quaùt quaù trình hoïc theo tröôøng hôïp döôùi daïng hình thöùc nhö sau : Döõ lieäu cung caáp cho heä thoáng laø moät aùnh xaï f trong ñoù öùng moät tröôøng hôïp p trong taäp hôïp P vôùi moät “lôùp” r trong taäp R. f : P R p r Tuy nhieân, taäp P thöôøng nhoû (vaø höõu haïn) so vôùi taäp taát caû caùc tröôøng hôïp caàn quan taâm P’ (P  P’). Muïc tieâu cuûa chuùng ta laø xaây döïng aùnh xaï f ’ sao cho coù theå öùng moïi tröôøng hôïp p’ trong taäp P’ vôùi moät “lôùp” r trong taäp R. Hôn nöõa, f ’ phaûi baûo toaøn f, nghóa laø : Vôùi moïi p P thì f(p)  f ’(p) f ’ P’ R f P Hình 3.1: Hoïc theo tröôøng hôïp laø tìm caùch xaây döïng aùnh xaï f’ döïa theo aùnh xaï f. f ñöôïc goïi laø taäp maãu. 154 - -
Phöông phaùp hoïc theo tröôøng hôïp laø moät phöông phaùp phoå bieán trong caû nghieân cöùu khoa hoïc vaø meâ tín dò ñoan. Caû hai ñeàu döïa treân caùc döõ lieäu quan saùt, thoáng keâ ñeå töø ñoù ruùt ra caùc quy luaät. Tuy nhieân, khaùc vôùi khoa hoïc, meâ tín dò ñoan thöôøng döïa treân taäp maãu khoâng ñaëc tröng, cuïc boä, thieáu cô sôû khoa hoïc. II. HOÏC BAÈNG CAÙCH XAÂY DÖÏNG CAÂY ÑÒNH DANH Phaùt bieåu hình thöùc coù theå khoù hình dung. Ñeå cuï theå hôïn, ta haõy cuøng nhau quan saùt moät ví duï. Nhieäm vuï cuûa chuùng ta trong ví duï naøy laø xaây döïng caùc quy luaät ñeå coù theå keát luaän moät ngöôøi nhö theá naøo khi ñi taém bieån thì bò chaùy naéng. Ta goïi tính chaát chaùy naéng hay khoâng chaùy naéng laø thuoäc tính quan taâm (thuoäc tính muïc tieâu). Nhö vaäy, trong tröôøng hôïp naøy, taäp R cuûa chuùng ta chæ goàm coù hai phaàn töû {“chaùy naéng”, “bình thöôøng”}. Coøn taäp P laø taát caû nhöõng ngöôøi ñöôïc lieät keâ trong baûng döôùi (8 ngöôøi) Chuùng ta quan saùt hieän töôïng chaùy naéng döïa treân boán thuoäc tính sau : chieàu cao (cao, trung bình, thaáp), maøu toùc (vaøng, naâu, ñoû) caân naëng (nheï, trung bình, naëng), duøng kem (coù, khoâng),. Ta goïi caùc thuoäc tính naøy goïi laø thuoäc tính daãn xuaát. Dó nhieân laø trong thöïc teá ñeå coù theå ñöa ra ñöôïc moät keát luaän nhö vaäy, chuùng ta caàn nhieàu döõ lieäu hôn vaø ñoàng thôøi cuõng caàn nhieàu thuoäc tính daãn xuaát hơn. Ví duï ñôn giaûn naøy chæ nhaèm ñeå minh hoïa yù töôûng cuûa thuaät toaùn maùy hoïc maø chuùng ta saép trình baøy. - - 155
Teân Toùc Ch.Cao Caân Duøng Keát quaû Naëng kem? Sarah Vaøng T.Bình Nheï Khoâng Chaùy Dana Vaøng Cao T.Bình Coù Khoâng Alex Naâu Thaáp T.Bình Coù Khoâng Annie Vaøng Thaáp T.Bình Khoâng Chaùy Emilie Ñoû T.Bình Naëng Khoâng Chaùy Peter Naâu Cao Naëng Khoâng Khoâng John Naâu T.Bình Naëng Khoâng Khoâng Kartie Vaøng Thaáp Nheï Coù Khoâng YÙ töôûng ñaàu tieân cuûa phöông phaùp naøy laø tìm caùch phaân hoaïch taäp P ban ñaàu thaønh caùc taäp Pi sao cho taát caû caùc phaàn töû trong taát caû caùc taäp Pi ñeàu coù chung thuoäc tính muïc tieâu. P = P1  P2   Pn vaø (i,j) i j : thì (Pi  Pj =  ) vaø i, k,l : pk Pi vaø pl Pi thì f(pk) = f(pl) Sau khi ñaõ phaân hoaïch xong taäp P thaønh taäp caùc phaân hoaïch Pi ñöôïc ñaëc tröng bôûi thuoäc tính ñích ri (ri R), böôùc tieáp theo laø öùng vôùi moãi phaân hoaïch Pi ta xaây döïng luaät Li : GTi ri trong ñoù caùc GTi laø meänh ñeà ñöôïc hình thaønh baèng caùch keát hôïp caùc thuoäc tính daãn xuaát. Moät laàn nöõa, vaán ñeà hình thöùc coù theå laøm baïn caûm thaáy khoù khaên. Chuùng ta haõy thöû yù töôûng treân vôùi baûng soá lieäu maø ta ñaõ coù. 156 - -
Coù hai caùch phaân hoaïch hieån nhieân nhaát maø ai cuõng coù theå nghó ra. Caùch ñaàu tieân laø cho moãi ngöôøi vaøo moät phaân hoaïch rieâng (P1 = {Sarah}, P2 = {Dana}, toång coäng seõ coù 8 phaân hoaïch cho 8 ngöôøi). Caùch thöù hai laø phaân hoaïch thaønh hai taäp, moät taäp goàm taát caû nhöõng ngöôøi chaùy naéng vaø taäp coøn laïi bao goàm taát caû nhöõng ngöôøi khoâng chaùy naéng. Tuy ñôn giaûn nhöng phaân hoaïch theo kieåu naøy thì chuùng ta chaúng giaûi quyeát ñöôïc gì !! Chuùng ta haõy thöû moät phöông phaùp khaùc. Baây giôø baïn haõy quan saùt thuoäc tính ñaàu tieân – maøu toùc. Neáu döïa theo maøu toùc ñeå phaân chia ta seõ coù ñöôïc ba phaân hoaïch khaùc nhau öùng vôùi moãi giaù trò cuûa thuoäc tính maøu toùc, cuï theå laø : Pvaøng = { Sarah, Dana, Annie, Kartie } Pnaâu = { Alex, Peter, John } Pñoû = { Emmile } * Caùc ngöôøi bò chaùy naéng ñöôïc gaïch döôùi vaø in ñaäm. Thay vì lieät keâ ra nhö treân, ta duøng sô ñoà caây ñeå tieän moâ taû cho caùc böôùc phaân hoaïch sau : Maøu toùc ñoû vaøng naâu Emmile Sarah Dana Alex Peter Annie John Kartie - - 157
Quan saùt hình treân ta thaáy raèng phaân hoaïch Pnaâu vaø Pñoû thoûa maõn ñöôïc ñieàu kieän “coù chung thuoäc tính muïc tieâu” (Pnaâu chöùa toaøn ngöôøi khoâng chaùy naéng, Pñoû chöùa toaøn ngöôøi chaùy naéng). Coøn laïi taäp Pvaøng laø coøn laãn loän ngöôøi chaùy nắng vaø khoâng chaùy naéng. Ta seõ tieáp tuïc phaân hoaïch taäp naøy thaønh caùc taäp con. Baây giôø ta haõy quan saùt thuoäc tính chieàu cao. Thuoäc tính naøy giuùp phaân hoaïch taäp Pvaøng thaønh ba taäp con:PVaøng, Thaáp = {Annie, Kartie}, PVaøng, T.Bình= {Sarah} vaø PVaøng,Cao= { Dana } Neáu noái tieáp vaøo caây ôû hình tröôùc ta seõ coù hình aûnh caây phaân hoaïch nhö sau : Maøu toùc Đỏ Vàng Sarah Nâu Emmile Dana Annie Chieàu cao Alex Kartie Peter John Thaáp T.Bình Cao Annie Sarah Kartie Dana Quaù trình naøy cöù theá tieáp tuïc cho ñeán khi taát caû caùc nuùt laù cuûa caây khoâng coøn laãn loän giöõa chaùy naéng vaø khoâng chaùy naéng nöõa. Baïn cuõng thaáy raèng, qua moãi böôùc phaân hoaïch caây phaân hoaïch ngaøy caøng “phình” ra. Chính vì vaäy 158 - -
maø quaù trình naøy ñöôïc goïi laø quaù trình “ñaâm choài”. Caây maø chuùng ta ñang xaây döïng ñöôïc goïi laø caây ñònh danh. Ñeán ñaây, chuùng ta laïi gaëp moät vaán ñeà môùi. Neáu nhö ban ñaàu ta khoâng choïn thuoäc tính maøu toùc ñeå phaân hoaïch maø choïn thuoäc tính khaùc nhö chieàu cao chaúng haïn ñeå phaân hoaïch thì sao? Cuoái cuøng thì caùch phaân hoaïch naøo seõ toát hôn? Vaán ñeà maø chuùng ta gaëp phaûi cuõng töông töï nhö baøi toaùn tìm kieám : “Ñöùng tröôùc moät ngaõ reõ, ta caàn phaûi ñi vaøo höôùng naøo?”. Hai phöông phaùp ñaùnh giaù döôùi ñaây seõ giuùp ta choïn ñöôïc thuoäc tính phaân hoaïch taïi moãi böôùc xaây döïng caây ñònh danh. II.2.1. Quinlan Quinlan quyeát ñònh thuoäc tính phaân hoaïch baèng caùch xaây döïng caùc vector ñaëc tröng cho moãi giaù trò cuûa töøng thuoäc tính daãn xuaát vaø thuoäc tính muïc tieâu. Caùch tính cuï theå nhö sau : Vôùi moãi thuoäc tính daãn xuaát A coøn coù theå söû duïng ñeå phaân hoaïch, tính : VA(j) = ( T(j , r1), T(j , r2) , , T(j , rn)) - - 159
T(j, ri) = (toång soá phaàn töû trong phaân hoaïch coù giaù trò thuoäc tính daãn xuaát A laø j vaø coù giaù trò thuoäc tính muïc tieâu laø ri ) / ( toång soá phaàn töû trong phaân hoaïch coù giaù trò thuoäc tính daãn xuaát A laø j ) * trong ñoù r1, r2, , rn laø caùc giaù trò cuûa thuoäc tính muïc tieâu  * T(j, ri ) 1 i Nhö vaäy neáu moät thuoäc tính A coù theå nhaän moät trong naêm giaù trò khaùc nhau thì noù seõ coù naêm vector ñaëc tröng. Moät vector V(Aj ) ñöôïc goïi laø vector ñôn vò neáu noù chæ coù duy nhaát moät thaønh phaàn coù giaù trò 1 vaø nhöõng thaønh phaàn khaùc coù giaù trò 0. Thuoäc tính ñöôïc choïn ñeå phaân hoaïch laø thuoäc tính coù nhieàu vector ñôn vò nhaát. Trôû laïi ví duï cuûa chuùng ta, ôû traïng thaùi ban ñaàu (chöa phaân hoaïch) chuùng ta seõ tính vector ñaëc tröng cho töøng thuoäc tính daãn xuaát ñeå tìm ra thuoäc tính duøng ñeå phaân hoaïch. Ñaàu tieân laø thuoäc tính maøu toùc. Thuoäc tính maøu toùc coù ba giaù trò khaùc nhau (vaøng, ñoû, naâu) neân seõ coù ba vector ñaëc tröng töông öùng laø : VToùc (vaøng) = ( T(vaøng, chaùy naéng), T(vaøng, khoâng chaùy naéng) ) Soá ngöôøi toùc vaøng laø : 4 Soá ngöôøi toùc vaøng vaø chaùy naéng laø : 2 Soá ngöôøi toùc vaøng vaø khoâng chaùy naéng laø : 2 160 - -
Do ñoù VToùc(vaøng) = (2/4 , 2/4) = (0.5, 0.5) Töông töï VToùc(naâu) = (0/3, 3/3) = (0,1) (vector ñôn vò) Soá ngöôøi toùc naâu laø : 3 Soá ngöôøi toùc naâu vaø chaùy naéng laø : 0 Soá ngöôøi toùc naâu vaø khoâng chaùy naéng laø : 3 VToùc(ñoû) = (1/1, 0/1) = (1,0) (vector ñôn vò) Toång soá vector ñôn vò cuûa thuoäc tính toùc vaøng laø 2 Caùc thuoäc tính khaùc ñöôïc tính töông töï, keát quaû nhö sau : VC.Cao(Cao) = (0/2,2/2) = (0,1) VC.Cao(T.B) = (2/3,1/3) VC.Cao(Thaáp) = (1/3,2/3) VC.Naëng (Nheï) = (1/2,1/2) VC.Naëng (T.B) = (1/3,2/3) VC.Naëng (Naëng) = (1/3,2/3) VKem (Coù) = (3/3,0/3) = (1,0) VKem (Khoâng) = (3/5,2/5) - - 161
Nhö vaäy thuoäc tính maøu toùc coù soá vector ñôn vò nhieàu nhaát neân seõ ñöôïc choïn ñeå phaân hoaïch. Sau khi phaân hoaïch theo maøu toùc xong, chæ coù phaân hoaïch theo toùc vaøng (Pvaøng) laø coøn chöùa nhöõng ngöôøi chaùy naéng vaø khoâng chaùy naéng neân ta seõ tieáp tuïc phaân hoaïch taäp naøy. Ta seõ thöïc hieän thao taùc tính vector ñaëc tröng töông töï ñoái vôùi caùc thuoäc tính coøn laïi (chieàu cao, caân naëng, duøng kem). Trong phaân hoaïch Pvaøng, taäp döõ lieäu cuûa chuùng ta coøn laïi laø : Teân Chieàu cao Caân naëng Duøng kem? Keát quaû Sarah T.Bình Nheï Khoâng Chaùy Dana Cao T.Bình Coù Khoâng Annie Thaáp T.Bình Khoâng Chaùy Kartie Thaáp Nheï Coù Khoâng VC.Cao(Cao) = (0/1,1/1) = (0,1) VC.Cao(T.B) = (1/1,0/1) = (1,0) VC.Cao(Thaáp) = (1/2,1/2) VC.Naëng (Nheï) = (1/2,1/2) VC.Naëng (T.B) = (1/2,1/2) VC.Naëng (Naëng) = (0,0) VKem (Coù) = (0/2,2/2) = (0,1) VKem (Khoâng) = (2/2,0/2) = (1,0) 162 - -
Hai thuoäc tính duømg kem vaø chieàu cao ñeàu coù hai vector ñôn vò. Tuy nhieân, soá phaân hoaïch cuûa thuoäc tính duøng kem laø ít hôn neân ta choïn phaân hoaïch theo thuoäc tính duøng kem. Caây ñònh danh cuoái cuøng cuûa chuùng ta seõ nhö sau : Maøu toùc Sarah Emmile Dana Annie Duøng kem Alex Kartie Peter John Coù Khoâng Dana Kartie Sarah Annie II.2.2. Ñoä ño hoãn loaïn Thay vì phaûi xaây döïng caùc vector ñaëc tröng nhö phöông phaùp cuûa Quinlan, öùng vôùi moãi thuoäc tính daãn xuaát ta chæ caàn tính ra ñoä ño hoãn loaïn vaø löïa choïn thuoäc tính naøo coù ñoä ño hoãn loaïi laø thaáp nhaát. Coâng thöùc tính nhö sau : b b b j ri log ri TA =  b  b 2 b j t i j j trong ñoù : bt laø toång soá phaàn töû coù trong phaân hoaïch - - 163
bj laø toång soá phaàn töû coù thuoäc tính daãn xuaát A coù giaù trò j. bri : toång soá phaàn töû coù thuoäc tính daãn xuaát A coù giaù trò j vaø thuoäc tính muïc tieâu coù giaù trò i. Nguyeân taéc phaùt sinh taäp luaät töø caây ñònh danh khaù ñôn giaûn. ÖÙng vôùi moãi nuùt laù, ta chæ vieäc ñi töø ñænh cho ñeán nuùt laù ñoù vaø phaùt sinh ra luaät töông öùng. Cuï theå laø töø caây ñònh danh keát quaû ôû cuoái phaàn II.2 ta coù caùc luaät sau (xeùt caùc nuùt laù töø traùi sang phaûi) (Maøu toùc vaøng) vaø (coù duøng kem) khoâng chaùy naéng (Maøu toùc vaøng) vaø (khoâng duøng kem) chaùy naéng (Maøu toùc naâu) khoâng chaùy naéng (Maøu toùc ñoû) chaùy naéng Khaù ñôn giaûn phaûi khoâng? Coù leõ khoâng coù gì phaûi noùi gì theâm. Chuùng ta haõy thöïc hieän böôùc cuoái cuøng laø toái öu taäp luaät. II.4.1. Loaïi boû meänh ñeà thöøa Khaùc so vôùi caùc phöông phaùp loaïi boû meänh ñeà thöøa ñaõ ñöôïc trình baøy trong phaàn bieåu dieãn tri thöùc (chæ quan taâm ñeán logic hình thöùc), phöông phaùp loaïi boû meänh ñeà thöøa ôû ñaây döïa vaøo döõ lieäu. Vôùi ví duï vaø taäp luaät ñaõ coù ôû phaàn tröôùc, baïn haõy quan saùt luaät sau : 164 - -
(Maøu toùc vaøng) vaø (coù duøng kem) khoâng chaùy naéng Baây giôø ta haõy laäp moät baûng (goïi laø baûng Contigency), baûng thoáng keâ nhöõng ngöôøi coù duøng kem töông öùng vôùi toùc maøu vaøng vaø bò chaùy naéng hay khoâng. Trong döõ lieäu ñaõ cho, coù ba ngöôøi khoâng duøng kem. Khoâng chaùy naéng Chaùy naéng Maøu vaøng 2 0 Maøu khaùc 1 0 Theo baûng thoáng keâ naøy thì roõ raøng laø thuoäc tính toùc vaøng (trong luaät treân) khoâng ñoùng goùp gì trong vieäc ñöa ra keát luaän chaùy naéng hay khoâng (caû ba ngöôøi duøng kem ñeàu khoâng chaùy naéng) neân ta coù theå loaïi boû thuoäc tính toùc vaøng ra khoûi taäp luaät. Sau khi loaïi boû meänh ñeà thöøa, taäp meänh ñeà cuûa chuùng ta trong ví duï treân seõ coøn : (co ù duøng kem) khoâng chaùy naéng (Maøu toùc vaøng) vaø (khoâng duøng kem) chaùy naéng (Maøu toùc naâu) khoâng chaùy naéng (Maøu toùc ñoû) chaùy naéng Nhö vaäy quy taéc chung ñeå coù theå loaïi boû moät meänh ñeà laø nhö theá naøo? Raát ñôn giaûn, giaû söû luaät cuûa chuùng ta coù n meänh ñeà : A1 vaø A2 vaø vaø An R - - 165
Ñeå kieåm tra xem coù theå loaïi boû meänh ñeà Ai hay khoâng, baïn haõy laäp ra moät taäp hôïp P bao goàm caùc phaàn töû thoûa taát caû meänh ñeà A1 ,A2 , Ai-,Ai+1, , An (löu yù : khoâng caàn xeùt laø coù thoûa Ai hay khoâng, chæ caàn thoûa caùc meänh ñeà coøn laïi laø ñöôïc) Sau ñoù, baïn haõy laäp baûng Contigency nhö sau : R R Ai E F Ai G H trong ñoù E laø soá phaàn töû trong P thoûa caû Ai vaø R. F laø soá phaàn töû trong P thoûa Ai vaø khoâng thoûa R G laø soá phaàn töû trong P khoâng thoûa Ai vaø thoûa R H laø soá phaàn töû trong P khoâng thoûa Ai vaø khoâng thoûa R Neáu toång F + H = 0 thì coù theå loaïi boû meänh ñeà Ai ra khoûi luaät. II.4.2. Xaây döïng meänh ñeà maëc ñònh Coù moät vaán ñeà ñaët ra laø khi gaëp phaûi moät tröôøng hôïp maø taát caû caùc luaät ñeàu khoâng thoûa thì phaûi laøm nhö theá naøo? Moät caùch haønh ñoäng laø ñaët ra moät luaät maëc ñònh ñaïi loaïi nhö : Neáu khoâng coù luaät naøo thoûa chaùy naéng (1) Hoaëc 166 - -
Neáu khoâng coù luaät naøo thoûa khoâng chaùy naéng. (2) (chæ coù hai luaät vì thuoäc tính muïc tieâu chæ coù theå nhaän moät trong hai giaù trò laø chaùy naéng hay khoâng chaùy naéng) Giaû söû ta ñaõ choïn luaät maëc ñònh laø (2) thì taäp luaät cuûa chuùng ta seõ trôû thaønh : (Maøu toùc vaøng) vaø (khoâng duøng kem) chaùy naéng (Maøu toùc ñoû) chaùy naéng Neáu khoâng coù luaät naøo thoûa khoâng chaùy naéng. (2) Löu yù raèng laø chuùng ta ñaõ loaïi boû ñi taát caû caùc luaät daãn ñeán keát luaän khoâng chaùy naéng vaø thay noù baèng luaät maëc ñònh. Taïi sao vaäy? Bôûi vì caùc luaät naøy coù cuøng keát luaän vôùi luaät maëc ñònh. Roõ raøng laø chæ coù theå coù moät trong hai khaû naêng laø chaùy naéng hay khoâng. Vaán ñeà laø choïn luaät naøo? Sau ñaây laø moät soá quy taéc. 1) Choïn luaät maëc ñònh sao cho noù coù theå thay theá cho nhieàu luaät nhaát. (trong ví duï cuûa ta thì nguyeân taéc naøy khoâng aùp duïng ñöôïc vì coù hai luaät daãn ñeán chaùy naéng vaø hai luaät daãn ñeán khoâng chaùy naéng) 2) Choïn luaät maëc ñònh coù keát luaän phoå bieán nhaát. Trong ví duï cuûa chuùng ta thì neân choïn luaät (2) vì soá tröôøng hôïp khoâng chaùy naéng laø 5 coøn khoâng chaùy naéng laø 3. 3) Choïn luaät maëc ñònh sao cho toång soá meänh ñeà cuûa caùc luaät maø noù thay theá laø nhieàu nhaát. Trong ví duï cuûa chuùng - - 167
ta thì luaät ñöôïc choïn seõ laø luaät (1) vì toång soá meänh ñeà cuûa luaät daãn ñeán chaùy naéng laø 3 trong khi toång soá meänh ñeà cuûa luaät daãn ñeán khoâng chaùy naéng chæ laø 2. 168 - -
BAØI TAÄP CHÖÔNG 1 1) Vieát chöông trình giaûi baøi toaùn haønh trình ngöôøi baùn haøng rong baèng hai thuaät giaûi GTS1 vaø GTS2 trong tröôøng hôïp coù n ñòa ñieåm khaùc nhau. 2) Vieát chöông trình giaûi baøi toaùn phaân coâng coâng vieäc baèng caùch öùng duïng nguyeân lyù thöù töï. 3) ÖÙng duïng nguyeân lyù thöù töï, haõy giaûi baøi toaùn chia ñoà vaät sau. Coù n vaät vôùi khoái löôïng laàn löôït laø M1,M2, Mn. Haõy tìm caùch chia n vaät naøy thaønh hai nhoùm sao cho cheânh leäch khoái löôïng giöõa hai nhoùm naøy laø nhoû nhaát. 4) Vieát chöông trình giaûi baøi toaùn maõ ñi tuaàn. 5) Vieát chöông trình giaûi baøi toaùn 8 haäu. 6) Vieát chöông trình giaûi baøi toaùn Ta-canh baèng thuaät giaûi A*. 7) Vieát chöông trình giaûi baøi toaùn thaùp Haø Noäi baèng thuaät giaûi A*. 8) Vieát chöông trình tìm kieám ñöôøng ñi ngaén nhaát trong moät baûn ñoà toång quaùt. Baûn ñoà ñöôïc bieåu dieãn baèng - - 169
moät maûng hai chieàu A, trong ñoù A[x,y] = 0 laø coù theå ñi ñöôïc vaø A[x,y] = 1 laø vaät caûn. Cho pheùp ngöôøi duøng click chuoät treân maøn hình ñeå taïo baûn ñoà vaø xaùc ñònh ñieåm xuaát phaùt vaø keát thuùc. Chi phí ñeå ñi töø moät oâ baát kyø sang oâ keá caän noù laø 1. Môû roäng baøi toaùn trong tröôøng hôïp chi phí ñeå di chuyeån töø oâ (x,y) sang moät baát kyø keá (x,y) laø A[x,y]. CHÖÔNG 2 1) Vieát chöông trình minh hoïa caùc böôùc giaûi baøi toaùn ñong nöôùc (söû duïng ñoà hoïa caøng toát). 2) Vieát chöông trình caøi ñaët hai thuaät toaùn Vöông Haïo vaø Robinson trong ñoù lieät keâ caùc böôùc chöùng minh moät bieåu thöùc logic. 3) Vieát chöông trình giaûi baøi toaùn tam giaùc toång quaùt baèng maïng ngöõ nghóa (löu yù söû duïng thuaät toaùn kyù phaùp nghòch ñaûo Ba Lan) 4) Haõy thöû xaây döïng moät boä luaät phöùc taïp hôn trong ví duï ñaõ ñöôïc trình baøy duøng ñeå chuaån ñoaùn hoûng hoùc cuûa maùy tính. Vieát chöông trình öùng duïng boä luaät naøy trong vieäc chuaån ñoaùn hoûng hoùc cuûa maùy tính (söû duïng thuaät toaùn suy dieãn luøi). 170 - -