Bài giảng Trí tuệ nhân tạo (Bản mới)

240 trang ngocly 30

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo (Bản mới)", để 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:

bai_giang_tri_tue_nhan_tao_ban_moi.pdf

Nội dung text: Bài giảng Trí tuệ nhân tạo (Bản mới)

Muïc luïc CHÖÔNG 1 MÔÛ ÑAÀU 1 1. Heä thoáng thoâng minh 1 1.1. Kieåm soaùt tình huoáng vaø löïa choïn 1 1.2. Hoïc 2 1.3. Söû duïng tri thöùc 2 2. Giôùi thieäu trí tueä nhaân taïo 3 2.1. Moät soá ví duï 3 2.2. Khaùi nieäm 6 2.3. Heä cô sôû tri thöùc 7 3. Moät soá baøi toaùn 8 CHÖÔNG 2 GIAÛI QUYEÁT VAÁN ÑEÀ BAÈNG TÌM KIEÁM 13 1. Khaùi nieäm 13 1.1. Khoâng gian traïng thaùi 13 1.2. Tìm kieám treân khoâng gian traïng thaùi 15 2. Caùc nguyeân lyù tìm kieám 17 2.1. Caùc nguyeân lyù cô baûn 17 2.2. Caùc nguyeân lyù thöû sai 18 2.3. Caùc nguyeân lyù heuristic 19 2.4. Caøi ñaët caùc nguyeân lyù 22 3. Aùp duïng 23 3.1. Caøi ñaët thuaät giaûi 23 3.2. Giaûi quyeát vaán ñeà 25 CHÖÔNG 3 TÌM KIEÁM VÔÙI HEURISTIC 29 1. Khaùi nieäm 29 2. Thuaät giaûi A* 31
3. Thuaät giaûi A0* 34 3.1. Tìm kieám treân caây AND/OR 35 3.2. Theâm heuristic - Thuaät giaûi AO* 38 CHÖÔNG 4 TROØ CHÔI ÑOÁI KHAÙNG VAØ PHÖÔNG PHAÙP GPS 43 1. Troø chôi ñoái khaùng 43 1.1. Khaùi nieäm 43 1.2. Thuaät giaûi 44 1.3. Baøn theâm veà heuristic 49 2. Phöông phaùp giaûi quyeát vaán ñeà toång quaùt (GPS) 50 2.1. Khaùi nieäm 50 2.2. Thuaät giaûi 51 CHÖÔNG 5 SUY LUAÄN LOGIC 63 1. Suy luaän 63 2. Suy luaän vôùi logic meänh ñeà 64 2.1. Khaùi nieäm 64 2.2. Moät soá cô cheá phaùt sinh söï kieän (quy taéc suy dieãn) 65 2.3. Suy luaän 67 3. Suy luaän vôùi logic caáp 1 71 3.1. Khaùi nieäm 71 3.2. Suy luaän 72 CHÖÔNG 6 SUY LUAÄN VÔÙI THOÂNG TIN KHOÂNG CHAÉC CHAÉN 79 1. Phaân boá xaùc suaát 79 1.1. Khaùi nieäm 79 1.2. Suy luaän 81 2. Suy luaän xaáp xæ 83 2.1. Khaùi nieäm 83 2.2. Suy luaän 85 3. Giôùi thieäu moät soá suy luaän khaùc 87 3.1. Phaân boá khaû xuaát 87 3.2. Logic môø 88
CHÖÔNG 7 BIEÅU DIEÃN TRI THÖÙC 97 1. Tri thöùc 97 1.1. Khaùi nieäm 97 1.2. Bieåu dieãn tri thöùc 99 2. Bieåu dieãn baèng logic vò töø 100 2.1. Bieåu dieãn caùc tri thöùc ñôn giaûn 100 2.2. Bieåu dieãn moái quan heä Instance vaø isa 101 2.3. Suy dieãn baèng hôïp giaûi (resolution) 101 3. Bieåu dieãn baèng luaät saûn xuaát 103 3.1. Khaùi nieäm 103 3.2. Bieåu dieãn 105 3.3. Suy dieãn 105 3.4. Baøn theâm 106 4. Laäp trình logic 107 4.1. Caùc thaønh phaàn 107 4.2. Söï kieän vaø luaät 107 4.3. Hôïp giaûi vaø prolog 108 4.4. Moät soá ví duï 109 CHÖÔNG 8 CAÙC BIEÅU DIEÃN COÙ CAÁU TRUÙC 117 1. Maïng ngöõ nghóa 117 1.1. Khaùi nieäm 117 1.2. Bieåu dieãn 118 1.3. Suy dieãn 120 1.4. Ñoà thò khaùi nieäm 121 1.5. Chuyeån veà logic vò töø 123 1.6. Moät ví duï phöùc taïp 124 2. Giôùi thieäu moät soá bieåu dieãn khaùc 127 2.1. Bieåu dieãn baèng khung (Frames) 127 2.2. Bieåu dieãn tri thöùc baèng boä ba OAV 128 2.3. Boä nhôù keát hôïp (bieåu dieãn tri thöùc moâ phoûng heä thaàn kinh) 129 CHÖÔNG 9 THU NAÏP TRI THÖÙC 135 1. Môû ñaàu 135
2. Toång quan veà thu nhaän tri thöùc 136 2.1. Khaùi nieäm 136 1.1. Caùc caùch tieáp caän 138 3. Phöông phaùp caây quyeát ñònh 139 3.1. Khaùi nieäm 139 3.2. Tieáp caän cöïc tieåu Entropy trung bình 139 4. Phöông phaùp khoâng gian theá heä 141 4.1. Khaùi nieäm 141 4.2. Thuaät toaùn 141 5. Phöông phaùp xaây döïng moät giaûi thích 144 5.1. Khaùi nieäm 144 5.2. Thuaät toaùn 144 CHÖÔNG 10 MOÄT SOÁ CHUÛ ÑEÀ 151 1. Maïng neuron nhaân taïo 151 1.1. Khaùi nieäm 151 1.2. Giôùi thieäu moät soá luaät hoïc 154 2. Thuaät toaùn di truyeàn 158 2.1. Khaùi nieäm 158 2.2. Moâ hình vaø Thuaät toaùn 158 3. Xöû lyù raøng buoäc 161 3.1. Khaùi nieäm 161 3.2. Thuaät giaûi 164 4. Maùy vector hoã trôï (Supported Vector Machine - SVM) 167 4.1. Khaùi nieäm 167 4.2. Thuaät toaùn 167 4.3. Taùch phi tuyeán 168 PHUÏ LUÏC 2 NGOÂN NGÖÕ PROLOG 175 1. Giôùi thieäu prolog 175 1.1. Caùc thaønh phaàn cuûa chöông trình 175 1.2. Söï kieän vaø luaät 175 1.3. Quan heä 176
1.4. Caùc kieåu ñoái töôïng 177 1.5. Cô cheá tìm kieám 180 1.6. Vaøi ví duï laäp trình prolog 182 2. Thaûo luaän 185 2.1. Bieåu dieãn caây 185 2.2. Duøng ñaïi soá quan heä 188 PHUÏ LUÏC 3 NGHIEÂN CÖÙU TÌNH HUOÁNG 191 1. Thieát keá höôùng ñoái töôïng duøng C++ 191 1.1. Moät thieát keá ñôn giaûn 191 1.2. Moät thieát keá toång quaùt 194 2. Caøi ñaët thuaät toaùn A* baèng prolog 201 3. Xaây döïng heä chuyeân gia ñôn giaûn baèng prolog 203 3.1. Cô sôû tri thöùc 203 3.2. Caøi ñaët baèng prolog 203 4. Xaây döïng moät cô cheá thu nhaän tri thöùc 205 4.1. Cô sôû tri thöùc 205 4.2. Minh hoïa cô cheá hoïc 206 5. Ñoái saùnh 208 5.1. Khaùi nieäm 208 5.2. Ñoái saùnh bieåu thöùc 208 Lôøi noùi ñaàu Ngaøy nay, haàu heát caùc lónh vöïc ñeàu coù söï tham gia cuûa maùy tính. Trong moät soá lónh vöïc, vai troø cuûa maùy tính laø raát quan troïng. Theá nhöng, vaãn coøn ñoù nhieàu coâng vieäc, duø giaûn ñôn, duø nguy hieåm, duø nhaøm chaùn, con ngöôøi vaãn cöù phaûi ñaûm nhieäm. Lieäu coù theå xaây döïng nhöõng heä coù khaû naêng haønh ñoäng nhö con ngöôøi, suy
nghó nhö con ngöôøi. Nhöõng heä nhö vaäy seõ laøm thay con ngöôøi nhieàu vieäc, cuõng nhö hoã trôï con ngöôøi moät caùch hieäu quaû; ñeå con ngöôøi taäp trung vaøo nhöõng hoaït ñoäng mang tính saùng taïo. Trí tueä nhaân taïo (AI – Artificial Intelligence) laø moät nhaùnh cuûa coâng ngheä thoâng tin nghieân cöùu caùc phöông phaùp xaây döïng trí tueä cho maùy. Taøi lieäu naøy giôùi thieäu cho sinh vieân nhöõng khía caïnh cô sôû quan troïng cuûa AI. Taøi lieäu goàm 10 chöông ñöôïc chia laøm 4 phaàn chính. Chöông 1 giôùi thieäu veà AI. Phaàn 1, goàm caùc chöông 2, 3 vaø 4, giôùi thieäu caùc phöông phaùp giaûi quyeát vaán ñeà. Phaàn 2, goàm caùc chöông 5 vaø 6, giôùi thieäu caùc phöông phaùp suy luaän, caùc phöông phaùp xöû lyù thoâng tin khoâng chaéc chaén. Phaàn 3, goàm caùc chöông 7, 8 vaø 9, giôùi thieäu caùc phöông phaùp bieåu dieãn vaø thu nhaän tri thöùc. Phaàn 4, goàm chöông 10 vaø hai phuï luïc, giôùi thieäu moät soá chuû ñeà nhö maïng neuron nhaân taïo, thuaät toaùn di truyeàn, xöû lyù raøng buoäc; cuõng giôùi thieäu veà prolog vaø thöû giaûi quyeát moät soá tình huoáng. Duø raát coá gaéng, taøi lieäu ñöôïc vieát ra khoâng khoûi coù thieáu soùt. Raát mong söï goùp yù cuûa baïn ñoïc ñeå laàn taùi baûn sau ñöôïc toát hôn. Nhaân dòp naøy toâi xin chaân thaønh caûm ôn Ban chuû nhieäm khoa Coâng ngheä thoâng tin tröôøng Ñaïi hoïc Kyõ thuaät Coâng ngheä ñaõ taïo ñieàu kieän cho toâi hoaøn thaønh taøi lieäu naøy. Moïi yù kieán ñoùng goùp xin gôûi veà [email protected]. Xin chaân thaønh caûm ôn. TpHCM, Thaùng 07/2006 Taùc giaû
Chöông 1 Môû ñaàu Muïc tieâu cuûa AI laø xaây döïng nhöõng heä thoáng suy nghó vaø haønh ñoäng nhö con ngöôøi. Khi aáy heä thoáng seõ ñöôïc goïi laø thoâng minh. Noù phaûi coù khaû naêng giaûi quyeát vaán ñeà nhö con ngöôøi khi ñöùng tröôùc nhöõng tình huoáng töông töï. 1. Heä thoáng thoâng minh 1.1. Kieåm soaùt tình huoáng vaø löïa choïn Xeùt heä giaûi phöông trình baäc hai. Yeâu caàu heä giaûi nhöõng phöông trình sau: 1) x2 – 3x – 4 = 0 4) x2 – 4 = 0 2) x2 – 4x + 3 = 0 5) x2 + 1 = 0 3) x2 – 4x + 4 = 0 6) x2 – 4x + 5 = 0 Tröôøng hôïp 1 Vôùi heä luoân luoân tính theo moät thuû tuïc cho tröôùc, chaúng haïn vôùi phöông trình thöù 1: Tính Δ = 25 Suy ra x1 = -1, x2 = 4 Ta khoâng theå cho raèng heä laø thoâng minh. Tröôøng hôïp 2 Vôùi heä coù nhöõng traû lôøi baát ngôø, chaúng haïn vôùi Phöông trình thöù 1: Vì a – b + c = 0, ta coù x1 = -1 vaø x2 = -c/a = 4; Phöông trình thöù 2: Vì a + b + c = 0, ta coù x1 = 1 vaø x2 = c/a = 3; 2 Phöông trình thöù 3: Bieán ñoåi thaønh (x – 2) = 0, ta coù x1 = x2 = 2;
Phöông trình thöù 4: Bieán ñoåi thaønh (x – 2)(x + 2) = 0, ta coù x1= 2, x2 = -2 Phöông trình thöù 5: Vì x2 + 1 > 0, phöông trình voâ nghieäm; Phöông trình thöù 6: Vì Δ = -4<0, phöông trình voâ nghieäm. Vaø ta coù theå cho raèng heä laø thoâng minh. 1.2. Hoïc Xeùt moät troø chöông trình chôi côø vua ñôn giaûn. Vôùi nhöõng vaùn côø ñaàu tieân, chuùng ta thua noù vaø ta nghó noù laø thoâng minh. Cho ñeán khi ta tìm ñöôïc moät caùch thaéng vaø phaùt hieän thaáy duø thua, noù vaãn cöù thöïc hieän nhöõng nöôùc ñi cuõ. Theá laø ta thaát voïng, vì noù chôi quaù maùy moùc, chöông trình chaúng coøn tí gì laø thoâng minh. Neáu nhö noù coù khaû naêng ruùt ra kinh nghieäm töø nhöõng vaùn côø thua thì laïi khaùc. Töùc heä ñaõ coù khaû naêng hoïc. Trôû laïi heä giaûi phöông trình baäc hai. Ta laïi yeâu caàu heä giaûi phöông trình x2 – x + 6 = 0 Ta chôø ñôïi heä giaûi nhö sau: Tìm thaáy x = 3 laø nghieäm, suy ra x1 = 3, x2 = -2. Tuy nhieân heä khoâng bieát caùch giaûi naøy. Ta seõ daïy heä tri thöùc sau: thöû xem x coù laø nghieäm vôùi x = -3, -2, -1, 0, 1, 2, 3. Roài yeâu caàu heä giaûi laïi. Vaø heä giaûi nhö sau: Tìm thaáy x = -2 laø nghieäm, suy ra x1 = -2, x2 = 3. Baây giôø yeâu caàu heä giaûi phöông trình 1 ôû treân x2 – 3x – 4 = 0 Coù khaû naêng heä seõ giaûi khaùc vôùi caùch giaûi cuõ Tìm thaáy x = -1 laø nghieäm, suy ra x1 = -1, x2 = 4. 1.3. Söû duïng tri thöùc Tieáp tuïc vôùi heä giaûi phöông trình baäc hai. Baây giôø chuùng ta yeâu caàu heä giaûi moät phöông trình baäc ba x3 – 2x2 – x + 2 = 0 Coù theå heä khoâng giaûi ñöôïc. Tuy nhieân giaû söû heä coù tri thöùc: neáu a laø moät
nghieäm cuûa phöông trình f(x) = 0 thì nghieäm cuûa noù goàm a vaø caùc nghieäm cuûa phöông trình g(x) = 0, trong ñoù f(x) = (x – a)g(x). Baây giôø ta cung caáp cho heä moät nghieäm x = 1. Luùc naøy heä coù theå giaûi nhö sau: Vì 1 laø nghieäm, bieán ñoåi x3 – 2x2 – x + 2 = (x – 1)(x2 – x – 2) Phöông trình x2 – x – 2 = 0 coù a – b + c = 0 neân coù hai nghieäm laø 1 vaø 2 Vaäy phöông trình coù 3 nghieäm: x1 = -1, x2 = 1, x3 = 2 Muoán söû duïng ñöôïc tri thöùc chöông trình phaûi coù khaû naêng nhaän bieát caùc söï kieän, caùc moái lieân heä vaø suy luaän. Roõ raøng moät heä giaûi phöông trình baäc hai nhö vaäy xöùng ñaùng ñöôïc goïi laø thoâng minh. 2. Giôùi thieäu trí tueä nhaân taïo 2.1. Moät soá ví duï Ví duï 1.1 Tìm ñöôøng ñi ngaén nhaát töø N ñeán L vôùi baûng döõ lieäu ñöôïc cho nhö sau N → C 10 N → D 19 T → C 5 H → L 15 C → D 10 T → G 15 D → U 10 D → L 10 N → T 8 T → L 18 D → H 15 • Ta thaáy töø ñænh N coù theå ñi ñeán ñænh C, T hoaëc D. Neân choïn ñænh naøo? lyù do? Coù khaû naêng thu ñöôïc ñöôøng ñi toái öu khoâng? Giaû söû ta choïn ñænh C, vaø töø C coù theå ñi ñeán ñænh D.
• Coù neân ñi tieáp vaø choïn D hay quay lui ñeå choïn T hoaëc D? • Duø ta coù choïn phöông aùn naøo ñi nöõa thì cuõng phaûi giaûi thích ñöôïc laø vì sao? • Roõ raøng ta caàn moät chieán löôïc löïa choïn maø ta goïi laø suy dieãn. Chaúng haïn neáu suy dieãn theo höôùng öu tieân khoaûng caùch ngaén nhaát (toaøn cuïc treân taát caû caùc nhaùnh) thì ñöôøng ñi tìm thaáy seõ laø N→ T→ L. Coøn neáu suy dieãn tham lam (cuïc boä taïi ñænh choïn) thì ñöôøng ñi tìm thaáy seõ laø N→ C→ D→ L Ví duï 1.2 Chöùng minh meänh ñeà (⎤ a+⎤ b+c) ( ⎤ b+⎤ c+d) a b → d. Neáu caùch giaûi quyeát laø töông töï nhö ôû ví duï 1 thì caùi gì ñoùng vai troø ñænh? Hôn nöõa töø ñænh hieän haønh ta coù theå ñi ñeán caùc ñænh naøo? Laøm sao phaùt sinh ra caùc ñænh môùi? Thöû aùp duïng phöông phaùp chöùng minh phaûn chöùng cho ví duï naøy. Thay vì chöùng minh α → β ta ñi chöùng minh α ⎤ β → 0. Nhö vaäy meänh ñeà treân laø töông ñöông vôùi (⎤ a+⎤ b+c) ( ⎤ b+⎤ c+d) a b⎤ d → 0. Khaùc vôùi ví duï 1, ôû ñaây ta phaûi söû duïng tri thöùc. Vôùi tri thöùc ( α + ⎤ β ) β → α, ta coi nhö laø töø 2 ñænh α + ⎤ β vaø β phaùt sinh ra ñænh môùi α. Nhö vaäy ñænh ôû ñaây laø bieåu thöùc vaø luaät daãn laø cô cheá phaùt sinh ra ñænh môùi. Baét ñaàu suy dieãn vôùi caùc ñænh (⎤ a+⎤ b+c), ( ⎤ b+⎤ c+d), a, b vaø ⎤ d. • Töø 2 ñænh (⎤ a+⎤ b+c) vaø a sinh ra ñænh ⎤ b+c
• Roài töø ⎤ b+⎤ c+d vaø b cho ta ⎤ c+d • Cöù nhö vaäy cho ñeán ñích (goal) cuoái laø ñænh roãng ∅. • Caùc ñænh ôû ñaây ta goïi laø söï kieän. Caùc tri thöùc duøng ñeå phaùt sinh ñænh môùi nhö ( α + ⎤ β ) β → α ta goïi laø luaät. Vaø moät laàn nöõa, caâu hoûi “chieán löôïc phaùt sinh laø gì?” Laïi ñöôïc ñaët ra. Trong tình huoáng naøy, neáu löïa choïn phöông aùn phaùt sinh taát caû caùc ñænh sau moãi böôùc seõ deã daãn ñeán tình traïng buøng noå toå hôïp, laø tình traïng maø chuùng ta khoâng heà mong muoán. Ta khoâng chôø ñôïi moät thuaät toaùn giuùp giaûi caùc baøi toaùn nhö theá naøy maø chæ hy voïng coù theâm nhöõng tri thöùc giuùp traùnh tình traïng buøng noå toài teä noùi treân. Caùc tri thöùc nhö vaäy ñöôïc goïi laø caùc heuristic. Ví duï 1.3 Troø chôi tic-tac-toe (gioáng troø chôi caro quen thuoäc nhöng giôùi haïn treân baûng 3×3). Moãi ñoái thuû coù 3 quaân, nhieäm vuï cuûa hoï laø xeáp cho 3 quaân thaúng haøng ñoàng thôøi ngaên caûn ñoái phöông thöïc hieän nhieäm vuï. Troø chôi ñöôïc chia laøm 2 giai ñoaïn. Giai ñoaïn ñaët quaân gioáng vôùi troø chôi caro, giai ñoaïn di chuyeån quaân chæ ñöôïc pheùp dòch chuyeån quaân sang oâ troáng laân caän (duøng laân caän 4). Troø chôi ñöôïc baét ñaàu vôùi baûng roãng
• Ngöôøi thöù 1 seõ choïn nöôùc ñi naøo trong soá 3 nöôùc ñi sau ñeå ñaët quaân? X X X phaûi chaêng neân suy dieãn theo höôùng öu tieân soá ñöôøng môû khaû dó? Neáu vaäy thì phöông aùn cuoái seõ laø phöông aùn ñöôïc choïn. Thaät ra, ta bieát laø vôùi caùc troø chôi loaïi naøy, ngöôøi chôi caàn phaûi tính saâu hôn tröôùc khi coù quyeát ñònh. • Quaû vaäy, nhöõng suy dieãn ban ñaàu coù theå khoâng coøn chính xaùc nöõa khi ngöôøi ñi chòu khoù ñaùnh giaù theâm caùc theá bieán ôû caùc möùc saâu hôn. Ngoaøi ra, trong ví duï naøy ta coøn quan saùt thaáy söï keùm töôøng minh cuûa ñích. Ví duï 1.4 Chöùng minh bieåu thöùc R(⎤ P → Q) = (Q+P)R baèng caùch aùp duïng caùc luaät nhö giao hoaùn ab = ba, a+b=b+a; keát hôïp (ab)c = a(bc), (a+b)+c = a+(b+c) v v Laøm caùch naøo coù theå aùp duïng moät luaät? Muoán aùp duïng luaät, chaúng haïn, a+b = b+a leân (Q+P)R tröôùc tieân caàn nhaän dieän (ñoái saùnh) Q laø a vaø P laø b vaø thu ñöôïc keát quaû (P+Q)R. • Nhö vaäy baèng caùch ñoái saùnh moät boä phaän hoaëc toaøn theå caùc söï kieän ta tìm thaáy caùc luaät coù theå aùp duïng ñöôïc. AÙp duïng caùc luaät naøy seõ cho ta keát quaû môùi laø caùc söï kieän ñöôïc phaùt sinh. Quaù trình suy dieãn ôû ñaây coù theå ñi theo höôùng laøm giaûm daàn söï khaùc bieät giöõa keát quaû tìm ñöôïc vaø ñích. 2.2. Khaùi nieäm (a) Trí tueä nhaân taïo laø gì Caùc ví duï neâu treân ñöa ra cho chuùng ta moät soá khaùi nieäm môùi, taïo tình huoáng daãn chuùng ta ñi tìm hieåu moät nhaùnh thuù vò cuûa khoa hoïc maùy tính ñoù laø ngaønh trí tueä nhaân taïo. Nhöõng khaùi nieäm môùi ñöôïc giôùi thieäu ôû ñaây laø:
1 Tri thöùc; 2 Heuristic; 3 Luaät; 4 Söï kieän; 5 Ñoái saùnh; 6 Suy dieãn; 7 Chöông trình thoâng minh. Ñònh nghóa 1.1 AI laø moät nhaùnh cuûa khoa hoïc maùy tính nghieân cöùu vaø taïo ra caùc chöông trình thöïc hieän caùc coâng vieäc nhö ngöôøi. Chöông trình ñöôïc taïo ra nhaèm thöïc hieän caùc coâng vieäc nhö ngöôøi, töùc laø thöïc hieäïn moät caùch thoâng minh: kieåm soaùt tình huoáng vaø löïa choïn. Noù theå hieän haønh vi töông töï con ngöôøi khi phaûi ñöông ñaàu vôùi nhöõng vaán ñeà töông töï. Noù coù khaû naêng nhaän bieát caùc söï kieän, caùc meänh ñeà, caùc moái lieân heä vaø suy luaän. Tuy nhieân, khi nghieân cöùu caáu truùc beân trong, caùc nhaø nghieân cöùu trí tueä nhaân taïo vaãn muoán xaây döïng heä coù suy nghó gioáng ngöôøi. Ñi vaøo chi tieát caùc chöông trình nhö vaäy höôùng ñeán caùc tieâu chí sau: 1. Coù suy nghó gioáng con ngöôøi – lieân quan ñeán moâ hình hoaù nhaän thöùc 2. Coù suy nghó hôïp lyù – lieân quan ñeán logic hình thöùc 3. Coù haønh vi gioáng con ngöôøi – lieân quan ñeán thí nghieäm Turing 4. Coù haønh vi hôïp lyù – lieân quan ñeán luaät (b) Cô sôû cuûa trí tueä nhaân taïo Trí tueä nhaân taïo ñöôïc phaùt trieån döïa treân: 1. Trieát hoïc (töø naêm 428 tröôùc coâng nguyeân ñeán nay): vôùi haàu heát caùc yù töôûng quan troïng cuûa AI; 2. Toaùn hoïc (töø naêm 800): bao goàm tính toaùn, logic vaø xaùc suaát; 3. Taâm lyù hoïc (töø naêm 1879): bao goàm nhaän thöùc vaø haønh vi; 4. Coâng ngheä maùy tính (töø naêm 1940);
5. Ngoân ngöõ hoïc (töø naêm 1957). (c) Moät soá lónh vöïc trí tueä nhaân taïo 1. Heä chuyeân gia chöùa thoâng tin veà moät lónh vöïc nhaát ñònh vaø neáu ñöôïc phoûng vaán seõ traû lôøi nhö moät chuyeân gia; 2. Xöû lyù ngoân ngöõ töï nhieân; 3. Chöùng minh töï ñoäng; 4. Nhaän daïng; 5. Caùc ngoân ngöõ trí tueä nhaân taïo (nhö LISP, PROLOG, ) laø caùc ngoân ngöõ maø beân trong coù gaén lieàn moät cô sôû döõ lieäu cuøng caùc thuû tuïc truy ngöôïc caàn thieát cho nhieàu tình huoáng giaûi quyeát vaán ñeà. Trong giaùo trình naøy, chuùng ta khoâng ñi saâu vaøo moät lónh vöïc naøo caû maø chæ khaûo saùt caùc vaán ñeà cô baûn trong quaù trình laøm vieäc vôùi AI nhö 1. Caùc phöông phaùp giaûi quyeát vaán ñeà 2. Caùc kyõ thuaät bieåu dieãn tri thöùc. 3. Caùch suy dieãn vaø thu nhaän tri thöùc trong moãi loaïi bieåu dieãn 4. Tìm hieåu ngoân ngöõ Prolog 2.3. Heä cô sôû tri thöùc (a) Cô sôû tri thöùc Nhö chuùng ta ñaõ thaáy, moät heä muoán hoaït ñoäng hieäu quaû phaûi söû duïng ñöôïc tri thöùc. Tri thöùc phaûi ñöôïc toå chöùc toát ñeå coù theå söû duïng. Heä söû duïng tri thöùc ñeå ñöa ra caùc söï kieän môùi. Thaønh phaàn ñöa ra caùc söï kieän môùi ñöôïc goïi laø moâ tô suy dieãn. Ñònh nghóa 1.2 1. Tri thöùc laø hieåu bieát. 2. Cô sôû tri thöùc laø tri thöùc ñöôïc maõ hoaù thaønh söï kieän, luaät, heuristic, thuû tuïc Caùc vaán ñeà lieân quan ñeán maõ hoaù tri thöùc laø
1. Toå chöùc tri thöùc laø chìa khoaù ñeå truy xuaát ñöôïc hieäu quaû. Tuy nhieân vieäc bieåu dieãn tri thöùc phuï thuoäc baøi toaùn vaø phöông phaùp suy dieãn 2. Thu nhaän tri thöùc laø moät trong nhöõng khoù khaên lôùn nhaát. Maùy phaûi töï hoïc vaø töï caûi thieän. (b) Heä cô sôû tri thöùc Ñònh nghóa 1.3 Heä cô sôû tri thöùc laø moät heä phaàn meàm phöùc taïp giuùp thu nhaän tri thöùc vaø giaûi quyeát caùc baøi toaùn lieân quan ñeán caùc lónh vöïc AI Noù coù caùc thaønh phaàn nhö 1. Boä thu naïp 2. Boä giaûi thích 3. Boä giao dieän xöû lyù ngoân ngöõ töï nhieân 4. Cô sôû tri thöùc 5. Moâ tô suy dieãn 6. Cô sôû döõ lieäu 3. Moät soá baøi toaùn Caùc baøi toaùn sau duøng ñeå minh hoïa cho vieäc khaûo saùt caùc muïc tieâu ñaët ra. Baøi toaùn 1 Tìm ñöôøng ñi giöõa 2 thaønh phoá (ví duï 1) Baøi toaùn 2 Chöùng minh meänh ñeà (ví duï 2) Baøi toaùn 3 Tic-tac-toe (ví duï 3) Baøi toaùn 4 Chöùng minh bieåu thöùc (ví duï 4)
Baøi toaùn 5 Toâ maøu baûn ñoà vôùi soá maøu toái thieåu sao cho hai thaønh phoá keà nhau baát kyø ñöôïc toâ bôûi nhöõng maøu khaùc nhau. Baøi toaùn 6 Ñaët 8 quaân haäu leân baøn côø 8×8 sao cho 2 quaân haäu baát kyø khoâng aên laãn nhau Baøi toaùn 7 Baøi toaùn roùt nöôùc : laøm theá naøo laáy ñöôïc ñuùng 2 lít nöôùc baèng caùch duøng 2 can vôùi dung tích thöù töï laø 3 lít vaø 4 lít. Baøi toaùn 8 Ñieàn chöõ. Thay caùc kyù töï bôûi caùc chöõ soá khaùc nhau, ví duï SEND + MORE = MONEY. Baøi toaùn 9 Thaùp Haø Noäi. Chuyeån choàng ñóa (xeáp nhö caùi thaùp) töø coïc A sang coïc C coù söû duïng coïc trung gian B. Baøi toaùn 10 Coù 3 tu só vaø 3 keû aên thòt ngöoøi caàn sang soâng. Chæ caàn soá löôïng aùp ñaûo laø nhöõng keû aên thòt ngöôøi seõ laøm thòt caùc tu só. Laøm theá naøo ñöa hoï sang soâng neáu ñoø chôû toái ña ñöôïc 2? Baøi toaùn 11 Troø chôi Puzzle 8 soá: Di chuyeån caùc soá vaøo oâ troáng ñöa baøn côø veà moät traïng thaùi cho tröôùc, chaúng haïn Baøi toaùn 12 Tính tích phaân baát ñònh
Baøi toaùn 13 Con khæ vaø naûi chuoái. Coù 1 con khæ, 1 naûi chuoái, 1 caùi gheá vaø 1 chieác gaäy. Naûi chuoái treo treân traàn nhaø. Laøm theá naøo ñeå con khæ laáy ñöôïc naûi chuoái? Baøi toaùn 14 Heä thöùc löôïng trong tam giaùc. Chaúng haïn cho tam giaùc ABC, bieát goùc A caïnh b vaø ñöôøng cao ha haõy chæ ra quaù trình tính caïnh c. BAØI TAÄP Baøi taäp 1.1 Xaây döïng heä giaûi phöông trình baäc hai coù khaû naêng 1. Kieåm soaùt tình huoáng vaø löïa choïn; 2. Hoïc ñöôïc nhöõng tình huoáng môùi; 3. Giaûi ñöôïc phöông trình baäc 3 khi cho tröôùc moät nghieäm. Baøi taäp 1.2 Vôùi baøi toaùn ñöôïc cho trong ví duï 1, haõy cho bieát ñöôøng ñi tìm thaáy laø gì neáu suy dieãn: 1. Theo chieàu saâu; 2. Theo chieàu roäng. Baøi taäp 1.3 Giaûi baøi toaùn ñöôïc cho trong ví duï 2 1. Tieáp tuïc phaàn dôõ dang; 2. Theâm ít nhaát moät tri thöùc roài môùi giaûi. Baøi taäp 1.4 Xeùt troø chôi tic-tac-toe ñöôïc cho trong ví duï 3, tìm moät caùch ñi ñeå ngöôøi ñi tröôùc luoân thaéng. Baïn giaûi baèng tìm kieám hay coù söû duïng tri thöùc rieâng? Tri thöùc ñoù laø gì, neáu coù?
Baøi taäp 1.5 Giaûi baøi toaùn ñöôïc cho trong ví duï 4. Ñöa ra moät haøm so saùnh hai bieåu thöùc laø gaàn nhau. Baøi taäp 1.6 Tìm hieåu heä cô sôû tri thöùc prolog (xem phaàn phuï luïc). Caøi ñaët heä giaûi phöông trình baäc hai. Baøi taäp 1.7 Haõy lieät keâ moät soá tri thöùc trong hình hoïc phaúng. Phaùt bieåu moät baøi toaùn. Giaûi noù baèng caùc tri thöùc ñaõ neâu. Thöû caøi ñaët baèng prolog. PHAÀN 1 GIAÛI QUYEÁT VAÁN ÑEÀ Cuoäc soáng laø moät chuoãi caùc vaán ñeà maø chuùng ta caàn giaûi quyeát (Socrates). Coù moät thôøi kyø daøi trong quaù khöù, caùc nhaø khoa hoïc ñeàu cho raèng: “moïi vaán ñeà ñeàu coù
theå ñöôïc bieåu dieãn döôùi daïng moät baøi toaùn”. Descartes ñaõ töøng phaùt bieåu “taát caû moïi baøi toaùn ñeàu coù theå quy veà baøi toaùn ñaïi soá, töø ñoù vieäc giaûi baøi toaùn chæ laø vaán ñeà cuûa giaûi phöông trình”. David Hilbert cuõng ñaõ töøng ñaët ra caâu hoûi: “lieäu coù toàn taïi moät phöông phaùp cho pheùp giaûi quyeát moïi loaïi vaán ñeà khoâng?”. Döôùi goùc nhìn khoa hoïc, vaán ñeà thöôøng ñöôïc theå hieän döôùi daïng moät baøi toaùn. Trong phaàn naøy chuùng ta seõ tìm hieåu moät soá phöông phaùp giaûi quyeát vaán ñeà vaø aùp duïng vaøo giaûi caùc baøi toaùn ñaõ neâu ôû chöông môû ñaàu.
Chöông 2 Giaûi quyeát vaán ñeà baèng tìm kieám 1. Khaùi nieäm 1.1. Khoâng gian traïng thaùi Thöôøng thì chuùng ta nhaän bieát caùc ñoái töôïng thoâng qua moät taäp caùc thuoäc tính naøo ñoù maø chuùng ta seõ goïi laø bieåu dieãn hay moâ hình. Caùc giaù trò cuï theå cuûa nhöõõng thuoäc tính naøy cho pheùp chuùng ta xaùc ñònh ñöôïc traïng thaùi cuûa ñoái töôïng. Vì chuùng ta chæ laøm vieäc chuû yeáu treân caùc bieåu dieãn neân chuùng ta seõ coi traïng thaùi cuûa ñoái töôïng chính laø taäp caùc giaù trò naøy. Caùc giaù trò naøy seõ bò thay ñoåi döôùi taùc ñoäng cuûa moät taäp caùc thao taùc naøo ñoù. Ví du,ï tình traïng beänh cuûa beänh nhaân ñöôïc xaùc ñònh qua moät soá keát quaû xeùt nghieäm, vaø vieäc uoáng thuoác seõ laøm tình traïng beänh ñaït ñeán moät traïng thaùi toát hôn; cuõng vaäy khaû naêng laøm vieäc cuûa nhaân vieân ñöôïc xaùc ñònh qua moät soá tieâu chí naøo ñoù, vaø vieäc ñaøo taïo seõ laøm khaû naêng laøm vieäc ñaït ñeán moät traïng thaùi hieäu quaû hôn. Vôùi ñoái töôïng, vieäc xaùc ñònh traïng thaùi cuûa noù cuõng nhö vieäc xaùc ñònh taäp caùc thao taùc laøm thay ñoåi traïng thaùi cuûa noù laø nhöõng baøi toaùn cô baûn quan troïng. Trong trí tueä nhaân taïo chuùng ta seõ bieåu dieãn vaán ñeà baèng caùc caáu truùc rôøi raïc nhö ma traän, ñoà thò, . Qua ñoù maø vaán ñeà ñöôïc chuyeån thaønh nhöõng baøi toaùn cuï theå. Trong chöông naøy, chuùng ta tìm caùch ñöa vaán ñeà veà baøi toaùn tìm kieám trong khoâng gian traïng thaùi. Caáu truùc ñoà thò ñöôïc duøng vaø baøi toaùn laø tìm ñöôøng ñi ngaén nhaát. Chuùng ta seõ xaây döïng caùc caây tìm kieám vaø trong nhieàu tröôøng hôïp caây naøy laø loaïi caây AND/OR. Ñònh nghóa 2.1 Traïng thaùi laø moät bieåu dieãn cuûa vaán ñeà. Pheùp bieán ñoåi chuyeån vaán ñeà töø traïng thaùi naøy sang traïng thaùi khaùc. Taäp caùc traïng thaùi cuøng vôùi caùc pheùp bieán ñoåi treân chuùng taïo thaønh khoâng gian traïng thaùi.
Ví duï 2.1 Moät vaán ñeà thöïc teá naøo ñoù coù theå ñöa veà vieäc giaûi phöông trình sau 5x2 – 4x – 9 = 0 Thöïc hieän caùc pheùp bieán ñoåi töông ñöông 5x2 – 4x – 9 = 0 ⇔ 5x2 – 4x – (5 + 4) = 0 ⇔ 5x2 – 4x – 5 – 4 = 0 ⇔ (x+1) (5x – 9) = 0 Vôùi bieåu dieãn sau cuøng naøy xem nhö vaán ñeà ñaõ ñöôïc giaûi quyeát Khi khoâng gian traïng thaùi laø höõu haïn chuùng ta coù theå moâ hình noù bôûi caùc caáu truùc rôøi raïc nhö ma traän, ñoà thò, Ví duï 2.2 Trong troø chôi Puzzle 8 soá coù theå xem moät caùch saép xeáp 9 soá töø 0 ñeán 8 trong baûng 3×3 laø moät traïng thaùi. Moãi thao taùc dòch chuyeån ñuùng luaät (ñoåi choã soá 0 vaø moät soá keà vôùi noù) laø moät pheùp bieán ñoåi. 7 2 5 4 3 1 0 6 8 7 2 5 7 2 5 0 3 1 4 3 1 4 6 8 6 0 8 Ví duï 2.3 Vôùi baøi toaùn tính tích phaân baát ñònh, sau khi phaân raõ thaønh caùc baøi toaùn con ñuùng luaät (duøng caùc coâng thöùc), chuùng ta phaûi giaûi taát caû nhöõng baøi toaùn con thì môùi coù lôøi giaûi cho baøi toaùn ban ñaàu. (x 2 +1)e x dx ∫
x 2e x dx e x dx ∫ ∫ e x dx 2xe x dx ∫ ∫ 1.2. Tìm kieám treân khoâng gian traïng thaùi Khoâng gian traïng thaùi töï noù khoâng coù cô cheá tìm kieám. Taäp caùc thao taùc giuùp chuùng ta xaây döïng moät khoâng gian tìm kieám, nghóa laø trang bò moät caáu truùc cho khoâng gian traïng thaùi. Tuy nhieân, khoâng gian tìm kieám thöôøng laø raát lôùn, do ñoù chuùng ta seõ phaùt trieån moät caây tìm kieám cho ñeán khi tìm thaáy lôøi giaûi cho baøi toaùn. (a) Baøi toaùn tìm ñöôøng ñi Ví duï 2.4 Xeùt baøi toaùn tìm ñöôøng ñi ngaén nhaát töø a ñeán e treân ñoà thò sau a 4 c 2 3 2 4 b 1 d 3 5 e Coi ñænh laø traïng thaùi, caïnh laø pheùp bieán ñoåi, baèng caùch moâ taû caùc ñoà thò con: a b c d e 2 4 2 3 1 5 4 3 2 4 1 2 3 5 4 3 b c a c d e a b d e b c e b c d chuùng ta xaây döïng caây tìm kieám bieåu dieãn taát caû caùc ñöôøng ñi töø a ñeán e: a
b c c d e (7) b d e (8) d e (9) c e (6) d e (12) b e (9) e (10) e (9) e (11) e (12) tìm thaáy ñöôøng ñi ngaén nhaát laø a → b → d → e (laø ñöôøng neùt ñoâi) vôùi toång khoaûng caùch baèng 6. ÔÛ ñaây moãi nuùt laù xaùc ñònh moät ñöôøng ñi, caùc soá gaén vôùi nuùt laù cho bieát khoaûng caùch cuûa ñöôøng ñi töông öùng. Theo ñoù chuùng ta coù taát caû 9 ñöôøng ñi (taäp phöông aùn) vaø moät ñöôøng ñi ngaén nhaát (phöông aùn toái öu). (b) Baøi toaùn tìm caây lôøi giaûi Ví duï 2.5 Cho tam giaùc ABC, bieát ñöôøng cao ha vaø hai goùc A, C. Haõy tính caïnh c döïa vaøo caùc coâng thöùc A + B + C = π, ha = csinB, hb = csinA vaø hc = asinB. Giaûi: Chuùng ta seõ khoâng xaây döïng tröïc tieáp ñoà thò maø chæ moâ taû caùc ñoà thò con; qua ñoù seõ xaây döïng caây tìm kieám. c B ha B hb A A C hc a vaø chuùng ta coù caây tìm kieám AND/OR cuøng vôùi caây lôøi giaûi nhö sau: c ha B hb A A C hc a Ví duï 2.6 Kieåm tra ab → m, bieát
ab → c; ah → d; ad → m; bc → e; ab → o; o → m; e → m. Giaûi: Töø caùc ñoà thò con moâ taû luaät: c d e m o a b a h b c a d o e a b Ta xaây döïng caây tìm kieám m a d o e a h a b b c a b vaø tìm thaáy caây lôøi giaûi toái öu coù chieàu cao thaáp nhaát. Khaùc vôùi caây thoâng thöôøng, moãi nuùt laù cuûa caây AND/OR khoâng xaùc ñònh ñöôïc caây lôøi giaûi. 2. Caùc nguyeân lyù tìm kieám 2.1. Caùc nguyeân lyù cô baûn (a) Nguyeân lyù meâ cung Moät ñænh khoâng ñöôïc pheùp xuaát hieän 2 laàn treân moät ñöôøng ñi. Nguyeân lyù naøy nhaèm baûo ñaûm khoâng xuaát hieän chu trình trong quaù trình tìm kieám. (b) Nguyeân lyù veùt caïn (nguyeân lyù Edison) Khoâng ñöôïc loaïi boû baát kyø moät ñöôøng ñi naøo. Nguyeân lyù naøy nhaèm baûo ñaûm luoân tìm thaáy lôøi giaûi neáu noù toàn taïi. (c) Nguyeân lyù quay lui Nguyeân lyù naøy nhaèm baûo ñaûm cho nguyeân lyù veùt caïn vì trong quaù trình tìm kieám chuùng ta chæ coù theå xem xeùt töøng ñænh moät. Khi aáy quaù trình tìm kieám gioáng nhö quaù trình duyeät caây vaø nhaát thieát phaûi bieát quay lui.
Ví duï 2.7 Khi xaây döïng caây tìm kieám: ôû ví duï 4 chuùng ta ñaõ duøng nguyeân lyù meâ cung vaø nguyeân lyù veùt caïn; ôû ví duï 6 chuùng ta ñaõ duøng nguyeân lyù veùt caïn; coøn ôû ví duï 5 chuùng ta ñaõ duøng nguyeân lyù quay lui. Vieäc löïa choïn moät trình töï ñeå phaùt trieån caây laø heát söùc quan troïng, ngoaøi ra caàn phaûi loaïi boû nhöõng ñænh maø vieäc xeùt noù laø khoâng caàn thieát. Thuaät toaùn Dijkstra laø moät minh hoïa cho ñieàu naøy. Noù chæ giöõ laïi nhöõng ñænh caàn thieát vaø öu tieân xeùt caùc ñænh coù toång khoaûng caùch beù nhaát. Ví duï 2.8 1 a (0) 2 4 b (2) c (4) 3 c (5) d (3) e (7) b (7) d (6) e (8) 5 c (5) e (6) ÔÛ ñaây, ñöôøng ñöùt neùt laø nhaùnh bò tæa vaø chæ soá treân laø thöù töï môû roäng caây. 2.2. Caùc nguyeân lyù thöû sai Caùc hình minh hoïa sau ñaây ñeàu söû duïng baøi toaùn cho ôû ví duï 4. Caây tìm kieám ñöôïc phaùt trieån theo nguyeân lyù meâ cung vaø nguyeân lyù quay lui (vaø do ñoù nguyeân lyù veùt caïn, xaûy ra trong tröôøng hôïp xaáu nhaát khi baøi toaùn khoâng coù lôøi giaûi hoaëc khi phaûi veùt caïn caây tìm kieám môùi thaáy lôøi giaûi) (a) Nguyeân lyù löïa choïn theo chieàu saâu a1 b2 c c3 d e
d4 e 5 e (10) (b) Nguyeân lyù löïa choïn theo chieàu roäng a1 b2 c3 4 5 6 c d e (7) b d e d e c e (c) Nguyeân lyù löïa choïn saâu daàn Chieàu saâu toái ña laø 3, tröôùc khi duyeät theo chieàu roäng. a1 b2 c c3 d e 4 5 d e (9) e (d) Nguyeân lyù ngaãu nhieân Nhaèm traùnh phaûi xöû lyù moät soá löôïng quaù lôùn caùc traïng thaùi, ñænh seõ ñöôïc choïn moät caùch ngaãu nhieân. Caùch choïn ngaãu nhieân tuyø thuoäc vaøo moät soá ñieàu kieän cuï theå cuûa baøi toaùn.
Ví duï 2.9 a1 b3 c2 4 c d e (7) b d e 2.3. Caùc nguyeân lyù heuristic Thuaät giaûi laø khaùi nieäm môû roäng cuûa thuaät toaùn. Noù ñöôïc môû roäng döïa treân vieäc môû roäng hai ñaëc tröng cuûa thuaät toaùn laø tính xaùc ñònh vaø tính ñuùng. Trong soá caùc thuaät giaûi thì thuaät giaûi heuristic cho pheùp tìm lôøi giaûi deã daøng vaø nhanh choùng, thöôøng thì noù tìm ra ñöôïc lôøi giaûi toát (nhöng khoâng chaéc laø toát nhaát, tuy nhieân caùch theå hieän cuûa noù laïi raát töï nhieân vaø gaàn guõi vôùi caùch suy nghó vaø haønh ñoäng cuûa con ngöôøi). Ñònh nghóa 2.2 Heuristic laø nhöõng thoâng tin giuùp vieäc ñònh höôùng taäp trung xung quanh ñöôøng ñi toái öu. Haøm heuristic laø nhöõng haøm ñaùnh giaù giuùp vieäc löïa choïn höôùng ñeán ñöôøng ñi toái öu. (a) Nguyeân lyù toái öu cuïc boä (nguyeân lyù greedy) Laáy tieâu chuaån toái öu toaøn cuïc laøm tieâu chuaån choïn löïa trong phaïm vi cuïc boä. a1 2 b (2) c (4) 3 c (5) d (3) e (7) 4 c (5) e (6)
5 e (9) (b) Nguyeân lyù höôùng ñích So saùnh traïng thaùi hieän taïi ñang xem xeùt vôùi traïng thaùi caàn ñaït ñeán laøm tieâu chuaån löïa choïn. Ví duï 2.10 Xeùt troø chôi 8 soá chuyeån ñænh veà ñænh Giaûi: Xaây döïng caây tìm kieám duøng nguyeân lyù greedy vôùi giaù trò taïi moãi ñænh laø söï khaùc bieät (soá chöõ soá sai vò trí) so vôùi ñænh cuoái (nguyeân lyù höôùng ñích) 2 8 3 1 6 4 7 0 5 2 8 3 2 8 3 2 8 3 1 0 4 1 6 4 1 6 4 7 6 5 (3) 7 5 0 (5) 0 7 5 (5) 2 0 3 2 8 3 2 8 3 1 8 4 0 1 4 1 4 0 7 6 5 (3) 7 6 5 (3) 7 6 5 (4) 2 3 0 0 2 3 1 8 4 1 8 4 7 6 5 (4) 7 6 5 (2) 1 2 3 0 8 4 7 6 5 (1)
1 2 3 1 2 3 8 0 4 7 8 4 7 6 5 (0) 0 6 5 (2) (c) Nguyeân lyù nhaùnh caän Phaân hoaïch khoâng gian traïng thaùi. Vôùi moãi lôùp töông ñöông, duøng moät öôùc löôïng so saùnh vôùi moät ngöôõng cho tröôùc ñeå quyeát ñònh coù loaïi boû hay khoâng. Nhôø ñoù chuùng ta coù theå tæa nhaùnh hieäu quaû, chæ giöõ nhöõng traïng thaùi cho pheùp daãn ñeán lôøi giaûi toát nhaát. Ví duï 2.11 Khi xaây döïng caây tìm kieám, coù theå xem taïi moãi böôùc phaùt trieån laø moät böôùc phaân hoaïch mòn hôn. Vaãn duøng ví duï 4, ñeå yù chieàu daøi ngaén nhaát cuûa moät caïnh noái vôùi e laø 3, boå sung nhaän xeùt naøy vaøo toång khoaûng caùch ta coù moät ñaùnh giaù vaø nhôø ñoù phaùt trieån caây tìm kieám nhö sau: 1 a (≥ 3) 2 b (≥ 5) c (≥ 7) 3 c (≥ 8) d (≥ 6) e (7) 4 c (≥ 8) e (6) Keát quaû tìm ñöôïc ñöôøng ñi ngaén nhaát nhanh hôn nhieàu so vôùi thuaät toaùn Dijsktra. Nhöõng nhaùt caét naøy seõ raát hieäu quaû khi laøm vieäc treân moät khoâng gian tìm kieám roäng lôùn. (d) Nguyeân lyù saép thöù töï Saép xeáp khoâng gian traïng thaùi theo moät caáu truùc hôïp lyù Ví duï 2.12 Moät saép xeáp hôïp lyù coù theå tìm ñöôïc ñöôøng ñi ngaén nhaát chæ vôùi thuû tuïc tìm kieám theo chieàu saâu ñôn giaûn
a b c d c e e (6) c 2.4. Caøi ñaët caùc nguyeân lyù Quan saùt quaù trình phaùt trieån caây tìm kieám ta thaáy vaán ñeà naèm ôû choã 1. Thöù töï thaùo caùc ñænh töùc laø quaûn lyù ñöôïc caùc nuùt laù. 2. Tröôøng hôïp neáu yeâu caàu moãi ñænh xuaát hieän treân caây khoâng quaù 1 laàn ta caàn quaûn lyù caùc ñænh khoâng laø laù. 3. Phaûi coù cô cheá kieåm tra söï xuaát hieän chu trình. Chuùng ta seõ giao nhieäm vuï quaûn lyù caùc nuùt laù cho moät ñoái töôïng ñöôïc goïi laø open; quaûn lyù caùc nuùt khoâng phaûi nuùt laù cho moät ñoái töôïng ñöôïc goïi laø close. Ñoàng thôøi moãi ñænh treân caây phaûi tham chieáu ñöôïc ñeán ñænh cha cuûa noù. Ñoái töôïng open coù vai troø chuû yeáu trong vieäc choïn ñænh tieáp theo ñoàng thôøi phoái hôïp vôùi close vaø ñænh hieän taïi ñeå quyeát ñònh coù löu traïng thaùi môùi hay khoâng. Thoâng qua open vaø close ta caøi ñaët caùc nguyeân lyù tìm kieám nhö sau: Caùc nguyeân lyù cô baûn 1. Nguyeân lyù quay lui vaø nguyeân lyù veùt caïn: open phaûi löu taát caû caùc khaû naêng khi thaùo moät nuùt; 2. Nguyeân lyù meâ cung: open phaûi laàn theo caùc tham chieáu ñeå baûo ñaûm caùc ñænh môùi khoâng laøm xuaát hieän chu trình; Caùc nguyeân lyù thöû sai 3. Nguyeân lyù löïa choïn theo chieàu saâu: open haønh xöû nhö moät ngaên xeáp; 4. Nguyeân lyù löïa choïn theo chieàu roäng: open haønh xöû nhö moät haøng ñôïi; 5. Nguyeân lyù löïa choïn saâu daàn: open haønh xöû nhö ngaên xeáp hoaëc haøng ñôïi
phuï thuoäc vaøo chieàu saâu ñaõ ñaït möùc giôùi haïn hay chöa; 6. Nguyeân lyù ngaãu nhieân: open ñöôïc trang bò moät cô cheá choïn ngaãu nhieân; Caùc nguyeân lyù heuristic 7. Nguyeân lyù greedy: open haønh xöû nhö moät ngaên xeáp vaø caùc nuùt phaùt sinh khi thaùo moät ñænh phaûi ñöôïc saép xeáp (töùc laø phaûi ñöôïc xöû lyù qua moät haøng ñôïi öu tieân); 8. Nguyeân lyù höôùng ñích: heä ñöôïc trang bò moät thuû tuïc so saùnh cho pheùp ñaùnh giaù söï gaàn nhau giöõa caùc traïng thaùi; 9. Nguyeân lyù nhaùnh caän: heä ñöôïc trang bò moät thuû tuïc ñaùnh giaù; close ñöôïc trang bò thuû tuïc vaø open haønh xöû nhö moät haøng ñôïi öu tieân; 10. Nguyeân lyù thöù töï: open ñöôïc trang bò moät thuû tuïc saép xeáp phuø hôïp. 3. Aùp duïng 3.1. Caøi ñaët thuaät giaûi Muïc naøy chæ ñöa ra hai thuaät giaûi: tröôøng hôïp toång quaùt vaø moät tröôøng hôïp rieâng quan troïng (tìm kieám leo ñoài). Caùc thuaät giaûi quan troïng khaùc seõ ñöôïc trình baøy ôû caùc chöông sau. (a) Toång quaùt Cô baûn ta seõ söû duïng 2 danh saùch • Danh saùch môû Open, chöùa caùc traïng thaùi seõ ñöôïc xem xeùt vaø • Danh saùch ñoùng Close, chöùa caùc traïng thaùi ñaõõ ñöôïc xem xeùt. Theâm moät soá ñoái töôïng khaùc • Traïng thaùi baét ñaàu s • Traïng thaùi keát thuùc g • Traïng thaùi ñang xeùt n • Danh saùch B(n) chöùa caùc traïng thaùi ñöôïc bieán ñoåi töø traïng thaùi n Caùc böôùc cô baûn cuûa caùc thuaät toaùn tìm kieám ñöôïc trình baøy nhö sau:
Thuaät giaûi tìm kieám treân khoâng gian traïng thaùi 1. Open.Store(s) 2. While not Open.Empty() do 2.1. n = Open.Retrieve() 2.2. Close.Store(n) 2.3. if n = g then return true 2.4. for m ∈ B(n) do Open.Store(m) 3. return false Chuùng ta seõ ñaùnh giaù tính hieäu quaû cuûa moãi thuaät toaùn qua hai thöôùc ño • Toác ñoä tìm thaáy lôøi giaûi vaø • Ñoä toát cuûa lôøi giaûi (b) Tìm kieám leo ñoài Caøi ñaët cuï theå nguyeân lyù greedy vaø nguyeân lyù meâ cung. Chuùng ta coi open laø moät ngaên xeáp; boå sung moät haøng ñôïi öu tieân q; cung caáp cho ñoái töôïng ñænh cuûa caây moät thao taùc truy ngöôïc exists() nhaèm kieåm tra xem moät traïng thaùi laø ñaõ coù maët trong moät ñænh tieàn boái naøo ñoù hay khoâng. Thuaät giaûi 1: Tìm kieám leo ñoài 1. Open.Store(s) 2. While not Open.Empty() do 2.1. n = Open.Retrieve() 2.2. Close.Store(n) 2.3. if n = g then return true 2.4. for m ∈ B(n) do if not n.exists(m) then q.Store(m); 2.5. for m = q.Retrieve() do Open.Store(m) 3. return false
Ví duï 2.13 Baøi toaùn toâ maøu baûn ñoà öu tieân toâ ñænh coù baäc cao tröôùc. b c a d e Giaûi: Baét ñaàu töø ñænh d vôùi maøu caïnh soá thöù töï môû roäng caây: d1 (1) 2 (2) a (2) b (2) c (1) e (1) 3 (2) b (1) c (1) e (0) 4 (3) b(0) e (0) 5 (3) e (0) chuù yù sau khi toâ moät ñænh ta thaùo noù ra khoûi ñoà thò vaø tính laïi baäc, ngoaøi ra khi choïn maøu ñeå toâ khoâng ñöôïc ñeå hai ñænh keà nhau coù cuøng maøu. 3.2. Giaûi quyeát vaán ñeà Tröôùc heát bieåu dieãn vaán ñeà nhö laø baøi toaùn tìm kieám trong khoâng gian traïng thaùi, roài xaùc ñònh xem ñaây laø baøi toaùn tìm ñöôøng ñi hay tìm caây lôøi giaûi. Sau ñoù aùp duïng caùc nguyeân lyù tìm kieám, phaùt trieån caây vaø thöïc hieän tìm kieám. Ví duï 2.14 Coù 3 tu só ñeán thuyeát giaùo taïi moät boä toäc aên thòt ngöôøi. Hoï gaëp 3 thoå daân thuoäc boä toäc naøy taïi bôø moät con soâng. Taò ñoù chæ coù moät chieác thuyeàn nhoû chôû toái ña ñöôïc 2 ngöôøi. Taát caû ñeàu muoán sang soâng. Haõy tìm moät giaûi
phaùp ñöa caû 3 tu só vaø 3 keû aên thòt ngöôøi cuøng qua soâng ñöôïc an toaøn, bieát raèng neáu soá löôïng nhöõng keû aên thòt ngöôøi nhieàu hôn soá tu só, chuùng seõ aên thòt hoï. Giaûi: Böôùc 1: bieåu dieãn 1 Kyù hieäu (a, b, t) nghóa laø ôû bôø beân naøy coù a tu só, b thoå daân vaø t cho bieát coù thuyeàn hay khoâng. 2 Thao taùc hôïp leä chuyeån (a, b, k) → (a’, b’, 1 – k) laø thao taùc thoûa: a’ + b’ nhieàu hôn a + b töø 1 ñeán 2 neáu k = 0 a’ + b’ ít hôn a + b töø 1 ñeán 2 neáu k = 1 b’ = a’ neáu a’ baèng 1 hoaëc 2 Minh hoïa moät tröôøng hôïp: (2, 2, 0) (3, 2, 1) (3, 3, 1) Vaø baøi toaùn laø tìm ñöôøng ñi töø (3, 3, 1) ñeán (0, 0, 0) Böôùc 2: Phaùt trieån caây tìm kieám theo chieàu saâu coù söû duïng caùc nguyeân lyù cô baûn vaø nguyeân lyù nhaùnh caän (3, 3, 1)1 (3, 2, 0) 2 (3, 1, 0) 3 (2, 2, 0) (3, 2, 1) 4 (3, 0, 0) 5 (3, 1, 1) 6
BAØI TAÄP Baøi taäp 2.1 Xaùc ñònh traïng thaùi vaø caùc pheùp bieán ñoåi cuûa caùc baøi toaùn ñaõ ñöôïc giôùi thieäu trong chöông moät, vaø thöû phaùt trieån caây tìm kieám. Baøi taäp 2.2 Toâ maøu baûn ñoà G vôùi ma traän keà ñöôïc cho nhö sau A B C D E F G H A 0 1 0 1 0 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 1 1 0 D 1 1 0 0 1 0 0 1 E 0 1 1 1 0 1 0 1 F 0 0 1 0 1 0 1 1 G 0 0 1 0 0 1 0 1 H 0 0 0 1 1 1 1 0 Baøi taäp 2.3 Tìm ñöôøng ñi töø N ñeán L vôùi baûng döõ lieäu ñöôïc cho nhö sau (ví duï 1.1) N→C 10 N→D 19 T→C 5 H→L 15 C→D 10 T→G 15 D→U 10 D→L 10 N→T 8 T→L 18 D→H 15 1. Tìm theo chieàu saâu 2. Tìm theo chieàu roäng 3. Tìm saâu daàn vôùi chieàu saâu toái ña laø 3. 4. Tìm ñöôøng ñi ngaén nhaát baèng veùt caïn 5. Tìm ñöôøng ñi ngaén nhaát baèng Dijkstra 6. Tìm ñöôøng ñi ngaén nhaát duøng nguyeân lyù nhaùnh caän vôùi nhaän xeùt khoaûng caùch nhoû nhaát cuûa caùc cung noái vôùi L laø 10 ñôn vò khoaûng caùch. 7. Tìm ñöôøng ñi ngaén nhaát baèng caùch loaïi boû nhöõng nhaùnh khoâng chöùa lôøi giaûi toái öu (nguyeân lyù veùt caïn thoâng minh). 8. Tìm ñöôøng ñi ngaén nhaát duøng nguyeân lyù höôùng ñích vaø nguyeân lyù tham
lam vôùi haøm heuristic h(n) ñaùnh giaù khoaûng caùch töø n ñeán L nhö sau: n C D G H L N T U h 15 8 12 12 0 26 22 15 Baøi taäp 2.4 Giaû söû chuùng ta ñang thieát keá moät trình bieân dòch cho moät maùy coù moät thanh ghi vaø caùc chæ thò sau: ONE ñaët giaù trò cuûa thanh ghi laø 1 DOUBLE nhaân ñoâi noäi dung thanh ghi ADD coäng 1 vaøo noäi dung thanh ghi SUB tröø 1 khoûi noäi dung thanh ghi DIV chia giaù trò cuûa thanh ghi cho 3 Boán chæ thò ñaàu aùp duïng khi giaù trò cuûa thanh ghi khoâng chia heát cho 3, chæ thò DIV aùp duïng khi giaù trò cuûa thanh ghi chia heát cho 3. Giaû söû noäi dung cuûa thanh ghi laø 4, laøm theá naøo ñaët 9 vaøo noäi dung thanh ghi? Duøng baát kyø moät giaûi thuaät naøo ñaõ hoïc thöïc hieän coâng vieäc treân (höôùng daãn : duøng thuaät giaûi tìm kieám) Baøi taäp 2.5 Duøng hai ñoàng hoà caùt, trong ñoù moät chieác ño 4 giaây vaø chieác coøn laïi ño 7 giaây. Chæ ra caùch ño khoaûng thôøi gian 9 giaây. Yeâu caàu phaùt bieåu luaät, baøi toaùn vaø trình baøy caùch giaûi quyeát. Baøi taäp 2.6 Cho meâ cung (hình). Baøi toaùn laø tìm ñöôøng ñi töø A ñeán Z
1. Moâ taû traïng thaùi (söï kieän), pheùp bieán ñoåi (luaät); 2. Xaây döïng caây tìm kieám giaûi baøi toaùn treân.
Chöông 3 Tìm kieám vôùi heuristic Trong chöông tröôùc ta ñaõ duøng open ñeå caøi ñaët caùc nguyeân lyù tìm kieám. Vai troø chuû yeáu vaø quan troïng cuûa open laø choïn ñænh tieáp theo trong quaù trình tìm kieám. Vôùi baøi toaùn tìm ñöôøng ñi, moãi ñænh maø open löu giöõ chính laø moät lôøi giaûi ñi qua ñænh naøy; do ñoù open ñuû söùc hoaøn thaønh nhieäm vuï khi maø noù quaûn lyù ñöôïc toaøn boä caùc lôøi giaûi. Tuy nhieân vôùi baøi toaùn tìm caây lôøi giaûi, moãi ñænh maø open löu giöõ khoâng theå xaùc ñònh ñöôïc lôøi giaûi ñi qua ñænh naøy; cho neân open phaûi phoái hôïp vôùi ñænh goác cuûa caây tìm kieám môùi coù theå xaùc ñònh ñöôïc toaøn boä caùc caây lôøi giaûi. Chöông naøy giôùi thieäu lôùp thuaät giaûi hieäu quaû aùp duïng caùc nguyeân lyù heuristic baèng caùch xaây döïng moät haøm heuristic ñaùnh giaù traïng thaùi ñang xeùt vôùi traïng thaùi caàn ñaït ñeán (nguyeân lyù höôùng ñích). Chuùng ñöôïc caøi ñaët treân hai caáu truùc caây, caây cuûa lyù thuyeát ñoà thò vaø caây AND/OR, tuyø theo töøng loaïi baøi toaùn, tìm ñöôøng ñi ngaén nhaát hay tìm caây lôøi giaûi toái öu. 1. Khaùi nieäm Moät lôøi giaûi toái öu laøm cöïc tieåu (cöïc ñaïi) moät haøm muïc tieâu naøo ñoù. Giaû söû toàn taïi lôøi giaûi toái öu. Goïi f laø giaù trò cöïc tieåu ñaït ñöôïc taïi lôøi giaûi toái öu naøy vaø f(n) laø giaù trò cuûa lôøi giaûi toát nhaát coù chöùa ñænh n. Nhöõng thoâng tin ta coù ñöôïc trong quaù trình tìm kieám ñeán ñænh n chöa cho pheùp chuùng ta xaùc ñònh ñöôïc f(n); chuùng ta caàn coù theâm nhöõng thoâng tin veà moái lieân quan giöõa n vaø ñích ñeán. Nhöõng thoâng tin naøy coù ñöôïc töø caùc öôùc löôïng hôïp lyù, töø nhöõng tri thöùc tröôùc ñoù cuõng nhö nhöõng kinh nghieäm saün coù cuûa caùc chuyeân gia. Ñeå laøm roõ tieáp caän naøy ta xeùt baøi toaùn tìm ñöôøng ñi ngaén töø a ñeán z treân ñoà thò G. Ñònh nghóa 3.1 Xeùt ñænh n treân G sao cho coù ñöôøng ñi töø a ñeán z thoâng qua n, ñònh nghóa: 1. g(n) laø ñoä daøi ñöôøng ñi ngaén nhaát töø a ñeán n
2. h(n) laø ñoä daøi ñöôøng ñi ngaén nhaát töø n ñeán z Khi aáy f(n) = g(n) + h(n) laø ñoä ñöôøng ñi ngaén nhaát töø a ñeán z coù ñi qua n. Hôn nöõa f = f(a) = h(a) = g(z). Thuaät toaùn Dijkstra tìm caùch tính g(n) cho ñeán khi tính ñöôïc g(z) vaø keát luaän tìm ñöôïc ñöôøng ñi toái öu. Moät öôùc löôïng hÂ ≤ h giuùp söû duïng nguyeân lyù nhaùnh caän trong tìm kieám vôùi toác ñoä raát nhanh. Ví duï 3.1 Giaûi laïi ví duï 4 a b c d e 2 4 2 3 1 5 4 3 2 4 1 2 3 5 4 3 b c a c d e a b d e b c e b c d giaû söû ñaõ tính ñöôïc hÂ nhö sau n a b c d e hÂ 6 4 4 3 0 1. Trong chöông 1 ta duøng hÂ1(n) = 3 ≤ h(n), vaø tìm ñöôïc ñöôøng ñi ngaén nhaát 1 a (f ≥ 3) 2 b (f ≥ 5) c (f ≥ 7) 3 c (f ≥ 8) d (f ≥ 6) e (f ≥ 7) 4 c (≥ 8) e (f ≥ 6) 2. Vôùi hÂ2(n) sau, vaãn coù hÂ2(n) ≤ h(n), neân vaãn tìm ñöôïc ñöôøng ñi ngaén nhaát n a b c d e hÂ2 5 3 3 3 0
1 a (f ≥ 5) 2 b (f ≥ 5) c (f ≥ 7) 3 c (f ≥ 8) d (f ≥ 6) e (f ≥ 7) 4 c (≥ 8) e (f ≥ 6) 3. Vôùi hÂ3 = 4, ta khoâng coù hÂ3(n) ≤ h(n), neân khoâng theå aùp duïng nguyeân lyù nhaùnh caän (tröø phi muoán xaây döïng moät thuaät giaûi thay vì thuaät toaùn). 2. Thuaät giaûi A* Tieáp caän naøy aùp duïng cho baøi toaùn tìm ñöôøng ñi ngaén nhaát treân ñoà thò. Moät caùch chính xaùc ñaây laø moät lôùp caùc thuaät giaûi phuï thuoäc vaøo öôùc löôïng hÂ cuûa haøm heuristic h. Ñoä toát cuûa lôøi giaûi tuøy thuoäc vaøo ñoä chính xaùc cuûa öôùc löôïng. Thuaät giaûi A* duøng haøm f Â = g + hÂ laøm öôùc löôïng cho haøm toång khoaûng caùch f. Noù duøng f Âlaøm tieâu chuaån löïa choïn. Cuï theå, chieán löôïc cuûa noù laø öu tieân choïn ñænh coù f Â beù. Thuaät giaûi ñöôïc trình baøy sau ñaây coù caøi ñaët cô cheá tæa nhaùnh. Thuaät giaûi 2: Thuaät giaûi A* 1 Ñaët nuùt baét ñaàu vaøo Open 2 Trong luùc Open khaùc roãng thöïc hieän 2.1 Choïn nuùt n trong Open coù f Â beù nhaát, laáy noù ra 2.2 Neáu n laø ñích thì keát thuùc thaønh coâng 2.3 Ñaët n vaøo Close 2.4 Vôùi moãi n’ con cuûa n 2.4.1 Tính f Â cho n’ 2.4.2 Neáu n’ chöa coù trong Open cuõng nhö Close thì ñaët noù vaøo
Open 2.4.3 Ngöôïc laïi, n’ coù trong Open hoaëc Close, ta so saùnh f Â môùi vaø f Â cuõ; neáu f Â môùi beù hôn f Â cuõ thì 2.4.3.1 Neáu n’ cuõ coù trong Open thì ñieàu chænh f Â vaø tham chieáu 2.4.3.2 Neáu n’ cuõ coù trong Close thì tæa caùc nhaùnh qua n’ cuõ naøy tröôùc khi ñaët noù vaøo Open 3 Keát thuùc khoâng thaønh coâng. Ví duï 3.2 Tìm ñöôøng ñi töø N ñeán L vôùi baûng döõ lieäu (vaãn ví duï 1.1 quen thuoäc) N→C 10 N→D 19 T→C 5 H→L 15 C→D 10 T→G 15 D→U 10 D→L 10 N→T 8 T→L 18 D→H 15 vaø moät haøm öôùc löôïng hÂ nhö sau n C D G H L N T U hÂ 15 8 12 12 0 26 22 15 Giaûi: 1 N (0+26) 2 3 C (10+15) T(8+22) D (19+8) 3 4 D (20+8) U (29+15) H (34+12) L (29+0) Hình treân minh hoaï quaù trình tìm lôøi giaûi toái öu baèng thuaät giaûi A*. Taïi moãi ñænh caëp giaù trò (g, hÂ) thay cho fÂ vaø moät chæ soá cho bieát thöù töï thaùo ñænh. Coù theå thaáy ñaây khoâng phaûi laø lôøi giaûi toái öu. Coù 2 caâu hoûi ñöôïc ñaët ra laø
1. Ñieàu gì baûo ñaûm thuaät giaûi tìm thaáy lôøi giaûi? 2. Thuaät giaûi naøo laø toát hôn, toát nhaát? Ñònh nghóa 3.2 1. Thuaät giaûi A laø ñaày ñuû neáu noù luoân tìm thaáy ñöôïc lôøi giaûi (neáu coù lôøi giaûi) 2. Thuaät giaûi A laø chaáp nhaän ñöôïc neáu noù ñaûm baûo tìm thaáy ñöôïc lôøi giaûi toái öu (neáu coù lôøi giaûi toái öu) 3. A1 troäi hôn A2 neáu hÂ1 > hÂ2 4. A laø toái öu trong lôùp G caùc thuaät giaûi neáu noù troäi nhaát Ñònh lyù 3.1 1. Neáu h ≥ hÂ thì thuaät giaûi laø chaáp nhaän ñöôïc 2. Neáu h ≥ hÂ1 > hÂ2 (A1, A2 chaáp nhaän ñöôïc vaø A1 troäi hôn A2) thì soá nuùt phaûi thaùo cuûa A1 laø ít hôn A2 Ví duï 3.3 1. Thuaät giaûi A* giaûi baøi toaùn ôû ví duï treân laø ñaày ñuû nhöng khoâng chaáp nhaän ñöôïc. Baây giôø ñieàu chænh hÂ(T) = 18 ta ñöôïc lôøi giaûi toái öu vì thuaät giaûi luùc naøy laø chaáp nhaän ñöôïc. 1 N (0+26) 2 3 C (10+15) T (8+18) D (19+8) 3 4 D (20+8) G (34+12) L (26+0) 2. Tieáp tuïc ñieàu chænh hÂ(C) = 18 ta ñöôïc thuaät giaûi chaáp nhaän ñöôïc troäi hôn neân cuõng hieäu quaû hôn. 1 N (0+26) 2 C (10+18) T (8+18) D (19+8)
3 G (34+12) L (26+0) Ví duï 3.4 Giaûi baøi toaùn thaùp Haø Noäi 2 ñóa vôùi soá laàn dòch chuyeån ít nhaát. Xeùt moãi coïc coù 4 traïng thaùi 0: khoâng ñiaõ, 1: ñóa nhoû, 2: ñóa lôùn vaø 3: coù 2 ñóa. Khi aáy traïng thaùi cuûa thaùp laø moät boä 3 caùc soá nguyeân töø 0 ñeán 3. Haøm heuristic maø ta choïn chæ quan taâm ñeán coïc thöù 3 (höôùng ñích) ñöôïc cho cuï theå nhö sau: • hÂ(3) = 0 : traïng thaùi ñích • hÂ(2) = 1 : chæ caàn 1 laàn chuyeån ñóa laø ñeán ñích • hÂ(1) = 3 : ñóa nhoû ôû ñaây gaây phieàn toaùi neân xa ñích nhaát • hÂ(0) = 2 : taát caû caùc traïng thaùi coøn laïi Kyù hieäu (a, b, c) laø soá ñóa ôû 3 coïc, ta coù keát quaû minh hoïa (khoâng veõ caùc nhaùnh bò tæa): 1 (3,0,0) (0+2) 2 (2,1,0) (1+2) (2,0,1) (1+2) 3 (0,1,2) (2+1) 4 (0,0,3) (3+0) 3. Thuaät giaûi A0* Vaán ñeà thöôøng ñöôïc theå hieän döôùi daïng moät baøi toaùn. Do vaäy ta coù theå xem baøi toaùn cuõng laø moät bieåu dieãn cuûa vaán ñeà. Theo ñoù ta cuõng coù caùc pheùp bieán ñoåi töø baøi toaùn naøy sang baøi toaùn khaùc. Muïc tieâu cuûa chuùng ta quan taâm ñeán tính giaûi ñöôïc neân cuõng chuù troïng ñeán caùc bieán ñoåi töông ñöông. Vieäc bieán ñoåi moät baøi toaùn coù theå töông ñöông vôùi nhieàu baøi toaùn con khaùc. Neáu môû roäng khaùi nieäm traïng thaùi thaønh caùc traïng thaùi phöùc, chöùa nhieàu traïng thaùi con, chuùng ta coù theå duøng phöông phaùp tìm kieám ôû muïc tröôùc.
Trong muïc naøy, chuùng ta seõ chia baøi toaùn ban ñaàu daàn daàn cho ñeán khi noù laø toå hôïp cuûa caùc baøi toaùn sô caáp giaûi ñöôïc. Ñeå tröïc quan chuùng ta duøng moät daïng ñoà thò ñaëc bieät goïi laø ñoà thò AND/OR (And/Or Graphs) ñeå bieåu dieãn vaø tìm lôøi giaûi. Ñònh nghóa 3.3 • Nuùt AND laø giaûi ñöôïc neáu vaø chæ neáu taát caû caùc nuùt con giaûi ñöôïc • Nuùt OR laø giaûi ñöôïc neáu vaø chæ neáu coù moät nuùt con giaûi ñöôïc Ví duï 3.5 1. Giaûi baøi toaùn thaùp Haø Noäi, chuyeån n ñóa töø coät A qua coät C thoâng qua coät B, baèng caùch phaân raõ noù thaønh 3 baøi toaùn con • Chuyeån n-1 ñóa töø coät A sang coät B thoâng qua coät C • Chuyeån 1 ñóa töø coät A sang coät C • Chuyeån 2 ñóa töø coät B sang coät C thoâng qua coät A Chuyeån(n,A,C,B) Chuyeån(n-1,A,B,C) Chuyeån(1,A,C) Chuyeån(n-1,B,C,A) (n-2,A,C,B) (1,A,B) (n-2,C,B,A) 2. Giaûi baøi toaùn tìm nguyeân haøm cuûa ex(sinx + x), baèng caùch phaân raõ nhö sau: (x 2 +1)e x dx ∫
x 2e x dx e x dx ∫ ∫ e x dx 2xe x dx ∫ ∫ 3. Tìm phöông aùn nguyeân cuûa baøi toaùn quy hoaïch tuyeán tính baèng nhaùt caét taïi phöông aùn toái öu (chöa nguyeân) thaønh 2 baøi toaùn con. 3.1. Tìm kieám treân caây AND/OR Nhöõng neùt chính Trong tìm kieám vai troø cuûa open laø quan troïng. Moät khi noù laáy ñöôïc traïng thaùi ñích ñeå xem xeùt thì quaù trình tìm kieám keát thuùc thaønh coâng, ñôn giaûn bôûi lôøi giaûi chæ laø moät ñöôøng ñi maø thoâi. Vôùi caây And/Or laïi khaùc, keát quaû tìm kieám cho ta caây lôøi giaûi thay vì ñöôøng ñi. Vì lôøi giaûi laø moät caây neân vieäc tìm thaáy moät baøi toaùn sô caáp giaûi ñöôïc (nuùt laù cuûa caây lôøi giaûi) khoâng theå keát luaän gì veà baøi toaùn goác. Ñeå xaây döïng thuaät giaûi ta ñeå open ñaûm nhaän luoân vai troø cuûa close ñoàng thôøi boå sung theâm ñoái töôïng caây lôøi giaûi höùa heïn T0 vaø moät soá thuû tuïc • Haøm xaây döïng caây lôøi giaûi höùa heïn Build()
• Phöông thöùc giaûi ñöôïc gd() • Phöông thöùc gaùn nhaõn giaûi ñöôïc gngd() • Phöông thöùc khoâng giaûi ñöôïc kgd() • Phöông thöùc gaùn nhaõn khoâng giaûi ñöôïc gnkgd() • Phöông thöùc xaây döïng laïi danh saùch Open ReBuild() Coi s laø baøi toaùn goác, caùc böôùc cô baûn coù daïng nhö sau: Thuaät giaûi tìm kieám treân caây AND/OR 1. Open.Store(s) 2. While not Open.Empty() do 2.1. T0 = Build() 2.2. n = Open ∩ leaf(T0) 2.3. if gd(n) 2.3.1. gngd(n) 2.3.2. if gd(s) return true 2.3.3. Open.ReBuild() 2.4. if kgd(n) 2.4.1. gnkgd(n) 2.4.2. if kgd(s) return false 2.4.3. Open.ReBuild() 2.5. for m ∈ B(n) do Open.Store(m) 3. return false Trong ñoù 1. Thuû tuïc xaây döïng laïi danh saùch Open tæa caùc nhaùnh con chöa xeùt cuûa caùc ñænh ñaõ ñöôïc gaùn nhaõn. 2. Hai thuû tuïc gaùn nhaõn giaûi ñöôïc vaø gaùn nhaõn khoâng giaûi ñöôïc, thöïc hieän vieäc gaùn nhaõn thích hôïp baèng caùch lan truyeàn ngöôïc treân caây tìm kieám (ta vaãn goïi caây bieåu dieãn quaù trình tìm lôøi giaûi laø caây tìm kieám).
Chieán löôïc tìm lôøi giaûi luùc naøy do haøm xaây döïng caây lôøi giaûi höùa heïn quyeát ñònh. Noù cuõng seõ bieát duøng caùc nguyeân lyù ñaõ neâu sao cho hieäu quaû. Ví duï 3.6 Töø caùc ñoà thò con moâ taû luaät phaân raõ caùc baøi toaùn: c d e m o a b a h b c a d o e a b Kieåm tra tính giaûi ñöôïc cuûa baøi toaùn m, bieát caùc baøi toaùn con a vaø b laø giaûi ñöôïc (tìm caây lôøi giaûi töø m ñeán {a,b}). Tieáp caän theo chieàu saâu, ta xaây döïng caây tìm kieám nhö sau 1 m(Ñ) 2 3 6 a(Ñ) d o(Ñ) e 4 5 7 8 a(Ñ) h(S) a(Ñ) b(Ñ) Ví duï 3.7 Cho ∆ABC. Tính c, bieát ñöôøng cao ha goùc A vaø caïnh b, duøng caùc coâng thöùc • A + B + C = π • ha = b*sin(C); ha = c*sin(B) (töông töï cho hb vaø hc) • S = ½ ha*a; S = ½ hb*b; S = ½ hc*c Xem A, B, C, a, b, c, laø caùc baøi toaùn; baøi toaùn sô caáp giaûi ñöôïc laø ñaïi löôïng ñaõ bieát; baøi toaùn caàn kieåm tra laø ñaïi löôïng caàn tính. Theo ñoù, chaúng haïn, ñeå tính a ta coù theå duøng moät trong caùc coâng thöùc hb = a*sin(C), hc = a*sin(B), S = ½ ha*a (hay hc,B → a; hb,C → a; ha,S → a). Minh hoïa quaù trình tính c baèng caùch tìm kieám treân caây AND/OR nhö sau: 1 c(Ñ) 2 3 ha (Ñ) B(Ñ) hb A hc S
4 5 A(Ñ) C(Ñ) hc a 6 7 ha (Ñ) b(Ñ) hb a Nhö vaäy duøng coâng thöùc ha = b*sin(C) ta tính ñöôïc goùc C, roài duøng coâng thöùc A + B + C = π ta tính ñöôïc goùc B vaø cuoái cuøng duøng coâng thöùc ha = c*sin(B) ta tính ñöôïc caïnh c. 3.2. Theâm heuristic - Thuaät giaûi AO* Chuùng ta muoán coù moät thuaät giaûi töông töï nhö A*. Thuaät giaûi AO* sau ñaây, gioáng nhö A* taïi moãi ñænh coù moät haøm öôùc löôïng heuristic hÂ, nhöng khaùc vôùi A* laø trong quaù trình xaây döïng caây caùc giaù trò hÂ ñöôïc tính laïi cho caùc nuùt moãi khi coù theâm thoâng tin. Caùch caäp nhaät laïi giaù trò hÂ tuøy thuoäc töøng baøi toaùn. Thoâng thöôøng ta hay duøng: • Haøm Min cho caùc nuùt OR • Haøm Max (hoaëc Sum) cho caùc nuùt AND. Thuaät giaûi 3 : Thuaät giaûi AO* 1 Ñaët nuùt baét ñaàu vaøo Open 2 Trong luùc Open khaùc roãng thöïc hieän 2.1 Xaùc ñònh caây lôøi giaûi T0 höùa heïn nhaát 2.2 Choïn nuùt n trong phaàn giao cuûa Open vaø caùc nuùt laù cuûa T0. 2.3 Neáu n sô caáp (hoaëc giaûi ñöôïc) thì gaùn nhaõn giaûi ñöôïc cho noù. Neáu n giaûi ñöôïc laøm toå tieân cuûa noù giaûi ñöôïc thì gaùn nhaõn giaûi ñöôïc cho toå tieân cuûa noù Neáu s giaûi ñöôïc thì keát thuùc vôùi T0 laø caây lôøi giaûi Loaïi khoûi Open taát caû caùc nuùt coù toå tieân giaûi ñöôïc 2.4 Neáu n khoâng giaûi ñöôïc thì gaùn nhaõn khoâng giaûi ñöôïc cho noù Neáu n khoâng giaûi ñöôïc laøm toå tieân cuûa noù khoâng giaûi ñöôïc thì gaùn nhaõn khoâng giaûi ñöôïc cho toå tieân cuûa noù
Neáu s ñöôïc gaùn nhaõn khoâng giaûi ñöôïc thì keát thuùc vaø baøi toaùn khoâng giaûi ñöôïc Loaïi khoûi Open taát caû caùc nuùt coù toå tieân khoâng giaûi ñöôïc 2.5 Ngöôïc laïi xeùt caùc nuùt con cuûa n. Ñöa chuùng vaøo Open, tính h cho chuùng, cho n vaø caùc toå tieân cuûa n 3 Keát luaän baøi toaùn khoâng theå keát luaän laø giaûi ñöôïc hay khoâng. Ví duï 3.8 Xeùt ví duï 2.7 vôùi f laø chieàu cao cuûa caây lôøi giaûi, bieát öôùc löôïng hÂ cuûa caây con: n a b c d e o h m hÂ 0 0 1 4 2 3 9 4 Giaûi: Duøng haøm Min cho ñænh OR vaø Max cho ñænh AND ta coù 1 m (0+ 4 3) 2 a(1+0) d(1+4) o(1+3) e (1+2) 6 3 b (2+0) c (2+1) 4 5 a (3+0) b (3+0) Ví duï 3.9 Tìm nguyeân haøm cuûa f(x) = (x2 + x) ex sao cho caây lôøi giaûi coù chieàu cao thaáp nhaát; duøng coâng thöùc tích phaân töøng phaàn vaø tính chaát tuyeán tính. Giaûi: Duøng thuaät giaûi A0* vôùi f laø chieàu cao caây lôøi giaûi, ta öôùc löôïng chieàu cao caây con baèng baäc cuûa ña thöùc coäng vôùi 1 ngoaïi tröø caùc tích phaân cô baûn . (x 2 + x)e x dx ∫ 1 (0+3)
x 2e x dx xe x dx e x dx g = (x 2 + x)dx g e x dx ∫ ∫ ∫ 1 ∫ ∫ 1 6 2 (1+3) (1+2) (1+0) (1+2) (1+3) (1+4) 2xe x dx e x dx e x dx 2e x dx g = (2x +1)dx g e x dx ∫ ∫ ∫ ∫ 2 ∫ ∫ 2 5 3 (2+2) (2+0) (2+0) (2+1) (2+2) (2+3) e x dx ∫ 4 (3+0) Gioáng nhö A*, ta cuõng coù 2 caâu hoûi caàn ñöôïc traû lôøi laø 1. Ñieàu gì baûo ñaûm thuaät giaûi tìm thaáy lôøi giaûi? 2. Thuaät giaûi naøo laø toát hôn, toát nhaát? Baèng caùch ñöa vaøo khaùi nieäm traïng thaùi phöùc, chuùng ta coù theå aùp duïng ñònh lyù 1 ñeå traû lôøi hai caâu hoûi treân. Ta coù keát quaû sau. Ñònh lyù 3.2 Neáu baøi toaùn coù lôøi giaûi toái öu vaø h ≥ hÂ thì thuaät giaûi tìm thaáy lôøi giaûi toái öu. BAØI TAÄP Baøi taäp 3.1 Duøng thuaät toaùn A*, vôùi traïng thaùi ñaàu a, traïng thaùi cuoái z vaø taäp luaät
bieát hÂ cuûa caùc söï kieän a, b, c, d, e, f, z, g, h thöù töï laø 10, 7, 9, 9, 6, 7, 0, 12, 2 Baøi taäp 3.2 Baèng thuaät giaûi A*, tìm ñöôøng ñi ngaén nhaát töø a ñeán g 6 4 b 6 h 6 e 5 7 5 18 a 4 3 g 15 8 f d c duøng haøm heuristic sau n a b c d e f g h hÂ 18 9 11 23 5 3 0 6 Baøi taäp 3.3 Cho taäp luaät (kyù hieäu x→y (n) hieåu laø x suy ra y vôùi chi phí n): a→b (3) b→c (6) c→f (3) e→g (2) d→i (5) i→z (12) j→z (2) a→c (7) b→e (3) c→e (5) e→h (4) d→z (11) i→j (1) j→b (4) a→d (4) e→z (14) d→b (4) Baèng thuaät giaûi A*, chæ ra quaù trình suy dieãn töø a ñeán z duøng heuristic x a b c d e f g h i j z hÂ 10 7 10 14 9 10 12 9 4 2 0 Baøi taäp 3.4 1. Duøng 2 bình coù dung tích laàn löôït laø 5 lít vaø 3 lít, haõy chæ ra caùch laáy ñuùng 1 lít baèng thuaät giaûi A* vôùi heuristic sau Bình 5 lít Bình 3 lít hÂ Bình 5 lít Bình 3 lít hÂ
1 ? 0 5 0 3 ? 1 0 2 ? 2 3 3 1 3 ? 2 2 3 2 ? ? 2 0 3 3 2. Tìm ñöôøng ñi ngaén nhaát töø A ñeán E baèng giaûi thuaät A*, bieát ma traän keà laø A B C D E F A 0 6 0 10 0 4 B 6 0 6 8 10 10 C 0 6 0 0 7 0 D 10 8 0 0 0 8 E 0 10 7 0 0 5 F 4 10 0 8 5 0 duøng heuristic laø moät trong soá caùc khoaûng caùch theo ñöôøng chim bay sau Töø E ñeán töø A ñeán A B C D F E B C D F 6 6 5 3 4 6 6 5 10 4 3. Giuùp ngöôøi noâng daân mang con soùi, thoû vaø gioû caø roát qua soâng bieát raèng moãi löôït anh ta chæ chôû ñöôïc moät trong 3 maø thoâi. Baøi taäp 3.5 1. Xeùt baøi toaùn Puzzle 8 soá. Goïi p1 laø soá caùc soá sai vò trí, p2 laø toång khoaûng caùch ñeán vò trí ñuùng cuûa moãi soá vaø p3 laø toång ñieåm cuûa caùc soá (soá ôû giöõa coù ñieåm laø 1, ôû rìa coù ñieåm laø 2). Giaû söû nuùt baét ñaàu laø (21683574_) vaø ñænh ñích laø (12345678_), ñaët hÂ1 = p1 vaø hÂ2 = p2 + 3p1p3, haõy tìm lôøi giaûi vôùi a) hÂ = hÂ1; b) hÂ = hÂ2; c) hÂ = hÂ2 sau 5 laàn thaùo ñònh roài thay hÂ = hÂ1 2. Tìm moät heuristic cho troø chôi thaùp Haø Noäi 3 ñóa, 4 ñóa. Baøi taäp 3.6 Giaûi laïi caùc ví duï tìm ñöôøng ñi duøng thuaät giaûi A0* thay cho A*
Baøi taäp 3.7 Veõ tam giaùc ABC, duøng nguyeân lyù höôùng ñích, thöû ñaùnh giaù soá coâng thöùc phaûi duøng ñeå tính cho moãi ñaïi löôïng trong tam giaùc. Baøi taäp 3.8 Xeùt baøi toaùn heä thöùc löôïng trong tam giaùc. Baèng thuaät giaûi AO*, haõy giaûi baøi toaùn sau: cho a, b vaø B tính c. Bieát ñaùnh giaù hÂ cuûa caùc baøi toaùn con tính c, A, C, ha, hb, hc, S laàn löôït laø 5, 2, 3, 4, 5, 1, 5. Baøi taäp 3.9 Cho taäp luaät Duøng thuaät toaùn A0* kieåm tra xem baøi toaùn x coù giaûi ñöôïc hay khoâng neáu: Bieát caùc baøi toaùn u vaø v laø giaûi ñöôïc vaø hÂ cuûa caùc baøi toaùn a, b, c, d, e, f, m, n, o, p, t, u, v, x vaø w thöù töï laø 4, 3, 2, 3, 1, 4, 3, 2, 2, 4, 1, 0, 0, 2 vaø 4 (duøng haøm max cho nuùt And vaø haøm min cho nuùt Or). Baøi taäp 3.10 Xeùt baøi toaùn tính cos(150), haõy 1. Trình baøy caùch tính 2. Minh hoïa baèng caây And/Or 3. Cung caáp moät heuristic roài giaûi baèng thuaät giaûi A0*
Chöông 4 Troø chôi ñoái khaùng vaø phöông phaùp GPS 1. Troø chôi ñoái khaùng 1.1. Khaùi nieäm Trong tieáp caän tröôùc, chuùng ta coù toaøn quyeàn trong vieäc löïa choïn traïng thaùi, vaø caùc pheùp bieán ñoåi ñeå giaûi quyeát vaán ñeà. Thöïc teá khoâng nhö vaäy, sau khi laäp keá hoaïch xong (A*, A0*), ñeán luùc thöïc hieän, laïi xuaát hieän nhöõng thoâng tin môùi, nhöõng tình huoáng môùi caûn trôû vieäc ñaït ñeán muïc tieâu cuûa chuùng ta. Trong muïc naøy, chuùng ta seõ khaûo saùt moät bieåu dieãn khaùc, ñoù laø troø chôi ñoái khaùng vôùi hai ñaáu thuû. Côø töôùng, côø vua, côø vaây, côø caro, laø nhöõng troø chôi ñoái khaùng maø chuùng ta ñaõ khaù quen thuoäc. Chuùng ta moâ hình noù nhö sau: Moãi theá côø laø moät traïng thaùi. Moät nöôùc ñi hôïp leä laø moät pheùp bieán ñoåi. Moät haøm lôïi ích ñònh nghóa treân taäp caùc theá côø. Muïc tieâu cuûa ngöôøi chôi laø, ñeán löôït mình, phaûi quyeát ñònh choïn moät nöôùc ñi. Ñaáu thuû naøo choïn ñöôïc theá thaéng cho mình thì ñaáu thuû ñoù thaéng cuoäc. Moät haøm öôùc löôïng khaû naêng thaéng cuûa ñaáu thuû ñi tröôùc ñöôïc ñònh nghóa treân taäp caùc theá côø. Caùc chieán löôïc cuûa caùc ñaáu thuû ñeàu taäp trung öôùc löôïng thaät chính xaùc caùc theá côø trong giôùi haïn thôøi gian cho pheùp. Nguyeân lyù höôùng ñích ñöôïc söû duïng, theo ñoù caøng gaàn ñích, haøm öôùc löôïng caøng chính xaùc. Ñaáu thuû ñi tröôùc choïn theá côø sao cho cöïc ñaïi haøm öôùc löôïng, trong khi ñaáu thuû coøn laïi (ñaáu thuû ñi sau) laïi coá coâng laøm cöïc tieåu noù. Duøng nguyeân lyù löïa choïn saâu daàn, caùc ñaáu thuû phaûi tính saâu xuoáng môùi mong coù nhöõng öôùc löôïng chính xaùc ñeå khoâng sai laàm trong choïn theá côø. Chuùng ta cuõng seõ bieåu dieãn quaù trình quyeát ñònh baèng caây And/Or vaø goïi laø caây troø chôi vôùi quy öôùc ñænh AND ñeán löôït choïn cuûa ñaáu thuû ñi tröôùc vaø duøng haøm Max coøn caùc löïa choïn cuûa ñaáu thuû ñi sau naèm ôû ñænh OR vaø duøng haøm Min
1.2. Thuaät giaûi (a) Nhöõng neùt chính Chuùng ta khoâng neân duøng nguyeân lyù veùt caïn bôûi soá theá côø laø voâ cuøng lôùn. Vieäc phaùt trieån caây troø chôi seõ döøng laïi khi hoaëc caùc öôùc löôïng laø ñuû tin caäy, hoaëc chieàu cao cuûa caây laø ñuû lôùn, hoaëc soá theá côø laø ñuû lôùn. Khi caây ñöôïc phaùt trieån xong, taäp caùc nuùt laù seõ hình thaønh moät hình aûnh gioáng nhö ñöôøng chaân trôøi. Taïi ñaây caùc giaù trò öôùc löôïng ñöôïc thöøa nhaän laø chính xaùc hôn vaø quaù trình tính toaùn ñöôïc lan truyeàn cho ñeán goác. Döïa treân keát quaû tính toaùn maø ñaáu thuû quyeát ñònh nöôùc ñi. Ví duï 4.1 Xeùt troø chôi tic-tac-toe sau (caùc theá côø ñöôïc minh hoïa khoâng ñaày ñuû)
(b) Thuû tuïc Min/Max Quaù trình tính toaùn raát ñôn giaûn, ví duï sau cho chuùng ta thaáy ñieàu ñoù. Ví duï 4.2 Moät caây troø chôi ñôn giaûn Trong quaù trình treân, caùc nuùt ñöôïc môû heát tröôùc khi caùc giaù trò Min, Max ñöôïc tính toaùn. Thaät ra moät ngöôøi chôi côø coù trình ñoä seõ khoâng thöïc hieän nhö vaäy. Tröôùc heát anh ta seõ choïn moät theá bieán (nöôùc ñi) coù nhieàu öu theá nhaát vaø tính toaùn caån thaän ñeå laøm cô sôû ñaùnh giaù tieáp. Sau ñoù xem xeùt caùc theá bieán khaùc, döïa treân cô sôû so saùnh vôùi theá bieán ñaõ choïn, anh ta coù theå nhanh choùng loaïi boû caùc theá bieán khoâng toát hoaëc tìm ra moät theá bieán khaùc toát hôn. Thuû tuïc α-β sau thöïc thi gioáng nhö theá, nhôø ñoù giaûm nheï ñöôïc quaù trình tính toaùn. (c) Caét nhaùnh baèng thuû tuïc α-β (alpha-beta) Ñònh nghóa 4.1 Nguyeân lyù α-β : Neáu moät ñieàu chaéc chaén laø toài thì ñöøng coá coâng ñeå thaáy noù toài nhö theá naøo. Quaû vaäy Ngöôøi chôi côø khi ñaõ phaùt hieän ñöôïc moät theá bieán baát lôïi cho mình thì anh ta seõ khoâng phaân tích theá bieán aáy nöõa. Xeùt thuaät toaùn tính min cuûa daõy ai (i = 1 n) β = a1 for i := 2 to n do if β > ai then β = ai min = β Töông töï cho max.
α = a1 for i := 2 to n do if α < ai then α = ai max = α ÔÛ ñaây chuùng ta coi α laø max taïm thôøi coøn β laø min taïm thôøi. Giaû söû ñang ñænh AND ñang coù max taïm thôøi laø α, hieän taïi ta ñang tính giaù trò cuûa moät nuùt con vaø coù giaù trò min taïm thôøi laø β. Neáu thaáy α ≥ β thì duø chöa tính xong min anh ta chaúng coù lyù do gì ñeå maát coâng tính cho xong Cuõng vaäy, ñaõ coù β, ñang tính max vaø neáu coù β ≤ α thì duø chöa tính xong max anh ta cuõng thoâi khoâng tính nöõa. Hai quaù trình noùi treân ñöôïc goïi laø caùc nhaùt caét α-β. Thuû tuïc α-β duøng caùc nhaùt caét naøy ñeå tæa nhaùnh cuûa caây tìm kieám. Ñònh nghóa 4.2 1. Nhaùt caét α caét caùc nhaùnh döôùi nuùt AND neáu β hieän thôøi cuûa noù khoâng lôùn hôn α hieän thôøi cuûa nuùt cha. 2. Nhaùt caét β caét caùc nhaùnh döôùi nuùt OR neáu α hieän thôøi cuûa noù khoâng beù hôn β hieän thôøi cuûa nuùt cha. Thöïc hieän nhaùt caét α khi α ≥ β vaø tröôøng hôïp ñaëc bieät
Thöïc hieän nhaùt caét β khi β ≤ α vaø tröôøng hôïp ñaëc bieät Thuaät toaùn alpha: nhaùt caét beta Vaøo: traïng thaùi S, nhaùt caét β, Ra: giaù trò max taïm thôøi α 1 If (S naèm ôû ñöôøng chaân trôøi) then return Utility(S) 2 Ñaët α = -∞ 3 Vôùi moãi traïng thaùi con n cuûa S 3.1 Tính t = beta(n, α) 3.2 If (α < t) then 3.2.1 α = t 3.2.2 If (β < α) then return α 4 return α Trong ñoù Utility(S) laø haøm lôïi ích cuûa S Thuaät toaùn beta: nhaùt caét alpha Töông töï thuaät toaùn alpha Thuaät giaûi 4: Thuû tuïc alpha-beta Vaøo: traïng thaùi S, löôït ñi T Ra: giaù trò öôùc löôïng cuûa S 1 If (T laø löôït ñi cuûa Max) return alpha(S,∞)
2 return beta(S,-∞) Ví duï 4.3 Trôû laïi ví duï 2. Tröôùc heát tính ñöôïc α cuûa goác: Tính β cuûa nuùt con thöù hai cuûa goác, vì β ≤ α, caét. Tính β cuûa nuùt con thöù ba cuûa goác, vì β > α, khoâng coù nhaùt caét xaûy ra. Tieáp tuïc tính β cuûa nuùt con thöù ba cuûa goác, vì β > α, vaãn khoâng coù nhaùt caét.
Tính xong min, roài xong max. Ví duï 4.4 Choïn nöôùc ñi cho ñaáu thuû Max treân caây troø chôi maø moãi ñænh coù 3 nuùt con coù chieàu cao baèng 3 vaø giaù trò öôùc löôïng h cuûa 27 nuùt laù theo thöù töï töø traùi qua laø 8,7,2, 9,1,6, 2,4,1, 1,3,5, 3,9,2, 6,5,2, 1,2,3, 9,7,2, 16,6,4. Minh hoïa 8 7 2 9 2 4 1 1 3 5 3 9 6 1 2 3
1.3. Baøn theâm veà heuristic Treân ñöôøng chaân trôøi coù voâ soá caùc theá côø caàn ñaùnh giaù. Thuaät giaûi chæ thaät söï hieäu quaû khi chuùng ta choïn ñöôïc sôùm caùc theá côø toát ôû ñoù. Nhö vaäy ngoaøi haøm öôùc löôïng ra chuùng ta coøn caàn ñeán moät soá thoâng tin heuristic daãn ñöôøng. Ví duï 4.5 Laøm laïi ví duï 2.18 treân coù theâm heuristic daãn ñöôøng: 5 ≤4 5 ≤3 4 5 ≥9 ≥6 3 2 4 1 1 2 5 9 6 1 2 3 Ngoaøi ra neáu muoán söû duïng nguyeân lyù höôùng ñích, ngöôøi chôi côø caàn ñöa ra caùc ñích trung gian, roài laäp keá hoaïch thöïc hieän muïc tieâu con naøy. Vôùi caùc ñích trung gian caùch theá côø hieän taïi khoâng quaù xa neân öôùc löôïng seõ chính xaùc hôn. 2. Phöông phaùp giaûi quyeát vaán ñeà toång quaùt (GPS) 2.1. Khaùi nieäm Trong thöïc teá, coù caû moät soá lôùn caùc luaät laøm cho caùc khaû naêng löïa choïn bò buøng noå. Phöông phaùp GPS ñöôïc khaûo saùt trong muïc naøy söû duïng moät soá caùc ñoä ño khaùc bieät ñeå giuùp löïa choïn maø khoâng caàn môû heát caùc nuùt. Ví duï 4.6 Trong logic meänh ñeà ta coù Taäp luaät Taäp caùc ñoä ño khaùc bieät
(r1) ¬¬p ↔ p D1. Nhieàu hôn moät chöõ (r2) p+q ↔ q+p D2. Ít hôn moät chöõ pq ↔ qp D3. Soá daáu phuû ñònh (r3) p⇒q ↔ ¬q⇒¬p D4. Soá pheùp toaùn +, * (r4) p+p ↔ p D5. Soá daáu ngoaëc pp ↔ p D6. Thöù töï caùc chöõ (r5) (p+q)+r ↔ p+(q+r) (pq)r ↔ p(qr) (r6) p+q ↔ ¬(¬p¬q) pq ↔ ¬(¬p + ¬q) (r7) p ⇒ q ↔ ¬p + q (r8) p(q+r) ↔ pq + pr p+qr ↔ (p+q)(p+r) (r9) pq → p pq → q (r10) p → p + q (r11) p, q → pq (r12) p, p ⇒ q → q (r13) p ⇒ q, q ⇒ r → p ⇒ r Ñònh nghóa 4.3 Moâi tröôøng cho phöông phaùp GPS laø boä boán , trong ñoù 1. S laø taäp traïng thaùi vôùi S0 vaø S* laø caùc traïng thaùi ñaàu vaø cuoái töông öùng 2. O laø taäp caùc pheùp bieán ñoåi treân S vaø 3. D laø taäp caùc khaùc bieät coù theå coù giöõa 2 traïng thaùi. 4. M laø ma traän quan heä Ví duï 4.7 Trong logic meänh ñeà ta ñaõ bieát S laø taäp caùc meänh ñeà coøn O vaø D cho trong
ví duï treân. Trong ví duï naøy ta boå sung theâm ma traän quan heä M r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 D1 x x x x D2 x x x x x D3 x x x x D4 x x x D5 x x D6 x x 2.2. Thuaät giaûi (a) Phaân tích means-end Thuaät toaùn: phaân tích means-end Vaøo: S Ra: Thaønh coâng hoaëc thaát baïi 1. So saùnh S vôùi S* vaø xaùc ñònh Ds* 2. Choïn moät pheùp bieán ñoåi Ok laøm giaûm Ds* 3. Aùp duïng Ok. Neáu khoâng ñöôïc thì löu laïi, phaùt sinh ñích môùi vaø phaân tích means-ends cho noù. 4. Neáu ñích con ñöôïc giaûi thì quay lui veà ñích ñaõ löu gaàn nhaát Thuaät giaûi 5: thuaät giaûi GPS 1. Phaân tích means-end cho traïng thaùi S0 2. Neáu thaønh coâng thì phaùt sinh lôøi giaûi Chuùng ta minh hoïa phöông phaùp naøy qua hai ví duï: baøi toaùn bieán ñoåi bieåu thöùc vaø baøi toaùn con khæ naûi chuoái. Chuùng ta baét ñaàu vôùi baøi toaùn bieán ñoåi bieåu thöùc cuûa meänh ñeà ñöôïc bieåu dieãn qua hai loaïi ñænh trong caây tìm kieám vaø baøi toaùn con khæ naûi chuoái vôùi caùc nuùt rieâng ñaëc thuø cho phöông phaùp GPS.
(b) Duøng caây vôùi caùc nuùt trong S Moãi nuùt laø meänh ñeà, pheùp bieán ñoåi laø luaät (ví duï 2.31, 2.32), löïa choïn luaät baèng caùch giaûm Di Ví duï 4.8 Haõy bieán ñoåi R(¬P ⇒ Q) thaønh (Q+P)R • So saùnh R(¬P ⇒ Q) vôùi (Q+P)R khaùc bieät D3, D4 vaø D6 • aùp duïng r1 (ñeå giaûm D6) ñöôïc (¬P ⇒ Q)R • aùp duïng r6 (ñeå giaûm D4) ñöôïc (¬¬P + Q)R • aùp duïng r0 (ñeå giaûm D3) ñöôïc (P + Q)R • aùp duïng r1 (ñeå giaûm D6) ñöôïc (Q + P)R (c) Duøng caây vôùi caùc nuùt rieâng ÔÛ ñaây ta duøng 3 loaïi nuùt ( goïi laø 3 ñích - Goal ) vôùi luaät phaùt sinh rieâng cho moãi loaïi nuùt 1. Nuùt nhaõn A nghóa laø aùp duïng luaät, neáu khoâng thaønh coâng nuùt ñöôïc löu vaø sinh ra (luaät rieâng cuûa baøi toaùn) nuùt F 2. Nuùt nhaõn F nghóa laø tìm luaät, neáu tìm thaáy sinh ra moät nuùt A 3. Nuùt nhaõn T nghóa laø tìm D, neáu tìm thaáy phaùt sinh F Giaûi baøi toaùn ñöôïc baét ñaàu vôùi nuùt T, dó nhieân T giaûi ñöôïc neáu khoâng tìm thaáy moät khaùc bieät naøo caû. Töø T sinh ra F, töø F sinh ra A. Neáu A khoâng giaûi ñöôïc, löu laïi vaø sinh ra F vaø cöù nhö vaäy Ví duï 4.9 Giaûi baøi toaùn con khæ vaø naûi chuoái. Tröôùc heát ta xaùc ñònh moâi tröôøng • Bieåu dieãn traïng thaùi laø boä 3, chaúng haïn traïng thaùi ban ñaàu S0 = {loc(M) = p1, loc(C) = p2, contents(hand M) = ∅ } nghóa laø con khæ M ôû taïi p1, chieác gheá C ôû p2, tay con khæ khoâng coù gì. Traïng thaùi ñích S* {?, ?, contents(hand M) = B }
nghóa laø tay con khæ coù naûi chuoái B • Taäp caùc khaùc bieät D1 = loc(M) khaùc veà vò trí con khæ D2 = loc(C) khaùc veà vò trí chieác gheá D3 = contents(hand M) khaùc veà caùi trong tay con khæ Trong ñoù ta quy öôùc thöù töï ñoä khoù laø D3 D2 vaø D1 • Caùc pheùp bieán ñoåi r1 : CLIMB condition loc(M) = loc(C) action loc(M) = on-C r2 : WALK condition x laø bieán vò trí action loc(M) = x r3 : MOVE condition x laø bieán vò trí loc(M) ≠ on-C loc(M) = loc(C) action loc(M) = x loc(C) = x r4 : GET condition loc(C) = under-B loc(M) = on-C action contents(hand M) = B • Ma traän quan heä D1 D2 D3 r1 x
r2 x r3 x x r4 x Ví duï 4.10 Minh hoïa baøi toaùn con khæ vaø naûi chuoái baèng caây vôùi 3 loaïi nuùt T, F vaø A 1 Baét ñaàu laø nuùt T 2 Choïn D3, phaùt sinh F 3 Choïn r4, khoâng aùp duïng ñöôïc 4 Phaùt sinh F laøm giaûm D2 5 Choïn r3, khoâng aùp duïng ñöôïc 6 Phaùt sinh F laøm giaûm D1
7 Choïn r2, aùp duïng ñöôïc S1= {loc(M)= p2, loc(C)= p2, contents(hand M)= ∅ } 8 Quay veà ñích G5 tieáp tuïc aùp duïng r3 ñöôïc S2 = {loc(M) = under-B, loc(C) = under-B, contents(hand M) = ∅ } 9 Quay veà ñích G3 tieáp tuïc aùp duïng r4 nhöng vaãn khoâng ñöôïc 10 Phaùt sinh F laøm giaûm D1 11 Choïn r1, aùp duïng ñöôïc S3 = {loc(M) = on-C, loc(C) = under-B, contents(hand M) = ∅ } 12 uay veà ñích G9 tieáp tuïc aùp duïng r4 ñöôïc S4 = {loc(M) = on-C, loc(C) = under-B, contents(hand M) = B } 13 Quay veà ñích G1 tieáp T vaø keát thuùc thaønh coâng Minh hoïa ñaày ñuû
Ví duï 4.11 Minh hoïa baøi toaùn con khæ vaø naûi chuoái baèng caây vôùi caùc nuùt laø caùc keát quaû trung gian. Quy öôùc caùc vò trí nhö sau • p, q laø tuyø yù • 1 laø under-B • 0 laø on-C Kyù hieäu boä ba (x, y, z) vôùi yù nghóa x laø vò trí con khæ, y laø vò trí caùi gheá coøn z nhaän 0 neáu tay khæ chöa coù chuoái, nhaän 1 trong tröôøng hôïp ngöôïc laïi. Ta coù S0= (p, q, 0) coøn S* = (.,.,1) Keát quaû tìm kieám
BAØI TAÄP Baøi taäp 4.1 Duøng thuaät giaûi alpha/beta, choïn nöôùc ñi tieáp theo vôùi caây troø chôi nhö sau: bieát ñaùnh giaù töø traùi sang laø 7,4, 6,2, 5,4,1, 3,1, 4,2,2, 3,1, 4,1, 2,4,6, 3,5 Baøi taäp 4.2 Xeùt troø chôi tic-tac-toe, vôùi theá côø hieän taïi daønh cho X nhö sau (X ñi tröôùc,) X O O O X X Baèng caùch tính xuoáng 2 nöôùc ñi, haõy xaùc ñònh nöôùc ñi keá tieáp bieát haøm ñaùnh giaù p laø toång cuûa caùc giaù trò quaân ñi tröôùc tröø cho toång cuûa caùc giaù trò quaân sau, vôùi toång giaù trò cuûa moät quaân côø laø söï cheânh leäch quaân trong laân caän 4. Baøi taäp 4.3 Cho caây troø chôi sau:
Bieát ñaùnh giaù caùc theá côø ôû ñöôøng chaân trôøi töø traùi qua phaûi laø 3, 2, 4, 5, 1, 3, 6, 4, 7, 5, 2, 3, 5, 3, 2, 4, 5 vaø 1. Haõy choïn nöôùc ñi vôùi yeâu caàu 1. Duøng minmax 2. Duøng minmax coù söû duïng nhaùt caét αβ vôùi thöù töï xeùt töø phaûi qua traùi. Baøi taäp 4.4 Xeùt troø chôi Tic-tac-toe, haõy chæ cho ñaáu thuû ñi tröôùc nöôùc ñi chính xaùc neáu haøm öôùc löôïng laø hieäu cuûa caùc ñöôøng môû cuûa hai ñaáu thuû. Bieát caây troø chôi X X O O X X X O O O O X X X X X X X Baøi taäp 4.5 Cho hai theá côø sau, trong theá côø thöù 1 ñeán löôït ñi cuûa traéng, coøn ôû theá côø
thöù 2 ñeán löôït cuûa ñen. Haõy xaùc ñònh moät haøm ñaùnh giaù ñeå chöùng toû traéng öu trong theá côø thöù 1 coøn ñen thaéng trong theá côø thöù 2. Baøi taäp 4.6 Chöùng toû nhaùt caét saâu sau ñaây khoâng aûnh höôûng ñeán thuû tuïc min-max (α ≥ β) Baøi taäp 4.7 Bieán ñoåi bieåu thöùc (r ⇒ ¬p) (¬r ⇒ q) veà ¬(¬qp) Baøi taäp 4.8 Cho 2 bình: bình I coù dung tích 5 lít vaø bình II coù dung tích 8 lít. Haõy chæ ra caùch laáy ñuùng 2 lít baèng phöông phaùp GPS, bieát moâi tröôøng cuûa baøi
toaùn nhö sau: 1 S0 = (0,0): hai bình roãng, S* = (2,8): bình I chöùa 2 lít coøn bình II ñaày. 2 Coi Di laø soá lít khaùc nhau ôû bình i (i=1,2) (giaû söû D1 quan troïng hôn D2) 3 R1: sang nöôùc töø bình I sang bình II R2: ñoå nöôùc vaøo hoaëc ra khoûi bình I R3: sang nöôùc töø bình II sang bình I R4: ñoå nöôùc vaøo hoaëc ra khoûi bình II 4 Quan heä: R2 thay ñoåi d1, R4 thay ñoåi d2 coøn R1 vaø R3 thay ñoåi caû d1, d2. Baøi taäp 4.9 Duøng phöông phaùp GPS ñöa S0 veà S* vôùi moâi tröôøng cuûa baøi toaùn nhö sau: 5 Traïng thaùi ñaàu S0 = (4, 6) Traïng thaùi cuoái S* = (0, 0) 6 d1 : söï khaùc bieät giöõa caùc soá thöù nhaát d2 : söï khaùc bieät giöõa caùc soá thöù hai 7 r1: ñöa (x, y) veà (x-2, y-1) vôùi ñieàu kieän x > y r2: ñöa (x, y) veà (x, y-2) vôùi ñieàu kieän y > 0 8 Ma traän quan heä nhö sau: r1 giaûm d1 vaø d2 coøn r2 chæ giaûm d2. Baøi taäp 4.10 Cho moâi tröôøng • Si = (5,3,2) vaø Sf = (0,0,0) • Xeùt S = (a1, a2, a3), ta noùi coù khoaûng caùch di neáu ai>0 • Taäp luaät goàm r1 : ñöa (a1, a2, a3) veà (0, a2, a3) neáu 0 < a1 < 4 r2 : ñöa (a1, a2, a3) veà (a1 –1 , a2 –1, a3) neáu 0 < a1, 0 < a2
hoaëc giöõ nguyeân traïng thaùi cuõ trong tröôøng hôïp ngöôïc laïi. r3 : ñöa (a1, a2, a3) veà (a1, a2, 0) • Ma traän quan heä nhö sau: r1 giaûm d1, r2 giaûm d1 vaø d2 coøn r3 giaûm d3. 1. Lieäu phaân tích means-end coù ñöa Si veà Sf ñöôïc khoâng? Veõ caây minh hoïa? 2. Tröôøng hôïp thay ñoåi ñoä öu tieân d2 tröôùc d1 vaø cuoái cuøng laø d3 thì keát quaû theá naøo? PHAÀN 2 SUY LUAÄN Khi xem xeùt caùc söï kieän chuùng ta ñeàu muoán coù ñöôïc moät ñaùnh giaù veà chuùng, raèng chuùng coù thaät söï xaûy ra khoâng, vôùi möùc ñoä bao nhieâu; ñeå töø ñoù maø coù nhöõng keát luaän phuø hôïp. Muoán vaäy chuùng ta caàn coù trong tay nhöõng chöùng cöù vaø tìm ra caùc moái lieân heä giöõa caùc chöùng cöù naøy vôùi nhöõng söï kieän
maø chuùng ta quan taâm. Trong thöïc teá coù nhöõng vaán ñeà ñoøi hoûi vieäc keát luaän phaûi thaät chính xaùc, hoaëc ñuùng hoaëc sai; chuùng thöôøng coù daïng ñònh lyù p→ q, trong ñoù p laø giaû thieát coøn q laø keát luaän. Tuy nhieân, haàu heát nhöõng thoâng tin maø chuùng ta coù ñöôïc laø khoâng chaéc chaén. Khi xem xeùt moät söï kieän, chuùng ta khoâng chaéc chaén laø noù xaûy ra hay khoâng. Thay vaøo ñoù chuùng ta tìm caùch ñaùnh giaù khaû naêng xaûy ra roài caên cöù vaøo ñoù maø keát luaän.
Chöông 5 Suy luaän logic Suy luaän logic duøng ñeå keát luaän veà nhöõng vaán ñeà ñoøi hoûi phaûi chính xaùc, hoaëc ñuùng hoaëc sai. Nhöõng vaán ñeà naøy thöôøng coù daïng ñònh lyù p→ q, trong ñoù p laø giaû thieát coøn q laø keát luaän. Vì yeâu caàu veà tính chaët cheõ vaø chính xaùc cuûa vaán ñeà caàn giaûi quyeát, chuùng ta caàn ñeán caùc suy luaän logic, vaø do ñoù caàn laøm quen vôùi caùch bieåu dieãn meänh ñeà. 1. Suy luaän Ñònh nghóa 5.1 1. Suy luaän laø quaù trình laøm vieäc vôùi tri thöùc, söï kieän vaø caùc chieán löôïc giaûi baøi toaùn ñeå ruùt ra keát luaän. 2. Suy dieãn laø phöông tieän sinh ra caùc söï kieän môùi. Ví duï 5.1 Xeùt baøi toaùn tìm ñöôøng ñi: 1 Thaønh phoá ñi vaø thaønh phoá ñeán laø caùc söï kieän ban ñaàu; 2 Baûn ñoà laø tri thöùc giuùp ta suy dieãn ra caùc thaønh phoá caàn xeùt laø caùc söï kieän môùi; 3 Vieäc quyeát ñònh xeùt nhöõng thaønh phoá naøo ñeå tìm thaáy ñöôøng ñi laø chieán löôïc giaûi baøi toaùn. 4 Keát quaû cuûa quaù trình naøy laø keát luaän veà vieäc coù tìm thaáy ñöôøng ñi hay khoâng; vaø vieäc chæ roõ ñöôøng ñi nhaèm khaúng ñònh keát luaän cuûa coù ñöôïc laø ñuùng ñaén vaø hôïp logic; töùc laø quaù trình suy luaän. Roõ raøng keát quaû suy luaän tuøy thuoäc vaøo caùch chuùng ta duøng söï kieän, tri thöùc vaø chieán löôïc giaûi baøi toaùn cuï theå nhö theá naøo. Theo ñoù, chuùng ta coù theå söû duïng phöông phaùp tìm kieám ñeå chæ ra quaù trình suy luaän.
Ñònh nghóa 5.2 Suy luaän ñôn ñieäu laø suy luaän maø caùc söï kieän (cuõ hoaëc môùi phaùt sinh trong quaù trình laøm vieäc) vaãn ñöôïc giöõ nguyeân veïn. Ngöôïc laïi vôùi suy luaän ñôn ñieäu laø suy luaän khoâng ñôn ñieäu. Ví duï 5.2 Trong baøi toaùn tìm ñöôøng ñi ta quan saùt thaáy caùc söï kieän (thaønh phoá caàn xem xeùt) ñöôïc boå sung daàn vaø vaãn ñöôïc giöõ nguyeân veïn. Baây giôø chaúng haïn ñaët baøi toaùn phuï thuoäc vaøo thôøi gian. Khi aáy trong khi suy luaän coù khaû naêng moät vaøi söï kieän ñaõ ñöôïc boå sung vì lyù do naøo ñoù trôû neân khoâng ñuùng ñaén (coù theå do söï coá giao thoâng!) hoaëc moät soá söï kieän leõ ra caàn ñöôïc boå sung (coù theå do môùi thoâng ñöôøng!) laøm cho taäp caùc söï kieän khoâng coøn toaøn veïn. Roõ raøng vôùi tröôøng hôïp sau thì suy luaän ñôn ñieäu trôû neân khoâng coøn phuø hôïp nöõa. 2. Suy luaän vôùi logic meänh ñeà 2.1. Khaùi nieäm Meänh ñeà laø moät phaùt bieåu hoaëc ñuùng hoaëc sai. Moät caùch hình thöùc, ngoân ngöõ cuûa logic meänh ñeà ñöôïc xaây döïng töø moät baûng caùc kyù hieäu meänh ñeà bao goàm caùc meänh ñeà, caùc haèng meänh ñeà vaø caùc bieán meänh ñeà, cuøng caùc pheùp toaùn logic quen thuoäc nhö tích (.), toång (+), phuû ñònh (¬), keùo theo (→) Ñònh nghóa 5.3 1. Moãi kyù hieäu meänh ñeà laø moät daïng meänh ñeà 2. Neáu p, q laø daïng meänh ñeà thì ¬p, p.q, p + q, p → q laø caùc daïng meänh ñeà Ví duï 5.3 1 5 > 7 laø meänh ñeà sai 2 12 ≤ 12 laø moät meänh ñeà ñuùng 3 x > 5 khoâng phaûi laø moät meänh ñeà 4 (p + q) → r ¬(s → p) laø moät daïng meänh ñeà, vôùi p, q, r vaø s laø caùc bieán meänh ñeà.
Ñònh nghóa 5.4 1. Daïng meänh ñeà chæ goàm moät bieán meänh ñeà hoaëc phuû ñònh cuûa moät bieán meänh ñeà ñöôïc goïi laø moät töø ñôn 2. Daïng meänh ñeà laø tích cuûa caùc töø ñôn ñöôïc goïi laø moät ñôn thöùc. 3. Daïng meänh ñeà laø toång cuûa caùc töø ñôn ñöôïc goïi laø moät caâu ñôn Ñònh lyù 5.1 Moïi daïng meänh ñeà ñeàu coù caùc daïng bieåu dieãn sau 1. Toång cuûa caùc ñôn thöùc hay daïng tuyeån chuaån taéc 2. Tích cuûa caùc caâu ñôn hay daïng hoäi chuaån taéc Thuaät toaùn ñöa daïng meänh ñeà veà daïng chuaån taéc 1 Khöû pheùp keùo theo baèng caùch thay daïng meänh ñeà p → q bôûi daïng meänh ñeà ¬p + q. 2 Ñöa daáu phuû ñònh vaøo taän cuøng baèng caùch thay daïng meänh ñeà ¬ (p + q) bôûi ¬p¬q vaø ¬ (p q) bôûi ¬p +¬q 3 Khai trieån baèng caùch thay daïng meänh ñeà p (q + r) bôûi pq + pr hoaëc thay daïng meänh ñeà p + qr bôûi (p + q)(p + r) Ví duï 5.4 Ñöa daïng meänh ñeà sau ¬ ( a → b ) + c ( d + a ) veà daïng tuyeån chuaån taéc • Sau böôùc 1: ¬ ( ⎤ a + b ) + c ( d + a ) • Sau böôùc 2: a¬ b + c ( d + a ) • Vaø cuoái cuøng: a¬ b + cd + ca 2.2. Moät soá cô cheá phaùt sinh söï kieän (quy taéc suy dieãn) (a) Suy dieãn Modus ponens P P → Q ∴Q
Modus tollens ¬Q P → Q ∴¬P Ví duï 5.5 Trôøi möa Trôøi möa → Ñaát öôùt ∴Ñaát öôùt Ñaát khoâng öôùt Trôøi möa → Ñaát öôùt ∴Trôøi khoâng möa (b) Quy dieãn Q P → Q ∴P Ví duï 5.6 Ñaát öôùt Trôøi möa → Ñaát öôùt ∴Trôøi möa (c) Quy naïp (khoâng hoaøn toaøn) P P1 → Q Pn → Q ∴Q Ví duï 5.7 Ngaøy mai, Noùng Hoâm qua, Noùng → Möa Hoâm nay, Noùng → Möa ∴Möa (d) Töông töï P’ P → Q
∴Q’ Ví duï 5.8 P’ P → Q ∴Q’ (e) Hôïp giaûi P ∨ Q ¬ P ∨ R ∴Q ∨ R Ví duï 5.9 Teøo taém möa ∨ Trôøi khoâng möa Trôøi möa ∨ Tyù chôi boùng ñaù ∴ Teøo taém möa ∨ Tyù chôi boùng ñaù 2.3. Suy luaän (a) Duøng caây AND/OR Ñænh AND duøng haøm MIN, ñænh OR duøng haøm MAX Ví duï 5.10 Haõy keát luaän xem A coù xaûy ra hay khoâng neáu F, I vaø J ñöôïc bieát laø ñaõ xaûy ra. Söû duïng taäp luaät sau r1: F → D r5: DE → B r2: IH → D r6: B → A r3: G+J → E r7: C → A r4: H+FG → C Taäp luaät A B C D E B C D E H F G F I H G J Caây suy luaän A Ñ
B Ñ C D Ñ E Ñ F Ñ I H G J Ñ Veà chieán löôïc giaûi quyeát vaán ñeà 1. Ta coù theå duøng caùc nguyeân lyù tìm kieám treân caây 2. Hoaëc thöïc hieän caùc nhaùt caét tuyeät ñoái nhôø ñoù maø neân vieäc nhanh choùng ñi ñeán caùc söï kieän cho tröôùc giuùp quaù trình suy luaän ñöôïc nhanh choùng. (b) Duøng hôïp giaûi Vieát laïi quy taéc suy dieãn hôïp giaûi p + q ¬p + r ∴q + r Vaø nhaéc laïi phöông phaùp chöùng minh phaûn chöùng: Thay vì chöùng minh p → q, ta ñi chöùng minh p¬ q suy ra ñieàu voâ lyù Thuaät giaûi 6: quaù trình hôïp giaûi Robinson Taäp luaät coù daïng hoäi chuaån taéc 1 Chuyeån baøi toaùn coù daïng meänh ñeà p → q thaønh p¬q 2 Ñöa caùc daïng meänh ñeà veà daïng hoäi chuaån taéc 3 Khôûi taïo taäp S goàm caùc caâu ñôn
4 Choïn trong S ra moät caëp, goïi laø caëp tieàn boái, coù theå duøng ñöôïc nguyeân lyù hôïp giaûi 4.1 Hôïp giaûi ñöôïc caâu môùi, goïi laø haäu dueä 4.2 Neáu haäu dueä laø caâu roãng thì return true 4.3 Traû hai tieàn boái vaø boå sung haäu dueä vaøo S 5 Return false Ví duï 5.11 Chöùng minh meänh ñeà (⎤ a+⎤ b+c) ( ⎤ b+⎤ c+d) a b → d • Baét ñaàu (⎤ a+⎤ b+c), ( ⎤ b+⎤ c+d), a, b vaø ⎤ d • Hôïp giaûi (⎤ a+⎤ b+c) vaø a ñöôïc (⎤ b+c) • Hôïp giaûi (⎤ a+⎤ b+c) vaø b ñöôïc (⎤ a+c) • Hôïp giaûi (⎤ b+⎤ c+d) vaø ⎤ d ñöôïc (⎤ b+⎤ c) • Hôïp giaûi (⎤ b+c) vaø b ñöôïc c • Hôïp giaûi (⎤ b+⎤ c) vaø b ñöôïc ⎤ c • Hôïp giaûi c vaø ⎤ c ñöôïc caâu roãng. Meänh ñeà ñöôïc chöùng minh Minh hoïa baèng caáu truùc caây
Minh hoïa baèng danh saùch (c) Moät soá chieán löôïc hôïp giaûi Trong suoát quaù trình hôïp giaûi, khi vaãn phaûi ñeå laïi caùc caâu tieàn boái trong S thì söï buøng noå toå hôïp laø keát quaû taát yeáu. Chuùng ta caàn khaûo saùt caùc nguyeân taéc hay caùc chieán löôïc hôïp giaûi ñeå quaù trình ñöôïc thöïc hieän nhanh hôn. AÙp duïng caùc chieán löôïc naøy coù theå phaûi hy sinh ñeán tính ñaày ñuû nghóa laø baûo ñaûm hoaøn taát chöùng minh neáu baøi toaùn laø ñuùng. 1. Chieán löôïc ñôn vò: Moät trong caùc meänh ñeà tieàn boái laø meänh ñeà taàm
thöôøng. 2. Chieán löôïc input: Moät trong caùc meänh ñeà laø giaû thieát hoaëc phuû ñònh cuûa keát luaän. 3. Chieán löôïc choáng ñôõ: Moät trong caùc meänh ñeà tieàn boái laø keát quaû hoaëc daãn xuaát cuûa keát quaû. Chieán löôïc naøy duøng suy dieãn luøi vaø khoâng ñaët keát quaû vaøo taäp khôûi taïo. 4. Chieán löôïc tuyeán tính: Moät trong caùc meänh ñeà tieàn boái laø keát quaû hôïp giaûi tröôùc ñoù, vaø meänh ñeà coøn laïi hoaëc laø tieàn boái cuûa caùi thöù nhaát hoaëc laø meänh ñeà input. Caùc chieán löôïc 1 vaø 2 laø khoâng ñaày ñuû; caùc chieán löôïc 3 vaø 4 laø ñaày ñuû, ngoaøi ra chieán löôïc 4 ñöôïc coi laø khaù hieäu quaû. Ví duï 5.12 Laøm laïi ví duï 2.21 duøng chieán löôïc choáng ñôõ
3. Suy luaän vôùi logic caáp 1 3.1. Khaùi nieäm Ñònh nghóa 5.5 • Vò töø caáp n laø moät phaùt bieåu chöùa n bieán xi (i=1 n) sao cho khi xi nhaän caùc giaù trò cuï theå thì noù trôû thaønh meänh ñeà • Moät trong hai löôïng töø ∃ (toàn taïi) vaø ∀ (vôùi moïi) ñaët tröôùc vò töø laøm giaûm caáp cuûa noù 1 ñôn vò Ví duï 5.13 • (x + y > 2) laø moät vò töø caáp 2 • (∀x) (x + y > 2) laø moät vò töø caáp 1 • (∀x) (∃y) (x + y > 2) laø moät meänh ñeà (coù chaân trò ñuùng neáu x, y laø caùc soá nguyeân chaúng haïn) Nhö vaäy töø moät vò töø caáp 2 chuùng ta seõ coù hai vò töø caáp 1 vaø boán meänh ñeà. Tuy nhieân, neáu xem taát caû caùc bieán laø moät bieán duy nhaát x = (x1, x2, , xn) thì vôùi vò töø P(x) ta seõ coù duy nhaát hai meänh ñeà daïng ∀x P(x) vaø ∃x P(x). Chaúng haïn xem (x, y) laø moät bieán, khi aáy coù theå coi vò töø (x + y > 2) laø moät vò töø caáp 1, do ñoù chuùng ta seõ coù hai meänh ñeà laø ∀(x,y) (x + y > 2) vaø ∃(x,y) (x + y > 2). Lónh vöïc logic lieân quan ñeán caùc vò töø nhöng chæ laøm vieäc vôùi caùc meänh ñeà daïng caáp 1 nhö vaäy ñöôïc goïi laø logic caáp 1. Thuaät toaùn sau ngoaøi vieäc ñöa ra danh saùch caùc caâu, noù ñöa caùc caâu, moãi caâu laø moät meänh ñeà, thaønh caùc meänh ñeà hoaëc laø söï kieän thuaàn tuyù hoaëc laø luaät daïng ∀x P(x). Thuaät toaùn ñöa vò töø veà daïng hoäi chuaån taéc 1. Khöû caùc daáu keùo theo vaø töông ñöông 2. Ñöa daáu phuû ñònh vaøo trong cuøng. 3. Thay teân bieán ñeå moãi löôïng töø coù moät teân bieán rieâng 4. Khöû caùc löôïng töø toàn taïi 5. Loaïi boû caùc löôïng töø vôùi moïi
6. Khai trieån vaø ruùt goïn Ví duï 5.14 Ñöa ∀x, (P(x) ⇒ ( ∀y ( P(y) ⇒ P(f(x,y)) ) ∧ ¬∀y (Q(x,y) ⇒ P(y))) veà daïng hoäi chuaån taéc Giaûi • b1: ∀x, (¬P(x) ∨ ( ∀y (¬P(y) V P(f(x,y)) ) ∧ ¬∀y (¬Q(x,y) ∨ P(y))) • b2: ∀x, (¬P(x) ∨ ( ∀y (¬P(y) V P(f(x,y)) ) ∧ ∃y (Q(x,y) ∧ ¬P(y))) • b3: ∀x, (¬P(x) ∨ ( ∀y (¬P(y) V P(f(x,y)) ) ∧ ∃z (Q(x,z) ∧ ¬P(z))) • b4: ∀x, (¬P(x) ∨ ( ∀y (¬P(y) V P(f(x,y)) ) ∧ (Q(x,g(x)) ∧ ¬P(g(x)))) • b5: ¬P(x) ∨ ( (¬P(y) ∨ P(f(x,y)) ) ∧ Q(x,g(x)) ∧ ¬P(g(x)) • b6: ¬P(x) ∨ ¬P(y) ∧ Q(x,g(x)) ∧ ¬P(g(x)) ∨ P(f(x,y)) ∧ Q(x,g(x)) ∧¬P(g(x)) 3.2. Suy luaän Baèng moät pheùp thay theá caùc bieán thích hôïp chuùng ta seõ xaây döïng caùc böôùc suy luaän vaø duøng ví duï sau ñeå minh hoaï. Ví duï 5.15 Cho vò töø P(x, y) vaø luaät P(x, y) ∧ P(y, z) → P(x, z). Töø caùc söï kieän P(a, b), P(b, c) vaø P(c, d), haõy keát luaän veà söï kieän P(a, d) (a) Duøng caây AND/OR Taäp luaät P(X, Z) P(a, b) P(b, c) P(c, d) P(X, Y) P(Y, Z) Caây suy luaän P(a, d) P(a, Y) P(Y, d)
P(a, b) P(a, Y1) P(Y1, Y) P(c, d) P(Y, d) P(d, Z) P(a,b) P(a,Y2) P(Y2,Y) . P(b, c) . . . (b) Duøng hôïp giaûi Tröôùc heát xaây döïng danh saùch caùc caâu (ta duøng caùc kyù hieäu +, * thay cho ∨, ∧): 1. P(x,z) + ¬P(x,y) + ¬P(y,z) 2. P(a, b) 3. P(b, c) 4. P(c, d) 5. ¬P(a, d) Thöïc hieän quaù trình suy luaän baèng hôïp giaûi 6. P(a, z) + ¬P(b, z) thay x = a, y = b hôïp giaûi 1 vaø 2 7. P(a, c) thay z = c, hôïp giaûi 3 vaø 6 8. ¬P(b, d) thay z = d, hôïp giaûi 5 vaø 6 9. P(x, b) + ¬P(x, a) thay y = a, z = b, hôïp giaûi 1 vaø 2 10. P(b, z) + ¬P(c, z) thay x = b, y = c, hôïp giaûi 1 vaø 3 11. P(b, d) thay z = d hôïp giaûi 4 vaø 10 12. Maâu thuaån hôïp giaûi 8 vaø 11 Vaøi ví duï Trong caùc ví duï sau ñaây, chìa khoaù ñeå giaûi caùc baøi toaùn laø ñònh nghóa caùc vò töø cho thích hôïp. Ví duï 5.16 Vôùi baøi toaùn tìm ñöôøng ñi, ta ñònh nghóa hai vò töø 1. P(x, y) : töø x coù ñöôøng ñi tröïc tieáp (road) ñeán y, vaø
2. Q(x, y) : töø x coù ñöôøng ñi (route) ñeán y. Vaø caùc meänh ñeà caàn thieát 1. (∃x) (∃y) (P(x,y)) 2. (∀x) (∀y) (P(x,y) → Q(x,y)) 3. (∀x) (∀y) (∀z) (Q(x,z) ∧ P(z,y) → Q(x,y)) Chaúng haïn vôùi baøi toaùn tìm ñöôøng ñi töø N ñeán L cho trong ví duï 1.1, caùc meänh ñeà ñöôïc cho cuï theå nhö sau 1. P(N, C) 2. P(C, D) 3. P(N, T) 4. P(N, D) 5. P(T, G) 6. P(T, L) 7. P(T, C) 8. P(D, U) 9. P(D, H) 10. P(H, L) 11. P(D, L) 12. ¬P(x, y) + Q(x, y) 13. ¬Q(x, f(x, y)) + ¬P(f(x, y), y) + Q(x, y) 14. ¬Q(N, L) vaø quaù trình hôïp giaûi 15. Q(N, C) thay x = N, y = C hôïp giaûi 1 vaø 12 16. Q(N, D) thay x = N, f(x, y) = C, y = D 2, 13 vaø 15 17. Q(N, L) thay x = N, f(x, y) = D, y = L 11, 13 vaø 16
18. maâu thuaãn 14 vaø 17 Ví duï 5.17 Baøi toaùn con khæ vaø naûi chuoái ñöôïc phaùt bieåu nhö sau: Trong phoøng coù con khæ, chieác gheá vaø naûi chuoái. Naûi chuoái ñöôïc treo treân traàn nhaø. Con khæ coù theå di chuyeån quanh phoøng, coù theå ñaët chieác gheá ôû baát cöù nôi naøo vaø coù theå leo leân gheá. Noù coù theå laáy ñöôïc naûi chuoái chæ khi chieác gheá ñöôïc ñaët tröïc tieáp döôùi naûi chuoái. Laøm theá naøo noù coù theå laáy ñöôïc naûi chuoái? Giaûi: Baøi toaùn coù theå giaûi ñöôïc nhôø caùc vò töø 1. in_room(X) : coù X trong phoøng 2. dexterrous(X) : X laø loaøi kheùo leùo 3. tail(X) : X cao 4. can_climb(X, Y) : X coù theå leo leân Y 5. can_move(X, Y, Z) : X coù theå di chuyeån Y ñeán gaàn Z 6. get_on(X, Y) : X ñöùng treân Y 7. under(X, Y) : X ôû beân döôùi Y 8. close(X, Y) : X gaàn Y 9. can_reach(X,Y) : X coù theå laáy ñöôïc Y Vaø caùc meänh ñeà cuï theå: 1. in_room(bananas) 2. in_room(chair) 3. in_room(monkey) 4. dexterrous(monkey) 5. tail(chair)
6. can_move(monkey, chair, bananas) 7. can_climb(monkey, chair) 8. can_climb(X, Y) ⇒ get_on(X, Y) 9. in_room(X) in_room(Y) in_room(Z) can_move(X, Y, Z) ⇒ under(Y, Z) 10. get_on(X,Y) under(Y,Z) tail(Y) ⇒ close(X,Z) 11. dexterrous(X) close(X,Y) ⇒ can_reach(X,Y) BAØI TAÄP Baøi taäp 5.1 ÔÛ nhaø Teøo laø ñöùa raát vuïng, ñuïng gì hö naáy. Ba Teøo hay ñaùnh ñoøn Teøo moãi khi teøo laøm hö baát kyø moät moùn gì. Moät hoâm ñi hoïc veà, Teøo thaáy ôû nhaø coù moät caùi ly bò vôõ, trong nhaø khoâng coøn ai. Theá laø Teøo khoùc. Hoûi Teøo baûo Teøo sôï ba ñaùnh ñoøn. Haõy chæ ra cô cheá suy dieãn naøo ñöôïc Teøo duøng ñeå suy ra raèng Teøo seõ bò ba ñaùnh ñoøn? Baøi taäp 5.2 Haõy hôïp giaûi baøi toaùn con khæ vaø naûi chuoái Baøi taäp 5.3 Ñöa caùc meänh ñeà sau veà daïng hoäi chuaån taéc vaø tuyeån chuaån taéc 1. (p→ q) → r 2. p → (q → (r + s)) Baøi taäp 5.4 Cho caùc tri thöùc r → s, p → s, q → p + r Chöùng toû q → (p + s) 1. Baèng hôïp giaûi Robinson
2. Baèng caùch tìm kieám treân caây And/Or Baøi taäp 5.5 Cho boä luaät: {fg → x, d → x, ac → f, be → g, ab → d, c → d} 1. Duøng thuaät giaûi Robinson, chöùng minh ac → x. 2. Duøng thuaät giaûi A0* kieåm tra tính giaûi ñöôïc cuûa x, duøng haøm MAX cho nuùt AND vaø haøm MIN cho nuùt OR. Bieát heuristic nhö sau nuùt a b c d e f g x hÂ 0 0 10 4 10 2 2 3 Baøi taäp 5.6 Bieåu dieãn baèng logic vò töø caùc tri thöùc sau: “Lan laø hoïc sinh gioûi”; “Haøng ngaøy, hoïc sinh gioûi luoân ñeán thö vieän”; “Luùc naøo cuõng vaäy, Lan ôû ñaâu laøMinh ôû ñoù”. Baøi taäp 5.7 Ñöa meänh ñeà sau veà daïng chuaån tích cuûa toång 1. (∀x) ( (∀y)( p(x,y) → q(x) ∨ r(y) ) + (∃y)( p(x,y) ∨ r(y) → q(x) ) ) 2. (∀x) (∀y) ( (∃z) ( p(x,z) ∧ (p(y,z) ) ) → ( (∃u) (q(x,y,u)) ) 3. (∀x) { ( ∃y, p(x,y) → q(x) ∨ r(y)) → (∀y)(∃z) ( s(x,y,z) → r(x) ∨ p(y,z) ) ) } Baøi taäp 5.8 Cho 3 vò töø p(x,y), q(x,y), r(x,y), s(x,y) vaø caùc quy taéc sau (∀x) (∀y) (∀z) ( q(x,y) ∧ r(y,z) → p(x,z) ) (∀x) (∀y) (∀z) ( s(x,y) ∧ p(y,z) → p(x,z) ) Xeùt baøi toaùn: Chöùng minh q(a,b) ∧ s(c,a) ∧ r(b,d) → p(c,d) 1. Xaây döïng danh saùch caùc caâu cho thuaät giaûi Robinson 2. Baèng thuaät giaûi Robinson giaûi baøi toaùn chöùng minh treân Baøi taäp 5.9 Cho cô sôû tri thöùc sau
• Neáu x naèm treân y ta noùi y ñôõ x. • Neáu x ôû treân y vaø chuùng tieáp xuùc nhau, ta noùi x naèm treân y. • x vaø y tieáp xuùc nhau neáu x tieáp xuùc vôùi y hoaëc y tieáp xuùc vôùi x • Coù moät caùi taùch cup ôû treân caùi baøn table • Taùch cup tieáp xuùc vôùi baøn table Coi caùc vò töø on_top(x,y) laø x naèm treân y, support(x,y) laø x ñôõ y, above(x,y) laø x ôû treân y, touch(x,y) laø x tieáp xuùc vôùi y. 1. Haõy bieåu dieãn cô sôû tri thöùc treân qua caùc vò töø ñaõ cho. 2. Baèng hôïp giaûi Robinson chöùng toû raèng caùi baøn table ñôõ chieác taùch cup. Baøi taäp 5.10 Cho caùc vò töø P(x), Q(x), R(x,y), S(x) Bieát caùc söï kieän S(a) P(b) R(a,b) vaø caùc luaät (∀x)( P(x) → Q(x) ) (∀x) (∀y) ( R(x,y) ∧ Q(y) → Q(x) ) Baèng phöông phaùp hôïp giaûi Robinson chöùng minh meänh ñeà sau ∃x, Q(x) ∧ S(x)
Chöông 6 Suy luaän vôùi thoâng tin khoâng chaéc chaén Chöông naøy cung caáp cho chuùng ta moät soá moâ hình ñeå laøm vieäc vôùi thoâng tin khoâng chaéc chaén. Moãi moâ hình, chuùng ta seõ khaûo saùt moät soá khaùi nieäm chuû yeáu, ñuû cho baøi toaùn suy luaän. Theo ñoù, vôùi nhieàu söï kieän lieân quan vôùi nhau, laøm sao keát luaän ñöôïc moät söï kieän ñang quan taâm laø coù xaûy ra hay khoâng döïa vaøo caùc söï kieän ñaõ bieát vôùi moät khaû naêng xaûy ra cho tröôùc. 1. Phaân boá xaùc suaát 1.1. Khaùi nieäm Caùc söï kieän ôû ñaây ñöôïc goïi laø caùc bieán coá, laø keát quaû cuûa caùc pheùp thöû (hay quan saùt) naøo ñoù. Moät bieán coá khoâng theå xaûy ra ñöôïc goïi laø bieán coá roãng ∅, moät bieán coá luoân xaûy ra ñöôïc goïi laø bieán coá chaéc chaén Ω, caùc bieán coá khaùc ñöôïc goïi laø bieán coá ngaãu nhieân. Hai bieán coá laø xung khaéc neáu chuùng khoâng theå cuøng ñoàng thôøi xaûy ra; laø ñoäc laäp neáu vieäc xaûy ra bieán coá naøy khoâng aûnh höôûng ñeán vieäc xaûy ra cuûa bieán coá kia. Bieán coá A ñöôïc goïi laø keùo theo B neáu A xaûy ra thì B phaûi xaûy ra. Moät hoï caùc bieán coá ñöôïc goïi laø moät phaân hoaïch ñaày ñuû neáu chuùng ñoâi moät xung khaéc vaø keát quaû cuûa pheùp thöû baát kyø seõ coù ñuùng moät trong chuùng xaûy ra. Ví duï 6.1 Tung con xuùc saéc (pheùp thöû). Goïi A laø bieán coá xuaát hieän soá chaün; B laø bieán coá xuaát hieän soá leû; C laø bieán coá xuaát hieän soá 2; D laø bieán coá xuaát hieän soá 0; E laø bieán coá xuaát hieän soá lôùn hôn 0; Ta coù: 1 D laø bieán coá roãng; 2 E laø bieán coá chaéc chaén; 3 A, B, C laø caùc bieán coá ngaãu nhieân; 4 B vaø C xung khaéc;
5 A vaø C khoâng xung khaéc, hôn nöõa C keùo theo A; 6 Caùc bieán coá treân laø ñoäc laäp; 7 {A, B} laø moät phaân hoaïch ñaày ñuû. Cho bieán coá A, bieán coá phuû ñònh cuûa A, kyù hieäu laø ¬A, xaûy ra khi A khoâng xaûy ra vaø ngöôïc laïi. Cho hai bieán coá A vaø B, bieán coá toång, kyù hieäu laø A + B, xaûy ra khi ít nhaát moät trong chuùng xaûy ra; bieán coá tích, kyù hieäu laø AB, xaûy ra khi caû hai cuøng xaûy ra. Moät ñoä ño xaùc suaát P treân bieán coá nhaän giaù trò trong khoaûng [0, 1] thoûa 1. 0 ≤ P(A) ≤ 1; P(∅) = 0; P(Ω) = 1; 2. P(¬A) = 1 – P(A); P(A + B) = P(A) + P(B) – P(AB) ñaëc bieät P(A + B) = P(A) + P(B) khi A, B xung khaéc, khi aáy P(AB) = 0; P(AB) = P(A)P(B) khi A, B ñoäc laäp. Xaùc suaát P(A) ño khaû naêng xaûy ra bieán coá A döôùi moät ñieàu kieän xaùc ñònh naøo ñoù. Trong tröôøng hôïp nhaán maïnh ñeán ñieàu kieän D, cuõng laø moät bieán coá, chuùng ta coù khaùi nieäm xaùc suaát coù ñieàu kieän, kyù hieäu laø P(A|D) ñoïc laø xaùc suaát xaûy ra A vôùi ñieàu kieän D ñaõ xaûy ra. 3. P(A|B) = P(AB)/P(B) Ta coù moät soá coâng thöùc quan troïng 1. P(AB) = P(A|B)P(B) = P(B|A)P(A); 2. Vôùi {Ai} laø moät phaân hoaïch ñaày ñuû, P(B) = Σ P(B|Ai)P(Ai); P(Ak|B) = P(B|Ak)P(Ak)/ Σ P(B|Ai)P(Ai). Ví duï 6.2 Xeùt 10 laàn thöû (hay quan saùt) vaø ghi laïi nhöõng laàn xaûy ra caùc bieán coá A, B,
C vaø D (xem trang sau) Ta coù: P(A) = 6/10 = 0.6; P(¬A) = 4/10 = 0.4; hoaëc P(¬A) = 1 – P(A) = 0.4 P(AB) = 0.4; P(B|A) = 2/3; hoaëc P(B|A) = P(AB) / P(A) = 0.4/0.6 = 2/3; P(A+B) = 0.8; hoaëc P(A+B) = P(A) + P(B) – P(AB) = 0.6 + 0.6 – 0,4 = 0.8; P(B) = 0.6; hoaëc P(B) = P(B|A)P(A)+P(B|¬A)P(¬A)=4/6×0.6+2/4×0.4 = 0.6 A B C D 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1.2. Suy luaän Nhaéc laïi coâng thöùc ñaày ñuû P(Ai) ai P(B|Ai) bi
∴P(B) Σbiai Ví duï 6.3 Cho luaät A B (0.8; 0.1) vaø bieát xaùc suaát xaûy ra A laø P(A) = 0.3. Tính xaùc suaát: 1 Xaûy ra söï kieän: P(B) = 0.8*0.3+ 0.1*0.7 = 0.31 2 Phaùt sinh luaät môùi P(A⏐B) = 0.8*0.3/0.31 = 0.77 vaø P(A⏐¬B) = 0.2*0.3/0.69 = 0.09 Ñaëc bieät, tính xaùc suaát haäu nghieäm: B xaûy ra, tính A; töùc P(A⏐B) = 0.77 Ví duï 6.4 Cho luaät AB → C vôùi phaân boá (0.95, 0.94, 0.29, 0.001), ñöôïc hieåu laø P(AB → C) = 0.95, P(A¬B → C) = 0.94, P(¬AB → C) = 0.29 vaø P(¬A¬B → C) = 0.001. Giaû söû bieát caùc söï kieän A vaø B vôùi xaùc suaát 0.2 vaø 0.4 töông öùng. C A (0.95, 0.94, 0.29, 0.001) B 0.2 0.4 Ta coù xaùc suaát 3 Xaûy ra söï kieän: P(C) = P(C⏐AB) P(A) P(B) + P(C⏐A¬B) P(A) P(¬B) + P(C⏐¬AB) P(¬A) P(B) + P(C⏐¬A¬B) P(¬A) P(¬B) = 0.95×0.2×0.4 + 0.94×0.2×0.6 + 0.29×0.8×0.4 + 0.001×0.8×0.6
= 0.076 + 0.1128 + 0.0928 + 0.00048 = 0.28208 P(BC) = P(BCA) + P(BC¬A) = P(C|AB) P(A) P(B) + P(C⏐¬AB) P(¬A) P(B) = 0.95×0.2×0.4 + 0.29×0.8×0.4 = 0.076 + 0.0928 = 0.1688 4 Phaùt sinh luaät môùi P(B⏐C) = P(BC) / P(C) = 0.1688 / 0.28208 ≈ 0.6 cuõng chính laø xaùc suaát haäu nghieäm cuûa B sau khi C xaûy ra. Bieåu dieãn baèng caây suy luaän Gioáng nhö ví duï treân, trong bieåu dieãn naøy, chuùng ta thöøa nhaän söï ñoäc laäp giöõa caùc söï kieän khi khoâng cung caáp moái lieân quan giöõa chuùng. Ví duï 6.5 Cho taäp luaät BE → A vôùi phaân boá xaùc suaát (0.8, 0.9, 0.2, 0.1) A → M (0.7, 0.2) A → J (0.9, 0.1) Töø caùc söï kieän P(B) = 0.1, P(E) = 0.2, haõy tính P(J → B) Giaûi: Ta phaûi tính P(J) vaø P(JP) Tính P(J) J (0.2568) (0.9, 0.1) A (0.196) (0.8, 0.9, 0.2, 0.1) B(0.1) E(0.2) ÔÛ ñaây taïi A, P(A) = 0.8×0.1×0.2 + 0.9×0.1×0.8 + 0.2×0.9×0.2 + 0.1×0.9×0.8
= 0.016 + 0.072 + 0.036 + 0.072 = 0.196 taïi J, P(J) = 0.9×0.196 + 0.1×(1 – 0.196) = 0.2568 Tính P(JB) J (0.0804) (0.9, 0.1) A (0.088) (0.8, 0.9, 0.2, 0.1) B(0.1) E(0.2) ÔÛ ñaây taïi A, tính P(AB) = 0.8×0.1×0.2 + 0.9×0.1×0.8 = 0.016 + 0.072 = 0.088 taïi J, tính P(JB) = 0.9×0.088 + 0.1×(0.1 – 0.088) = 0.0804 Vaäy P(J → B) = P(JB) / P(J) = 0.0804 / 0.2568 ≈ 0.31 2. Suy luaän xaáp xæ 2.1. Khaùi nieäm Trong thöïc teá ñeå tính chính xaùc xaùc suaát cuûa moät bieán coá laø raát khoù. Thay vaøo ñoù ta duøng moät haøm öôùc löôïng. Chaúng haïn vôùi öôùc löôïng p(.) ≥ p, ta coù p(α) ≥ a p(β) ≤ a p(α → β) ≥ b p(α → β) ≥ b ∴p(β) ≥ max(0, a+b-1) ∴p(α) ≤ min(1, 1 – b + a) Baây giôø chuùng ta seõ ñöa ra 2 haøm öôùc löôïng veà caû hai phía cuûa xaùc suaát p. Xeùt hoï P caùc meänh ñeà vaø aùnh xaï m: P →[0,1] thoûa Σm(p) = 1, toång tính treân taát caû p thuoäc P. Ta ñònh nghóa hai haøm öôùc löôïng xaùc suaát p nhö sau: Ñònh nghóa 6.1 • Haøm caän döôùi hay ñoä thoûa ñaùng (Credible): Cr(p)= Σm(q), ∀q∈P, q→ p
• Caän treân hay ñoä ñaùng tin (Plausible): Pl(p) = 1 – Cr(p) Ñeå suy luaän ta caàn ñònh nghóa hai haøm Cr vaø Pl ñaëc bieät Ñònh nghóa 6.2 • Ñoä nhaát thieát Nec laø moät ñoä thoûa ñaùng Cr thoûa Nec(p q) = min (Nec(p), Nec(q)) • Ñoä coù theå Pos laø moät ñoä ñaùng tin Pl thoûa Pos(p + q) = max (Pos(p), Pos(q)) Ñònh lyù 6.1 1. Nec(p) + Nec(¬p) ≤ 1 2. Pos(p) + Pos(¬p) ≥ 1 3. Nec(p) ≤ Pos(p) 4. Nec(p) = 1 - Pos(p) 5. min (Nec(p), Nec(¬p)) = 0 6. max (Pos(p), Pos(¬p)) = 1 7. Pos(p) 0 → Pos(p) = 1 Cuøng vôùi chuùng laø söï môû roäng caùc suy dieãn Ñònh lyù 6.2 Vôùi Nec Nec(α) ≥ a Nec(α → β) ≥ b ∴Nec(β) ≥ min(a, b) Nec(β) ≤ a Nec(α → β) ≥ b
∴Nec(α) ≤ 1 (b ≤ a) ≤ a (b > a) Vôùi Nec vaø Pos Pos(α) ≥ a Nec(α → β) ≥ b ∴Pos(β) ≥ 0 (a+b ≤ 1) ≥ a (a+b > 1) Nec(α) ≥ a Pos(α → β) ≥ b ∴Pos(β) ≥ 0 (a+b ≤ 1) ≥ b (a+b > 1) Pos(β) ≤ a Nec(α → β) ≥ b ∴Pos(α) ≤ max (1 – b, a) 2.2. Suy luaän Ñònh nghóa 6.3 Hieäu Nec – Pos ñöôïc goïi laø ñoä chaéc chaén, kyù hieäu laø CF, nhaän giaù trò töø –1 (chaéc chaén khoâng xaûy ra) ñeán 1 (chaéc chaén xaûy ra). Trong thöïc teá, khi keát luaän veà moät söï kieän chuùng ta ñeàu coù muïc ñích. Ví duï ñeå khaúng ñònh söï kieän xaûy ra chuùng ta coá tìm nhöõng chöùng cöù laøm taêng CF. Ñònh lyù 6.3 1. CF(¬p) = – CF(p) 2. CF(pq) = Min(CF(p), CF(q)) 3. CF(p + q) = Max(CF(p), CF(q))
Suy luaän vôùi CF duøng caây AND/OR môû roäng ÔÛ ñaây chuùng toâi giôùi thieäu moät ñoä ño CF ñôn giaûn: Nuùt AND duøng Min; nuùt OR duøng Max; coøn nuùt toå hôïp duøng coâng thöùc sau ⎧ ⎪ C1 + C2 − C1C2 C1,C2 > 0 ⎪ C = ⎨C1 + C2 + C1C2 C1,C2 ≤ 0 ⎪ C1+ C2 ⎪ C × C ≤ 0 ⎪1− Min(C , C ) 1 2 ⎩ 1 2 Ví duï 6.6 Cho boä luaät, vôùi caùc soá trong caëp daáu ngoaëc laø ñoä CF töông öùng: e1 + e2 → a (0.5) e3 → f (0.5) e3 e4 → b (0.8) c + e4 → f (0.7) e1 e3 → c (0.9) d e4 → h (1.0) e2 + e4 → g (0.9) e → z (1.0) e1 + e3 → d (1.0) ¬f → z (0.8) a b → e (0.5) g h → z (0.7) Bieát CF cuûa e1, e2, e3 vaø e4 thöù töï laø 0.7, 0.8, 0.6 vaø 1.0, tính CF(f). Veõ caây suy luaän: f (0.79) e3 c (0.54) e4 e1 e3 Tính CF(c) = Min(0.6, 0.7)*0.9 = 0.54; CF(f) töø e3 = 0.6*0.5 = 0.3; töø c vaø e4 = Max(1.0, 0.54)*0.7 = 0.7; suy ra CF(f) = 0.3 + 0.7 – 0.3*0.7 = 0.79
3. Giôùi thieäu moät soá suy luaän khaùc 3.1. Phaân boá khaû xuaát Trong thöïc teá, coù raát nhieàu söï kieän ñöôïc phaùt bieåu moät caùch ñaïi khaùi. Chaúng haïn, ta vaãn thöôøng gaëp caùc thuaät ngöõ nhö “Ña soá”, “noùi chung” thay vì moät giaù trò baèng soá. Caùc khaùi nieäm khoâng chính xaùc nhö vaäy ñöôïc goïi laø caùc khaùi luaät. Chuùng khoâng döïa treân phaân boá xaùc suaát maø ñöôïc ñaët cô sôû treân moät phaân boá khaùc: phaân boá khaû xuaát. Ñònh nghóa 6.4 Haøm π : P → [0,1] ñöôïc goïi laø moät phaân boá khaû xuaát neáu thoûa 1. max(π(p), π(¬p)) = 1. 2. π(p + q) = min(π(p), π(q)) 3. π(pq) = max(π(p), π(q)) Ñònh nghóa 6.5 1. Veùc tô (π(p), π(¬p))T laø phaân boá (khaû xuaát) cuûa p theo π. 2. Ma traän laø phaân boá (khaû xuaát) cuûa (khaùi luaät) p→ q theo π. ⎛ π (q) ⎞ ⎛ π ( p → q) π (¬p → q) ⎞⎛ π ( p) ⎞ ⎜ ⎟ = ⎜ ⎟⎜ ⎟ ⎜π (¬q)⎟ ⎜π ( p → ¬q) π (¬p → ¬q)⎟⎜π (¬p)⎟ Ta coù ⎝ ⎠ ⎝ ⎠⎝ ⎠ Roõ raøng logic laø tröôøng hôïp rieâng cuûa phaân boá khaû xuaát khi aáy phaân boá cuûa p coù daïng (1, 0)T hoaëc (0, 1)T. Ví duï 6.7 Cho caùc daïng luaät vaø khaùi luaät (coù daáu !) sau • Neáu Baûo ñeán thì noùi chung Mai ñeán (B→M)! • Baûo ñeán (B) Haõy cho bieát phaân boá khaû xuaát cuûa söï kieän Mai ñeán?