Giáo trình Trí tuệ nhân tạo (Phần 1)

Nội dung text: Giáo trình Trí tuệ nhân tạo (Phần 1)

1. Giáo trình Trí tuệ nhân tạo 1
2. Lời nói đầu Trí tuệ nhân tạo (hay AI: Artificial Intelligence), là nỗ lực tìm hiểu những yếu tố trí tuệ. Lý do khác để nghiên cứu lĩnh vực này là cách để ta tự tìm hiểu bản thân chúng ta. Không giống triết học và tâm lý học, hai khoa học liên quan đến trí tuệ, còn AI cố gắng thiết lập các các yếu tố trí tuệ cũng như tìm biết về chúng. Lý do khác để nghiên cứu AI là để tạo ra các thực thể thông minh giúp ích cho chúng ta. AI có nhiều sản phẩm quan trọng và đáng lưu ý, thậm chí ngay từ lúc sản phẩm mới được hình thành. Mặc dù không dự báo được tương lai, nhưng rõ ràng máy tính điện tử với độ thông minh nhất định đã có ảnh hưởng lớn tới cuộc sống ngày nay và tương lai phát triển của văn minh nhân loại. Tài liệu gồm các phần sau: - Phần 1 : Tri thức và lập luận - Phần 2 : Giải quyết vấn đề bằng tìm kiếm - Phần 3 : Tiếp cận ký hiệu Còn nhiều vấn đề khác chưa đề cập được trong phạm vi tài liệu này. Đề nghị các bạn đọc tìm hiểu thêm sau khi đã có những kiến thức cơ bản này. 2
3. Môc lôc PhÇn I 6 Tri thøc vμ lËp luËn 6 Ch−¬ng I 7 Logic mÖnh ®Ò 7 I. BiÓu diÔn tri thøc 7 II. Có ph¸p vμ ng÷ nghÜa cña logic mÖnh ®Ò 8 II.1 Có ph¸p 8 II.2 Ng÷ nghÜa 9 III. D¹ng chuÈn t¾c 11 IV. LuËt suy diÔn 13 V. LuËt gi¶i, chøng minh b¸c bá b»ng luËt gi¶i 16 VI. Bμi tËp 18 Ch−¬ng II 21 LOGIC VÞ Tõ CÊP MéT 21 I. Có ph¸p 21 II. Ng÷ nghÜa 23 III. Bμi tËp 25 PhÇn II 28 Gi¶i quyÕt vÊn ®Ò b»ng t×m kiÕm 28 Ch−¬ng III 29 C¸c chiÕn l−îc t×m kiÕm mï 29 I. BiÓu diÔn vÊn ®Ò trong kh«ng gian tr¹ng th¸i 29 II. C¸c chiÕn l−îc t×m kiÕm 31 III. C¸c chiÕn l−îc t×m kiÕm mï 33 III.1 T×m kiÕm theo bÒ réng 33 III.2 T×m kiÕm theo ®é s©u 35 III.3 C¸c tr¹ng th¸i lÆp 36 III.4 T×m kiÕm s©u lÆp 36 IV. Quy vÊn ®Ò vÒ c¸c vÊn ®Ò con 38 V. ®å thÞ 40 VI. Bμi tËp 44 Ch−¬ng IV 45 C¸c chiÕn l−îc t×m kiÕm kinh nghiÖm 45 I. Hμm ®¸nh gi¸ vμ t×m kiÕm kinh nghiÖm 45 II. T×m kiÕm tèt nhÊt - ®Çu tiªn 46 III. T×m kiÕm leo ®åi 48 IV. T×m kiÕm beam 49 V. Bμi tËp 50 Ch−¬ng V 51 C¸c chiÕn l−îc t×m kiÕm tèi −u 51 I. T×m ®−êng ®i ng¾n nhÊt 51 3
4. I.1 ThuËt to¸n A* 52 I.2 ThuËt to¸n t×m kiÕm nh¸nh-vμ-cËn 54 II. T×m ®èi t−îng tèt nhÊt 56 II.1 T×m kiÕm leo ®åi 57 II.2 T×m kiÕm gradient 58 II.3 T×m kiÕm m« pháng luyÖn kim 58 III. T×m kiÕm m« pháng sù tiÕn hãa. ThuËt to¸n di truyÒn 59 IV. Bμi tËp 63 Ch−¬ng VI 65 T×m kiÕm cã ®èi thñ 65 I. C©y trß ch¬i vμ t×m kiÕm trªn c©y trß ch¬i 65 II. Ph−¬ng ph¸p c¾t côt alpha - beta 71 III. Bμi tËp 73 PhÇn III 75 HỌC MÁY (MACHINE LEARNING) 75 Chương VII 77 TIẾP CẬN KÝ HIỆU: 77 GIẢI THUẬT QUY NẠP CÂY QUYẾT ĐỊNH ID3 77 I. Giới thiệu 77 II. Giải thuật ID3 xây dựng cây quyết định từ trên–xuống 80 III. Thuộc tính nào là thuộc tính dùng để phân loại tốt nhất? 82 III.1 Entropy đo tính thuần nhất của tập ví dụ 82 III.2 Lượng thông tin thu được đo mức độ giảm entropy mong đợi 84 IV. Tìm kiếm không gian giả thuyết trong ID3 84 V. Đánh giá hiệu suất của cây quyết định 85 VI. Chuyển cây về các luật 86 VII. Khi nào nên sử dụng ID3 86 Chương VIII 88 TIẾP CẬN KẾT NỐI: MẠNG NEURON 88 I. Giới thiệu 88 II. Cơ bản về mạng kết nối 89 II.1 Một neuron nhân tạo 89 II.2 Các đặc trưng của một mạng Neuron 89 II.3 Mạng neuron McCulloch-Pitts 90 III. Học perceptron 91 III.1 Giải thuật học perceptron 91 III.2 Sử dụng mạng perceptron cho bài toán phân loại 92 III.3 Giới hạn của perceptron – tính tách rời tuyến tính của bài toán 95 III.4 Luật Delta 96 IV. Học Lan truyền ngược 98 IV.1 Giải thuật học lan truyền ngược 98 IV.2 Ví dụ 1: Mạng NetTalk 99 IV.3 Ví dụ 2: Exclusive–or 100 V. Nhận xét chung về mạng neuron 101 Chương IX 102 4
5. TIẾP CẬN XÃ HỘI VÀ NỔI TRỘI: GIẢI THUẬT DI TRUYỀN (GENETIC ALGORITHM - GA) 102 I. Giải thuật 102 II Ví dụ 1: Bài toán thỏa CNF 104 III. Ví dụ 2: Bài toán người đi bán hàng TSP 105 IV. Đánh giá giải thuật 107 Bài tập 109 Tài liệu tham khảo 111 5
6. PhÇn I Tri thøc vμ lËp luËn 6
7. Ch−¬ng I Logic mÖnh ®Ò Trong ch−¬ng nμy chóng ta sÏ tr×nh bμy c¸c ®Æc tr−ng cña ng«n ng÷ biÓu diÔn tri thøc. Chóng ta sÏ nghiªn cøu logic mÖnh ®Ò, mét ng«n ng÷ biÓu diÔn tri thøc rÊt ®¬n gi¶n, cã kh¶ n¨ng biÓu diÔn hÑp, nh−ng thuËn lîi cho ta lμm quen víi nhiÒu kh¸i niÖm quan träng trong logic, ®Æc biÖt trong logic vÞ tõ cÊp mét sÏ ®−îc nghiªn cøu trong c¸c ch−¬ng sau. I. BiÓu diÔn tri thøc Con ng−êi sèng trong m«i tr−êng cã thÓ nhËn thøc ®−îc thÕ giíi nhê c¸c gi¸c quan (tai, m¾t vμ c¸c bé phËn kh¸c), sö dông c¸c tri thøc tÝch luü ®−îc vμ nhê kh¶ n¨ng lËp luËn, suy diÔn, con ng−êi cã thÓ ®−a ra c¸c hμnh ®éng hîp lý cho c«ng viÖc mμ con ng−êi ®ang lμm. Mét môc tiªu cña TrÝ tuÖ nh©n t¹o øng dông lμ thiÕt kÕ c¸c t¸c nh©n th«ng minh (intelligent agent) còng cã kh¶ n¨ng ®ã nh− con ng−êi. Chóng ta cã thÓ hiÓu t¸c nh©n th«ng minh lμ bÊt cø c¸i g× cã thÓ nhËn thøc ®−îc m«i tr−êng th«ng qua c¸c bé c¶m nhËn (sensors) vμ ®−a ra hμnh ®éng hîp lý ®¸p øng l¹i m«i tr−êng th«ng qua bé phËn hμnh ®éng (effectors). C¸c robots, c¸c softbot (software robot), c¸c hÖ chuyªn gia, lμ c¸c vÝ dô vÒ t¸c nh©n th«ng minh. C¸c t¸c nh©n th«ng minh cÇn ph¶i cã tri thøc vÒ thÕ giíi hiÖn thùc míi cã thÓ ®−a ra c¸c quyÕt ®Þnh ®óng ®¾n. Thμnh phÇn trung t©m cña c¸c t¸c nh©n dùa trªn tri thøc (knowledge-based agent), cßn ®−îc gäi lμ hÖ dùa trªn tri thøc (knowledge-based system) hoÆc ®¬n gi¶n lμ hÖ tri thøc, lμ c¬ së tri thøc. C¬ së tri thøc (CSTT) lμ mét tËp hîp c¸c tri thøc ®−îc biÓu diÔn d−íi d¹ng nμo ®ã. Mçi khi nhËn ®−îc c¸c th«ng tin ®−a vμo, t¸c nh©n cÇn cã kh¶ n¨ng suy diÔn ®Ó ®−a ra c¸c c©u tr¶ lêi, c¸c hμnh ®éng hîp lý, ®óng ®¾n. NhiÖm vô nμy ®−îc thùc hiÖn bëi bé suy diÔn. Bé suy diÔn lμ thμnh phÇn c¬ b¶n kh¸c cña c¸c hÖ tri thøc. Nh− vËy hÖ tri thøc b¶o tr× mét CSTT vμ ®−îc trang bÞ mét thñ tôc suy diÔn. Mçi khi tiÕp nhËn ®−îc c¸c sù kiÖn tõ m«i tr−êng, thñ tôc suy diÔn thùc hiÖn qu¸ tr×nh liªn kÕt c¸c sù kiÖn víi c¸c tri thøc trong CSTT ®Ó rót ra c¸c c©u tr¶ lêi, hoÆc c¸c hμnh ®éng hîp lý mμ t¸c nh©n cÇn thùc hiÖn. §−¬ng nhiªn lμ, khi ta thiÕt kÕ mét t¸c nh©n gi¶i quyÕt mét vÊn ®Ò nμo ®ã th× CSTT sÏ chøa c¸c tri thøc vÒ miÒn ®èi t−îng cô thÓ ®ã. §Ó m¸y tÝnh cã thÓ sö dông ®−îc tri thøc, cã thÓ xö lý tri thøc, chóng ta cÇn biÓu diÔn tri thøc d−íi d¹ng thuËn tiÖn cho m¸y tÝnh. §ã lμ môc tiªu cña biÓu diÔn tri thøc. Tri thøc ®−îc m« t¶ d−íi d¹ng c¸c c©u trong ng«n ng÷ biÓu diÔn tri thøc. Mçi c©u cã thÓ xem nh− sù m· hãa cña mét sù hiÓu biÕt cña chóng ta vÒ thÕ giíi hiÖn thùc. Ng«n ng÷ biÓu diÔn tri thøc (còng nh− mäi ng«n ng÷ h×nh thøc kh¸c) gåm hai thμnh phÇn c¬ b¶n lμ có ph¸p vμ ng÷ nghÜa. • Có ph¸p cña mét ng«n ng÷ bao gåm c¸c ký hiÖu vÒ c¸c quy t¾c liªn kÕt c¸c ký hiÖu (c¸c luËt có ph¸p) ®Ó t¹o thμnh c¸c c©u (c«ng thøc) trong ng«n ng÷. C¸c c©u ë ®©y lμ biÓu diÔn ngoμi, cÇn ph©n biÖt víi biÓu diÔn bªn trong m¸y tÝnh. C¸c c©u sÏ ®−îc chuyÓn thμnh c¸c cÊu tróc d÷ liÖu thÝch hîp ®−îc cμi ®Æt trong mét vïng nhí nμo ®ã 7
8. cña m¸y tÝnh, ®ã lμ biÓu diÔn bªn trong. B¶n th©n c¸c c©u ch−a chøa ®ùng mét néi dung nμo c¶, ch−a mang mét ý nghÜa nμo c¶. • Ng÷ nghÜa cña ng«n ng÷ cho phÐp ta x¸c ®Þnh ý nghÜa cña c¸c c©u trong mét miÒn nμo ®ã cña thÕ giíi hiÖn thùc. Ch¼ng h¹n, trong ng«n ng÷ c¸c biÓu thøc sè häc, d·y ký hiÖu (x+y)*z lμ mét c©u viÕt ®óng có ph¸p. Ng÷ nghÜa cña ng«n ng÷ nμy cho phÐp ta hiÓu r»ng, nÕu x, y, z, øng víi c¸c sè nguyªn, ký hiÖu + øng víi phÐp to¸n céng, cßn * øng víi phÐp chia, th× biÓu thøc (x+y)*z biÓu diÔn qu¸ tr×nh tÝnh to¸n: lÊy sè nguyªn x céng víi sè nguyªn y, kÕt qu¶ ®−îc nh©n víi sè nguyªn z. • Ngoμi hai thμnh phÇn có ph¸p vμ ng÷ nghÜa, ng«n ng÷ biÓu diÔn tri thøc cÇn ®−îc cung cÊp c¬ chÕ suy diÔn. Mét luËt suy diÔn (rule of inference) cho phÐp ta suy ra mét c«ng thøc tõ mét tËp nμo ®ã c¸c c«ng thøc. Ch¼ng h¹n, trong logic mÖnh ®Ò, luËt modus ponens tõ hai c«ng thøc A vμ A⇒ B suy ra c«ng thøc B. Chóng ta sÏ hiÓu lËp luËn hoÆc suy diÔn lμ mét qu¸ tr×nh ¸p dông c¸c luËt suy diÔn ®Ó tõ c¸c tri thøc trong c¬ së tri thøc vμ c¸c sù kiÖn ta nhËn ®−îc c¸c tri thøc míi. Nh− vËy chóng ta x¸c ®Þnh: Ng«n ng÷ biÓu diÔn tri thøc = Có ph¸p + Ng÷ nghÜa + C¬ chÕ suy diÔn. Mét ng«n ng÷ biÓu diÔn tri thøc tèt cÇn ph¶i cã kh¶ n¨ng biÓu diÔn réng, tøc lμ cã thÓ m« t¶ ®−îc mäi ®iÒu mμ chóng ta muèn nãi. Nã cÇn ph¶i hiÖu qu¶ theo nghÜa lμ, ®Ó ®i tíi c¸c kÕt luËn, thñ tôc suy diÔn ®ßi hái Ýt thêi gian tÝnh to¸n vμ Ýt kh«ng gian nhí. Ng−êi ta còng mong muèn ng«n ng÷ biÓu diÔn tri thøc gÇn víi ng«n ng÷ tù nhiªn. Trong tμi liÖu nμy, chóng ta sÏ tËp trung nghiªn cøu logic vÞ tõ cÊp mét (first- order predicate logic hoÆc first-order predicate calculus) - mét ng«n ng÷ biÓu diÔn tri thøc, bëi v× logic vÞ tõ cÊp mét cã kh¶ n¨ng biÓu diÔn t−¬ng ®èi tèt, vμ h¬n n÷a nã lμ c¬ së cho nhiÒu ng«n ng÷ biÓu diÔn tri thøc kh¸c, ch¼ng h¹n to¸n hoμn c¶nh (situation calculus) hoÆc logic thêi gian kho¶ng cÊp mét (first-order interval tempral logic). Nh−ng tr−íc hÕt chóng ta sÏ nghiªn cøu logic mÖnh ®Ò (propositional logic hoÆc propositional calculus). Nã lμ ng«n ng÷ rÊt ®¬n gi¶n, cã kh¶ n¨ng biÓu diÔn h¹n chÕ, song thuËn tiÖn cho ta ®−a vμo nhiÒu kh¸i niÖm quan träng trong logic. II. Có ph¸p vμ ng÷ nghÜa cña logic mÖnh ®Ò II.1 Có ph¸p Có ph¸p cña logic mÖnh ®Ò rÊt ®¬n gi¶n, nã cho phÐp x©y dùng nªn c¸c c«ng thøc. Có ph¸p cña logic mÖnh ®Ò bao gåm tËp c¸c ký hiÖu vμ tËp c¸c luËt x©y dùng c«ng thøc. C¸c ký hiÖu • Hai h»ng logic True vμ False. • C¸c ký hiÖu mÖnh ®Ò (cßn ®−îc gäi lμ c¸c biÕn mÖnh ®Ò): P, Q, • C¸c kÕt nèi logic ∧,∨,¬,⇒,⇔ • C¸c dÊu më ngoÆc (vμ ®ãng ngoÆc). C¸c quy t¾c x©y dùng c¸c c«ng thøc • C¸c biÕn mÖnh ®Ò lμ c«ng thøc. • NÕu A vμ B lμ c«ng thøc th×: 8
9. (A ∧ B) (®äc “A héi B” hoÆc “A vμ B”) (A ∨ B) (®äc “A tuyÓn B” hoÆc “A hoÆc B”) ( ¬ A) (®äc “phñ ®Þnh A”) (A⇒ B) (®äc “A kÐo theo B” hoÆc “nÕu A th× B”) (A ⇔ B) (®äc “A vμ B kÐo theo nhau”) lμ c¸c c«ng thøc. Sau nμy ®Ó cho ng¾n gän, ta sÏ bá ®i c¸c cÆp dÊu ngoÆc kh«ng cÇn thiÕt. Ch¼ng h¹n, thay cho ((A ∨ B) ∧ C) ta sÏ viÕt lμ (A ∨ B) ∧ C. C¸c c«ng thøc lμ c¸c ký hiÖu mÖnh ®Ò sÏ ®−îc gäi lμ c¸c c©u ®¬n hoÆc c©u ph©n tö. C¸c c«ng thøc kh«ng ph¶i lμ c©u ®¬n sÏ ®−îc gäi lμ c©u phøc hîp. NÕu P lμ ký hiÖu mÖnh ®Ò th× P vμ TP ®−îc gäi lμ literal, P lμ literal d−¬ng, cßn TP lμ literal ©m. C©u phøc hîp cã d¹ng A1 ∨ ∨ Am trong ®ã Ai lμ c¸c literal sÏ ®−îc gäi lμ c©u tuyÓn (clause). II.2 Ng÷ nghÜa Ng÷ nghÜa cña logic mÖnh ®Ò cho phÐp ta x¸c ®Þnh thiÕt lËp ý nghÜa cña c¸c c«ng thøc trong thÕ giíi hiÖn thùc nμo ®ã. §iÒu ®ã ®−îc thùc hiÖn b»ng c¸ch kÕt hîp mÖnh ®Ò víi sù kiÖn nμo ®ã trong thÕ giíi hiÖn thùc. Ch¼ng h¹n, ký hiÖu mÖnh ®Ò P cã thÓ øng víi sù kiÖn “Paris lμ thñ ®« n−íc Ph¸p” hoÆc bÊt kú mét sù kiÖn nμo kh¸c. BÊt kú mét sù kÕt hîp c¸c kÝ hiÖu mÖnh ®Ò víi c¸c sù kiÖn trong thÕ giíi thùc ®−îc gäi lμ mét minh häa (interpretation ). Ch¼ng h¹n minh häa cña kÝ hiÖu mÖnh ®Ò P cã thÓ lμ mét sù kiÖn (mÖnh ®Ò) “Paris lμ thñ ®« n−íc Ph¸p ”. Mét sù kiÖn chØ cã thÓ ®óng hoÆc sai. Ch¼ng h¹n, sù kiÖn “Paris lμ thñ ®« n−íc Ph¸p ” lμ ®óng, cßn sù kiÖn “Sè Pi lμ sè h÷u tØ ” lμ sai. Mét c¸ch chÝnh x¸c h¬n, cho ta hiÓu mét minh häa lμ mét c¸ch g¸n cho mçi ký hiÖu mÖnh ®Ò mét gi¸ trÞ ch©n trÞ True hoÆc False. Trong mét minh häa, nÕu kÝ hiÖu mÖnh ®Ò P ®−îc g¸n gi¸ trÞ ch©n trÞ True/False (P ←True/ P←False) th× ta nãi mÖnh ®Ò P ®óng/sai trong minh häa ®ã. Trong mét minh häa, ý nghÜa cña c¸c c©u phøc hîp ®−îc x¸c ®Þnh bëi ý nghÜa cña c¸c kÕt nèi logic. Chóng ta x¸c ®Þnh ý nghÜa cña c¸c kÕt nèi logic trong c¸c b¶ng ch©n trÞ (xem h×nh 1.1) P Q ¬P P ∧ Q P ∨ Q P ⇒ Q P ⇔ Q False False True False False True True False True True False True True Fasle True False False False True False False True True False True True True True H×nh 1.1 B¶ng ch©n trÞ cña c¸c kÕt nèi logic ý nghÜa cña c¸c kÕt nèi logic ∧, ∨ vμ ¬ ®−îc x¸c ®Þnh nh− c¸c tõ “vμ”,“hoÆc lμ” vμ “phñ ®Þnh” trong ng«n ng÷ tù nhiªn. Chóng ta cÇn ph¶i gi¶i thÝch thªm vÒ ý nghÜa cña phÐp kÐo theo P ⇒ Q (P kÐo theo Q ), P lμ gi¶ thiÕt, cßn Q lμ kÕt luËn. Trùc quan cho phÐp ta xem r»ng, khi P lμ ®óng vμ Q lμ ®óng th× c©u “P kÐo theo Q ” lμ ®óng, cßn khi 9
10. P lμ ®óng Q lμ sai th× c©u “P kÐo theo Q” lμ sai. Nh−ng nÕu P sai vμ Q ®óng , hoÆc P sai Q sai th× “P kÐo theo Q” lμ ®óng hay sai ? NÕu chóng ta xuÊt ph¸t tõ gi¶ thiÕt sai, th× chóng ta kh«ng thÓ kh¼ng ®Þnh g× vÒ kÕt luËn. Kh«ng cã lý do g× ®Ó nãi r»ng, nÕu P sai vμ Q ®óng hoÆc P sai vμ Q sai th× “P kÐo theo Q” lμ sai. Do ®ã trong tr−êng hîp P sai th× “P kÐo theo Q ” lμ ®óng dï Q lμ ®óng hay Q lμ sai. B¶ng ch©n trÞ cho phÐp ta x¸c ®Þnh ngÉu nhiªn c¸c c©u phøc hîp. Ch¼ng h¹n ng÷ nghÜa cña c¸c c©u P ∧ Q trong minh häa {P ← True , Q← False } lμ False. ViÖc x¸c ®Þnh ng÷ nghÜa cña mét c©u (P ∨ Q) ∧ ¬S trong mét minh häa ®−îc tiÕn hμnh nh− sau: ®Çu tiªn ta x¸c ®Þnh gi¸ trÞ ch©n trÞ cña P ∨ Q vμ ¬S , sau ®ã ta sö dông b¶ng ch©n trÞ ∧ ®Ó x¸c ®Þnh gi¸ trÞ (P ∨ Q) ∧ ¬S. • Mét c«ng thøc lμ hîp lÖ (valid) nÕu vμ chØ nÕu nã ®óng trong mäi minh ho¹ ch¼ng h¹n c©u P ∨ ¬P, nguîc l¹i nã lμ kh«ng hîp lÖ. • Mét c«ng thøc ®−îc gäi lμ tho¶ ®−îc (satisfiable) hay bÒn v÷ng (consistent) nÕu nã ®óng trong mét minh häa nμo ®ã. Ch¼ng h¹n c«ng thøc (P ∨ Q) ∧ ¬S lμ tho¶ ®−îc, v× nã cã gi¸ trÞ True trong minh häa {P ← True, Q ← False, S ← False}. • Mét c«ng thøc ®−îc gäi lμ kh«ng tho¶ ®−îc (insatisfiable) hay kh«ng bÒn v÷ng (inconsistent), nÕu nã lμ sai trong mäi minh häa (m©u thuÉn), ch¼ng h¹n c«ng thøc P ∧ ¬P. Chóng ta sÏ gäi mét m« h×nh (model) cña mét c«ng thøc lμ mét minh häa sao cho c«ng thøc lμ ®óng trong minh häa nμy. Nh− vËy mét c«ng thøc tho¶ ®−îc lμ c«ng thøc cã mét m« h×nh. Ch¼ng h¹n, minh häa {P ← False , Q ← False , S ←True } lμ mét m« h×nh cña c«ng thøc (P ⇒ Q) ∧ S. B»ng c¸ch lËp b¶ng ch©n trÞ (ph−¬ng ph¸p b¶ng ch©n trÞ ) lμ ta cã thÓ x¸c ®Þnh ®−îc mét c«ng thøc cã tho¶ ®−îc hay kh«ng. Trong b¶ng nμy, mçi biÕn mÖnh ®Ò ®øng ®Çu víi mét cét, c«ng thøc cÇn kiÓm tra ®øng ®Çu mét cét, mçi dßng t−¬ng øng víi mét minh häa. Ch¼ng h¹n h×nh 1.2 lμ b¶ng ch©n trÞ cho c«ng thøc (P ⇒ Q) ∧ S. Trong b¶ng ch©n trÞ nμy ta cÇn ®−a vμo c¸c cét phô øng víi c¸c c«ng thøc con cña c¸c c«ng thøc cÇn kiÓm tra ®Ó viÖc tÝnh gi¸ trÞ cña c«ng thøc nμy ®−îc dÔ dμng. Tõ b¶ng ch©n trÞ ta thÊy r»ng c«ng thøc (P ⇒ Q) ∧ S lμ tho¶ ®−îc nh−ng kh«ng hîp lÖ vμ. P Q S P ⇒ Q (P ⇒ Q) ∧ S False False False True False False False True True True False True False True False False True True True True True False False False False True False True False False True True False True False True True True True True H×nh 1.2 B¶ng ch©n trÞ cho c«ng thøc (P ⇒ Q) ∧ S 10
11. CÇn l−u ý r»ng, mét c«ng thøc chøa n biÕn, th× sè c¸c minh häa cña nã lμ 2n , tøc lμ b¶ng ch©n trÞ cã 2n dßng. Nh− vËy viÖc kiÓm tra mét c«ng thøc cã tho¶ ®−îc hay kh«ng b»ng ph−¬ng ph¸p b¶ng ch©n trÞ, ®ßi hái thêi gian mò. Cook (1971) ®· chøng minh r»ng, vÊn ®Ò kiÓm tra mét c«ng thøc trong logic mÖnh ®Ò cã tho¶ ®−îc hay kh«ng lμ vÊn ®Ò NP-®Çy ®ñ. Chóng ta sÏ nãi r»ng tho¶ ®−îc/ kh«ng tho¶ ®−îc nÕu héi cña chóng G1 ∧ ∧ Gm lμ v÷ng ch¾c (tho¶ ®−îc, kh«ng tho¶ ®−îc). Mét m« h×nh cña tËp c«ng thøc G lμ m« h×nh cña tËp c«ng thøc G1 ∧ ∧ Gm. §Þnh nghÜa: Cho c¸c c«ng thøc F1, F2, , Fn vμ c«ng thøc G, G lμ hÖ qu¶ logic cña F1, F2, , Fn nÕu vμ chØ nÕu cho bÊt kú minh ho¹ I nμo trong ®ã F1 ∧ F2 ∧ ∧ Fn lμ ®óng th× G còng ®óng, F1, F2, , Fn lμ tiÒn ®Ò cña G. §Þnh lý: Cho c¸c c«ng thøc F1, F2, , Fn vμ c«ng thøc G, G lμ hÖ qu¶ logic cña F1, F2, , Fn nÕu vμ chØ nÕu c«ng thøc (F1 ∧ F2 ∧ ∧ Fn ) → G lμ hîp lÖ. §Þnh lý: Cho c¸c c«ng thøc F1, F2, , Fn vμ c«ng thøc G, G lμ hÖ qu¶ logic cña F1, F2, , Fn nÕu vμ chØ nÕu c«ng thøc (F1 ∧ F2 ∧ ∧ Fn ∧ ¬G) lμ kh«ng bÒn v÷ng. VÝ dô: NÕu quèc héi tõ chèi ban hμnh luËt míi th× tæng thèng tõ chøc vμ cuéc ®×nh c«ng kÐo dμi h¬n mét tuÇn trõ khi nã chÊm døt ngay. C©u hái r»ng liÖu cuéc ®×nh c«ng sÏ chÊm døt ngay nÕu quèc héi tõ chèi ban hμnh vμ cuéc ®×nh c«ng kh«ng kÐo dμi h¬n mét tuÇn? Ta ®Æt: P: quèc héi tõ chèi ban hμnh. Q: tæng thèng tõ chøc. R: cuéc ®×nh c«ng kÐo dμi h¬n mét tuÇn. S: cuéc ®×nh c«ng chÊm døt ngay. Ta cã F1: P → (Q ∧ R) ∨ S ≡ NÕu quèc héi tõ chèi ban hμnh luËt míi th× tæng thèng tõ chøc vμ cuéc ®×nh c«ng kÐo dμi h¬n mét tuÇn trõ khi nã chÊm døt ngay. F2: P ≡ Quèc héi tõ chèi ban hμnh. F3: ¬R ≡ Cuéc ®×nh c«ng kh«ng kÐo dμi h¬n mét tuÇn. Ta chøng minh r»ng S lμ hÖ qu¶ logic cña F1, F2 vμ F3. III. D¹ng chuÈn t¾c Trong môc nμy chóng ta sÏ xÐt viÖc chuÈn hãa c¸c c«ng thøc, ®−a c¸c c«ng thøc vÒ d¹ng thuËn lîi cho viÖc lËp luËn, suy diÔn. Tr−íc hÕt ta sÏ xÐt c¸c phÐp biÕn ®æi t−¬ng ®−¬ng. Sö dông c¸c phÐp biÓn ®æi nμy, ta cã thÓ ®−a mét c«ng thøc bÊt kú vÒ c¸c d¹ng chuÈn t¾c. Sù t−¬ng ®−¬ng cña c¸c c«ng thøc 11
12. Hai c«ng thøc A vμ B ®−îc xem lμ t−¬ng ®−¬ng nÕu chóng cã cïng mét gi¸ trÞ ch©n trÞ trong mäi minh häa. §Ó chØ A t−¬ng ®−¬ng víi B ta viÕt A≡ B b»ng ph−¬ng ph¸p b¶ng ch©n trÞ, dÔ dμng chøng minh ®−îc sù t−¬ng ®−¬ng cña c¸c c«ng thøc sau ®©y : • A ⇒ B  ¬A ∨ B • A ⇔ B  (A ⇒ B) ∧ (B ⇒ A) • ¬ (¬A)  A LuËt De Morgan • ¬(A ∨ B) ≡ ¬A ∧ ¬B • ¬(A ∧ B) ≡ ¬A ∨ ¬B LuËt giao ho¸n • A ∨ B ≡ B ∨ A • A ∧ B ≡ B ∧ A LuËt kÕt hîp • (A ∨ B) ∨ C ≡ A∨( B ∨ C) • (A ∨ B) ∨ C ≡ A∨ ( B ∨ C) LuËt ph©n phèi • A ∧ (B ∨ C) ≡ (A ∧ B ) ∨ (A ∧ C) • A ∨ (B ∧ C) ≡ (A ∨ B ) ∧ (A ∨ C) D¹ng chuÈn t¾c : C¸c c«ng thøc t−¬ng ®−¬ng cã thÓ xem nh− c¸c biÓu diÔn kh¸c nhau cña cïng mét sù kiÖn. §Ó dÔ dμng viÕt c¸c ch−¬ng tr×nh m¸y tÝnh thao t¸c trªn c¸c c«ng thøc, chóng ta sÏ chuÈn hãa c¸c c«ng thøc, ®−a chóng vÒ d¹ng biÓu diÔn chuÈn ®−îc gäi lμ d¹ng chuÈn héi. Mét c«ng thøc ë d¹ng chuÈn héi, cã d¹ng A1 ∧ . ∧ Am trong ®ã c¸c Ai lμ literal. Chóng ta cã thÓ biÕn ®æi mét c«ng thøc bÊt kú vÒ c«ng thøc ë d¹ng chuÈn héi b»ng c¸ch ¸p dông c¸c thñ tôc sau. • Bá c¸c dÊu kÐo theo (⇒) b»ng c¸ch thay (A ⇒ B) bëi (¬A ∨ B). • ChuyÓn c¸c dÊu phñ ®Þnh (¬) vμo s¸t c¸c kÕt hiÖu mÖnh ®Ò b»ng c¸ch ¸p dông luËt De Morgan vμ thay ¬(¬A) bëi A. • ¸p dông luËt ph©n phèi, thay c¸c c«ng thøc cã d¹ng A ∨ (B ∧ C) bëi (A ∨ B) ∧ ( A ∨ B ). VÝ dô : Ta chuÈn hãa c«ng thøc ( P ⇒ Q) ∨ ¬(R ∨ ¬S) : (P ⇒ Q) ∨ ¬(R ∨ ¬S) ≡ (¬P ∨ Q) ∨ (¬R ∧ S) ≡ ((¬P ∨ Q) ∨ ¬R) ∧ ( (¬P ∨ Q) ∨ S) ≡ (¬ P ∨ Q ∨ ¬R) ∧ (¬P ∨ Q ∨ S). Nh− vËy c«ng thøc (P ⇒ Q) ∨ ¬(R ∨ ¬S) ®−îc ®−a vÒ d¹ng chuÈn héi (¬P ∨ Q ∨ ¬R) ∧ (¬P ∨ Q ∨ S). 12
13. Khi biÓu diÔn tri thøc bëi c¸c c«ng thøc trong logic mÖnh ®Ò, c¬ së tri thøc lμ mét tËp nμo ®ã c¸c c«ng thøc. B»ng c¸ch chuÈn ho¸ c¸c c«ng thøc, c¬ së tri thøc lμ mét tËp nμo ®ã c¸c c©u tuyÓn. C¸c c©u Horn : ë trªn ta ®· chØ ra, mäi c«ng thøc ®Òu cã thÓ ®−a vÒ d¹ng chuÈn héi, tøc lμ c¸c héi cña c¸c tuyÓn, mçi c©u tuyÓn cã d¹ng ¬P1 ∨ ∨ ¬Pm ∨ Q1 ∨ Qn trong ®ã Pi , Qi lμ c¸c ký hiÖu mÖnh ®Ò (literal d−¬ng) c©u nμy t−¬ng ®−¬ng víi c©u P1 ∧ ∧ Pm ⇒ Q1 ∨ ∨ Qn ≈ p1 ∧ ∧ pm ⇒ Q D¹ng c©u nμy ®−îc gäi lμ c©u Kowalski (do nhμ logic Kowalski ®−a ra n¨m 1971). Khi n ≤ 1, tøc lμ c©u Kowalski chØ chøa nhiÒu nhÊt mét literal d−¬ng ta cã d¹ng mét c©u ®Æc biÖt quan träng ®−îc gäi lμ c©u Horn (mang tªn nhμ logic Alfred Horn n¨m 1951). NÕu m>0, n=1, c©u Horn cã d¹ng : P1 ∧ ∧ Pm ⇒ Q Trong ®ã Pi , Q lμ c¸c literal d−¬ng. C¸c Pi ®−îc gäi lμ c¸c ®iÒu kiÖn (hoÆc gi¶ thiÕt), cßn Q ®−îc gäi lμ kÕt luËn (hoÆc hÖ qu¶). C¸c c©u Horn d¹ng nμy cßn ®−îc gäi lμ c¸c luËt if then vμ ®−îc biÓu diÔn nh− sau : If P1 and and Pm then Q. Khi m=0, n=1 c©u Horn trë thμnh c©u ®¬n Q, hay sù kiÖn Q. NÕu m>0, n=0 c©u Horn trë thμnh d¹ng ¬P1 ∨ ∨ ¬Pm hay t−¬ng ®−¬ng ¬(P1 ∧ ∧ Pm). CÇn chó ý r»ng, kh«ng ph¶i mäi c«ng thøc ®Òu cã thÓ biÓu diÔn d−íi d¹ng héi cña c¸c c©u Horn. Tuy nhiªn trong c¸c øng dông, c¬ së tri thøc th−êng lμ mét tËp nμo ®ã c¸c c©u Horn (tøc lμ mét tËp nμo ®ã c¸c luËt if-then). IV. LuËt suy diÔn Mét c«ng thøc H ®−îc xem lμ hÖ qu¶ logic (logical consequence) cña mét tËp c«ng thøc G={G1, ,Gm} nÕu trong bÊt kú minh häa nμo mμ {G1, ,Gm} ®óng th× H còng ®óng, hay nãi c¸ch kh¸c bÊt kú mét m« h×nh nμo cña G còng lμ m« h×nh cña H. Khi cã mét c¬ së tri thøc, ta muèn sö dông c¸c tri thøc trong c¬ së nμy ®Ó suy ra tri thøc míi mμ nã lμ hÖ qu¶ logic cña c¸c c«ng thøc trong c¬ së tri thøc. thùc hiÖn b»ng c¸c thùc hiÖn c¸c luËt suy diÔn (rule of inference). LuËt suy diÔn gièng nh− mét thñ tôc mμ chóng ta sö dông ®Ó sinh ra mét c«ng thøc míi tõ c¸c c«ng thøc ®· cã. Mét luËt suy diÔn gåm hai phÇn: mét tËp c¸c ®iÒu kiÖn vμ mét kÕt luËn. Chóng ta sÏ biÓu diÔn c¸c luËt suy diÔn d−íi d¹ng “ph©n sè ”, trong ®ã tö sè lμ danh s¸ch c¸c ®iÒu kiÖn, cßn mÉu sè lμ kÕt luËn cña luËt, tøc lμ mÉu sè lμ c«ng thøc míi ®−îc suy ra tõ c¸c c«ng thøc ë tö sè. Sau ®©y lμ mét sè luËt suy diÔn quan träng trong logic mÖnh ®Ò. Trong c¸c luËt nμy α, αi , β, γ lμ c¸c c«ng thøc : LuËt Modus Ponens 13
14. α ⇒ β,α β Tõ mét kÐo theo vμ gi¶ thiÕt cña kÐo theo, ta suy ra kÕt luËn cña nã. LuËt Modus Tollens α ⇒ β, ¬β ¬α Tõ mét kÐo theo vμ phñ ®Þnh kÕt luËn cña nã, ta suy ra phñ ®Þnh gi¶ thiÕt cña kÐo theo. LuËt b¾c cÇu α ⇒ β, β ⇒ γ α ⇒ γ Tõ hai kÐo theo, mμ kÕt luËn cña nã lμ cña kÐo theo thø nhÊt trïng víi gi¶ thiÕt cña kÐo theo thø hai, ta suy ra kÐo theo míi mμ gi¶ thiÕt cña nã lμ gi¶ thiÕt cña kÐo theo thø nhÊt, cßn kÕt luËn cña nã lμ kÕt luËn cña kÐo theo thø hai. LuËt lo¹i bá héi α1 ∧ ∧ αi ∧ ∧ αm αi Tõ mét héi ta ®−a ra mét nh©n tö bÊt kú cña héi. LuËt ®−a vμo héi α1, ,αi, αm α1 ∧ ∧ αi ∧ ∧ αm Tõ mét danh s¸ch c¸c c«ng thøc, ta suy ra héi cña chóng. LuËt ®−a vμo tuyÓn αi α1 ∨ ∨ αi. ∨ ∨ αm Tõ mét c«ng thøc, ta suy ra mét tuyÓn mμ mét trong c¸c h¹ng tö cña c¸c tuyÓn lμ c«ng thøc ®ã. LuËt gi¶i α ∨ β, ¬β ∨ γ α ∨ γ Tõ hai tuyÓn, mét tuyÓn chøa mét h¹ng tö ®èi lËp víi mét h¹ng tö trong tuyÓn kia, ta suy ra tuyÓn cña c¸c h¹ng tö cßn l¹i trong c¶ hai tuyÓn. Mét luËt suy diÔn ®−îc xem lμ tin cËy (secured) nÕu bÊt kú mét m« h×nh nμo cña gi¶ thiÕt cña luËt còng lμ m« h×nh kÕt luËn cña luËt. Chóng ta chØ quan t©m ®Õn c¸c luËt suy diÔn tin cËy. 14
15. B»ng ph−¬ng ph¸p b¶ng ch©n trÞ, ta cã thÓ kiÓm chøng ®−îc c¸c luËt suy diÔn nªu trªn ®Òu lμ tin cËy. B¶ng ch©n trÞ cña luËt gi¶i ®−îc cho trong h×nh 1.3. Tõ b¶ng nμy ta thÊy r»ng , trong bÊt kú mét minh häa nμo mμ c¶ hai gi¶ thiÕt α ∨ β , ¬β ∨ γ ®óng th× kÕt luËn α ∨ γ còng ®óng. Do ®ã luËt gi¶i lμ luËt suy ®iÔn tin cËy. α β γ α ∨ β ¬β ∨ γ α ∨ γ False False False False True False False False True False True True False True False True False False False True True True True True True False False True True True True False True True True True True True False True False True True True True True True True H×nh 1.3 B¶ng ch©n trÞ chøng minh tÝnh tin cËy cña luËt gi¶i. Ta cã nhËn xÐt r»ng, luËt gi¶i lμ mét luËt suy diÔn tæng qu¸t, nã bao gåm luËt Modus Ponens, luËt Modus Tollens, luËt b¾c cÇu nh− c¸c tr−êng hîp riªng. Tiªn ®Ò ®Þnh lý chøng minh Gi¶ sö chóng ta cã mét tËp nμo ®ã c¸c c«ng thøc. C¸c luËt suy diÔn cho phÐp ta tõ c¸c c«ng thøc ®· cã suy ra c«ng thøc míi b»ng mét d·y ¸p dông c¸c luËt suy diÔn. C¸c c«ng thøc ®· cho ®−îc gäi lμ c¸c tiªn ®Ò. C¸c c«ng thøc ®−îc suy ra ®−îc gäi lμ c¸c ®Þnh lý. D·y c¸c luËt ®−îc ¸p dông ®Ó dÉn tíi ®Þnh lý ®−îc gäi lμ mét chøng minh cña ®Þnh lý. NÕu c¸c luËt suy diÔn lμ tin cËy, th× c¸c ®Þnh lý lμ hÖ qu¶ logic cña c¸c tiªn ®Ò. VÝ dô: Gi¶ sö ta cã c¸c c«ng thøc sau : Q ∧ S ⇒ G ∧ H (1) P ⇒ Q (2) R ⇒ S (3) P (4) R (5) Tõ c«ng thøc (2) vμ (4), ta suy ra Q (LuËt Modus Ponens) . L¹i ¸p dông luËt Modus Ponens, tõ (3) vμ (5) ta suy ra S . Tõ Q, S ta suy ra Q ∧ S (luËt ®−a vμo héi ). Tõ (1) vμ Q ∧ S ta suy ra G ∨ H. C«ng thøc G ∨ H ®· ®−îc chøng minh. Trong c¸c hÖ tri thøc, ch¼ng h¹n c¸c hÖ chuyªn gia, hÖ lËp tr×nh logic, , sö dông c¸c luËt suy diÔn ng−êi ta thiÕt kÕ lªn c¸c thñ tôc suy diÔn (cßn ®−îc gäi lμ thñ tôc chøng minh) ®Ó tõ c¸c tri thøc trong c¬ së tri thøc ta suy ra c¸c tri thøc míi ®¸p øng nhu cÇu cña ng−êi sö dông. Mét hÖ h×nh thøc (formal system) bao gåm mét tËp c¸c tiªn ®Ò vμ mét tËp c¸c luËt suy diÔn nμo ®ã (trong ng«n ng÷ biÓu diÔn tri thøc nμo ®ã). 15
16. Mét tËp luËt suy diÔn ®−îc xem lμ ®Çy ®ñ, nÕu mäi hÖ qu¶ logic cña mét tËp c¸c tiªn ®Ò ®Òu chøng minh ®−îc b»ng c¸ch chØ sö dông c¸c luËt cña tËp ®ã. Ph−¬ng ph¸p chøng minh b¸c bá Ph−¬ng ph¸p chøng minh b¸c bá (refutation proof hoÆc proof by contradiction) lμ mét ph−¬ng ph¸p th−êng xuyªn ®−îc sö dông trong c¸c chøng minh to¸n häc. T− t−ëng cña ph−¬ng ph¸p nμy lμ nh− sau: §Ó chøng minh P ®óng, ta gi¶ sö P sai ( thªm ¬P vμo c¸c gi¶ thiÕt ) vμ dÉn tíi mét m©u thuÉn. Sau ®©y ta sÏ tr×nh bÇy c¬ së nμy. Gi¶ sö chóng ta cã mét tËp hîp c¸c c«ng thøc G ={G1, ,Gm} ta cÇn chøng minh c«ng thøc H lμ hÖ qu¶ logic cña G . §iÒu ®ã t−¬ng ®−¬ng víi chøng minh c«ng thøc G1 ∧ ∧ Gm ⇒ H lμ v÷ng ch¾c. Thay cho chøng minh G1 ∧ ∧ Gm ⇒ H lμ v÷ng ch¾c, ta chøng minh G1 ∧ ∧ Gm ∧ ¬H lμ kh«ng tháa m·n ®−îc. Tøc lμ ta chøng minh tËp G’= (G1, ,Gm,¬H ) lμ kh«ng tháa ®−îc nÕu tõ G’ta suy ra hai mÖnh ®Ò ®èi lËp nhau. ViÖc chøng minh c«ng thøc H lμ hÖ qu¶ logic cña tËp c¸c tiªu ®Ò G b»ng c¸ch chøng minh tÝnh kh«ng tháa ®−îc cña tËp c¸c tiªu ®Ò ®−îc thªm vμo phñ ®Þnh cña c«ng thøc cÇn chøng minh, ®−îc gäi lμ chøng minh b¸c bá. V. LuËt gi¶i, chøng minh b¸c bá b»ng luËt gi¶i §Ó thuËn tiÖn cho viÖc sö dông luËt gi¶i, chóng ta sÏ cô thÓ ho¸ luËt gi¶i trªn c¸c d¹ng c©u ®Æc biÖt quan träng. •LuËt gi¶i trªn c¸c c©u tuyÓn A1∨ ∨ Am ∨ C ¬C ∨ B1 ∨ Bn A1∨ ∨ Am ∨ B1∨ ∨Bn trong ®ã Ai, Bj vμ C lμ c¸c literal. •LuËt gi¶i trªn c¸c c©u Horn Gi¶ sö Pi, Rj, Q vμ S lμ c¸c literal. Khi ®ã ta cã c¸c luËt sau : P1 ∧ ∧ Pm ∧ S ⇒ Q, R1 ∧ ∧ Rn ⇒ S P1 ∧ ∧ Pm ∧ R1 ∧ ∧ Rn ⇒Q Mét tr−êng hîp riªng hay ®−îc sö dông cña luËt trªn lμ : P1 ∧ ∧ Pm ∧ S ⇒ Q, S P1 ∧ ∧ Pm ⇒ Q Khi ta cã thÓ ¸p dông luËt gi¶i cho hai c©u, th× hai c©u nμy ®−îc gäi lμ hai c©u gi¶i ®−îc vμ kÕt qu¶ nhËn ®−îc khi ¸p dông luËt gi¶i cho hai c©u ®ã ®−îc gäi lμ gi¶i thøc cña chóng. Gi¶i thøc cña hai c©u A vμ B ®−îc kÝ hiÖu lμ res(A, B). Ch¼ng h¹n, hai c©u tuyÓn gi¶i ®−îc nÕu mét c©u chøa mét literal ®èi lËp víi mét literal trong c©u kia. Gi¶i thøc cña hai literal ®èi lËp nhau (P vμ ¬P) lμ c©u rçng, chóng ta sÏ ký hiÖu c©u rçng lμ [] , c©u rçng kh«ng tho¶ ®−îc. 16
17. Gi¶ sö G lμ mét tËp c¸c c©u tuyÓn (B»ng c¸ch chuÈn ho¸ ta cã thÓ ®−a mét tËp c¸c c«ng thøc vÒ mét tËp c¸c c©u tuyÓn). Ta sÏ ký hiÖu R(G ) lμ tËp c©u bao gåm c¸c c©u thuéc G vμ tÊt c¶ c¸c c©u nhËn ®−îc tõ G b»ng mét d·y ¸p dông luËt gi¶i. LuËt gi¶i lμ luËt ®Çy ®ñ ®Ó chøng minh mét tËp c©u lμ kh«ng tháa ®−îc. §iÒu nμy ®−îc suy tõ ®Þnh lý sau : §Þnh lý gi¶i: Mét tËp c©u tuyÓn lμ kh«ng tháa ®−îc nÕu vμ chØ nÕu c©u rçng [] ∈ R(G ). §Þnh lý gi¶i cã nghÜa r»ng, nÕu tõ c¸c c©u thuéc G, b»ng c¸ch ¸p dông luËt gi¶i ta dÉn tíi c©u rçng th× G lμ kh«ng tháa ®−îc, cßn nÕu kh«ng thÓ sinh ra c©u rçng b»ng luËt gi¶i th× G tháa ®−îc. L−u ý r»ng, viÖc dÉn tíi c©u rçng cã nghÜa lμ ta ®· dÉn tíi hai literal ®èi lËp nhau P vμ ¬P ( tøc lμ dÉn tíi m©u thuÉn ). Tõ ®Þnh lý gi¶i, ta ®−a ra thñ tôc sau ®©y ®Ó x¸c ®Þnh mét tËp c©u tuyÓn G lμ tháa ®−îc hay kh«ng. Thñ tôc nμy ®−îc gäi lμ thñ tôc gi¶i. Procedure Resolution ; Input : tËp G c¸c c©u tuyÓn ; Begin 1.Repeat 1.1 Chän hai c©u A vμ B thuéc G ; 1.2 if A vμ B gi¶i ®−îc then tÝnh Res ( A,B ) ; 1.3 if Res (A,B ) lμ c©u míi then thªm Res ( A,B ) vμo G ; until nhËn ®−îc [] hoÆc kh«ng cã c©u míi xuÊt hiÖn ; 2. if nhËn ®−îc c©u rçng then th«ng b¸o G kh«ng tho¶ ®−îc else th«ng b¸o G tho¶ ®−îc ; end; Chóng ta cã nhËn xÐt r»ng, nÕu G lμ tËp h÷u h¹n c¸c c©u th× c¸c literal cã mÆt trong c¸c c©u cña G lμ h÷u h¹n. Do ®ã sè c¸c c©u tuyÓn thμnh lËp ®−îc tõ c¸c literal ®ã lμ h÷u h¹n. V× vËy chØ cã mét sè h÷u h¹n c©u ®−îc sinh ra b»ng luËt gi¶i. Thñ tôc gi¶i sÏ dõng l¹i sau mét sè h÷u h¹n b−íc. ChØ sö dông luËt gi¶i ta kh«ng thÓ suy ra mäi c«ng thøc lμ hÖ qu¶ logic cña mét tËp c«ng thøc ®· cho. Tuy nhiªn, sö dông luËt gi¶i ta cã thÓ chøng minh ®−îc mét c«ng thøc bÊt k× cã lμ hÖ qu¶ cña mét tËp c«ng thøc ®· cho hay kh«ng b»ng ph−¬ng ph¸p chøng minh b¸c bá. V× vËy luËt gi¶i ®−îc xem lμ luËt ®Çy ®ñ cho b¸c bá. Sau ®©y lμ thñ tôc chøng minh b¸c bá b»ng luËt gi¶i Procedure Refutation_Proof ; Input : TËp G c¸c c«ng thøc ; C«ng thøc cÇn chøng minh H; Begin 17
18. 1. Thªm ¬H vμo G ; 2. ChuyÓn c¸c c«ng thøc trong G vÒ d¹ng chuÈn héi ; 3. Tõ c¸c d¹ng chuÈn héi ë b−íc hai, thμnh lËp t¹p c¸c c©u tuyÓn G’ ; 4. ¸p dông thñ tôc gi¶i cho tËp c©u G’ ; 5. if G’ kh«ng tho¶ ®−îc then th«ng b¸o H lμ hÖ qu¶ logic else th«ng b¸o H kh«ng lμ hÖ qu¶ logic cña G ; end; VÝ dô: Gi¶ giö G lμ tËp hîp c¸c c©u tuyÓn sau : ¬A ∨ ¬B ∨ P (1) ¬C ∨ ¬D ∨ P (2) ¬E ∨ C (3) A (4) E (5) D (6) Gi¶ sö ta cÇn chøng minh P. Thªm vμo G c©u sau: ¬P (7) ¸p dông luËt gi¶i cho c©u (2) vμ (7) ta ®−îc c©u: ¬C ∨ ¬D (8) Tõ c©u (6) vμ (8) ta nhËn ®−îc c©u: ¬C (9) Tõ c©u (3) vμ (9) ta nhËn ®−îc c©u: ¬E (10) Tíi ®©y ®· xuÊt hiÖn m©u thuÉn, v× c©u (5) vμ (10) ®èi lËp nhau. Tõ c©u (5) vμ (10) ta nhËn ®−îc c©u rçng []. VËy P lμ hÖ qu¶ logic cña c¸c c©u (1) (6). VI. Bμi tËp 1. ThÓ hiÖn c¸c c©u sau b»ng mÖnh ®Ò logic a. Mét quan hÖ lμ t−¬ng ®−¬ng nÕu vμ chØ nÕu nã ph¶n x¹, b¾t cÇu vμ ®èi xøng. b. NÕu ®é Èm qu¸ cao th× trêi sÏ m−a vμo buæi chiÒu hay buæi tèi. c. Ung th− sÏ kh«ng ch÷a trÞ ®−îc trõ khi t×m ra nguyªn nh©n vμ thuèc ®iÒu trÞ míi. d. §Ó leo lªn nói cao th× ®ßi hái sù dòng c¶m vμ kü n¨ng leo nói. e. NÕu «ng ta vËn ®éng nhiÒu th× cã thÓ sÏ ®−îc bÇu. 2. §Æt P : ¤ng ta cÇn mét b¸c sÜ Q : ¤ng ta cÇn mét luËt s− 18
19. R : ¤ng ta gÆp tai n¹n S : ¤ng ta bÞ bÖnh U : ¤ng ta bÞ th−¬ng Ph¸t biÓu ý nghÜa c¸c c«ng thøc sau: (S → P) ∧ (R → Q) P → (S ∨ U) (P ∧ Q) → R (P ∧ Q) ↔ (S ∧ U) ¬ (S ∨ U) → ¬P 3. T¹o b¶ng ch©n trÞ cña c«ng thøc : (¬P ∨ Q) ∧ (¬ (P ∧ ¬Q)) 4. Cho c¸c c«ng thøc sau, x¸c ®Þnh c«ng thøc nμo lμ hîp lÖ, kh«ng hîp lÖ, bÒn v÷ng, kh«ng bÒn v÷ng hoÆc kÕt hîp c¸c tÝnh chÊt trªn: a. ¬ (¬P) →P b. P → (P ∧ Q) c. ¬ (P ∨ Q) ∨ ¬Q d. (P ∨ Q) ∨ P e. (P → Q) → (¬Q → ¬P) f. (P → Q) → (Q → P) g. P ∨ (P → Q) h. (P ∧ (Q → P)) → P i. P ∨ (Q →¬P) j. (P ∨ ¬Q) ∧ (¬P ∨ Q) k. ¬P ∧ (¬ (P → Q)) l. P → ¬P m. ¬P → P 5. ChuyÓn c¸c c«ng thøc sau ra d¹ng c©u tuyÓn a. (¬P ∧ Q) → R b. P → ((Q ∧ R) → S) c. ¬(P ∨ ¬Q) ∧ (S → T) d. (P → Q) → R e. ¬(P ∧ Q) ∧ (P ∨ Q) 19
20. 6. ChuyÓn c¸c c«ng thøc sau ra d¹ng c©u héi a. P ∨ (¬P ∧ Q ∧ R) b. ¬ (P → Q) ∨ (P ∨ Q) c. ¬(P → Q) d. (¬P ∧ Q) ∨ (P ∧ ¬Q) 7. Cã c«ng thøc nμo mμ nã cã thÓ ë d¹ng tuyÓn lÉn d¹ng héi? NÕu cã, h·y cho vÝ dô 8. Chøng minh c¸c c«ng thøc sau lμ t−¬ng ®−¬ng a. (P → Q) ∧ (P → R) ≡ (P → (Q ∧ R)) b. (P → Q) → (P ∧ Q) ≡ (¬P → Q) ∧ (Q → P) c. P ∧ Q ∧ (¬P ∨ ¬Q) ≡ ¬P ∧ ¬Q ∧ (P ∨ Q) d. P ∨ (P → (P ∧ Q)) ≡ ¬P ∨ ¬Q ∨ (P ∧ Q) 9. Chøng minh r»ng (¬Q → ¬P) lμ hÖ qu¶ l«gic cña (P → Q) 10. Xem xÐt c¸c c©u sau: F1: S¬n kh«ng thÓ lμ sinh viªn giái trõ khi anh ta th«ng minh vμ cha S¬n hç trî S¬n. F2: NÕu S¬n lμ sinh viªn giái th× do cha S¬n hç trî anh ta. Chøng minh r»ng F2 lμ hÖ qu¶ l«gic cña F1 11. Xem xÐt c©u ph¸t biÓu sau: NÕu quèc héi tõ chèi ban hμnh luËt míi th× cuéc ®×nh c«ng sÏ kh«ng kÕt thóc trõ khi nã kÐo dμi h¬n mét tuÇn vμ tæng thèng tõ chøc. Gi¶ sö quèc héi tõ chèi ban hμnh luËt míi, cuéc ®×nh c«ng kÕt thóc vμ tæng thèng kh«ng tõ chøc. Chøng minh ®iÒu m©u thuÈn sÎ x·y ra. 12. Chøng minh r»ng F5 lμ hÖ qu¶ l«gic cña F1, F2 , F3vμ F4 F1 : Nếu tổng thống không có đủ quyền và ông ta vô trách nhiệm thì trật tự không được vãn hồi hay cuộc bạo loạn sẽ lan rộng trừ khi những kẻ bạo loạn cảm thấy mệt mỏi và các nhà chức trách địa phương có những hành động hoà giải. F2: Trật tự được vãn hồi. F3: Những kẻ bạo loạn cảm thấy mệt mỏi F4: Tổng thống vô trách nhiệm và cuộc bạo loạn không lan rộng F5: Nếu tổng thống không có đủ quyền thì các nhà chức trách địa phương có những hành động hoà giải. 13. Chứng minh tập hợp S= {P∨Q, ¬Q∨R, ¬P∨Q, ¬R} sÏ cho c©u rçng [] bëi luËt gi¶i. 20
21. Ch−¬ng II LOGIC VÞ Tõ CÊP MéT Logic mÖnh ®Ò cho phÐp ta biÓu diÔn c¸c sù kiÖn, mçi kÝ hiÖu trong logic mÖnh ®Ò ®−îc minh häa nh− lμ mét sù kiÖn trong thÕ giíi hiÖn thùc, sö dông c¸c kÕt nèi logic ta cã thÓ t¹o ra c¸c c©u phøc hîp biÓu diÔn c¸c sù kiÖn mang ý nghÜa phøc t¹p h¬n. Nh− vËy kh¶ n¨ng biÓu diÔn cña logic mÖnh ®Ò chØ giíi h¹n trong ph¹m vi thÕ giíi c¸c sù kiÖn. ThÕ giíi hiÖn thùc bao gåm c¸c ®èi t−îng, mçi ®èi t−îng cã nh÷ng tÝnh chÊt riªng ®Ó ph©n biÖt nã víi c¸c ®èi t−îng kh¸c. C¸c ®èi t−îng l¹i cã quan hÖ víi nhau. C¸c mèi quan hÖ rÊt ®a d¹ng vμ phong phó. Chóng ta cã thÓ liÖt kª ra rÊt nhiÒu vÝ dô vÒ ®èi t−îng, tÝnh chÊt, quan hÖ. §èi t−îng : mét c¸i bμn, mét c¸i nhμ, mét c¸i c©y, mét con ng−êi, mét con sè. TÝnh chÊt : C¸i bμn cã thÓ cã tÝnh chÊt : cã bèn ch©n, lμm b»ng gç, kh«ng cã ng¨n kÐo. Con sè cã thÓ cã tÝnh chÊt lμ sè nguyªn, sè h÷u tØ, lμ sè chÝnh ph−¬ng. Quan hÖ : cha con, anh em, bÌ b¹n (gi÷a con ng−êi ); lín h¬n nhá h¬n, b»ng nhau (gi÷a c¸c con sè ) ; bªn trong, bªn ngoμi n»m trªn n»m d−íi (gi÷a c¸c ®å vËt ) Hμm : Mét tr−êng hîp riªng cña quan hÖ lμ quan hÖ hμm. Ch¼ng h¹n, v× mçi ng−êi cã mét mÑ, do ®ã ta cã quan hÖ hμm øng mçi ng−êi víi mÑ cña nã. Logic vÞ tõ cÊp mét lμ më réng cña logic mÖnh ®Ò. Nã cho phÐp ta m« t¶ thÕ giíi víi c¸c ®èi t−îng, c¸c thuéc tÝnh cña ®èi t−îng vμ c¸c mèi quan hÖ gi÷a c¸c ®èi t−îng. Nã sö dông c¸c biÕn ( biÕn ®èi t−îng ) ®Ó chØ mét ®èi t−îng trong mét miÒn ®èi t−îng nμo ®ã. §Ó m« t¶ c¸c thuéc tÝnh cña ®èi t−îng, c¸c quan hÖ gi÷a c¸c ®èi t−îng, trong logic vÞ tõ, ng−êi ta dùa vμo c¸c vÞ tõ ( predicate). Ngoμi c¸c kÕt nèi logic nh− trong logic mÖnh ®Ò, logic vÞ tõ cÊp mét cßn sö dông c¸c l−îng tö. Ch¼ng h¹n, l−îng tö ∀ (víi mäi) cho phÐp ta t¹o ra c¸c c©u nãi tíi mäi ®èi t−îng trong mét miÒn ®èi t−îng nμo ®ã. Ch−¬ng nμy dμnh cho nghiªn cøu logic vÞ tõ cÊp mét víi t− c¸ch lμ mét ng«n ng÷ biÓu diÔn tri thøc. Logic vÞ tõ cÊp mét ®ãng vai trß cùc k× quan träng trong biÓu diÔn tri thøc, v× kh¶ n¨ng biÓu diÔn cña nã ( nã cho phÐp ta biÓu diÔn tri thøc vÒ thÕ giíi víi c¸c ®èi t−îng, c¸c thuéc tÝnh cña ®èi t−îng vμ c¸c quan hÖ cña ®èi t−îng), vμ h¬n n÷a, nã lμ c¬ së cho nhiÒu ng«n ng÷ logic kh¸c. I. Có ph¸p C¸c ký hiÖu • C¸c ký hiÖu h»ng: a, b, c, An, Ba, John, • C¸c ký hiÖu biÕn: x, y, z, u, v, w, • C¸c ký hiÖu vÞ tõ: P, Q, R, S, Like, Havecolor, Prime, 21
22. Mçi vÞ tõ lμ vÞ tõ cña n biÕn ( n≥0). Ch¼ng h¹n Like lμ vÞ tõ cña hai biÕn, Prime lμ vÞ tõ mét biÕn. C¸c ký hiÖu vÞ tõ kh«ng biÕn lμ c¸c ký hiÖu mÖnh ®Ò. • C¸c ký hiÖu hμm: f, g, cos, sin, mother, husband, distance, Mçi hμm lμ hμm cña n biÕn ( n≥1). Ch¼ng h¹n, cos, sin lμ hμm mét biÕn, distance lμ hμm cña hai biÕn. • C¸c ký hiÖu kÕt nèi logic: ∧ ( héi), ∨ (tuyÓn), ¬ ( phñ ®Þnh), ⇒ (kÐo theo), ⇔ (kÐo theo nhau). • C¸c ký hiÖu l−îng tö: ∀ ( víi mäi), ∃ ( tån t¹i). • C¸c ký hiÖu ng¨n c¸ch: dÊu phÈy, dÊu më ngoÆc vμ dÊu ®ãng ngoÆc. C¸c h¹ng thøc C¸c h¹ng thøc ( term) lμ c¸c biÓu thøc m« t¶ c¸c ®èi t−îng. C¸c h¹ng thøc ®−îc x¸c ®Þnh ®Ö quy nh− sau: • C¸c ký hiÖu h»ng vμ c¸c ký hiÖu biÕn lμ h¹ng thøc. • NÕu t1, t2, t3, , tn lμ n h¹ng thøc vμ f lμ mét ký hiÖu hμm n biÕn th× f(t1, t2, t3, , tn) lμ h¹ng thøc. Mét h¹ng thøc kh«ng chøa biÕn ®−îc gäi lμ mét h¹ng thøc cô thÓ ( ground term). Ch¼ng h¹n, An lμ ký hiÖu h»ng, mother lμ ký hiÖu hμm mét biÕn, th× mother (An) lμ mét h¹ng thøc cô thÓ. C¸c c«ng thøc ph©n tö Chóng ta sÏ biÓu diÔn c¸c tÝnh chÊt cña ®èi t−îng, hoÆc c¸c quan hÖ cña ®èi t−îng bëi c¸c c«ng thøc ph©n tö (c©u ®¬n). C¸c c«ng thøc ph©n tö ®−îc x¸c ®Þnh ®Ö quy nh− sau. • C¸c ký hiÖu vÞ tõ kh«ng biÕn ( c¸c ký hiÖu mÖnh ®Ò ) lμ c©u ®¬n. • NÕu t1, t2, t3, , tn lμ n h¹ng thøc vμ p lμ vÞ tõ cña n biÕn th× p(t1, t2, t3, , tn) lμ c©u ®¬n. Ch¼ng h¹n, Hoa lμ mét ký hiÖu h»ng, Love lμ mét vÞ tõ cña hai biÕn, husband lμ hμm cña mét biÕn, th× Love (Hoa, husband( Hoa)) lμ mét c©u ®¬n. C¸c c«ng thøc Tõ c«ng thøc phÇn tö, sö dông c¸c kÕt nèi logic vμ c¸c l−îng tö, ta x©y dùng nªn c¸c c«ng thøc (c¸c c©u). C¸c c«ng thøc ®−îc x¸c ®Þnh ®Ö quy nh− sau: • C¸c c«ng thøc ph©n tö lμ c«ng thøc. • NÕu G vμ H lμ c¸c c«ng thøc, th× c¸c biÓu thøc (G ∧ H), (G ∨ H), (¬ G), (G ⇒ H), (G ⇔ H) lμ c«ng thøc. • NÕu G lμ mét c«ng thøc vμ x lμ biÕn th× c¸c biÓu thøc (∀ x G), ( ∃ x G) lμ c«ng thøc. C¸c c«ng thøc kh«ng ph¶i lμ c«ng thøc ph©n tö sÏ ®−îc gäi lμ c¸c c©u phøc hîp. C¸c c«ng thøc kh«ng chøa biÕn sÏ ®−îc gäi lμ c«ng thøc cô thÓ. Khi viÕt c¸c c«ng thøc ta sÏ bá ®i c¸c dÊu ngoÆc kh«ng cÇn thiÕt, ch¼ng h¹n c¸c dÊu ngoÆc ngoμi cïng. 22
23. • L−îng tö phæ dông (∀ ) cho phÐp m« t¶ tÝnh chÊt cña c¶ mét líp c¸c ®èi t−îng, chø kh«ng ph¶i cña mét ®èi t−îng, mμ kh«ng cÇn ph¶i liÖt kª ra tÊt c¶ c¸c ®èi t−îng trong líp. Ch¼ng h¹n sö dông vÞ tõ Elephant(x) (®èi t−îng x lμ con voi ) vμ vÞ tõ Color(x, Gray) (®èi t−îng x cã mμu x¸m) th× c©u “ tÊt c¶ c¸c con voi ®Òu cã mμu x¸m” cã thÓ biÓu diÔn bëi c«ng thøc ∀ x (Elephant(x) ⇒ Color(x, Gray)). • L−îng tö tån t¹i ( ∃ ) cho phÐp ta t¹o ra c¸c c©u nãi ®Õn mét ®èi t−îng nμo ®ã trong mét líp ®èi t−îng mμ nã cã mét tÝnh chÊt hoÆc tho¶ m·n mét quan hÖ nμo ®ã. Ch¼ng h¹n b»ng c¸ch sö dông c¸c c©u ®¬n Student(x) (x lμ sinh viªn) vμ Inside(x, P301), (x ë trong phßng 301), ta cã thÓ biÓu diÔn c©u “ Cã mét sinh viªn ë phßng 301” bëi biÓu thøc ∃ x (Student(x) ∧ Inside(x, P301)). Mét c«ng thøc lμ c«ng thøc ph©n tö hoÆc phñ ®Þnh cña c«ng thøc ph©n tö ®−îc gäi lμ literal. Ch¼ng h¹n, Play(x, Football), ¬Like( Lan, Rose) lμ c¸c literal. Mét c«ng thøc lμ tuyÓn cña c¸c literal sÏ ®−îc gäi lμ c©u tuyÓn. Ch¼ng h¹n, Male(x) ∨ ¬Like(x, Foodball) lμ c©u tuyÓn. Trong c«ng thøc ∀ x G, hoÆc ∃ x G trong ®ã G lμ mét c«ng thøc nμo ®ã, th× mçi xuÊt hiÖn cña biÕn x trong c«ng thøc G ®−îc gäi lμ xuÊt hiÖn buéc. Mét c«ng thøc mμ tÊt c¶ c¸c biÕn ®Òu lμ xuÊt hiÖn buéc th× ®−îc gäi lμ c«ng thøc ®ãng. VÝ dô: C«ng thøc ∀ xP( x, f(a, x)) ∧ ∃ y Q(y) lμ c«ng thøc ®ãng, cßn c«ng thøc ∀ x P( x, f(y, x)) kh«ng ph¶i lμ c«ng thøc ®ãng, v× sù xuÊt hiÖn cña biÕn y trong c«ng thøc nμy kh«ng chÞu rμng buéc bëi mét l−îng tö nμo c¶ (sù xuÊt hiÖn cña y gäi lμ sù xuÊt hiÖn tù do). Sau nμy chóng ta chØ quan t©m tíi c¸c c«ng thøc ®ãng. II. Ng÷ nghÜa Còng nh− trong logic mÖnh ®Ò, nãi ®Õn ng÷ nghÜa lμ chóng ta nãi ®Õn ý nghÜa cña c¸c c«ng thøc trong mét thÕ giíi hiÖn thùc nμo ®ã mμ chóng ta sÏ gäi lμ mét minh häa. §Ó x¸c ®Þnh mét minh ho¹, tr−íc hÕt ta cÇn x¸c ®Þnh mét miÒn ®èi t−îng ( nã bao gåm tÊt c¶ c¸c ®èi t−îng trong thÕ giíi hiÖn thùc mμ ta quan t©m). Trong mét minh ho¹, c¸c ký hiÖu h»ng sÏ ®−îc g¾n víi c¸c ®èi t−îng cô thÓ trong miÒn ®èi t−îng c¸c ký hiÖu hμm sÏ ®−îc g¾n víi mét hμm cô thÓ nμo ®ã. Khi ®ã, mçi h¹ng thøc cô thÓ sÏ chØ ®Þnh mét ®èi t−îng cô thÓ trong miÒn ®èi t−îng. Ch¼ng h¹n, nÕu An lμ mét ký hiÖu h»ng, Father lμ mét ký hiÖu hμm, nÕu trong minh ho¹ An øng víi mét ng−êi cô thÓ nμo ®ã, cßn Father(x) g¾n víi hμm; øng víi mçi x lμ cha cña nã, th× h¹ng thøc Father(An) sÏ chØ ng−êi cha cña An . Ng÷ nghÜa cña c¸c c©u ®¬n Trong mét minh ho¹, c¸c ký hiÖu vÞ tõ sÏ ®−îc g¾n víi mét thuéc tÝnh, hoÆc mét quan hÖ cô thÓ nμo ®ã. Khi ®ã mçi c«ng thøc ph©n tö (kh«ng chøa biÕn) sÏ chØ ®Þnh mét sù kiÖn cô thÓ. §−¬ng nhiªn sù kiÖn nμy cã thÓ lμ ®óng (True) hoÆc sai (False). Ch¼ng h¹n, nÕu trong minh ho¹, ký hiÖu h»ng Lan øng víi mét c« g¸i cô thÓ nμo ®ã, cßn Student(x) øng víi thuéc tÝnh “x lμ sinh viªn” th× c©u Student (Lan) cã gi¸ trÞ ch©n trÞ lμ True hoÆc False tuú thuéc trong thùc tÕ Lan cã ph¶i lμ sinh viªn hay kh«ng. 23
24. Ng÷ nghÜa cña c¸c c©u phøc hîp Khi ®· x¸c ®Þnh ®−îc ng÷ nghÜa cña c¸c c©u ®¬n, ta cã thÓ thùc hiÖn ®−îc ng÷ nghÜa cña c¸c c©u phøc hîp (®−îc t¹o thμnh tõ c¸c c©u ®¬n b»ng c¸ch liªn kÕt c¸c c©u ®¬n bëi c¸c kÕt nèi logic) nh− trong logic mÖnh ®Ò. VÝ dô: C©u Student(Lan) ∧ Student(An) nhËn gi¸ trÞ True nÕu c¶ hai c©u Student(Lan) vμ Student(An) ®Òu cã gi¸ trÞ True, tøc lμ c¶ Lan vμ An ®Òu lμ sinh viªn. C©u Like(Lan, Rose) ∨ Like(An, Tulip) lμ ®óng nÕu c©u Like(Lan, Rose) lμ ®óng hay c©u Like(An, Tulip) lμ ®óng. Ng÷ nghÜa cña c¸c c©u chøa c¸c l−îng tö Ng÷ nghÜa cña c¸c c©u ∀ x G, trong ®ã G lμ mét c«ng thøc nμo ®ã, ®−îc x¸c ®Þnh nh− lμ ng÷ nghÜa cña c«ng thøc lμ héi cña tÊt c¶ c¸c c«ng thøc nhËn ®−îc tõ c«ng thøc G b»ng c¸ch thay x bëi mét ®èi t−îng trong miÒn ®èi t−îng. Ch¼ng h¹n, nÕu miÒn ®èi t−îng gåm ba ng−êi {Lan, An, Hoa} th× ng÷ nghÜa cña c©u ∀ x Student(x) ®−îc x¸c ®Þnh lμ ng÷ nghÜa cña c©u Student(Lan) ∧ Student(An) ∧ Student(Hoa). C©u nμy ®óng khi vμ chØ khi c¶ ba c©u thμnh phÇn ®Òu ®óng, tøc lμ c¶ Lan, An, Hoa ®Òu lμ sinh viªn. Nh− vËy, c«ng thøc ∀ x G lμ ®óng nÕu vμ chØ nÕu mäi c«ng thøc nhËn ®−îc tõ G b»ng c¸ch thay x bëi mäi ®èi t−îng trong miÒn ®èi t−îng ®Òu ®óng, tøc lμ G ®óng cho tÊt c¶ c¸c ®èi t−îng x trong miÒn ®èi t−îng. Ng÷ nghÜa cña c«ng thøc ∃ x G ®−îc x¸c ®Þnh nh− lμ ng÷ nghÜa cña c«ng thøc lμ tuyÓn cña tÊt c¶ c¸c c«ng thøc nhËn ®−îc tõ G b»ng c¸ch thay x bëi mét ®èi t−îng trong miÒn ®èi t−îng. Ch¼ng h¹n, nÕu ng÷ nghÜa cña c©u Younger(x, 20) lμ “ x trÎ h¬n 30 tuæi ” vμ miÒn ®èi t−îng gåm ba ng−êi {Lan, An, Hoa} th× ng÷ nghÜa cña c©u ∃ x Yourger(x, 20) lμ ng÷ nghÜa cña c©u Yourger(Lan, 20) ∨ Yourger(An, 20) ∨ Yourger(Hoa, 20). C©u nμy nhËn gi¸ trÞ True nÕu vμ chØ nÕu Ýt nhÊt mét trong ba ng−êi Lan, An, Hoa trÎ h¬n 20. Nh− vËy c«ng thøc ∃ x G lμ ®óng nÕu vμ chØ nÕu mét trong c¸c c«ng thøc nhËn ®−îc tõ G b»ng c¸ch thay x b»ng mét ®èi t−îng trong miÒn ®èi t−îng lμ ®óng. B»ng c¸c ph−¬ng ph¸p ®· tr×nh bμy ë trªn, ta cã thÓ x¸c ®Þnh ®−îc gi¸ trÞ ch©n trÞ (True,False) cña mét c«ng thøc bÊt kú trong mét minh ho¹. (l−u ý r»ng, ta chØ quan t©m tíi c¸c c«ng thøc ®óng). Sau khi ®· x¸c ®Þnh kh¸i niÖm minh ho¹ vμ gi¸ trÞ ch©n trÞ cña mét c«ng thøc trong mét minh ho¹, cã thÓ ®−a ra c¸c kh¸i niÖm c«ng thøc v÷ng ch¾c ( tho¶ ®−îc, kh«ng tho¶ ®−îc ), m« h×nh cña c«ng thøc gièng nh− trong logic mÖnh ®Ò. C¸c c«ng thøc t−¬ng ®−¬ng Còng nh− trong logic mÖnh ®Ò, ta nãi hai c«ng thøc G vμ H t−¬ng ®−¬ng ( viÕt lμ G ≡ H ) nÕu chóng cïng ®óng hoÆc cïng sai trong mét minh ho¹. Ngoμi c¸c t−¬ng ®−¬ng ®· biÕt trong logic mÖnh ®Ò, trong logic vÞ tõ cÊp mét cßn cã c¸c t−¬ng ®−¬ng kh¸c liªn quan tíi c¸c l−îng tö. Gi¶ sö G lμ mét c«ng thøc, c¸ch viÕt G(x) nãi r»ng c«ng thøc G cã chøa c¸c xuÊt hiÖn cña biÕn x. Khi ®ã c«ng thøc G(y) lμ c«ng thøc nhËn ®−îc tõ G(x) b»ng c¸ch thay tÊt c¶ c¸c xuÊt hiÖn cña x bëi y. Ta nãi G(y) lμ c«ng thøc nhËn ®−îc tõ G(x) b»ng c¸ch ®Æt tªn l¹i ( biÕn x ®−îc ®æi tªn l¹i lμ y ). 24
25. §Þnh nghÜa: mét c«ng thøc F trong logic vÞ tõ cÊp mét lμ d¹ng prenex chuÈn nÕu vμ chØ nÕu F ë d¹ng thøc sau: (Q1 x1) (Qn xn)(M) Trong ®ã (Qi xi), ∀ i=1 n th× hoÆc (∀ xi) hoÆc ( ∃ xi)vμ M kh«ng chøa l−îng tö, (Q1 x1) (Qn xn) gäi lμ tiÒn tè vμ M lμ ma trËn cña c«ng thøc F Chóng ta cã c¸c t−¬ng ®−¬ng sau ®©y: 1. ∀ x G(x) ≡ ∀ y G(y) ∃ x G(x) ≡ ∃ y G(y) §Æt tªn l¹i biÕn ®i sau l−îng tö phæ dông ( tån t¹i ), ta nhËn ®−îc c«ng thøc t−¬ng ®−¬ng. VÝ dô : ∀ x Love(x, Husband(x)) ≡ ∀ y Love(y, Husband(y)) 2. ¬(∀ x G(x)) ≡ ∃ x (¬ G(x)) ¬( ∃ x G(x)) ≡ ∀ x (¬ G(x)) 3. ∀ x (G(x) ∧ H(x)) ≡ ∀ x G(x) ∧ ∀ x H(x) ∃ x (G(x) ∨ H(x)) ≡ ∃ x G(x) ∨ ∃ x H(x) 4. (Qx)F(x) ∨ G ≡ (Qx)(F(x) ∨ G) 5. (Qx)F(x) ∧ G ≡ (Qx)(F(x) ∧ G) III. Bμi tËp 1. Đặt P(x): x là số hửu tỷ, Q(x): x là số thực. Mô tả các câu sau dưới dạng logic vị từ cấp một a. Mỗi số hữu tỷ là số thực b. Vài số thực là số hửu tỷ c. Không phải tất cả số thực là số hửu tỷ 2. Đặt C(x): x là người bán xe hơi cũ và H(x): x thành thật. Hãy phát biểu các công thức sau đây: a. ∃ x C(x) b. ∃ x H(x) c. ∀ x (C(x) → ¬H(x)) d. ∃ x (C(x) ∧ H(x)) e. ∃ x (H(x) → C(x)) 3. Đặt P(x): x là một điểm, L(x): x là một đường, R(x,y,z): z đi qua x và y, E(x,y): x=y. Mô tả các câu sau dưới dạng logic vị từ cấp một: Với mỗi hai điểm khác nhau, có một và chỉ một đường qua hai điểm 4. Một nhóm Abelian là một tập hợp A với một toán tử nhị phân +. Đặt P(x,y,z) và E(x,y) biểu diễn x+y=z và x=y tương ứng. Mô tả các tiên đề cho nhóm Abelian dưới dạng logic vị từ cấp một a. Với mỗi x, y trong A, Có tồn tại một z trong trong A sao cho x+y=z (đóng) b. Nếu x+y=z và x+y=w thì z=w (duy nhất) c. (x+y)+z = x+(y+z) (liên kết) d. x+y = y+x (đối xứng) 25
26. e. Cho mỗi x và y trong A, tồn tại z sao cho x+z=y (giải pháp đúng) 5. Cho minh hoạ sau (D={a,b}) P(a,a) P(a,b) P(b,a) P(b,b) T F F T xác định giá trị đúng của các công thức sau: ∀ x ∃ y P(x,y) ∀ x ∀ y P(x,y) ∃ x ∀ y P(x,y) ∃ y ¬P(a,y) ∀ x ∀ y (P(x,y) →P(y,x)) ∀ x P(x,x) 6. Xét công thức sau: A: ∃ x P(x) →∀ x P(x) a. Chứng minh rằng công thức này luôn luôn đúng nếu miền giá trị D chỉ có một phần tử b. Đặt D={a,b}. Tìm một minh hoạ trên D mà A là F 7. Xem minh hoạ sau: Miền giá trị D={1,2} Phép gán hằng a và b a b 1 2 Phép gán hàm f f(1) f(2) 2 1 Phép gán cho vị từ P P(1,1) P(1,2) P(2,1) P(2,2) T T F F Lượng giá giá trị đúng của các công thức sau theo các phép gán trên P(a,f(a)) ∧ P(b, f(b)) ∀ x ∃ y P(y,x) ∀ x ∀ y (P(x,y) → P(f(x),f(y))) 8. Đặt 26
27. F1: ∀ x (P(x) → Q(x)) F2: ¬Q(a) Chứng minh rằng ¬P(a) là hệ quả logic của F1 và F2 9. Chuyển các công thức sau thành dạng prenex chuẩn: a. ∀ x (P(x) → ∃ y Q(x, y)) b. ∃ x ¬( ∃ y P(x,y) → (∃ z Q(z) → R(x))) c. ∀ x ∀ y ( ∃ z P(x,y,z) ∧ ( ∃ u Q(x, u) →∃ v Q(y, v))) 10. Xem xét các câu sau: F1: Mỗi sinh viên thì thành thật F2: An không thành thật Chứng minh An không là một sinh viên Xem xét các tiền đề sau (1) Tất cả vận động viên thì khoẻ (2) Người nào vừa khoẻ và thông minh thì sẽ thành công trong sự nghiệp (3) An là vận động viên (4) An thông minh Hãy kết luận rằng An sẽ thành công trong sự nghiệp 12. Giả sử rằng Sơn được yêu bởi bất cứ người nào mà có yêu ai đó. Giả sử thêm rằng không ai không yêu người nào. Chứng tỏ rằng Sơn được yêu bởi ai đó. 27
28. PhÇn II Gi¶i quyÕt vÊn ®Ò b»ng t×m kiÕm VÊn ®Ò t×m kiÕm, mét c¸ch tæng qu¸t, cã thÓ hiÓu lμ t×m mét ®èi t−îng tháa m·n mét sè ®ßi hái nμo ®ã, trong mét tËp hîp réng lín c¸c ®èi t−îng. Chóng ta cã thÓ kÓ ra rÊt nhiÒu vÊn ®Ò mμ viÖc gi¶i quyÕt nã ®−îc quy vÒ vÊn ®Ò t×m kiÕm. C¸c trß ch¬i, ch¼ng h¹n cê vua, cê car« cã thÓ xem nh− vÊn ®Ò t×m kiÕm. Trong sè rÊt nhiÒu n−íc ®i ®−îc phÐp thùc hiÖn, ta ph¶i t×m ra c¸c n−íc ®i dÉn tíi t×nh thÕ kÕt cuéc mμ ta lμ ng−êi th¾ng. Chøng minh ®Þnh lý còng cã thÓ xem nh− vÊn ®Ò t×m kiÕm. Cho mét tËp c¸c tiªn ®Ò vμ c¸c luËt suy diÔn, trong tr−êng hîp nμy môc tiªu cña ta lμ t×m ra mét chøng minh (mét d·y c¸c luËt suy diÔn ®−îc ¸p dông) ®Ó ®−îc ®−a ®Õn c«ng thøc mμ ta cÇn chøng minh. Trong c¸c lÜnh vùc nghiªn cøu cña TrÝ TuÖ Nh©n T¹o, chóng ta th−êng xuyªn ph¶i ®èi ®Çu víi vÊn ®Ò t×m kiÕm. §Æc biÖt trong lËp kÕ ho¹ch vμ häc m¸y, t×m kiÕm ®ãng vai trß quan träng. Trong phÇn nμy chóng ta sÏ nghiªn cøu c¸c kü thuËt t×m kiÕm c¬ b¶n ®−îc ¸p dông ®Ó gi¶i quyÕt c¸c vÊn ®Ò vμ ®−îc ¸p dông réng r·i trong c¸c lÜnh vùc nghiªn cøu kh¸c cña TrÝ TuÖ Nh©n T¹o. Chóng ta lÇn l−ît nghiªn cøu c¸c kü thuËt sau: C¸c kü thuËt t×m kiÕm mï, trong ®ã chóng ta kh«ng cã hiÓu biÕt g× vÒ c¸c ®èi t−îng ®Ó h−íng dÉn t×m kiÕm mμ chØ ®¬n thuÇn lμ xem xÐt theo mét hÖ thèng nμo ®ã tÊt c¶ c¸c ®èi t−îng ®Ó ph¸t hiÖn ra ®èi t−îng cÇn t×m. C¸c kü thuËt t×m kiÕm kinh nghiÖm (t×m kiÕm heuristic) trong ®ã chóng ta dùa vμo kinh nghiÖm vμ sù hiÓu biÕt cña chóng ta vÒ vÊn ®Ò cÇn gi¶i quyÕt ®Ó x©y dùng nªn hμm ®¸nh gi¸ h−íng dÉn sù t×m kiÕm. C¸c kü thuËt t×m kiÕm tèi −u. C¸c ph−¬ng ph¸p t×m kiÕm cã ®èi thñ, tøc lμ c¸c chiÕn l−îc t×m kiÕm n−íc ®i trong c¸c trß ch¬i hai ng−êi, ch¼ng h¹n cê vua, cê t−íng, cê car«. 28
29. Ch−¬ng III C¸c chiÕn l−îc t×m kiÕm mï Trong ch−¬ng nμy, chóng ta sÏ nghiªn cøu c¸c chiÕn l−îc t×m kiÕm mï (blind search): t×m kiÕm theo bÒ réng (breadth-first search) vμ t×m kiÕm theo ®é s©u (depth-first search). HiÖu qu¶ cña c¸c ph−¬ng ph¸p t×m kiÕm nμy còng sÏ ®−îc ®¸nh gi¸. I. BiÓu diÔn vÊn ®Ò trong kh«ng gian tr¹ng th¸i Mét khi chóng ta muèn gi¶i quyÕt mét vÊn ®Ò nμo ®ã b»ng t×m kiÕm, ®Çu tiªn ta ph¶i x¸c ®Þnh kh«ng gian t×m kiÕm. Kh«ng gian t×m kiÕm bao gåm tÊt c¶ c¸c ®èi t−îng mμ ta cÇn quan t©m t×m kiÕm. Nã cã thÓ lμ kh«ng gian liªn tôc, ch¼ng h¹n kh«ng gian c¸c vÐct¬ thùc n chiÒu; nã còng cã thÓ lμ kh«ng gian c¸c ®èi t−îng rêi r¹c. Trong môc nμy ta sÏ xÐt viÖc biÓu diÔn mét vÊn ®Ò trong kh«ng gian tr¹ng th¸i sao cho viÖc gi¶i quyÕt vÊn ®Ò ®−îc quy vÒ viÖc t×m kiÕm trong kh«ng gian tr¹ng th¸i. Mét ph¹m vi réng lín c¸c vÊn ®Ò, ®Æc biÖt c¸c c©u ®è, c¸c trß ch¬i, cã thÓ m« t¶ b»ng c¸ch sö dông kh¸i niÖm tr¹ng th¸i vμ to¸n tö (phÐp biÕn ®æi tr¹ng th¸i). Ch¼ng h¹n, mét kh¸ch du lÞch cã trong tay b¶n ®å m¹ng l−íi giao th«ng nèi c¸c thμnh phè trong mét vïng l·nh thæ (h×nh 3.1), du kh¸ch ®ang ë thμnh phè A vμ anh ta muèn t×m ®−êng ®i tíi th¨m thμnh phè B. Trong bμi to¸n nμy, c¸c thμnh phè cã trong c¸c b¶n ®å lμ c¸c tr¹ng th¸i, thμnh phè A lμ tr¹ng th¸i ban ®Çu, B lμ tr¹ng th¸i kÕt thóc. Khi ®ang ë mét thμnh phè, ch¼ng h¹n ë thμnh phè D anh ta cã thÓ ®i theo c¸c con ®−êng ®Ó nèi tíi c¸c thμnh phè C, F vμ G. C¸c con ®−êng nèi c¸c thμnh phè sÏ ®−îc biÓu diÔn bëi c¸c to¸n tö. Mét to¸n tö biÕn ®æi mét tr¹ng th¸i thμnh mét tr¹ng th¸i kh¸c. Ch¼ng h¹n, ë tr¹ng th¸i D sÏ cã ba to¸n tö dÉn tr¹ng th¸i D tíi c¸c tr¹ng th¸i C, F vμ G. H×nh 3.1 T×m ®−êng ®i tõ A tíi B VÊn ®Ò cña du kh¸ch b©y giê sÏ lμ t×m mét d·y to¸n tö ®Ó ®−a tr¹ng th¸i ban ®Çu A tíi tr¹ng th¸i kÕt thóc B. 29
30. Mét vÝ dô kh¸c, trong trß ch¬i cê vua, mçi c¸ch bè trÝ c¸c qu©n trªn bμn cê lμ mét tr¹ng th¸i. Tr¹ng th¸i ban ®Çu lμ sù s¾p xÕp c¸c qu©n lóc b¾t ®Çu cuéc ch¬i. Mçi n−íc ®i hîp lÖ lμ mét to¸n tö, nã biÕn ®æi mét c¶nh huèng trªn bμn cê thμnh mét c¶nh huèng kh¸c. Nh− vËy muèn biÓu diÔn mét vÊn ®Ò trong kh«ng gian tr¹ng th¸i, ta cÇn x¸c ®Þnh c¸c yÕu tè sau: Tr¹ng th¸i ban ®Çu. Mét tËp hîp c¸c to¸n tö. Trong ®ã mçi to¸n tö m« t¶ mét hμnh ®éng hoÆc mét phÐp biÕn ®æi cã thÓ ®−a mét tr¹ng th¸i tíi mét tr¹ng th¸i kh¸c. TËp hîp tÊt c¶ c¸c tr¹ng th¸i cã thÓ ®¹t tíi tõ tr¹ng th¸i ban ®Çu b»ng c¸ch ¸p dông mét d·y to¸n tö, lËp thμnh kh«ng gian tr¹ng th¸i cña vÊn ®Ò. Ta sÏ ký hiÖu kh«ng gian tr¹ng th¸i lμ U, tr¹ng th¸i ban ®Çu lμ u0 (u0 ∈ U). Mçi to¸n tö R cã thÓ xem nh− mét ¸nh x¹ R: U → U. Nãi chung R lμ mét ¸nh x¹ kh«ng x¸c ®Þnh kh¾p n¬i trªn U. Mét tËp hîp T c¸c tr¹ng th¸i kÕt thóc (tr¹ng th¸i ®Ých). T lμ tËp con cña kh«ng gian U. Trong vÊn ®Ò cña du kh¸ch trªn, chØ cã mét tr¹ng th¸i ®Ých, ®ã lμ thμnh phè B. Nh−ng trong nhiÒu vÊn ®Ò (ch¼ng h¹n c¸c lo¹i cê) cã thÓ cã nhiÒu tr¹ng th¸i ®Ých vμ ta kh«ng thÓ x¸c ®Þnh tr−íc ®−îc c¸c tr¹ng th¸i ®Ých. Nãi chung trong phÇn lín c¸c vÊn ®Ò ta chØ cã thÓ m« t¶ c¸c tr¹ng th¸i ®Ých lμ c¸c tr¹ng th¸i tháa m·n mét sè ®iÒu kiÖn nμo ®ã. Khi chóng ta biÓu diÔn mét vÊn ®Ò th«ng qua c¸c tr¹ng th¸i vμ c¸c to¸n tö, th× viÖc t×m nghiÖm cña bμi to¸n ®−îc quy vÒ viÖc t×m ®−êng ®i tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i ®Ých. (Mét ®−êng ®i trong kh«ng gian tr¹ng th¸i lμ mét d·y to¸n tö dÉn mét tr¹ng th¸i tíi mét tr¹ng th¸i kh¸c). Chóng ta cã thÓ biÓu diÔn kh«ng gian tr¹ng th¸i b»ng ®å thÞ ®Þnh h−íng, trong ®ã mçi ®Ønh cña ®å thÞ t−¬ng øng víi mét tr¹ng th¸i. NÕu cã to¸n tö R biÕn ®æi tr¹ng th¸i u thμnh tr¹ng th¸i v, th× cã cung g¸n nh·n R ®i tõ ®Ønh u tíi ®Ønh v. Khi ®ã mét ®−êng ®i trong kh«ng gian tr¹ng th¸i sÏ lμ mét ®−êng ®i trong ®å thÞ nμy. Sau ®©y chóng ta sÏ xÐt mét sè vÝ dô vÒ c¸c kh«ng gian tr¹ng th¸i ®−îc x©y dùng cho mét sè vÊn ®Ò. VÝ dô 1: Bμi to¸n 8 sè. Chóng ta cã b¶ng 3x3 « vμ t¸m qu©n mang sè hiÖu tõ 1 ®Õn 8 ®−îc xÕp vμo t¸m «, cßn l¹i mét « trèng, ch¼ng h¹n nh− trong h×nh 2 bªn tr¸i. Trong trß ch¬i nμy, b¹n cã thÓ chuyÓn dÞch c¸c qu©n ë c¹ch « trèng tíi « trèng ®ã. VÊn ®Ò cña b¹n lμ t×m ra mét d·y c¸c chuyÓn dÞch ®Ó biÕn ®æi c¶nh huèng ban ®Çu (h×nh 3.2 bªn tr¸i) thμnh mét c¶nh huèng x¸c ®Þnh nμo ®ã, ch¼ng h¹n c¶nh huèng trong h×nh 3.2 bªn ph¶i. H×nh 3.2 Tr¹ng th¸i ban ®Çu vμ tr¹ng th¸i kÕt thóc cña bμi to¸n sè. 30
31. Trong bμi to¸n nμy, tr¹ng th¸i ban ®Çu lμ c¶nh huèng ë bªn tr¸i h×nh 3.2, cßn tr¹ng th¸i kÕt thóc ë bªn ph¶i h×nh 3.2. T−¬ng øng víi c¸c quy t¾c chuyÓn dÞch c¸c qu©n, ta cã bèn to¸n tö: up (®Èy qu©n lªn trªn), down (®Èy qu©n xuèng d−íi), left (®Èy qu©n sang tr¸i), right (®Èy qu©n sang ph¶i). Râ rμng lμ, c¸c to¸n tö nμy chØ lμ c¸c to¸n tö bé phËn; ch¼ng h¹n, tõ tr¹ng th¸i ban ®Çu (h×nh 3.2), ta chØ cã thÓ ¸p dông c¸c to¸n tö down, left, right. Trong c¸c vÝ dô trªn viÖc t×m ra mét biÓu diÔn thÝch hîp ®Ó m« t¶ c¸c tr¹ng th¸i cña vÊn ®Ò lμ kh¸ dÔ dμng vμ tù nhiªn. Song trong nhiÒu vÊn ®Ò viÖc t×m hiÓu ®−îc biÓu diÔn thÝch hîp cho c¸c tr¹ng th¸i cña vÊn ®Ò lμ hoμn toμn kh«ng ®¬n gi¶n. ViÖc t×m ra d¹ng biÓu diÔn tèt cho c¸c tr¹ng th¸i ®ãng vai trß hÕt søc quan träng trong qu¸ tr×nh gi¶i quyÕt mét vÊn ®Ò. Cã thÓ nãi r»ng, nÕu ta t×m ®−îc d¹ng biÓu diÔn tèt cho c¸c tr¹ng th¸i cña vÊn ®Ò, th× vÊn ®Ò hÇu nh− ®· ®−îc gi¶i quyÕt. VÝ dô 2: VÊn ®Ò triÖu phó vμ kÎ c−íp. Cã ba nhμ triÖu phó vμ ba tªn c−íp ë bªn bê t¶ ng¹n mét con s«ng, cïng mét chiÕc thuyÒn chë ®−îc mét hoÆc hai ng−êi. H·y t×m c¸ch ®−a mäi ng−êi qua s«ng sao cho kh«ng ®Ó l¹i ë bªn bê s«ng kÎ c−íp nhiÒu h¬n triÖu phó. §−¬ng nhiªn trong bμi to¸n nμy, c¸c to¸n tö t−¬ng øng víi c¸c hμnh ®éng chë 1 hoÆc 2 ng−êi qua s«ng. Nh−ng ë ®©y ta cÇn l−u ý r»ng, khi hμnh ®éng xÈy ra (lóc thuyÒn ®ang b¬i qua s«ng) th× ë bªn bê s«ng thuyÒn võa dêi chç, sè kÎ c−íp kh«ng ®−îc nhiÒu h¬n sè triÖu phó. TiÕp theo ta cÇn quyÕt ®Þnh c¸i g× lμ tr¹ng th¸i cña vÊn ®Ò. ë ®©y ta kh«ng cÇn ph©n biÖt c¸c nhμ triÖu phó vμ c¸c tªn c−íp, mμ chØ sè l−îng cña hä ë bªn bê s«ng lμ quan träng. §Ó biÓu diÔn c¸c tr¹ng th¸i, ta sö dông bé ba (a, b, k), trong ®ã a lμ sè triÖu phó, b lμ sè kÎ c−íp ë bªn bê t¶ ng¹n vμo c¸c thêi ®iÓm mμ thuyÒn ë bê nμy hoÆc bê kia, k = 1 nÕu thuyÒn ë bê t¶ ng¹n vμ k = 0 nÕu thuyÒn ë bê h÷u ng¹n. Nh− vËy, kh«ng gian tr¹ng th¸i cho bμi to¸n triÖu phó vμ kÎ c−íp ®−îc x¸c ®Þnh nh− sau: Tr¹ng th¸i ban ®Çu lμ (3, 3, 1). C¸c to¸n tö. Cã n¨m to¸n tö t−¬ng øng víi hμnh ®éng thuyÒn chë qua s«ng 1 triÖu phó, hoÆc 1 kÎ c−íp, hoÆc 2 triÖu phó, hoÆc 2 kÎ c−íp, hoÆc 1 triÖu phó vμ 1 kÎ c−íp. Tr¹ng th¸i kÕt thóc lμ (3, 3, 0). II. C¸c chiÕn l−îc t×m kiÕm Nh− ta ®· thÊy trong môc 1.1, ®Ó gi¶i quyÕt mét vÊn ®Ò b»ng t×m kiÕm trong kh«ng gian tr¹ng th¸i, ®Çu tiªn ta cÇn t×m d¹ng thÝch hîp m« t¶ c¸c tr¹ng th¸i cña vÊn ®Ò. Sau ®ã cÇn x¸c ®Þnh: Tr¹ng th¸i ban ®Çu. TËp c¸c to¸n tö. TËp T c¸c tr¹ng th¸i kÕt thóc. (T cã thÓ kh«ng ®−îc x¸c ®Þnh cô thÓ gåm c¸c tr¹ng th¸i nμo mμ chØ ®−îc chØ ®Þnh bëi mét sè ®iÒu kiÖn nμo ®ã). Gi¶ sö u lμ mét tr¹ng th¸i nμo ®ã vμ R lμ mét to¸n tö biÕn ®æi u thμnh v. Ta sÏ gäi v lμ tr¹ng th¸i kÒ u, hoÆc v ®−îc sinh ra tõ tr¹ng th¸i u bëi to¸n tö R. Qu¸ tr×nh ¸p dông c¸c to¸n tö ®Ó sinh ra c¸c tr¹ng th¸i kÒ u ®−îc gäi lμ ph¸t triÓn tr¹ng th¸i u. Ch¼ng h¹n, trong bμi to¸n to¸n sè, ph¸t triÓn tr¹ng th¸i ban ®Çu (h×nh 2 bªn tr¸i), ta nhËn ®−îc ba tr¹ng th¸i kÒ (h×nh 3.3). 31
32. Khi chóng ta biÓu diÔn mét vÊn ®Ò cÇn gi¶i quyÕt th«ng qua c¸c tr¹ng th¸i vμ c¸c to¸n tö th× viÖc t×m lêi gi¶i cña vÊn ®Ò ®−îc quy vÒ viÖc t×m ®−êng ®i tõ tr¹ng th¸i ban ®Çu tíi mét tr¹ng th¸i kÕt thóc nμo ®ã. Cã thÓ ph©n c¸c chiÕn l−îc t×m kiÕm thμnh hai lo¹i: C¸c chiÕn l−îc t×m kiÕm mï. Trong c¸c chiÕn l−îc t×m kiÕm nμy, kh«ng cã mét sù h−íng dÉn nμo cho sù t×m kiÕm, mμ ta chØ ph¸t triÓn c¸c tr¹ng th¸i ban ®Çu cho tíi khi gÆp mét tr¹ng th¸i ®Ých nμo ®ã. Cã hai kü thuËt t×m kiÕm mï, ®ã lμ t×m kiÕm theo bÒ réng vμ t×m kiÕm theo ®é s©u. H×nh 3.3 Ph¸t triÔn mét tr¹ng th¸i T− t−ëng cña t×m kiÕm theo bÒ réng lμ c¸c tr¹ng th¸i ®−îc ph¸t triÓn theo thø tù mμ chóng ®−îc sinh ra, tøc lμ tr¹ng th¸i nμo ®−îc sinh ra tr−íc sÏ ®−îc ph¸t triÓn tr−íc. Trong nhiÒu vÊn ®Ò, dï chóng ta ph¸t triÓn c¸c tr¹ng th¸i theo hÖ thèng nμo (theo bÒ réng hoÆc theo ®é s©u) th× sè l−îng c¸c tr¹ng th¸i ®−îc sinh ra tr−íc khi ta gÆp tr¹ng th¸i ®Ých th−êng lμ cùc kú lín. Do ®ã c¸c thuËt to¸n t×m kiÕm mï kÐm hiÖu qu¶, ®ßi hái rÊt nhiÒu kh«ng gian vμ thêi gian. Trong thùc tÕ, nhiÒu vÊn ®Ò kh«ng thÓ gi¶i quyÕt ®−îc b»ng t×m kiÕm mï. • T×m kiÕm kinh nghiÖm (t×m kiÕm heuristic). Trong rÊt nhiÒu vÊn ®Ò, chóng ta cã thÓ dùa vμo sù hiÓu biÕt cña chóng ta vÒ vÊn ®Ò, dùa vμo kinh nghiÖm, trùc gi¸c, ®Ó ®¸nh gi¸ c¸c tr¹ng th¸i. Sö dông sù ®¸nh gi¸ c¸c tr¹ng th¸i ®Ó h−íng dÉn sù t×m kiÕm: trong qu¸ tr×nh ph¸t triÓn c¸c tr¹ng th¸i, ta sÏ chän trong sè c¸c tr¹ng th¸i chê ph¸t triÓn, tr¹ng th¸i ®−îc ®¸nh gi¸ lμ tèt nhÊt ®Ó ph¸t triÓn. Do ®ã tèc ®é t×m kiÕm sÏ nhanh h¬n. C¸c ph−¬ng ph¸p t×m kiÕm dùa vμo sù ®¸nh gi¸ c¸c tr¹ng th¸i ®Ó h−íng dÉn sù t×m kiÕm gäi chung lμ c¸c ph−¬ng ph¸p t×m kiÕm kinh nghiÖm. Nh− vËy chiÕn l−îc t×m kiÕm ®−îc x¸c ®Þnh bëi chiÕn l−îc chän tr¹ng th¸i ®Ó ph¸t triÓn ë mçi b−íc. Trong t×m kiÕm mï, ta chän tr¹ng th¸i ®Ó ph¸t triÓn theo thø tù mμ chóng ®−îc sinh ra; cßn trong t×m kiÕm kinh nghiÖm ta chän tr¹ng th¸i dùa vμo sù ®¸nh gi¸ c¸c tr¹ng th¸i. 32
33. Chóng ta cã thÓ nghÜ ®Õn qu¸ tr×nh t×m kiÕm nh− qu¸ tr×nh x©y dùng c©y t×m kiÕm. C©y t×m kiÕm lμ c©y mμ c¸c ®Ønh ®−îc g¾n bëi c¸c tr¹ng th¸i cña kh«ng gian tr¹ng th¸i. Gèc cña c©y t×m kiÕm t−¬ng øng víi tr¹ng th¸i ban ®Çu. NÕu mét ®Ønh øng víi tr¹ng th¸i u, th× c¸c ®Ønh con cña nã øng víi c¸c tr¹ng th¸i v kÒ u. H×nh 3.4a lμ ®å thÞ biÓu diÔn mét kh«ng gian tr¹ng th¸i víi tr¹ng th¸i ban ®Çu lμ A, h×nh 3.4b lμ c©y t×m kiÕm t−¬ng øng. H×nh 3.4 Mçi chiÕn l−îc t×m kiÕm trong kh«ng gian tr¹ng th¸i t−¬ng øng víi mét ph−¬ng ph¸p x©y dùng c©y t×m kiÕm. Qu¸ tr×nh x©y dùng c©y b¾t ®Çu tõ c©y chØ cã mét ®Ønh lμ tr¹ng th¸i ban ®Çu. Gi¶ sö tíi mét b−íc nμo ®ã trong chiÕn l−îc t×m kiÕm, ta ®· x©y dùng ®−îc mét c©y nμo ®ã, c¸c l¸ cña c©y t−¬ng øng víi c¸c tr¹ng th¸i ch−a ®−îc ph¸t triÓn. B−íc tiÕp theo phô thuéc vμo chiÕn l−îc t×m kiÕm mμ mét ®Ønh nμo ®ã trong c¸c l¸ ®−îc chän ®Ó ph¸t triÓn. Khi ph¸t triÓn ®Ønh ®ã, c©y t×m kiÕm ®−îc më réng b»ng c¸ch thªm vμo c¸c ®Ønh con cña ®Ønh ®ã. Kü thuËt t×m kiÕm theo bÒ réng (theo ®é s©u) t−¬ng øng víi ph−¬ng ph¸p x©y dùng c©y t×m kiÕm theo bÒ réng (theo ®é s©u). III. C¸c chiÕn l−îc t×m kiÕm mï Trong môc nμy chóng ta sÏ tr×nh bμy hai chiÕn l−îc t×m kiÕm mï: t×m kiÕm theo bÒ réng vμ t×m kiÕm theo ®é s©u. Trong t×m kiÕm theo bÒ réng, t¹i mçi b−íc ta sÏ chän tr¹ng th¸i ®Ó ph¸t triÓn lμ tr¹ng th¸i ®−îc sinh ra tr−íc c¸c tr¹ng th¸i chê ph¸t triÓn kh¸c. Cßn trong t×m kiÕm theo ®é s©u, tr¹ng th¸i ®−îc chän ®Ó ph¸t triÓn lμ tr¹ng th¸i ®−îc sinh ra sau cïng trong sè c¸c tr¹ng th¸i chê ph¸t triÓn. Chóng ta sö dông danh s¸ch L ®Ó l−u c¸c tr¹ng th¸i ®· ®−îc sinh ra vμ chê ®−îc ph¸t triÓn. Môc tiªu cña t×m kiÕm trong kh«ng gian tr¹ng th¸i lμ t×m ®−êng ®i tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i ®Ých, do ®ã ta cÇn l−u l¹i vÕt cña ®−êng ®i. Ta cã thÓ sö dông hμm father ®Ó l−u l¹i cha cña mçi ®Ønh trªn ®−êng ®i, father(v) = u nÕu cha cña ®Ønh v lμ u. III.1 T×m kiÕm theo bÒ réng ThuËt to¸n t×m kiÕm theo bÒ réng ®−îc m« t¶ bëi thñ tôc sau: procedure Breadth_First_Search; begin 1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu; 33
34. 2. loop do 2.1 if L rçng then {th«ng b¸o t×m kiÕm thÊt b¹i; stop}; 2.2 Lo¹i tr¹ng th¸i u ë ®Çu danh s¸ch L; 2.3 if u lμ tr¹ng th¸i kÕt thóc then {th«ng b¸o t×m kiÕm thμnh c«ng; stop}; 2.4 for mçi tr¹ng th¸i v kÒ u do { §Æt v vμo cuèi danh s¸ch L; father(v) ← u} end; Chóng ta cã mét sè nhËn xÐt sau ®©y vÒ thuËt to¸n t×m kiÕm theo bÒ réng: • Trong t×m kiÕm theo bÒ réng, tr¹ng th¸i nμo ®−îc sinh ra tr−íc sÏ ®−îc ph¸t triÓn tr−íc, do ®ã danh s¸ch L ®−îc xö lý nh− hμng ®îi. Trong b−íc 2.3, ta cÇn kiÓm tra xem u cã lμ tr¹ng th¸i kÕt thóc hay kh«ng. Nãi chung c¸c tr¹ng th¸i kÕt thóc ®−îc x¸c ®Þnh bëi mét sè ®iÒu kiÖn nμo ®ã, khi ®ã ta cÇn kiÓm tra xem u cã tháa m·n c¸c ®iÒu kiÖn ®ã hay kh«ng. • NÕu bμi to¸n cã nghiÖm (tån t¹i ®−êng ®i tõ tr¹ng th¸i ban ®Çu tíi tr¹ng th¸i ®Ých), th× thuËt to¸n t×m kiÕm theo bÒ réng sÏ t×m ra nghiÖm, ®ång thêi ®−êng ®i t×m ®−îc sÏ lμ ng¾n nhÊt. Trong tr−êng hîp bμi to¸n v« nghiÖm vμ kh«ng gian tr¹ng th¸i h÷u h¹n, thuËt to¸n sÏ dõng vμ cho th«ng b¸o v« nghiÖm. §¸nh gi¸ t×m kiÕm theo bÒ réng B©y giê ta ®¸nh gi¸ thêi gian vμ bé nhí mμ t×m kiÕm theo bÒ réng ®ßi hái. Gi¶ sö r»ng, mçi tr¹ng th¸i khi ®−îc ph¸t triÓn sÏ sinh ra b tr¹ng th¸i kÒ. Ta sÏ gäi b lμ nh©n tè nh¸nh. Gi¶ sö r»ng, nghiÖm cña bμi to¸n lμ ®−êng ®i cã ®é dμi d. Bëi nhiÒu nghiÖm cã thÓ ®−îc t×m ra t¹i mét ®Ønh bÊt kú ë møc d cña c©y t×m kiÕm, do ®ã sè ®Ønh cÇn xem xÐt ®Ó t×m ra nghiÖm lμ: 1 + b + b2 + + bd-1 + k Trong ®ã k cã thÓ lμ 1, 2, , bd. Do ®ã sè lín nhÊt c¸c ®Ønh cÇn xem xÐt lμ: 1 + b + b2 + + bd Nh− vËy, ®é phøc t¹p thêi gian cña thuËt to¸n t×m kiÕm theo bÒ réng lμ O(bd). §é phøc t¹p kh«ng gian còng lμ O(bd), bëi v× ta cÇn l−u vμo danh s¸ch L tÊt c¶ c¸c ®Ønh cña c©y t×m kiÕm ë møc d, sè c¸c ®Ønh nμy lμ bd. 34
35. §Ó thÊy râ t×m kiÕm theo bÒ réng ®ßi hái thêi gian vμ kh«ng gian lín tíi møc nμo, ta xÐt tr−êng hîp nh©n tè nh¸nh b = 10 vμ ®é s©u d thay ®æi. Gi¶ sö ®Ó ph¸t hiÖn vμ kiÓm tra 1000 tr¹ng th¸i cÇn 1 gi©y, vμ l−u gi÷ 1 tr¹ng th¸i cÇn 100 bytes. Khi ®ã thêi gian vμ kh«ng gian mμ thuËt to¸n ®ßi hái ®−îc cho trong b¶ng sau: §é s©u d Thêi gian Kh«ng gian 4 11 gi©y 1 MB 6 18 phót 111 MB 8 31 giê 11 GB 10 128 ngμy 1TB 12 35 n¨m 111 TB 14 3500 n¨m 11 PB III.2 T×m kiÕm theo ®é s©u Nh− ta ®· biÕt, t− t−ëng cña chiÕn l−îc t×m kiÕm theo ®é s©u lμ, t¹i mçi b−íc tr¹ng th¸i ®−îc chän ®Ó ph¸t triÓn lμ tr¹ng th¸i ®−îc sinh ra sau cïng trong sè c¸c tr¹ng th¸i chê ph¸t triÓn. Do ®ã thuËt to¸n t×m kiÕm theo ®é s©u lμ hoμn toμn t−¬ng tù nh− thuËt to¸n t×m kiÕm theo bÒ réng, chØ cã mét ®iÒu kh¸c lμ, ta xö lý danh s¸ch L c¸c tr¹ng th¸i chê ph¸t triÓn kh«ng ph¶i nh− hμng ®îi mμ nh− ng¨n xÕp. Cô thÓ lμ trong b−íc 2.4 cña thuËt to¸n t×m kiÕm theo bÒ réng, ta cÇn söa l¹i lμ “§Æt v vμo ®Çu danh s¸ch L”. Sau ®©y chóng ta sÏ ®−a ra c¸c nhËn xÐt so s¸nh hai chiÕn l−îc t×m kiÕm mï: • ThuËt to¸n t×m kiÕm theo bÒ réng lu«n lu«n t×m ra nghiÖm nÕu bμi to¸n cã nghiÖm. Song kh«ng ph¶i víi bÊt kú bμi to¸n cã nghiÖm nμo thuËt to¸n t×m kiÕm theo ®é s©u còng t×m ra nghiÖm! NÕu bμi to¸n cã nghiÖm vμ kh«ng gian tr¹ng th¸i h÷u h¹n, th× thuËt to¸n t×m kiÕm theo ®é s©u sÏ t×m ra nghiÖm. Tuy nhiªn, trong tr−êng hîp kh«ng gian tr¹ng th¸i v« h¹n, th× cã thÓ nã kh«ng t×m ra nghiÖm, lý do lμ ta lu«n lu«n ®i xuèng theo ®é s©u, nÕu ta ®i theo mét nh¸nh v« h¹n mμ nghiÖm kh«ng n»m trªn nh¸nh ®ã th× thuËt to¸n sÏ kh«ng dõng. Do ®ã ng−êi ta khuyªn r»ng, kh«ng nªn ¸p dông t×m kiÕm theo dé s©u cho c¸c bμi to¸n cã c©y t×m kiÕm chøa c¸c nh¸nh v« h¹n. • §é phøc t¹p cña thuËt to¸n t×m kiÕm theo ®é s©u. Gi¶ sö r»ng, nghiÖm cña bμi to¸n lμ ®−êng ®i cã ®é dμi d, c©y t×m kiÕm cã nh©n tè nh¸nh lμ b vμ cã chiÒu cao lμ d. Cã thÓ xÈy ra, nghiÖm lμ ®Ønh ngoμi cïng bªn ph¶i trªn møc d cña c©y t×m kiÕm, do ®ã ®é phøc t¹p thêi gian cña t×m kiÕm theo ®é s©u trong tr−êng hîp xÊu nhÊt lμ O(bd), tøc lμ còng nh− t×m kiÕm theo bÒ réng. Tuy nhiªn, trªn thùc tÕ ®èi víi nhiÒu bμi to¸n, t×m kiÕm theo ®é s©u thùc sù nhanh h¬n t×m kiÕm theo bÒ réng. Lý do lμ t×m kiÕm theo bÒ réng ph¶i xem xÐt toμn bé c©y t×m kiÕm tíi møc d-1, råi míi xem xÐt c¸c ®Ønh ë møc d. Cßn trong t×m kiÕm theo ®é s©u, cã thÓ ta chØ cÇn xem xÐt mét bé phËn nhá cña c©y t×m kiÕm th× ®· t×m ra nghiÖm. §Ó ®¸nh gi¸ ®é phøc t¹p kh«ng gian cña t×m kiÕm theo ®é s©u ta cã nhËn xÐt r»ng, khi ta ph¸t triÓn mét ®Ønh u trªn c©y t×m kiÕm theo ®é s©u, ta chØ cÇn l−u c¸c ®Ønh ch−a ®−îc ph¸t triÓn mμ chóng lμ c¸c ®Ønh con cña c¸c ®Ønh n»m trªn ®−êng ®i tõ gèc tíi ®Ønh u. Nh− vËy ®èi víi c©y t×m kiÕm cã nh©n tè nh¸nh b vμ ®é s©u lín nhÊt lμ d, ta chØ 35
36. cÇn l−u Ýt h¬n db ®Ønh. Do ®ã ®é phøc t¹p kh«ng gian cña t×m kiÕm theo ®é s©u lμ O(db), trong khi ®ã t×m kiÕm theo bÒ réng ®ßi hái kh«ng gian nhí O(bd)! III.3 C¸c tr¹ng th¸i lÆp Nh− ta thÊy trong môc 1.2, c©y t×m kiÕm cã thÓ chøa nhiÒu ®Ønh øng víi cïng mét tr¹ng th¸i, c¸c tr¹ng th¸i nμy ®−îc gäi lμ tr¹ng th¸i lÆp. Ch¼ng h¹n, trong c©y t×m kiÕm h×nh 4b, c¸c tr¹ng th¸i C, E, F lμ c¸c tr¹ng th¸i lÆp. Trong ®å thÞ biÓu diÔn kh«ng gian tr¹ng th¸i, c¸c tr¹ng th¸i lÆp øng víi c¸c ®Ønh cã nhiÒu ®−êng ®i dÉn tíi nã tõ tr¹ng th¸i ban ®Çu. NÕu ®å thÞ cã chu tr×nh th× c©y t×m kiÕm sÏ chøa c¸c nh¸nh víi mét sè ®Ønh lËp l¹i v« h¹n lÇn. Trong c¸c thuËt to¸n t×m kiÕm sÏ l·ng phÝ rÊt nhiÒu thêi gian ®Ó ph¸t triÓn l¹i c¸c tr¹ng th¸i mμ ta ®· gÆp vμ ®· ph¸t triÓn. V× vËy trong qu¸ tr×nh t×m kiÕm ta cÇn tr¸nh ph¸t sinh ra c¸c tr¹ng th¸i mμ ta ®· ph¸t triÓn. Chóng ta cã thÓ ¸p dông mét trong c¸c gi¶i ph¸p sau ®©y: 1. Khi ph¸t triÓn ®Ønh u, kh«ng sinh ra c¸c ®Ønh trïng víi cha cña u. 2. Khi ph¸t triÓn ®Ønh u, kh«ng sinh ra c¸c ®Ønh trïng víi mét ®Ønh nμo ®ã n»m trªn ®−êng ®i dÉn tíi u. 3. Kh«ng sinh ra c¸c ®Ønh mμ nã ®· ®−îc sinh ra, tøc lμ chØ sinh ra c¸c ®Ønh míi. Hai gi¶i ph¸p ®Çu dÔ cμi ®Æt vμ kh«ng tèn nhiÒu kh«ng gian nhí, tuy nhiªn c¸c gi¶i ph¸p nμy kh«ng tr¸nh ®−îc hÕt c¸c tr¹ng th¸i lÆp. §Ó thùc hiÖn gi¶i ph¸p thø 3 ta cÇn l−u c¸c tr¹ng th¸i ®· ph¸t triÓn vμo tËp Q, l−u c¸c tr¹ng th¸i chê ph¸t triÓn vμo danh s¸ch L. §−¬ng nhiªn, tr¹ng th¸i v lÇn ®Çu ®−îc sinh ra nÕu nã kh«ng cã trong Q vμ L. ViÖc l−u c¸c tr¹ng th¸i ®· ph¸t triÓn vμ kiÓm tra xem mét tr¹ng th¸i cã ph¶i lÇn ®Çu ®−îc sinh ra kh«ng ®ßi hái rÊt nhiÒu kh«ng gian vμ thêi gian. Chóng ta cã thÓ cμi ®Æt tËp Q bëi b¶ng b¨m. III.4 T×m kiÕm s©u lÆp Nh− chóng ta ®· nhËn xÐt, nÕu c©y t×m kiÕm chøa nh¸nh v« h¹n, khi sö dông t×m kiÕm theo ®é s©u, ta cã thÓ m¾c kÑt ë nh¸nh ®ã vμ kh«ng t×m ra nghiÖm. §Ó kh¾c phôc hoμn c¶nh ®ã, ta t×m kiÕm theo ®é s©u chØ tíi møc d nμo ®ã; nÕu kh«ng t×m ra nghiÖm, ta t¨ng ®é s©u lªn d+1 vμ l¹i t×m kiÕm theo ®é s©u tíi møc d+1. Qu¸ tr×nh trªn ®−îc lÆp l¹i víi d lÇn l−ît lμ 1, 2, dÕn mét ®é s©u max nμo ®ã. Nh− vËy, thuËt to¸n t×m kiÕm s©u lÆp (iterative deepening search) sÏ sö dông thñ tôc t×m kiÕm s©u h¹n chÕ (depth_limited search) nh− thñ tôc con. §ã lμ thñ tôc t×m kiÕm theo ®é s©u, nh−ng chØ ®i tíi ®é s©u d nμo ®ã råi quay lªn. Trong thñ tôc t×m kiÕm s©u h¹n chÕ, d lμ tham sè ®é s©u, hμm depth ghi l¹i ®é s©u cña mçi ®Ønh procedure Depth_Limited_Search(d); begin 1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu u0; depth(u0) ← 0; 2. loop do 2.1 if L rçng then 36
37. {th«ng b¸o thÊt b¹i; stop}; 2.2 Lo¹i tr¹ng th¸i u ë ®Çu danh s¸ch L; 2.3 if u lμ tr¹ng th¸i kÕt thóc then {th«ng b¸o thμnh c«ng; stop}; 2.4 if depth(u) ≤ d then for mçi tr¹ng th¸i v kÒ u do {§Æt v vμo ®Çu danh s¸ch L; depth(v) ← depth(u) + 1}; end; procedure Depth_Deepening_Search; begin for d ← 0 to max do {Depth_Limited_Search(d); if thμnh c«ng then exit} end; Kü thuËt t×m kiÕm s©u lÆp kÕt hîp ®−îc c¸c −u ®iÓm cña t×m kiÕm theo bÒ réng vμ t×m kiÕm theo ®é s©u. Chóng ta cã mét sè nhËn xÐt sau: Còng nh− t×m kiÕm theo bÒ réng, t×m kiÕm s©u lÆp lu«n lu«n t×m ra nghiÖm (nÕu bμi to¸n cã nghiÖm), miÔn lμ ta chän ®é s©u ®ñ lín. T×m kiÕm s©u lÆp chØ cÇn kh«ng gian nhí nh− t×m kiÕm theo ®é s©u. Trong t×m kiÕm s©u lÆp, ta ph¶i ph¸t triÓn lÆp l¹i nhiÒu lÇn cïng mét tr¹ng th¸i. §iÒu ®ã lμm cho ta cã c¶m gi¸c r»ng, t×m kiÕm s©u lÆp l·ng phÝ nhiÒu thêi gian. Thùc ra thêi gian tiªu tèn cho ph¸t triÓn lÆp l¹i c¸c tr¹ng th¸i lμ kh«ng ®¸ng kÓ so víi thêi gian t×m kiÕm theo bÒ réng. ThËt vËy, mçi lÇn gäi thñ tôc t×m kiÕm s©u h¹n chÕ tíi møc d, nÕu c©y t×m kiÕm cã nh©n tè nh¸nh lμ b, th× sè ®Ønh cÇn ph¸t triÓn lμ: 1 + b + b2 + + bd NÕu nghiÖm ë ®é s©u d, th× trong t×m kiÕm s©u lÆp, ta ph¶i gäi thñ tôc t×m kiÕm s©u h¹n chÕ víi ®é s©u lÇn l−ît lμ 0, 1, 2, , d. Do ®ã c¸c ®Ønh ë møc 1 ph¶i ph¸t triÓn lÆp d lÇn, c¸c ®Ønh ë møc 2 lÆp d-1 lÇn, , c¸c ®Ønh ë møc d lÆp 1 lÇn. Nh− vËy tæng sè ®Ønh cÇn ph¸t triÓn trong t×m kiÕm s©u lÆp lμ: (d+1)1 + db + (d-1)b2 + + 2bd-1 + 1bd Do ®ã thêi gian t×m kiÕm s©u lÆp lμ O(bd). Tãm l¹i, t×m kiÕm s©u lÆp cã ®é phøc t¹p thêi gian lμ O(bd) (nh− t×m kiÕm theo bÒ réng), vμ cã ®é phøc t¹p kh«ng gian lμ O(biÓu diÔn) (nh− t×m kiÕm theo ®é s©u). Nãi chung, chóng ta nªn ¸p dông t×m kiÕm s©u lÆp cho c¸c vÊn ®Ò cã kh«ng gian tr¹ng th¸i lín vμ ®é s©u cña nghiÖm kh«ng biÕt tr−íc. 37
38. IV. Quy vÊn ®Ò vÒ c¸c vÊn ®Ò con Chóng ta ®· nghiªn cøu viÖc biÓu diÔn vÊn ®Ò th«ng qua c¸c tr¹ng th¸i vμ c¸c to¸n tö. Khi ®ã viÖc t×m nghiÖm cña vÊn ®Ò ®−îc quy vÒ viÖc t×m ®−êng trong kh«ng gian tr¹ng th¸i. Trong môc nμy chóng ta sÏ nghiªn cøu mét ph−¬ng ph¸p luËn kh¸c ®Ó gi¶i quyÕt vÊn ®Ò, dùa trªn viÖc quy vÊn ®Ò vÒ c¸c vÊn ®Ò con. Quy vÊn ®Ò vÒ c¸c vÊn ®Ò con (cßn gäi lμ rót gän vÊn ®Ò) lμ mét ph−¬ng ph¸p ®−îc sö dông réng r·i nhÊt ®Ó gi¶i quyÕt c¸c vÊn ®Ò. Trong ®êi sèng hμng ngμy, còng nh− trong khoa häc kü thuËt, mçi khi gÆp mét vÊn ®Ò cÇn gi¶i quyÕt, ta vÉn th−êng cè g¾ng t×m c¸ch ®−a nã vÒ c¸c vÊn ®Ò ®¬n gi¶n h¬n. Qu¸ tr×nh rót gän vÊn ®Ò sÏ ®−îc tiÕp tôc cho tíi khi ta dÉn tíi c¸c vÊn ®Ò con cã thÓ gi¶i quyÕt ®−îc dÔ dμng. Sau ®©y chóng ta xÐt mét sè vÊn ®Ò. VÊn ®Ò tÝnh tÝch ph©n bÊt ®Þnh Gi¶ sö ta cÇn tÝnh mét tÝch ph©n bÊt ®Þnh, ch¼ng h¹n ∫(xex + x3) dx. Qu¸ tr×nh chóng ta vÉn th−êng lμm ®Ó tÝnh tÝch ph©n bÊt ®Þnh lμ nh− sau. Sö dông c¸c quy t¾c tÝnh tÝch ph©n (quy t¾c tÝnh tÝch ph©n cña mét tæng, quy t¾c tÝnh tÝch ph©n tõng phÇn ), sö dông c¸c phÐp biÕn ®æi biÕn sè, c¸c phÐp biÕn ®æi c¸c hμm (ch¼ng h¹n, c¸c phÐp biÕn ®æi l−îng gi¸c), ®Ó ®−a tÝch ph©n cÇn tÝnh vÒ tÝch ph©n cña c¸c hμm sè s¬ cÊp mμ chóng ta ®· biÕt c¸ch tÝnh. Ch¼ng h¹n, ®èi víi tÝch ph©n ∫(xex + x3) dx, ¸p dông quy t¾c tÝch ph©n cña tæng ta ®−a vÒ hai tÝch ph©n ∫xexdx vμ ∫x3dx. ¸p dông quy t¾c tÝch ph©n tõng phÇn ta ®−a tÝch ph©n ∫xexdx vÒ tÝch ph©n ∫exdx. Qu¸ tr×nh trªn cã thÓ biÓu diÔn bëi ®å thÞ trong h×nh 3.5. H×nh 3.5 Quy mét sè tÝch ph©n vÒ tÝch ph©n c¬ b¶n C¸c tÝch ph©n ∫exdx vμ ∫x3dx lμ c¸c tÝch ph©n c¬ b¶n ®· cã trong b¶ng tÝch ph©n. KÕt hîp c¸c kÕt qu¶ cña c¸c tÝch ph©n c¬ b¶n, ta nhËn ®−îc kÕt qu¶ cña tÝch ph©n ®· cho. Chóng ta cã thÓ biÓu diÔn viÖc quy mét vÊn ®Ò vÒ c¸c vÊn ®Ò con c¬ bëi c¸c tr¹ng th¸i vμ c¸c to¸n tö. ë ®©y, bμi to¸n cÇn gi¶i lμ tr¹ng th¸i ban ®Çu. Mçi c¸ch quy bμi to¸n vÒ c¸c bμi to¸n con ®−îc biÓu diÔn bëi mét to¸n tö, to¸n tö A→B, C biÓu diÔn viÖc quy bμi to¸n A vÒ hai bμi to¸n B vμ C. Ch¼ng h¹n, ®èi víi bμi to¸n tÝnh tÝch ph©n bÊt ®Þnh, ta cã thÓ x¸c ®Þnh c¸c to¸n tö d¹ng: ∫(f1 + f2) dx → ∫f1 dx, ∫f2 dx vμ ∫u dv → ∫v du C¸c tr¹ng th¸i kÕt thóc lμ c¸c bμi to¸n s¬ cÊp (c¸c bμi to¸n ®· biÕt c¸ch gi¶i). Ch¼ng h¹n, trong bμi to¸n tÝnh tÝch ph©n, c¸c tÝch ph©n c¬ b¶n lμ c¸c tr¹ng th¸i kÕt thóc. Mét 38
39. ®iÒu cÇn l−u ý lμ, trong kh«ng gian tr¹ng th¸i biÓu diÔn viÖc quy vÊn ®Ò vÒ c¸c vÊn ®Ò con, c¸c to¸n tö cã thÓ lμ ®a trÞ, nã biÕn ®æi mét tr¹ng th¸i thμnh nhiÒu tr¹ng th¸i kh¸c. VÊn ®Ò t×m ®−êng ®i trªn b¶n ®å giao th«ng Bμi to¸n nμy ®· ®−îc ph¸t triÓn nh− bμi to¸n t×m ®−êng ®i trong kh«ng gian tr¹ng th¸i (xem 3.1), trong ®ã mçi tr¹ng th¸i øng víi mét thμnh phè, mçi to¸n tö øng víi mét con ®−êng nèi, nèi thμnh phè nμy víi thμnh phè kh¸c. B©y giê ta ®−a ra mét c¸ch biÓu diÔn kh¸c dùa trªn viÖc quy vÊn ®Ò vÒ c¸c vÊn ®Ò con. H×nh 3.6 Gi¶ sö ta cã b¶n ®å giao th«ng trong mét vïng l·nh thæ (xem h×nh 3.6). Gi¶ sö ta cÇn t×m ®−êng ®i tõ thμnh phè A tíi thμnh phè B. Cã con s«ng ch¶y qua hai thμnh phè E vμ G vμ cã cÇu qua s«ng ë mçi thμnh phè ®ã. Mäi ®−êng ®i tõ A ®Õn B chØ cã thÓ qua E hoÆc G. Nh− vËy bμi to¸n t×m ®−êng ®i tõ A ®Õn B ®−îc quy vÒ: 1) Bμi to¸n t×m ®−êng ®i tõ A ®Õn B qua E (hoÆc) 2) Bμi to¸n t×m ®−êng ®i tõ A ®Õn b qua G. Mçi mét trong hai bμi to¸n trªn l¹i cã thÓ ph©n nhá nh− sau 1) Bμi to¸n t×m ®−êng ®i tõ A ®Õn B qua E ®−îc quy vÒ: 1.1 T×m ®−êng ®i tõ A ®Õn E (vμ) 1.2 T×m ®−êng ®i tõ E ®Õn B. 2) Bμi to¸n t×m ®−êng ®i tõ A ®Õn B qua G ®−îc quy vÒ: 2.1 T×m ®−êng ®i tõ A ®Õn G (vμ) 2.2 T×m ®−êng ®i tõ G ®Õn B. Qu¸ tr×nh rót gän vÊn ®Ò nh− trªn cã thÓ biÓu diÔn d−íi d¹ng ®å thÞ (®å thÞ vμ/hoÆc) trong h×nh 3.7. ë ®©y mçi bμi to¸n t×m ®−êng ®i tõ mét thμnh phè tíi mét thμnh phè kh¸c øng víi mét tr¹ng th¸i. C¸c tr¹ng th¸i kÕt thóc lμ c¸c tr¹ng th¸i øng víi c¸c bμi to¸n t×m ®−êng ®i, ch¼ng h¹n tõ A ®Õn C, hoÆc tõ D ®Õn E, bëi v× ®· cã ®−êng nèi A víi C, nèi D víi E. 39
40. H×nh 3.7 §å thÞ vμ/hoÆc cña vÊn ®Ò t×m ®−êng ®i V. ®å thÞ Kh«ng gian tr¹ng th¸i m« t¶ viÖc quy vÊn ®Ò vÒ c¸c vÊn ®Ò con cã thÓ biÓu diÔn d−íi d¹ng ®å thÞ ®Þnh h−íng ®Æc biÖt ®−îc gäi lμ ®å thÞ vμ/hoÆc. §å thÞ nμy ®−îc x©y dùng nh− sau: Mçi bμi to¸n øng víi mét ®Ønh cña ®å thÞ. NÕu cã mét to¸n tö quy mét bμi to¸n vÒ mét bμi to¸n kh¸c, ch¼ng h¹n R : a → b, th× trong ®å thÞ sÏ cã cung g¸n nh·n ®i tõ ®Ønh a tíi ®Ønh b. §èi víi mçi to¸n tö quy mét bμi to¸n vÒ mét sè bμi to¸n con, ch¼ng h¹n R : a → b, c, d ta ®−a vμo mét ®Ønh míi a1, ®Ønh nμy biÓu diÔn tËp c¸c bμi to¸n con {b, c, d} vμ to¸n tö R : a → b, c, d ®−îc biÓu diÔn bëi ®å thÞ h×nh 3.8. H×nh 3.8 §å thÞ biÓu diÔn to¸n tö R : a → b, c, d VÝ dô: Gi¶ sö chóng ta cã kh«ng gian tr¹ng th¸i sau: Tr¹ng th¸i ban ®Çu (bμi to¸n cÇn gi¶i) lμ a. TËp c¸c to¸n tö gåm: R1 : a → d, e, f R2 : a → d, k R3 : a → g, h R4 : d → b, c 40
41. R5 : f → i R6 : f → c, g R7 : k → e, l R8 : k → h • TËp c¸c tr¹ng th¸i kÕt thóc (c¸c bμi to¸n s¬ cÊp) lμ T = {b, c, e, g}. Kh«ng gian tr¹ng th¸i trªn cã thÓ biÓu diÔn bëi ®å thÞ vμ/hoÆc trong h×nh 3.9. Trong ®å thÞ ®ã, c¸c ®Ønh ch¼ng h¹n a, f, k hoÆc a1, a2, a3 ®−îc gäi lμ ®Ønh. Lý do lμ, ®Ønh a1 biÓu diÔn tËp c¸c bμi to¸n {d, e, f} vμ a1 ®−îc gi¶i quyÕt nÕu d vμ e vμ f ®−îc gi¶i quyÕt. Cßn t¹i ®Ønh a, ta cã c¸c to¸n tö R1, R2, R3 quy bμi to¸n a vÒ c¸c bμi to¸n con kh¸c nhau, do ®ã a ®−îc gi¶i quyÕt nÕu hoÆc a1 = {d, e, f}, hoÆc a2 = {d, k}, hoÆc a3 = {g, h} ®−îc gi¶i quyÕt. H×nh 3.9 Mét ®å thÞ vμ/hoÆc Ng−êi ta th−êng sö dông ®å thÞ vμ/hoÆc ë d¹ng rót gän. Ch¼ng h¹n, ®å thÞ vμ/hoÆc trong h×nh 3.9 cã thÓ rót gän thμnh ®å thÞ trong h×nh 3.10. Trong ®å thÞ rót gän nμy, ta sÏ nãi ch¼ng h¹n d, e, f lμ c¸c ®Ønh kÒ ®Ønh a theo to¸n tö R1, cßn d, k lμ c¸c ®Ønh kÒ a theo to¸n tö R2. Khi ®· cã c¸c to¸n tö rót gän vÊn ®Ò, th× b»ng c¸ch ¸p dông liªn tiÕp c¸c to¸n tö, ta cã thÓ ®−a bμi to¸n cÇn gi¶i vÒ mét tËp c¸c bμi to¸n con. Ch¼ng h¹n, trong vÝ dô trªn nÕu ta ¸p dông c¸c to¸n tö R1, R4, R6, ta sÏ quy bμi to¸n a vÒ tËp c¸c bμi to¸n con {b, c, e, g}, tÊt c¶ c¸c bμi to¸n con nμy ®Òu lμ s¬ cÊp. Tõ c¸c to¸n tö R1, R4 vμ R6 ta x©y dùng ®−îc mét c©y trong h×nh 1.11a, c©y nμy ®−îc gäi lμ c©y nghiÖm. C©y nghiÖm ®−îc ®Þnh nghÜa nh− sau: C©y nghiÖm lμ mét c©y, trong ®ã: Gèc cña c©y øng víi bμi to¸n cÇn gi¶i. TÊt c¶ c¸c l¸ cña c©y lμ c¸c ®Ønh kÕt thóc (®Ønh øng víi c¸c bμi to¸n s¬ cÊp). 41
42. NÕu u lμ ®Ønh trong cña c©y, th× c¸c ®Ønh con cña u lμ c¸c ®Ønh kÒ u theo mét to¸n tö nμo ®ã. C¸c ®Ønh cña ®å thÞ vμ/hoÆc sÏ ®−îc g¾n nh·n gi¶i ®−îc hoÆc kh«ng gi¶i ®−îc. H×nh 3.10 §å thÞ rót gän cña ®å thÞ trong h×nh 3.9 H×nh 3.11 C¸c c©y nghiÖm C¸c ®Ønh gi¶i ®−îc ®−îc x¸c ®Þnh ®Ö quy nh− sau: C¸c ®Ønh kÕt thóc lμ c¸c ®Ønh gi¶i ®−îc. NÕu u kh«ng ph¶i lμ ®Ønh kÕt thóc, nh−ng cã mét to¸n tö R sao cho tÊt c¶ c¸c ®Ønh kÒ u theo R ®Òu gi¶i ®−îc th× u gi¶i ®−îc. C¸c ®Ønh kh«ng gi¶i ®−îc ®−îc x¸c ®Þnh ®Ö quy nh− sau: C¸c ®Ønh kh«ng ph¶i lμ ®Ønh kÕt thóc vμ kh«ng cã ®Ønh kÒ, lμ c¸c ®Ønh kh«ng gi¶i ®−îc. NÕu u kh«ng ph¶i lμ ®Ønh kÕt thóc vμ víi mäi to¸n tö R ¸p dông ®−îc t¹i u ®Òu cã mét ®Ønh v kÒ u theo R kh«ng gi¶i ®−îc, th× u kh«ng gi¶i ®−îc. Ta cã nhËn xÐt r»ng, nÕu bμi to¸n a gi¶i ®−îc th× sÏ cã mét c©y nghiÖm gèc a, vμ ng−îc l¹i nÕu cã mét c©y nghiÖm gèc a th× a gi¶i ®−îc. HiÓn nhiªn lμ, mét bμi to¸n gi¶i ®−îc cã thÓ cã nhiÒu c©y nghiÖm, mçi c©y nghiÖm biÓu diÔn mét c¸ch gi¶i bμi to¸n ®ã. Ch¼ng h¹n trong vÝ dô ®· nªu, bμi to¸n a cã hai c©y nghiÖm trong h×nh 3.11. Thø tù gi¶i c¸c bμi to¸n con trong mét c©y nghiÖm lμ nh− sau. Bμi to¸n øng víi ®Ønh u chØ ®−îc gi¶i sau khi tÊt c¶ c¸c bμi to¸n øng víi c¸c ®Ønh con cña u ®· ®−îc gi¶i. 42
43. Ch¼ng h¹n, víi c©y nghiÖm trong h×nh 3.11a, thø tù gi¶i c¸c bμi to¸n cã thÓ lμ b, c, d, g, f, e, a. ta cã thÓ sö dông thñ tôc s¾p xÕp topo ®Ó s¾p xÕp thø tù c¸c bμi to¸n trong mét c©y nghiÖm. §−¬ng nhiªn ta còng cã thÓ gi¶i quyÕt ®ång thêi c¸c bμi to¸n con ë cïng mét møc trong c©y nghiÖm. VÊn ®Ò cña chóng ta b©y giê lμ, t×m kiÕm trªn ®å thÞ vμ/hoÆc ®Ó x¸c ®Þnh ®−îc ®Ønh øng víi bμi to¸n ban ®Çu lμ gi¶i ®−îc hay kh«ng gi¶i ®−îc, vμ nÕu nã gi¶i ®−îc th× x©y dùng mét c©y nghiÖm cho nã. T×m kiÕm trªn ®å thÞ vμ/hoÆc Ta sÏ sö dông kü thuËt t×m kiÕm theo ®é s©u trªn ®å thÞ vμ/hoÆc ®Ó ®¸nh dÊu c¸c ®Ønh. C¸c ®Ønh sÏ ®−îc ®¸nh dÊu gi¶i ®−îc hoÆc kh«ng gi¶i ®−îc theo ®Þnh nghÜa ®Ö quy vÒ ®Ønh gi¶i ®−îc vμ kh«ng gi¶i ®−îc. XuÊt ph¸t tõ ®Ønh øng víi bμi to¸n ban ®Çu, ®i xuèng theo ®é s©u, nÕu gÆp ®Ønh u lμ ®Ønh kÕt thóc th× nã ®−îc ®¸nh dÊu gi¶i ®−îc. NÕu gÆp ®Ønh u kh«ng ph¶i lμ ®Ønh kÕt thóc vμ tõ u kh«ng ®i tiÕp ®−îc, th× u ®−îc ®¸nh dÊu kh«ng gi¶i ®−îc. Khi ®i tíi ®Ønh u, th× tõ u ta lÇn l−ît ®i xuèng c¸c ®Ønh v kÒ u theo mét to¸n tö R nμo ®ã. NÕu ®¸nh dÊu ®−îc mét ®Ønh v kh«ng gi¶i ®−îc th× kh«ng cÇn ®i tiÕp xuèng c¸c ®Ønh v cßn l¹i. TiÕp tôc ®i xuèng c¸c ®Ønh kÒ u theo mét to¸n tö kh¸c. NÕu tÊt c¶ c¸c ®Ønh kÒ u theo mét to¸n tö nμo ®ã ®−îc ®¸nh dÊu gi¶i ®−îc th× u sÏ ®−îc ®¸nh dÊu gi¶i ®−îc vμ quay lªn cha cña u. Cßn nÕu tõ u ®i xuèng c¸c ®Ønh kÒ nã theo mäi to¸n tö ®Òu gÆp c¸c ®Ønh kÒ ®−îc ®¸nh dÊu kh«ng gi¶i ®−îc, th× u ®−îc ®¸nh dÊu kh«ng gi¶i ®−îc vμ quay lªn cha cña u. Ta sÏ biÓu diÔn thñ tôc t×m kiÕm theo ®é s©u vμ ®¸nh dÊu c¸c ®Ønh ®· tr×nh bμy trªn bëi hμm ®Ö quy Solvable(u). Hμm nμy nhËn gi¸ trÞ true nÕu u gi¶i ®−îc vμ nhËn gi¸ trÞ false nÕu u kh«ng gi¶i ®−îc. Trong hμm Solvable(u), ta sÏ sö dông: BiÕn Ok. Víi mçi to¸n tö R ¸p dông ®−îc t¹i u, biÕn Ok nhËn gi¸ trÞ true nÕu tÊt c¶ c¸c ®Ønh v kÒ u theo R ®Òu gi¶i ®−îc, vμ Ok nhËn gi¸ trÞ false nÕu cã mét ®Ønh v kÒ u theo R kh«ng gi¶i ®−îc. Hμm Operator(u) ghi l¹i to¸n tö ¸p dông thμnh c«ng t¹i u, tøc lμ Operator(u) = R nÕu mäi ®Ønh v kÒ u theo R ®Òu gi¶i ®−îc. function Solvable(u); begin 1. if u lμ ®Ønh kÕt thóc then {Solvable(u) ←true; stop}; 2. if u kh«ng lμ ®Ønh kÕt thóc vμ kh«ng cã ®Ønh kÒ then {Solvable(u) ← false; stop}; 3. for mçi to¸n tö R ¸p dông ®−îc t¹i u do (1) {Ok ← true; for mçi v kÒ u theo R do (2) if Solvable(v) = false then {Ok ← false; exit}; // tho¸t for (2) if Ok then 43
44. {Solvable(u) ← true; Operator(u) ← R; stop} } 4. Solvable(u) ← false; end; NhËn xÐt Hoμn toμn t−¬ng tù nh− thuËt to¸n t×m kiÕm theo ®é s©u trong kh«ng gian tr¹ng th¸i (môc III.2), thuËt to¸n t×m kiÕm theo ®é s©u trªn ®å thÞ vμ/hoÆc sÏ x¸c ®Þnh ®−îc bμi to¸n ban ®Çu lμ gi¶i ®−îc hay kh«ng gi¶i ®−îc, nÕu c©y t×m kiÕm kh«ng cã nh¸nh v« h¹n. NÕu c©y t×m kiÕm cã nh¸nh v« h¹n th× ch−a ch¾c thuËt to¸n ®· dõng, v× cã thÓ nã bÞ xa lÇy khi ®i xuèng nh¸nh v« h¹n. Trong tr−êng hîp nμy ta nªn sö dông thuËt to¸n t×m kiÕm s©u lÆp (môc III.4). NÕu bμi to¸n ban ®Çu gi¶i ®−îc, th× b»ng c¸ch sö dông hμm Operator ta sÏ x©y dùng ®−îc c©y nghiÖm. VI. Bμi tËp 1. TÝnh sè tr¹ng th¸i tèi ®a ph¶i l−u khi duyÖt mét c©y theo bÒ réng cã ®é s©u lμ 5 vμ hÖ sè nh¸nh lμ 4 2. ViÕt ch−¬ng tr×nh minh häa t×m kiÕm theo bÒ réng vμ ®é s©u cña bμi to¸n 8 sè víi c¸c yªu cÇu sau a) Tr¹ng th¸i ban ®Çu cña bμi to¸n cã c¸c sè ë vÞ trÝ ngÉu nhiªn b) Tr×nh bμy tÊt c¶ tr¹ng th¸i trong qu¸ tr×nh t×m tr¹ng th¸i ®Ých 3. ViÕt ch−¬ng tr×nh minh häa bμi to¸n nhμ triÖu phó vμ kÎ c−íp víi sè nhμ triÖu phó vμ kÎ c−íp tuú ý 4. ViÕt ch−¬ng tr×nh gi¶i bμi to¸n tÝch ph©n ∫(xex + x3) dx 44
45. Ch−¬ng IV C¸c chiÕn l−îc t×m kiÕm kinh nghiÖm Trong ch−¬ng III, chóng ta ®· nghiªn cøu viÖc biÓu diÔn vÊn ®Ò trong kh«ng gian tr¹ng th¸i vμ c¸c kü thuËt t×m kiÕm mï. C¸c kü thuËt t×m kiÕm mï rÊt kÐm hiÖu qu¶ vμ trong nhiÒu tr−êng hîp kh«ng thÓ ¸p dông ®−îc. Trong ch−¬ng nμy, chóng ta sÏ nghiªn cøu c¸c ph−¬ng ph¸p t×m kiÕm kinh nghiÖm (t×m kiÕm heuristic), ®ã lμ c¸c ph−¬ng ph¸p sö dông hμm ®¸nh gi¸ ®Ó h−íng dÉn sù t×m kiÕm. I. Hμm ®¸nh gi¸ vμ t×m kiÕm kinh nghiÖm Trong nhiÒu vÊn ®Ò, ta cã thÓ sö dông kinh nghiÖm, tri thøc cña chóng ta vÒ vÊn ®Ò ®Ó ®¸nh gi¸ c¸c tr¹ng th¸i cña vÊn ®Ò. Víi mçi tr¹ng th¸i u, chóng ta sÏ x¸c ®Þnh mét gi¸ trÞ sè h(u), sè nμy ®¸nh gi¸ “sù gÇn ®Ých” cña tr¹ng th¸i u. Hμm h(u) ®−îc gäi lμ hμm ®¸nh gi¸. Chóng ta sÏ sö dông hμm ®¸nh gi¸ ®Ó h−íng dÉn sù t×m kiÕm. Trong qu¸ tr×nh t×m kiÕm, t¹i mçi b−íc ta sÏ chän tr¹ng th¸i ®Ó ph¸t triÓn lμ tr¹ng th¸i cã gi¸ trÞ hμm ®¸nh gi¸ nhá nhÊt, tr¹ng th¸i nμy ®−îc xem lμ tr¹ng th¸i cã nhiÒu høa hÑn nhÊt h−íng tíi ®Ých. C¸c kü thuËt t×m kiÕm sö dông hμm ®¸nh gi¸ ®Ó h−íng dÉn sù t×m kiÕm ®−îc gäi chung lμ c¸c kü thuËt t×m kiÕm kinh nghiÖm (heuristic search). C¸c giai ®o¹n c¬ b¶n ®Ó gi¶i quyÕt vÊn ®Ò b»ng t×m kiÕm kinh nghiÖm nh− sau: 1. T×m biÓu diÔn thÝch hîp m« t¶ c¸c tr¹ng th¸i vμ c¸c to¸n tö cña vÊn ®Ò. 2. X©y dùng hμm ®¸nh gi¸. 3. ThiÕt kÕ chiÕn l−îc chän tr¹ng th¸i ®Ó ph¸t triÓn ë mçi b−íc. Hμm ®¸nh gi¸ Trong t×m kiÕm kinh nghiÖm, hμm ®¸nh gi¸ ®ãng vai trß cùc kú quan träng. Chóng ta cã x©y dùng ®−îc hμm ®¸nh gi¸ cho ta sù ®¸nh gi¸ ®óng c¸c tr¹ng th¸i th× t×m kiÕm míi hiÖu qu¶. NÕu hμm ®¸nh gi¸ kh«ng chÝnh x¸c, nã cã thÓ dÉn ta ®i chÖch h−íng vμ do ®ã t×m kiÕm kÐm hiÖu qu¶. Hμm ®¸nh gi¸ ®−îc x©y dùng tïy thuéc vμo vÊn ®Ò. Sau ®©y lμ mét sè vÝ dô vÒ hμm ®¸nh gi¸: • Trong bμi to¸n t×m kiÕm ®−êng ®i trªn b¶n ®å giao th«ng, ta cã thÓ lÊy ®é dμi cña ®−êng chim bay tõ mét thμnh phè tíi mét thμnh phè ®Ých lμm gi¸ trÞ cña hμm ®¸nh gi¸. • Bμi to¸n 8 sè. Chóng ta cã thÓ ®−a ra hai c¸ch x©y dùng hμm ®¸nh gi¸. Hμm h1: Víi mçi tr¹ng th¸i u th× h1(u) lμ sè qu©n kh«ng n»m ®óng vÞ trÝ cña nã trong tr¹ng th¸i ®Ých. Ch¼ng h¹n tr¹ng th¸i ®Ých ë bªn ph¶i h×nh 4.1, vμ u lμ tr¹ng th¸i ë bªn tr¸i h×nh 4.1, th× h1(u) = 4, v× c¸c qu©n kh«ng ®óng vÞ trÝ lμ 3, 8, 6 vμ 1. 45
46. H×nh 4.1 §¸nh gi¸ tr¹ng th¸i u Hμm h2: h2(u) lμ tæng kho¶ng c¸ch gi÷a vÞ trÝ cña c¸c qu©n trong tr¹ng th¸i u vμ vÞ trÝ cña nã trong tr¹ng th¸i ®Ých. ë ®©y kho¶ng c¸ch ®−îc hiÓu lμ sè Ýt nhÊt c¸c dÞch chuyÓn theo hμng hoÆc cét ®Ó ®−a mét qu©n tíi vÞ trÝ cña nã trong tr¹ng th¸i ®Ých. Ch¼ng h¹n víi tr¹ng th¸i u vμ tr¹ng th¸i ®Ých nh− trong h×nh 2.1, ta cã: h2(u) = 2 + 3 + 1 + 3 = 9 V× qu©n 3 cÇn Ýt nhÊt 2 dÞch chuyÓn, qu©n 8 cÇn Ýt nhÊt 3 dÞch chuyÓn, qu©n 6 cÇn Ýt nhÊt 1 dÞch chuyÓn vμ qu©n 1 cÇn Ýt nhÊt 3 dÞch chuyÓn. Hai chiÕn l−îc t×m kiÕm kinh nghiÖm quan träng nhÊt lμ t×m kiÕm tèt nhÊt - ®Çu tiªn (best-first search) vμ t×m kiÕm leo ®åi (hill-climbing search). Cã thÓ x¸c ®Þnh c¸c chiÕn l−îc nμy nh− sau: T×m kiÕm tèt nhÊt ®Çu tiªn = T×m kiÕm theo bÒ réng + Hμm ®¸nh gi¸ T×m kiÕm leo ®åi = T×m kiÕm theo ®é s©u + Hμm ®¸nh gi¸ Chóng ta sÏ lÇn l−ît nghiªn cøu c¸c kü thuËt t×m kiÕm nμy trong c¸c môc sau. II. T×m kiÕm tèt nhÊt - ®Çu tiªn T×m kiÕm tèt nhÊt - ®Çu tiªn (best-first search) lμ t×m kiÕm theo bÒ réng ®−îc h−íng dÉn bëi hμm ®¸nh gi¸. Nh−ng nã kh¸c víi t×m kiÕm theo bÒ réng ë chç, trong t×m kiÕm theo bÒ réng ta lÇn l−ît ph¸t triÓn tÊt c¶ c¸c ®Ønh ë møc hiÖn t¹i ®Ó sinh ra c¸c ®Ønh ë møc tiÕp theo, cßn trong t×m kiÕm tèt nhÊt - ®Çu tiªn ta chän ®Ønh ®Ó ph¸t triÓn lμ ®Ønh tèt nhÊt ®−îc x¸c ®Þnh bëi hμm ®¸nh gi¸ (tøc lμ ®Ønh cã gi¸ trÞ hμm ®¸nh gi¸ lμ nhá nhÊt), ®Ønh nμy cã thÓ ë møc hiÖn t¹i hoÆc ë c¸c møc trªn. 46
47. H×nh 4.2 §å thÞ kh«ng gian tr¹ng th¸i VÝ dô: XÐt kh«ng gian tr¹ng th¸i ®−îc biÓu diÔn bëi ®å thÞ trong h×nh 4.2, trong ®ã tr¹ng th¸i ban ®Çu lμ A, tr¹ng th¸i kÕt thóc lμ B. Gi¸ trÞ cña hμm ®¸nh gi¸ lμ c¸c sè ghi c¹nh mçi ®Ønh. Qu¸ tr×nh t×m kiÕm tèt nhÊt - ®Çu tiªn diÔn ra nh− sau: §Çu tiªn ph¸t triÓn ®Ønh A sinh ra c¸c ®Ønh kÒ lμ C, D vμ E. Trong ba ®Ønh nμy, ®Ønh D cã gi¸ trÞ hμm ®¸nh gi¸ nhá nhÊt, nã ®−îc chän ®Ó ph¸t triÓn vμ sinh ra F, I. Trong sè c¸c ®Ønh ch−a ®−îc ph¸t triÓn C, E, F, I th× ®Ønh E cã gi¸ trÞ ®¸nh gi¸ nhá nhÊt, nã ®−îc chän ®Ó ph¸t triÓn vμ sinh ra c¸c ®Ønh G, K. Trong sè c¸c ®Ønh ch−a ®−îc ph¸t triÓn th× G tèt nhÊt, ph¸t triÓn G sinh ra B, H. §Õn ®©y ta ®· ®¹t tíi tr¹ng th¸i kÕt thóc. C©y t×m kiÕm tèt nhÊt - ®Çu tiªn ®−îc biÓu diÔn trong h×nh 4.3. H×nh 4.3 C©y t×m kiÕm tèt nhÊt - ®Çu tiªn Sau ®©y lμ thñ tôc t×m kiÕm tèt nhÊt - ®Çu tiªn. Trong thñ tôc nμy, chóng ta sö dông danh s¸ch L ®Ó l−u c¸c tr¹ng th¸i chê ph¸t triÓn, danh s¸ch ®−îc s¾p theo thø tù t¨ng dÇn cña hμm ®¸nh gi¸ sao cho tr¹ng th¸i cã gi¸ trÞ hμm ®¸nh gi¸ nhá nhÊt ë ®Çu danh s¸ch. 47
48. procedure Best_First_Search; begin 1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu; 2. loop do 2.1 if L rçng then {th«ng b¸o thÊt b¹i; stop}; 2.2 Lo¹i tr¹ng th¸i u ë ®Çu danh s¸ch L; 2.3 if u lμ tr¹ng th¸i kÕt thóc then {th«ng b¸o thμnh c«ng; stop} 2.4 for mçi tr¹ng th¸i v kÒ u do Xen v vμo danh s¸ch L sao cho L ®−îc s¾p theo thø tù t¨ng dÇn cña hμm ®¸nh gi¸; end; III. T×m kiÕm leo ®åi T×m kiÕm leo ®åi (hill-climbing search) lμ t×m kiÕm theo ®é s©u ®−îc h−íng dÉn bëi hμm ®¸nh gi¸. Song kh¸c víi t×m kiÕm theo ®é s©u, khi ta ph¸t triÓn mét ®Ønh u th× b−íc tiÕp theo, ta chän trong sè c¸c ®Ønh con cña u, ®Ønh cã nhiÒu høa hÑn nhÊt ®Ó ph¸t triÓn, ®Ønh nμy ®−îc x¸c ®Þnh bëi hμm ®¸nh gi¸. VÝ dô: Ta l¹i xÐt ®å thÞ kh«ng gian tr¹ng th¸i trong h×nh 2.2. Qu¸ tr×nh t×m kiÕm leo ®åi ®−îc tiÕn hμnh nh− sau. §Çu tiªn ph¸t triÓn ®Ønh A sinh ra c¸c ®Ønh con C, D, E. Trong c¸c ®Ønh nμy chän D ®Ó ph¸t triÓn, vμ nã sinh ra c¸c ®Ønh con B, G. Qu¸ tr×nh t×m kiÕm kÕt thóc. C©y t×m kiÕm leo ®åi ®−îc cho trong h×nh 4.4. Trong thñ tôc t×m kiÕm leo ®åi ®−îc tr×nh bμy d−íi ®©y, ngoμi danh s¸ch L l−u c¸c tr¹ng th¸i chê ®−îc ph¸t triÓn, chóng ta sö dông danh s¸ch L1 ®Ó l−u gi÷ t¹m thêi c¸c tr¹ng th¸i kÒ tr¹ng th¸i u, khi ta ph¸t triÓn u. Danh s¸ch L1 ®−îc s¾p xÕp theo thø tù t¨ng dÇn cña hμm ®¸nh gi¸, råi ®−îc chuyÓn vμo danh s¸ch L sao tr¹ng th¸i tèt nhÊt kÒ u ®øng ë danh s¸ch L. H×nh 4.4 C©y t×m kiÕm leo ®åi 48
49. procedure Hill_Climbing_Search; begin 1. Khëi t¹o danh s¸ch L chØ chøa tr¹ng th¸i ban ®Çu; 2. loop do 2.1 if L rçng then {th«ng b¸o thÊt b¹i; stop}; 2.2 Lo¹i tr¹ng th¸i u ë ®Çu danh s¸ch L; 2.3 if u lμ tr¹ng th¸i kÕt thóc then {th«ng b¸o thμnh c«ng; stop}; 2.4 for mçi tr¹ng th¸i v kÒ u do ®Æt v vμo L1; 2.5 S¾p xÕp L1 theo thø tù t¨ng dÇn cña hμm ®¸nh gi¸; 2.6 ChuyÓn danh s¸ch L1 vμo ®Çu danh s¸ch L; end; IV. T×m kiÕm beam T×m kiÕm beam (beam search) gièng nh− t×m kiÕm theo bÒ réng, nã ph¸t triÓn c¸c ®Ønh ë mét møc råi ph¸t triÓn c¸c ®Ønh ë møc tiÕp theo. Tuy nhiªn, trong t×m kiÕm theo bÒ réng, ta ph¸t triÓn tÊt c¶ c¸c ®Ønh ë mét møc, cßn trong t×m kiÕm beam, ta h¹n chÕ chØ ph¸t triÓn k ®Ønh tèt nhÊt (c¸c ®Ønh nμy ®−îc x¸c ®Þnh bëi hμm ®¸nh gi¸). Do ®ã trong t×m kiÕm beam, ë bÊt kú møc nμo còng chØ cã nhiÒu nhÊt k ®Ønh ®−îc ph¸t triÓn, trong khi t×m kiÕm theo bÒ réng, sè ®Ønh cÇn ph¸t triÓn ë møc d lμ bd (b lμ nh©n tè nh¸nh). VÝ dô: Chóng ta l¹i xÐt ®å thÞ kh«ng gian tr¹ng th¸i trong h×nh 4.2. Chän k = 2. Khi ®ã c©y t×m kiÕm beam ®−îc cho nh− h×nh 4.5. C¸c ®Ønh ®−îc g¹ch d−íi lμ c¸c ®Ønh ®−îc chän ®Ó ph¸t triÓn ë mçi møc. H×nh 4.5 C©y t×m kiÕm beam 49
50. V. Bμi tËp 1. Trong t×m kiÕm tèt nhÊt - ®Çu tiªn nÕu gi¸ trÞ cña hμm ®¸nh gi¸ cña c¸c tr¹ng th¸i thay ®æi sau mçi b−íc chän th× thñ tôc t×m kiÕm tèt nhÊt - ®Çu tiªn cÇn thay ®æi nh− thÕ nμo ? 2. ViÕt ch−¬ng tr×nh minh häa t×m kiÕm tèt nhÊt - ®Çu tiªn vμ leo ®åi vμ beam cña bμi to¸n 8 sè víi c¸c yªu cÇu sau a) Tr¹ng th¸i ban ®Çu cña bμi to¸n cã c¸c sè ë vÞ trÝ ngÉu nhiªn b) Tr×nh bμy tÊt c¶ tr¹ng th¸i trong qu¸ tr×nh t×m tr¹ng th¸i ®Ých 3. Viết giải thuật tìm kiếm beam (dùng mã giả) 4. Cho ®å thÞ kh«ng gian tr¹ng th¸i: §Ó t×m ®−êng ®i tõ A tíi K, h·y vÏ c©y t×m kiÕm cña t×m kiÕm tèt nhÊt-®Çu tiªn, t×m kiÕm leo ®åi vμ t×m kiÕm beam cã k = 2 50