1、Symbolic AIChapter 2-32021-12-11AI:Summary22.3 請用狀態空間法求解農夫過河問題，該問題是：一農夫請用狀態空間法求解農夫過河問題，該問題是：一農夫帶著一只狼、一只羊和一筐菜來到河邊，欲乘船到河對岸。帶著一只狼、一只羊和一筐菜來到河邊，欲乘船到河對岸。但船太小，農夫每次只能帶一樣東西過河。而在沒有農夫但船太小，農夫每次只能帶一樣東西過河。而在沒有農夫看管的情況下，狼會吃羊，羊會吃菜。農夫應該怎樣做，看管的情況下，狼會吃羊，羊會吃菜。農夫應該怎樣做，才能在沒有任何損失的情況下把所有東西帶到河對岸？才能在沒有任何損失的情況下把所有東西帶到河對岸？2.13

2、試用試用A*算法解決習題算法解決習題2.3中給出的農夫過河問題。中給出的農夫過河問題。解解：問題：問題狀態表示狀態表示為（為（a, b, c, d），其中），其中a, b, c, d分別表示分別表示農夫、狼，羊和菜的位置，農夫、狼，羊和菜的位置，1表示在左岸，表示在左岸，0表示在右岸。表示在右岸。則起始狀態為則起始狀態為 (1,1,1,1)，終止狀態為，終止狀態為 (0, 0, 0, 0)。改變狀態。改變狀態的的操作操作共八種，分別為：農夫帶著共八種，分別為：農夫帶著狼、羊、菜狼、羊、菜從從左岸到左岸到右岸、右岸到左岸右岸、右岸到左岸。搜索路徑搜索路徑為：為：(1,1,1,1)(0,1,0,1

3、)(1,1,0,1)(0,0,0,1)(1,0,1,1)(0,0,1,0)(1,0,1,0)(0,0,0,0) 2021-12-11AI:Summary3h(x)=河左岸物體個數河左岸物體個數或無窮大（或無窮大（人：狼、羊對應位不人：狼、羊對應位不能相等；羊、菜對應位不能相等能相等；羊、菜對應位不能相等）(1,1,1,1)h=3f=3(0,0,1,1)h=f=(0,1,0,1)h=2f=3(0,1,1,0)h=f=(1,1,0,1)h=2f=4(0,0,0,1)h=1f=4(0,1,0,0)h=1f=4(1,0,0,1)h=f=(1,0,1,1)h=2f=6(1,1,0,0)h=f= (1,1

4、,1,0)h=2f=61023452021-12-11AI:Summary4(1,0,1,1)h=2f=6(0,0,1,0)h=1f=6(0,0,0,1)h=1f=6(1,0,1,0)h=1f=8(1,1,1,0)h=2f=8(0,0,0,0)h=0f=7h(x)=河左岸物體個數河左岸物體個數或無窮大（或無窮大（人：狼、羊對應位不人：狼、羊對應位不能相等；羊、菜對應位不能相等能相等；羊、菜對應位不能相等）續上圖6(1,0,0,1)h=f=7910(1,1,1,0)h=2f=682021-12-11AI:Summary52.21 設有如圖所示的一棵博弈樹，其中末一行的數字是葉頂設有如圖所示的一棵

5、博弈樹，其中末一行的數字是葉頂點的靜態估值，請對該博弈樹作如下工作：點的靜態估值，請對該博弈樹作如下工作：用極小極大值法計算各節點的倒推值。用極小極大值法計算各節點的倒推值。利用利用alpha-beta剪枝技術剪去不必要搜索的分枝。敘述剪枝發生剪枝技術剪去不必要搜索的分枝。敘述剪枝發生在何處，即剪去了哪些分枝（在剪枝處用在何處，即剪去了哪些分枝（在剪枝處用在圖上做標記）。在圖上做標記）。 2021-12-11AI:Summary6小測驗小測驗2. 有如圖所示的一棵博弈樹，其中末一行的數字是節有如圖所示的一棵博弈樹，其中末一行的數字是節點的靜態估值。如按點的靜態估值。如按優先生成左邊節點優先生成

6、左邊節點方式進行剪枝搜索。方式進行剪枝搜索。請在圖上標注搜索與剪枝過程，包括節點上的倒推值和被請在圖上標注搜索與剪枝過程，包括節點上的倒推值和被剪去的分枝（在剪枝處用剪去的分枝（在剪枝處用做標記）。在此基礎上用箭線做標記）。在此基礎上用箭線標示標示MAX將采取的行動。將采取的行動。2021-12-11AI:Summary73.9 用謂詞公式表示以下語句用謂詞公式表示以下語句（1）西安市的夏天既干燥又炎熱。）西安市的夏天既干燥又炎熱。（2）并不是每一個人都喜歡吃臭豆腐）并不是每一個人都喜歡吃臭豆腐 （3）喜歡讀）喜歡讀三國演義三國演義的人必讀的人必讀水滸水滸。 （4）魚我所欲也，熊掌亦我所欲也。

7、）魚我所欲也，熊掌亦我所欲也。（5）任意一個實數都有比它大的整數。）任意一個實數都有比它大的整數。（6）并不是所有的學生選修了歷史和生物。）并不是所有的學生選修了歷史和生物。（7）星期六，所有學生或者去參加舞會了，或者工作去了，二者必居其一。星期六，所有學生或者去參加舞會了，或者工作去了，二者必居其一。)()(xiansummerhotxiansummerdry choudoufuxlikexpersonx, shuihuxreadsanguoxlikereadxpersonx,xiongzhangIwantfishIwant, xybiggeryintegerxrealyx, ybioxse

8、lecthistoryxselectxstudentxlog, yxdanceyxworkyxdanceyxworkysaturdayxstudentyx,2021-12-11AI:Summary8小測驗小測驗1. 用謂詞公式表示以下語句并轉化為子句集：用謂詞公式表示以下語句并轉化為子句集： 1）沒有學生會買昂貴的轎車）沒有學生會買昂貴的轎車 2）每一個學習人工智能的人都會學習哲學）每一個學習人工智能的人都會學習哲學 3）所有紫色的蘑菇都是有毒的。）所有紫色的蘑菇都是有毒的。 arExpensivecxBuyxStudentx, philosophyxLearnAIxLearnxPersonx

9、, xpoisonousxPurplexMushroomx arExpensivecxBuyxStudent, philosophyxLearnAIxLearnxPerson, xpoisonousxPurplexMushroom2021-12-11AI:Summary93.14 把下列謂詞公式轉化為相應的子句集：把下列謂詞公式轉化為相應的子句集： （3）1. Eliminate biconditionals and implications2. Move inwardsyxRyxQyxPyx,yxRyxQyxPyx,3. Standardize variables4. Skolemize:

10、a more general form of existential instantiationyxRyxQyxPyx, xfxRxfxQxfxPx,Table 3-5 (P87) + Table 3-2 (P83)2021-12-11AI:Summary105. Drop universal quantifiers:6. Distribute over : xfxRxfxQxfxP, xfxRxfxQxfxRxfxP,Table 3-5 (P87) + Table 3-2 (P83)Clause 1Clause 2注意：注意：Skeleom標準化標準化2021-12-11AI:Summary

11、113.14 把下列謂詞公式轉化為相應的子句集：把下列謂詞公式轉化為相應的子句集：（1）（2） （4） （5）),(),(yxQyxPyxyxQyxPyx,),(),(vuQyxPyxQyxP,zxRyxQyxPzyx,yxfxRyxQyxP,wzxRwvuzyxQwvuzyxPwvuzyx, , , , ,vzgzxRvzgvzfzyxQvzgvzfzyxP2021-12-11AI:Summary123.20已知：已知： 規則規則1：任何人的兄弟不是女性：任何人的兄弟不是女性 規則規則2：任何人的姐妹必是女性：任何人的姐妹必是女性 事實：事實：Mary是是Bill的姐妹的姐妹 求證：用歸結反

12、演方法證明求證：用歸結反演方法證明Mary不是不是Tom的兄弟的兄弟解：解：（1）將規則和事實表示為一階謂詞：）將規則和事實表示為一階謂詞： xWyxByx, xWyxSyx,BillMaryS,2021-12-11AI:Summary132. 將事實和規則轉換為子句集將事實和規則轉換為子句集 xWyxB, uWvuS,BillMaryS,3. 結論取反，并加入子句集結論取反，并加入子句集TomMaryB,4. 進行歸結反演進行歸結反演2021-12-11AI:Summary14 xWyxB,TomMaryB,MaryW uWvuS,vMaryS,BillMaryS,NILMary/x, To

13、m/yMary/uBill/vArtificial Neural NetworksChapter 42021-12-11AI:Summary16（0, 0）（1, -0.5）（1, 1.5）（2, 0.5） class 1 class 24.11 設計一個感知器，用于區分兩類數據，其中第一類數據設計一個感知器，用于區分兩類數據，其中第一類數據是（是（1, 1.5）和（）和（2, 0.5），第二類數據是（），第二類數據是（0, 0）和（）和（1, -0.5）輸入輸入1輸入輸入2輸出輸出11.5020.500011-0.510 , 00 , 122112211xwxwxwxwyw1w2yx1x22

14、021-12-11AI:Summary1705 . 0005 . 0205 . 1212121wwwwww005 . 025. 05 . 022121wwwww121ww滿足以上約束滿足以上約束（只是一種可能）（只是一種可能）-1-1yx1x2-12021-12-11AI:Summary184.14 給定一個給定一個322的的BP網絡。初始時，該網絡中所有神網絡。初始時，該網絡中所有神經元的輸出閾值設定為經元的輸出閾值設定為0.01，輸入層到隱含層的所有連接權，輸入層到隱含層的所有連接權值設定為值設定為-0.5，隱含層到輸出層的所有連接權值設定為，隱含層到輸出層的所有連接權值設定為0.25。采

15、用學習率為采用學習率為1.2的的BP算法進行學習。請手工計算當給定如算法進行學習。請手工計算當給定如下兩個輸入下兩個輸入-輸出數據對：輸出數據對：( (0.2,0.4,0.7), (1,0) )，( (0.7,0.4,0.2), (0,1) )時，網絡連接權值和神經元輸出閾值的時，網絡連接權值和神經元輸出閾值的調整過程。調整過程。注：注：（1）反向傳播，應）反向傳播，應先進行隱含層到輸出層的權值調整，先進行隱含層到輸出層的權值調整，再進行輸入層到隱含層的權值調整再進行輸入層到隱含層的權值調整，此時使用調整后的，此時使用調整后的隱含層到輸出層的權值。隱含層到輸出層的權值。（2）對于）對于單個數據

16、而言，不存在迭代單個數據而言，不存在迭代。需所有數據處。需所有數據處理完后，再根據情況確定是否迭代理完后，再根據情況確定是否迭代2021-12-11AI:Summary194.15 使用雙曲正切函數取代Sigmoid函數，作為誤差反向傳播網絡中神經元的輸函數，作為誤差反向傳播網絡中神經元的輸出函數。出函數。 設設 表表 示神經元的輸出，示神經元的輸出， 分別表示神經元的第分別表示神經元的第i個輸入及其對應權值，個輸入及其對應權值， （包括閾值），（包括閾值）， 則每個神經元的輸出是：則每個神經元的輸出是：試推導相應BP算法中輸出層和隱含層的權值更新法則。提示：算法中輸出層和隱含層的權值更新法則

17、。提示：iix,yni,1L= =niiixy1tanh()()Machine LearningChapter 52021-12-11AI:Summary24真值表真值表BAABResult000010101110決策樹決策樹AB0011001A、B: 屬性屬性Result：決策結果：決策結果0、1：屬性值和結果值（：屬性值和結果值（note: 結果值不一定與屬性值形式相同）結果值不一定與屬性值形式相同）5.12 給出表示如下布爾函數的決策樹：給出表示如下布爾函數的決策樹：2021-12-11AI:Summary255.13 有如下訓練樣本集合，每個樣本或者屬于有如下訓練樣本集合，每個樣本或者

18、屬于A類，或者屬于類，或者屬于B類。同時，每個樣本具有兩個屬性類。同時，每個樣本具有兩個屬性a1和和a2, 屬性可取值為屬性可取值為True或或False。樣本屬性與類別的對應關系如下表所示：。樣本屬性與類別的對應關系如下表所示：樣本樣本類別類別屬性屬性a1屬性屬性a21BTrueFalse2BTrueTrue3AFalseTrue4BFalseFalse5ATrueFalse6ATrueTrue如果以信息增益為依據，請確定在屬性如果以信息增益為依據，請確定在屬性a1和和a2之間，哪個之間，哪個屬性更適合作為分類以上樣例的屬性。屬性更適合作為分類以上樣例的屬性。 2021-12-11AI:Su

19、mmary26082. 0,918. 0918. 031log3132log32918. 031log3132log3221210, 1121log2121log21121log2121log213132121log2121log21222222221112222122aaafalsetruefalsetrueaaaafalsetruefalsetrueaSEGSEEEESSEGSEEEESE因為因為:12aaGG，所以，所以a2更適合作為更適合作為分類以上樣例的屬性。分類以上樣例的屬性。2021-12-11AI:Summary275.15 考慮例考慮例5-4所述癌癥診斷問題。如果醫生要求病人

20、再重所述癌癥診斷問題。如果醫生要求病人再重新做一次化驗，并且化驗結果同樣為陽性，則根據兩次新做一次化驗，并且化驗結果同樣為陽性，則根據兩次化驗結果，化驗結果，癌癥癌癥和和非癌癥非癌癥的后驗概率分別是多的后驗概率分別是多少？（假設兩次測試相互獨立）少？（假設兩次測試相互獨立）P(cancer)=0.008, P(cancer)=0.992P(+|cancer)=0.98, P(-|cancer)=0.02P(+|cancer)=0.03, P(-|cancer)=0.97 DPhPhDPDPhDPDhP),(P(+, +|cancer)P(cancer) = P(+|cancer)P(+|can

21、cer) P(cancer) =0.980.980.008 = 0.00768P(+, +|cancer) P(cancer)= P(+| cancer)P(+| cancer) P( cancer) =0.030.030.992=0.000893P(+, +) = P(+, +|cancer)P(cancer) + P(+, +| cancer)P(cancer) = 0.008573P(cancer|+,+)=0.00768/0.008573=0.8958P(cancer|+,+)=0.000893/0.008573=0.10422021-12-11AI:Summary28 MPIPBPM

22、IBP,IGJPGJP,JIBGMPIBGMP,5.19 假設有如下貝葉斯信念網：假設有如下貝葉斯信念網： 其中，各屬性均為布爾型，含義分別是：其中，各屬性均為布爾型，含義分別是： B=BrokeElectionLaw，表示是否違反選，表示是否違反選舉法；舉法； I=Indicted，表示是否被起訴；，表示是否被起訴；M=PoliticallyMotivatedProsecutor，表示檢，表示檢查官是否有政治傾向；查官是否有政治傾向；G=FoundGuilty，表示是否判定有罪；，表示是否判定有罪；J=Jailed，表示是否，表示是否投入監獄。投入監獄。 請根據上述貝葉斯信念網，解答以下問題

23、：請根據上述貝葉斯信念網，解答以下問題： （1）根據網絡結構（不考慮條件概率表），以下各公式是否一定成立？）根據網絡結構（不考慮條件概率表），以下各公式是否一定成立？ (a) (b) (c) 不成立不成立成立成立成立成立2021-12-11AI:Summary29jgmibP, （2）計算）計算 2916. 09 . 08 . 05 . 09 . 09 . 0,gjPmibgPmbiPmPbPjgmibP（3）如果某人違法了選舉法，并且被有政治傾向的檢察官）如果某人違法了選舉法，并且被有政治傾向的檢察官起訴，則他被投入監獄的概率是多少？起訴，則他被投入監獄的概率是多少？ mibjP, mibj

24、PmibjPmibjPmibjPmibPmibPmibjPmibPmibjPmibjPmibjPmib, , , , , ,1, , , , ,JP2021-12-11AI:Summary30 06561. 001 . 09 . 01 . 09 . 09 . 09 . 09 . 01 . 09 . 0, , , ,gjPmibgPmbiPmPbPgjPmibgPmbiPmPbPgmibjPgmibjPmibjP 01539. 00081. 000729. 011 . 09 . 01 . 09 . 01 . 09 . 09 . 01 . 09 . 0, , , ,gjPmibgPmbiPmPbP

25、gjPmibgPmbiPmPbPgmibjPgmibjPmibjP345679.12101539. 006561. 081. 006561. 0345679.12,mibjP2021-12-11AI:Summary315.20 請說明最小平方誤差（請說明最小平方誤差（MSE），最小描述長度），最小描述長度（MDL），最大后驗概率（），最大后驗概率（MAP），極大似然（），極大似然（ML）等準則之間的聯系與區別，以及它們在智能系統中的重等準則之間的聯系與區別，以及它們在智能系統中的重要作用。要作用。答：答：聯系聯系：均為問題求解的優化準則，確定了智能系統的計：均為問題求解的優化準則，確定了智能系

26、統的計算目標（算目標（重要性重要性） 區別區別：最小平方誤差最小平方誤差是使輸入與輸出的誤差平方和最小是使輸入與輸出的誤差平方和最小化；化；最小描述長度最小描述長度是使描述數據所需編碼長度最小化；是使描述數據所需編碼長度最小化；最大后驗概率最大后驗概率是使數據對應的后驗概率最大化；是使數據對應的后驗概率最大化；極大似極大似然準則然準則是使數據同時出現的可能性最大化。是使數據同時出現的可能性最大化。2021-12-11AI:Summary335.24 假設數據集假設數據集D中含有中含有9個二維數據對象：個二維數據對象： A1(3,2), A2(3,9), A3(8,6), B1(9,5), B2

27、(2,4), B3(3,10), C1(2,6), C2(9,6), C3(2,2) 采用采用k-均值方法對數據集均值方法對數據集D進行聚類（進行聚類（k=3），），相似性度量采用歐氏距離。假設初始的三個簇相似性度量采用歐氏距離。假設初始的三個簇均值為均值為A1,B1,和和C1，求：，求： （1）第一次循環結束時的三個簇的均值。）第一次循環結束時的三個簇的均值。 （2）最后求得的三個簇。）最后求得的三個簇。 （3）當采用城區距離或）當采用城區距離或q=3的閔可夫斯基距離的閔可夫斯基距離時，情況如何？時，情況如何？ 2021-12-11AI:Summary34解：（解：（1）第一次循環：）第一次

28、循環： 計算各數據到聚類中心計算各數據到聚類中心K1=A1, K2=B1, K3=C1的歐氏的歐氏距離的平方距離的平方 d(A2, K1) =49； d(A2, K2) =52； d(A2, K3) =10； d(A3, K1) =41； d(A3, K2) =2； d(A3, K3) =36； d(B2, K1) =5； d(B2, K2) =50； d(B2, K3) =4； d(B3, K1) =64； d(B3, K2) =61； d(B3, K3) =17； d(C2, K1) =52； d(C2, K2) =1； d(C2, K3) =49； d(C3, K1) =1； d(C3,

29、 K2) =58； d(C3, K3) =16； 則三個簇及其均值分別更新為則三個簇及其均值分別更新為 A1, C3， K1=(2.5, 2) B1, A3, C2, K2=(8.7, 5.7) C1, A2, B2, B3, K3=(2.5, 7.25)2021-12-11AI:Summary35（2）第二次循環：）第二次循環： 計算各數據到聚類中心計算各數據到聚類中心K1, K2, K3的歐氏距離的平方的歐氏距離的平方 d(A1, K1) =0.25； d(A1, K2) =32.49； d(A1, K3) =27.81； d(A2, K1) =49.25； d(A2, K2) =54.5

30、8；d(A2, K3) =3.31； d(A3, K1) =46.25； d(A3, K2) =0.58； d(A3, K3) =31.81； d(B1, K1) =51.25； d(B1, K2) =0.58； d(B1, K3) =47.31 ； d(B2, K1) =4.25； d(B2, K2) =47.78； d(B2, K3) =10.81； d(B3, K1) =64.25； d(B3, K2) =50.98； d(B3, K3) =7.61； d(C1, K1) =16.25； d(C1, K2) =44.98； d(C1, K3) =1.81； d(C2, K1) =58.2

31、5； d(C2, K2) =0.18； d(C2, K3) =43.81； d(C3, K1) =0.25； d(C3, K2) =58.58； d(C3, K3) =27.81； 則三個簇及其均值分別更新為則三個簇及其均值分別更新為 A1, B2, C3， K1=(2.3, 2.7) B1, A3, C2, K2=(8.7, 5.7) C1, A2, B3, K3=(2.7, 8.3)2021-12-11AI:Summary36 第三次循環：第三次循環： 計算各數據到聚類中心計算各數據到聚類中心K1, K2, K3的歐氏距離的平方的歐氏距離的平方 d(A1, K1) =0.98； d(A1,

32、 K2) =32.49； d(A1, K3) =39.78； d(A2, K1) =40.18； d(A2, K2) =54.58；d(A2, K3) =0.58； d(A3, K1) =43.38； d(A3, K2) =0.58； d(A3, K3) =33.38； d(B1, K1) =50.18； d(B1, K2) =0.58； d(B1, K3) =50.58 ； d(B2, K1) =1.78； d(B2, K2) =47.78； d(B2, K3) =18.98； d(B3, K1) =53.78； d(B3, K2) =50.98； d(B3, K3) =2.98； d(C1

33、, K1) =10.98； d(C1, K2) =44.98； d(C1, K3) =5.78； d(C2, K1) =55.78； d(C2, K2) =0.18； d(C2, K3) =44.98； d(C3, K1) =0.58； d(C3, K2) =58.58； d(C3, K3) =38.29； 則三個簇及其均值分別更新為則三個簇及其均值分別更新為 A1, B2, C3， K1=(2.3, 2.7) B1, A3, C2, K2=(8.7, 5.7) C1, A2, B3, K3=(2.7, 8.3) 聚類穩定，循環結束聚類穩定，循環結束Nouvelle AIChapter 620

34、21-12-11AI:Summary38小測驗小測驗4. 以下以下Grid World中，除了到達目標狀態（中，除了到達目標狀態（G）的動作）的動作獲得的即時獎勵為獲得的即時獎勵為10以外，其余動作對應的即時獎勵皆為以外，其余動作對應的即時獎勵皆為0。如采用折扣系數為如采用折扣系數為0.8的累積折扣收益，請計算圖中的的累積折扣收益，請計算圖中的Q函數值，函數值，直接標注在圖中。直接標注在圖中。G1086.41086.486.41086.4Evolutionary ComputationChapter 72021-12-11AI:Summary40小測驗小測驗6.啟發式搜索算法的全局探測能力啟發式搜索算法的全局探測能力（Exploration）和局部探索能力（）和局部探索能力（Exploitation）分別指什么？分別指什么？答：答：全局探測能力全局探測能力指啟發式搜索算法在整個解空間上指啟發式搜索算法在整個解空間上進行有效探測，以免陷入局部最優解的能力。類似進行有效探測，以免陷入局部最優解的能力。類似于礦區勘探；于礦區勘探；局部探索能力局部探索能力