人工智能復(fù)習(xí)資料

1、S 狀態(tài)G 狀態(tài)、選擇填空1. 產(chǎn)生式系統(tǒng)由 綜合數(shù)據(jù)庫，規(guī)則庫，控制策略 三個部分組成2. - 剪枝中，極大節(jié)點下界是 ，極小節(jié)點是 。3. 發(fā)生剪枝的條件是 祖先節(jié)點 值<=后輩節(jié)點的 值。4. 發(fā)生剪枝的條件是 后輩節(jié)點 值<=祖先節(jié)點的 值。5. 在 證 據(jù) 理 論 中 ， 信 任 函 數(shù) Bel(A) 與 似 然 函 數(shù) Pl(A) 的 關(guān) 系 為 0<=Bel(A)<=Pl(A)<=1 。6. 深度優(yōu)先算法 的節(jié)點按深度遞減 的順序排列 OPEN中的節(jié)點。7. 寬度優(yōu)先算法 的節(jié)點按深度遞增 的順序排列 OPEN中的節(jié)點。8. A 算法失敗的充分條件是

2、 OPEN 表為空。9. A 算法中 OPEN 中的節(jié)點按 f 值從小到大 排序。10. 爬山算法(不可撤回方式) 是只考慮局部信息， 沒有從全局角度考慮最佳選 擇。 f(n)= g(n) 只考慮搜索過的路徑已經(jīng)耗費的費用11. 分支界限算法(動態(tài)規(guī)劃算法) ：f(n)= h(n) 只考慮未來的發(fā)展趨勢。僅保留 queue中公共節(jié)點路徑中 耗散值最小的路徑 ，余者刪去，按 g 值升序排序。12. 回溯策略 是試探性地選擇一條規(guī)則，如發(fā)現(xiàn)此規(guī)則不合適，則退回去另選其 它規(guī)則。定義合適的回溯條件新產(chǎn)生的狀態(tài)在搜索路徑上已經(jīng)出現(xiàn)過。 深度 限制 (走到多少層還沒有到目標，就限制往回退 ) 當前狀態(tài)無

3、可用規(guī)則。13.A* 選中的任何節(jié)點都有 f(n)<=f*(s)<f(t) 。14. h(n)與 h*(n)的關(guān)系是 h(n)>=h*(n) ，g(n)與 g*(n)的關(guān)系是 g(n) g*(n) 。15. 求解圖的時候，選擇一個正確的外向連接符是 順著現(xiàn)有的連接符的箭頭方向 去找，不能逆著箭頭走 。16. 根節(jié)點 ：不存在任何 父節(jié)點 的節(jié)點。 葉節(jié)點 ：不存在任何 后繼節(jié)點 的節(jié)點。17. 兩個置換 s1,s2的合成置換用 s1s2表示。它是 s2作用到 s1 的 項。18. LS和 LN 兩個參數(shù)之間應(yīng)該滿足 LS、LN>=0,不獨立，LS、LN 可以同時 =1，

4、 LS、LN 不能同時 >1 或<1。19. 語義網(wǎng)絡(luò) ：一般用三元組(對象，屬性，值)或(關(guān)系，對象 1，對象 2)20. 反向推理方法 ：定義：首先提出假設(shè)，然后驗證假設(shè)的真假性，找到假設(shè)成 立的所有證據(jù)或事實。21. 證據(jù) A 的不確定性范圍： -1 CF( A) 1。22. 析取范式 ：僅由有限個簡單 合取式組成 的析取式。23. 合取范式 ：僅由有限個簡單 析取式組成 的合取式。24. 原子公式 ：由原子符號 與 項(為常量、變量和函數(shù)) 構(gòu)成的公式為原子公式。二、產(chǎn)生式系統(tǒng)(第一章)給定一個初始狀態(tài) S、一個目標狀態(tài) G，求從 S到 G 的走步序列。解： 綜合數(shù)據(jù)庫定義

5、：矩陣（ Sij）表示任何狀態(tài)，其中：Sij0,1, 8 1i,j 3 Sij 互不相同 狀態(tài)空間： 9！ =362,880 種狀態(tài) 規(guī)則集 設(shè)：空格移動代替數(shù)碼移動。至多有四種移動的可能： 上、下、左、右。定義： Sij 為矩陣第 i 行 j 列的數(shù)碼 ;其中： i0,j0 表示 空格所在的位置，則 Si0j0=0 （ 0 代表空格） 空格左移規(guī)則：if j0-1 1 then j0 j0-1; Si0j0 0如果當前空格不在第一列，則空格左移一位，新的空格位置賦值為 0 同理：右移規(guī)則： if j0+1 3 then j0 j0+1; Si0j0 0 上移規(guī)則： if i0-1 1 the

6、n i0i0-1; Si0j0 0 下移規(guī)則： if i0+1 3 then i0 i0+1; Si0j0 0 控制策略（1）爬山算法目標狀態(tài)， 最不利狀態(tài)，W(n)=0 W(n)= 8設(shè)： W（n） ：不在位的數(shù)碼個數(shù)n：任意狀態(tài)每個數(shù)碼都在規(guī)定的位置）每個數(shù)碼都不在規(guī)定的位置） W(n)= 5左 W(n)= 4右（ 3）上上 W(n)=5左 3） 3）其余 2 種移 動（略）深度 =1深度 =42）回溯策略限定搜索深度為6，移動次序為左上右下。可用規(guī)則：左、上、右左可用規(guī)則：上、右可用規(guī)則：左、右、下左限定搜索深度 = 6 規(guī)則排列次序： 左移、上移、右移、下移深度 =5此狀態(tài)與深度 =3

7、 的狀態(tài)相同深度 =6與深度 =4 狀 態(tài)相同且深 度=63） A 算法令： g(n)=d(n) h(n)=w(n)則 f(n)=d(n)+w(n)節(jié)點深度不在位的數(shù)碼個數(shù)（啟發(fā)函數(shù)）632 4G 7423L(5)47427351 4 742736)4H41732 831 6C(6)F(6)427 5 81 47 6521475867138475目標1 237 8465M(7)三、第二章和第四章1）超圖（與或圖）找解圖，并計算解圖耗散值n4n8解圖 1n4n8解圖 2左圖耗散值 K(n0,N) 1+ K(n1,N) 1+1+ K(n3,N) 1+1+2+ K(n5,N)+ K(n6,N) 1+

8、1+2+2+ K(n7,N)+ K(n8,N)+2+ K(n7,N)+ K(n8,N) 1+ 1+ 2+ 2+ 0+ 0+ 2+ 0+ 0 8右圖耗散值 K(n0,N) 2+ K(n4,N) + K(n5,N) 2+ 1+K(n5N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+K(n7,N) +K(n8,N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+ 0+ 0+ 2+ 0+ 0 7（2） -剪枝，并在博弈樹上給出是何處發(fā)生剪枝的標志， 并標明 是哪種剪枝，各生成節(jié)點的到推值以及選擇的走步路徑。-33）語義網(wǎng)絡(luò)表示1. 書本 p137，根據(jù)已知規(guī)則畫出與或圖答案

9、：斑馬長頸鹿 信天翁企鵝鴕鳥有毛發(fā) 有奶有羽毛 會飛 會下蛋2. 王峰熱愛祖國。 答案：（熱愛，王峰，祖國）3、Micheal 是一個雇員， Jack 是他老板，有一天 Micheal 這個人 kickedemployee boss答案：4、李強是某大學(xué)計算機系教師， 35 歲，副教授，該大學(xué)位于北京 答案：四、第五章（1）確定性推理1、已知： R1：A1B1 CF（B1，A1） 0.8R2：A2B1 CF（B1，A2 ）0.5 R3：B1A3B2CF（B2，B1A3）0.8CF（A1）=CF（A2）=CF（A3）=1；CF（B1）= CF（B2）=0；計算 ：CF（B1）、 CF（B2）解：

10、依規(guī)則 R1，CF（B1|A1）CF（B1）CF（B1，A1）（1CF（B1） 0.8， 即更新后 CF（B1） 0.8依規(guī)則 R2：CF（B1|A2）CF（B1）CF（B1，A2）（1CF（B1） 0.9 更新后 CF（B1） 0.9依 R3，先計算CF（B1A3）min（CF（A3），CF（B1） 0.9由于 CF（B1A3 ） <1，CF（B2| B1A3）= CF（B2）+ CF（B1A3）× CF（B2，B1A3）×（1-CF（B2）=0+0.9×0.8（1-0）=0.722、課本 p203 頁 作業(yè) 5.10 設(shè)有以下知識：R1：IF E1 TH

11、EN H(0.9);R2：IF E2 THEN H(0.6);R3：IF E3 THEN H(-0.5);R4：IF E4 AND (E5 OR E6) THEN E1(0.8);已知 CF(E2)=0.8，CF(E3)=0.6,CF(E4)=0.5,CF(E5)=0.6， CF(E6)=0.8. 求： CH(H).解：CF (E5 E6) max CF ( E 5), CF (E6) 0.8CF(E4 (E5 E6) min CF(E4),CF(E5 E6) 0.5CF (E1) max0, CF (E4 (E5 E6) CF (E1,E4 (E5 E6) 0.5 0.8 0.4CF1(H)

12、 max0, CF (E1) CF (H,E1) 0.4 0.9 0.36CF2(H ) max0, CF ( E2) CF(H ,E2) 0.8 0.6 0.48CF3(H ) max0, CF ( E3) CF(H , E3) 0.6 0.5 0.3CF12(H) CF1(H ) CF2(H) CF1(H)CF2(H ) 0.36 0.48 0.36 0.48 0.6672CF (H ) CF12(H) CF3(H ) 0.6672 0.3 0.3672(2)證據(jù)理論1、設(shè) U=a,b,c,d ，A=a,b ，B=a,b,c ，m(A)=0.6 ，m(U)=0.4，U 的其它子集的 m 值

13、均為 0 。解：Bel(B)=m(a,b,c)+m(a,b)+m(a,c)+m(b,c)+m(a)+m(b) +m(c)+m( )=0.6Pl(A)=1-Bel(a,b')=1-Bel(c,d)=1-(m(c,d)+m(c)+m(d)+m( )=1Bel(A)=m(a,b)+m(a)+m(b)+m( )=0.63、已 知 ： f1(A1) = 0.40， f1(A2)=0.50 ， |U| = 20， A1 B=b1,b2,b3 ，(c1,c2,c3)=(0.1,0.2,0.3)，A2B=b1,b2,b3 ， (c1,c2,c3)=(0.5,0.2,0.1)求： f1(B)解：先求：

14、m1(b1,b2,b3)=(0.4*0.1,0.4*0.2,0.4*0.3)=(0.04,0.08,0.12); m1(U)=1- m1(b1)+m1(b2)+m1(b3)=0.76; m2(b1,b2,b3)=(0.5*0.5,0.5*0.2,0.5*0.1)=(0.25,0.10,0.05); m2(U)=1- m2(b1)+m2(b2)+m2(b3)=0.70;求 m =m1 m21/K=m1(b1)*m2(b1)+ m1(b1)*m2(U)+ m1(b2)*m2(b2)+ m1(b2)*m2(U)+ m1(b3)*m2(b3)+ m1(b3)*m2(U)+ m1(U)*m2(b1)+

15、m1(U)*m2(b2)+ m1(U)*m2(b3)+ m1(U)*m2(U)=0.01+0.028+0.008+0.056+0.06+0.084+0.19+0.076+0.038+0.532=1/1.082有：m(b1)=K*(m1(b1)*m2(b1)+m1(b1)*m2(U) +m1(U)*m2(b1)=1.082*(0.01+0.028+0.19)=0.247 m(b2)=K*(m1(b2)*m2(b2)+m1(b2)*m2(U)+m1(U)*m2(b2)=1.082*(0.008+0.056+0.076) =0.151 m(b3)=K*(m1(b3)*m2(b3)+m1(b3)*m2

16、(U)+m1(U)* m2(b3) =1.082*(0.06+0.084+0.038)=0.138 m(U)=1- m(b1)+ m(b2)+ m(b3)=0.464 最后：Bel( B) m(b1)+ m(b2)+ m(b3) 0.536P1(B)1-Bel(B)由于基本概率分配函數(shù)只定義在 B 集合和全集 U 之上，所以其它集合的分配函數(shù)值為 0，即 Bel(B)=0所以，可得P1(B)1-Bel(B)=1 f1(B)=Bel(B)+(P1(B)-Bel(B)*|B|/|U|=0.536+(1-0.536)*3/20=0.606五、第三章(1)基于歸結(jié)的演繹系統(tǒng)1、已知前提： (1)能閱讀

17、的人是識字的(2) 海豚都不識字(3) 有些海豚是聰明的 求證：有些聰明的東西不會閱讀 證明：用謂詞形式表達所有前提以及結(jié)論。R(x)：x 會閱讀L(x)：x 識字D(x)：x 是海豚I(x)：x 是聰明的解： x(R(x) L(x) x(D(x) I(x) x(I(x) R(x)結(jié)論： x(D(x) L(x)利用公式標準化方法求出上式的 S 標準形，再寫出對應(yīng)的子句集求證過S程0 ： W R(x) L(x), D(y) L( y), D ( A), I (A), I (z) R(z) R(A)(4)， (5) 的歸結(jié)式L (A)(1)， (6) 的歸結(jié)式D (A)(2)，(7) 的歸結(jié)式NI

18、L(3) ，(8) 的歸結(jié)式2、證明R1：所有不貧窮且聰明的人都快樂：R2：那些看書的人是聰明的：R3：李明能看書且不貧窮：R4：快樂的人過著激動人心的生活： 結(jié)論李明過著激動人心的生活的否定： 將上述謂詞公式轉(zhuǎn)化為子句集并進行歸結(jié)如下： 由 R1 可得子句： Poor ( x) Smart( x) Happy(x)由 R2 可得子句： read( y ) Smart( y)由 R3 可得子句： read (Li ) Poor(Li )由 R4 可得子句： Happy( z) Exciting (z)有結(jié)論的否定可得子句： Exciting (Li )根據(jù)以上 6 條子句，歸結(jié)如下：Happy

19、(Li )Li/zPoor ( Li ) Smart(Li )Li/xSmart( Li )read( Li )Li/y11由上可得原命題成立(2)基于歸結(jié)的問答系統(tǒng) 如果 Peter去哪兒，則 Fido 就去那兒 如果 Peter 在學(xué)校 問題： Fido 就去那兒？ 解：用謂詞公式表達所有前提以及結(jié)論。 x(AT(Peter,x) AT( Fido, x) AT(Peter,school)結(jié)論 AT(Fido,y) AT(Fido,y)子句集： AT ( Peter , x) AT ( Fido , x), AT ( Peter, school ), AATT(Fi(dofi,dyo) ,AyT)(Fido, y)練習(xí)：1、已知： U=