1、人工智能課程習題與部分解答第1章 緒論 什么是人工智能 它的研究目標是什么 什么是圖靈測試簡述圖靈測試的基本過程及其重要特征. 在人工智能的發(fā)展過程中，有哪些思想和思潮起了重要作用 在人工智能的發(fā)展過程中，有哪些思想和思潮起了重要作用 人工智能的主要研究和應用領(lǐng)域是什么其中，哪些是新的研究熱點第2章 知識表示方法 什么是知識分類情況如何 什么是知識表示不同的知識表示方法各有什么優(yōu)缺點 人工智能對知識表示有什么要求 用謂詞公式表示下列規(guī)則性知識：自然數(shù)都是大于零的整數(shù)。任何人都會死的。解 定義謂詞如下: N(x): “x是自然數(shù)”, I(x): “x是整數(shù)”, L(x): “x大于0”, D(x

2、): “x會死的”, M(x): “x是人”,則上述知識可用謂詞分別表示為: 用謂詞公式表示下列事實性知識：小明是計算機系的學生，但他不喜歡編程。李曉新比他父親長得高。 產(chǎn)生式系統(tǒng)由哪幾個部分組成 它們各自的作用是什么 可以從哪些角度對產(chǎn)生式系統(tǒng)進行分類 闡述各類產(chǎn)生式系統(tǒng)的特點。簡述產(chǎn)生式系統(tǒng)的優(yōu)缺點。 簡述框架表示的基本構(gòu)成，并給出框架的一般結(jié)構(gòu)框架表示法有什么特點試構(gòu)造一個描述你的臥室的框架系統(tǒng)。 試描述一個具體的大學教師的框架系統(tǒng)。解 一個具體大學教師的框架系統(tǒng)為：框架名：<教師-1> 類屬：<大學教師> 姓名：張宇 性別：男 年齡：32 職業(yè)：<教師&g

3、t; 職稱：副教授 部門：計算機系 研究方向：計算機軟件與理論 工作：參加時間：2000年7月 工齡：當前年份-2000工資：<工資單>把下列命題用一個語義網(wǎng)絡表示出來 (1)樹和草都是植物； (2)樹和草都是有根有葉的； (3)水草是草，且生長在水中；(4)果樹是樹，且會結(jié)果；(5)蘋果樹是果樹的一種，它結(jié)蘋果。解植物 AKOAKOHAVEHAVE有根有葉草樹AKOAKO水草果樹AKOLocate at蘋果樹水HAVE蘋果在基于語義網(wǎng)絡的推理系統(tǒng)中，一般有幾種推理方法，簡述它們的推理過程。 簡述語義網(wǎng)絡中常用的語義聯(lián)系。 用一個語義網(wǎng)絡表示：“我的汽車是棕黃色的”“李華的汽車是綠

4、色的”解 參考課件。 用語義網(wǎng)絡和框架方法表示下列知識：John gives a book to Mary解 參考課件。第3章 搜索推理技術(shù) 在人工智能中，搜索問題一般包括哪兩個重要問題 簡述搜索策略的評價標準。 比較盲目搜索中各種方法的優(yōu)缺點。試用寬度優(yōu)先搜索策略，畫出搜索樹、找出最優(yōu)搜索路線。解 （1）搜索樹參考課件。（2）最優(yōu)搜索路線：S0S1S5S10. 對于八數(shù)碼問題，設初始狀態(tài)和目標狀態(tài)如圖所示：S1=283Sg=1231648475765圖 八數(shù)碼問題試給出深度優(yōu)先（深度限制為5）和寬度優(yōu)先狀態(tài)圖。解(1) 深度優(yōu)先（深度限制為5）狀態(tài)圖為(2)寬度優(yōu)先狀態(tài)圖為 什么是啟發(fā)式搜索

5、 其中什么是評估函數(shù) 其主要作用是什么 最好優(yōu)先的基本思想是什么 有什么優(yōu)缺點 對于八數(shù)碼問題，設初始狀態(tài)和目標狀態(tài)如圖所示。設d (x)表示節(jié)點x在搜索樹中的深度，評估函數(shù)為f (x)=d (x)+w(x)，其中w(x)為啟發(fā)式函數(shù)。試按下列要求給出八數(shù)碼問題的搜索圖，并說明滿是一種A*算法，找出對應的最優(yōu)搜索路徑。（1）w (x)=h(x)表示節(jié)點x中不在目標狀態(tài)中相應位置的數(shù)碼個數(shù)；（2）w (x)=p(x)表示節(jié)點x的每一數(shù)碼與其目標位置之間的距離總和。 （3）w (x)=0，情況又如何 解 (1) 8數(shù)碼的搜索過程如圖所示：在上面確定h(x)時，盡管并不知道h*(x)具體為多少，但當

6、采用單位代價時，通過對不在目標狀態(tài)中相應位置的數(shù)碼個數(shù)的估計，可以得出至少需要移動h(x)步才能夠到達目標，顯然h(x)h*(x)。因此它滿足A*算法的要求。最優(yōu)搜索路徑: 如圖粗線所示。(2) 此時8數(shù)碼搜索圖可表示為：這時，顯然有h(x)p(x)h*(n)，相應的搜索過程也是A*算法。然而，p(x)比h(n)有更強的啟發(fā)式信息，由w(x)=p(x)構(gòu)造的啟發(fā)式搜索樹，比w(x)=h(x)構(gòu)造的啟發(fā)式搜索樹節(jié)點數(shù)要少。（3）若w(x)=0，該問題就變?yōu)閷挾葍?yōu)先搜索問題。 如圖所示，是5個城市之間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市之間的交通費用（代價）如圖中的數(shù)字，求從A到E

7、的最小費用交通路線。35ACDEB3424 圖 旅行交通圖本題是考察代價樹搜索的基本概念，了解這種搜索方法與深度優(yōu)先和寬度優(yōu)先的不同。首先將旅行交通圖轉(zhuǎn)換為代價樹如圖所示。圖 交通圖的代價樹(1) 如果一個節(jié)點已經(jīng)成為某各節(jié)點的前驅(qū)節(jié)點，則它就不能再作為該節(jié)點的后繼節(jié)點。例如節(jié)點B相鄰的節(jié)點有A和D，但由于在代價樹中，A已經(jīng)作為B的前驅(qū)節(jié)點出現(xiàn)，則它就不再作為B的后繼節(jié)點。(2) 除了初始節(jié)點A外，其它節(jié)點都有可能在代價樹中多次出現(xiàn)，為了區(qū)分它們的多次出現(xiàn)，分別用下標1、2、3標出，但它們都是圖中同一節(jié)點。例如C1和C2都代表圖中節(jié)點C。對上面所示的代價樹做寬度優(yōu)先搜索，可得到最優(yōu)解為：AC1

8、D1E2代價為8。由此可見，從A城市到E城市的最小費用路線為：ACDE如果采用代價樹的深度優(yōu)先搜索，也會得到同樣的結(jié)果：ACDE但注意：這只是一種巧合，一般情況下，這兩種方法得到的結(jié)果不一定相同。再者，代價樹的深度優(yōu)先搜索可能進入無窮分支路徑，因此也是不完備的。 對于圖所示的狀態(tài)空間圖，假設U是目標狀態(tài)，試給出寬度優(yōu)先搜索與深度優(yōu)搜索的OPEN表和CLOSED表的變化情況。圖 狀態(tài)空間圖解 寬度優(yōu)先搜索的OPEN表和CLOSED表的變化情況：1. OPEN=A; CLOSED= 2. OPEN=B,C,D; CLOSED=A3. OPEN=C,D,E,F; CLOSED=B,A4. OPEN=

9、D,E,F,G,H; CLOSED=C,B, A5. OPEN=E,F,G,H,I,J; CLOSED=D,C,B, A6. OPEN=F,G,H,I,J,K,L; CLOSED=E,D,C,B,A7. OPEN=G,H,I,J,K,L,M（由于L已在OPEN中）; CLOSED=F,E,D,C,B,A8. OPEN=H,I,J,K,L,M,N; CLOSED=G,F,E,D,C,B,A9. 以此類推，直到找到了U或OPEN= 。深度優(yōu)先搜索的OPEN表和CLOSED表的變化情況：1. OPEN=A; CLOSED= 2. OPEN=B,C,D; CLOSED=A3. OPEN=E,F,C,D

10、; CLOSED=B,A4. OPEN=K,L,F,C,D; CLOSED=E,B, A5. OPEN=S,L,F,C,D; CLOSED=K,E,B, A6. OPEN=L,F,C,D; CLOSED=S,K,E,B,A7. OPEN=T,F,C,D; CLOSED=L,S,K,E,B,A8. OPEN=F,C,D; CLOSED=T,L,S,K,E,B,A9. OPEN=M,C,D（由于L已經(jīng)在CLOSED中; CLOSED=F,T,L,S,K,E,B,A10. OPEN=C,D; CLOSED=M,F,T,L,S,K,E,B,A11. OPEN=G,H,D; CLOSED=C,M,F,T

11、,L,S,K,E,B,A12. 以此類推，直到找到了U或OPEN= 。第4章 自動推理什么是推理的控制策略有哪幾種主要的推理驅(qū)動模式自然演繹推理的基本概念與基本的推理規(guī)則。 什么是合取范式 什么是析取范式 什么是Skolem標準化 如何將一個公式化為這些形式 將下列公式化為Skolem標準型:解 在公式中，的前面沒有全稱量詞，的前面有全稱量詞和, 在的前面有全稱量詞,和。所以，在中，用常數(shù)a代替x, 用二元函數(shù)f(y,z)代替u, 用三元函數(shù)g(y,z,v)代替w,去掉前綴中的所有存在量詞之后得出Skolem標準型：化為子句形有哪些步驟解(1)利用等價謂詞關(guān)系消去謂詞公式中的蘊涵符“ ”和雙條

12、件符“ ”。(2)利用等價關(guān)系把否定符號“”移到緊靠謂詞的位置上。(3)重新命名變元名，使不同量詞約束的變元有不同的名字。(4)消去存在量詞。(5)將公式化為前束形。(6)把公式化為Skolem標準形。(7)消去全稱量詞。(8)消去合取詞。(9)對變元更名，使不同子句中的變元不同名。將下列謂詞公式化為子句集:(1) (x)P(x)Q(x)(y)S(x,y)Q(x)(x)P(x)B(x)(2)解 (1) 轉(zhuǎn)換過程遵照下列9個步驟依此為:A. 消去蘊涵符符號：B.減少否定符號的轄域：C. 變量標準化：D. 消去存在量詞：E. 化為前束型：F. 把母式化為合取范式：G. 消去全稱量詞：H. 消去合取

13、詞：I. 子句變量標準化后, 最終的子句集為：(2) 參見課本P122A. 消去蘊涵符符號：B. 減少否定符號的轄域:C. 變量標準化:D. 消去存在量詞:E. 化為前束型:F. 把母式化為合取范式:G. 消去全稱量詞:H. 消去合取詞:I. 更改變量名: 把下面的表達式轉(zhuǎn)化成子句形式 （1） （2）（3）解(1) 則子句集為 (2) 則子句集為 (3) 則子句集為 求證G是F1和F2的邏輯結(jié)論。 證明 首先將和化為子句集：F1： 所以F2： 所以 所以下面進行歸結(jié)： R(b) Q(b) L(a,b) 和 和 和 Nil 和所以，G是F1,F2的邏輯結(jié)論。利用歸結(jié)原理證明：“有些患者喜歡任一醫(yī)

14、生。沒有任一患者喜歡任一庸醫(yī)。所以沒有庸醫(yī)的醫(yī)生”。解 定義謂詞為: P(x): “x是患者”, D(x): “x是醫(yī)生”, Q(x): “x是庸醫(yī)”, L(x,y): “x喜歡y”, 則前提與結(jié)論可以符號化為:A1: A2: G: 目前是證明G是A1和A2的邏輯結(jié)論, 即證明是不可滿足的. 首先, 求出子句集合:A1: A2: : 因此的子句集合S為:歸結(jié)證明S是不可滿足的: S (2)(4) (1)(3) (5)(7)(9) Nil (6)(8)已知：能閱讀的都是有文化的； 海豚是沒有文化的； 某些海豚是有智能的；用歸結(jié)反演法證明：某些有智能的并不能閱讀。證明 首先定義謂詞:R(x): x

15、能閱讀, L(x): x有文化D(x): x是海豚, I(x): x有智能將前提形式化地表示為: A1: A2: A3: 將結(jié)論形式化地表示為: G: 即要證明為真. 即證明是不可滿足的. 把它化為子句集為:現(xiàn)在用歸結(jié)證明S是不可滿足的: S (4)(5) (1)(6) (2)(7) (9) Nil (3)(8)某人被盜，公安局派出所派出5個偵察員去調(diào)查。研究案情時: 偵察員A說：“趙與錢中至少有一人作案”； 偵察員B說：“錢與孫中至少有一人作案”； 偵察員C說：“孫與李中至少有一人作案”； 偵察員D說：“趙與孫中至少有一人與此案無關(guān)”； 偵察員E說：“錢與李中至少有一人與此案無關(guān)”。如果這5

16、個偵察員的話都是可信的，試問誰是盜竊犯呢解第一步: 設謂詞P(x)表示x是作案者，所以根據(jù)題意: A: P(zhao)P(qian) B: P(qian)P(sun) C: P(sun)P(li) D: P(zhao)P(sun) E: P(qian)P(li) 以上每個偵查員的話都是一個子句。第二步：將待求解的問題表示成謂詞。設y是盜竊犯，則問題的謂詞公式為P(y),將其否定并與ANS(y)做析取得: P(y)ANS(y)第三步:求前提條件及P(y)ANS(y)的子句集，并將各子句列表如下:(1) P(zhao)P(qian)(2) P(qian)P(sun)(3) P(sun)P(li)(

17、4) P(zhao)P(sun)(5) P(qian)P(li)(6) P(y)ANS(y)第四步：應用歸結(jié)原理進行推理。(7) P(qian)P(sun) (1) 與 (4) 歸結(jié)(8) P(zhao)P(li) (1) 與 (5) 歸結(jié)(9) P(qian)P(zhao) (2) 與 (4) 歸結(jié)(10) P(sun)P(li) (2) 與 (5) 歸結(jié)(11) P(zhao)P(li) (3) 與 (4) 歸結(jié)(12) P(sun)P(qian) (3) 與 (5) 歸結(jié)(13) P(qian) (2) 與 (7) 歸結(jié)(14) P(sun) (2) 與 (12) 歸結(jié)(15) ANS(

18、qian) (6) 與 (13) 歸結(jié)(16) ANS(sun) (6) 與 (14) 歸結(jié)所以，本題的盜竊犯是兩個人:錢和孫。 已知：張和李是同班同學，如果x和y是同班同學，則x的教室也是y的教室?，F(xiàn)在張在J1-3上課，問李在哪里上課解 首先定義謂詞：C(x,y): x 和y是同學At(x,u): x在u教室上課則已知前提可表示為C(Zhang, Li)At(Zhang, J1-3)將目標表示成謂詞:典At(Li, v)，采用重言式，得到子句集合S為：歸結(jié)過程如下：(5) (2)(4)歸結(jié) Li|y, v|u(6) (1)(5)歸結(jié) Zhang|x(7) (3)(6)歸結(jié) J1-3|v最后就

19、是所得到的答案：李在J1-3上課。第5章 不確定性推理什么是不確定性推理不確定性推理的基本問題是什么在主觀Bayes方法中，如何引入規(guī)則的強度的似然率來計算條件概率這種方法優(yōu)點是什么主觀Bayes方法有什么問題試說明LS和LN的意義。設有規(guī)則： R1: IF E1 THEN (20, 1) H R2: IF E2 THEN (300, 1) H已知證據(jù)E1和E2必然發(fā)生，并且P(H)=，求H的后驗概率。解 因為P(H)=, 則O(H)=根據(jù)R1有O(H|E1)=LS1×O(H)=20×=根據(jù)R2有O(H|E2)=LS2×O(H)=300×=那么所以H的后

20、驗概率為 設有規(guī)則： R1: IF E1 THEN (65, H R2: IF E2 THEN (300, H已知:P(E1|S1)=, P(E2|S2)=, P(H)=, P(E1)=, P(E2)=求:P(H|S1S2) 解 根據(jù)R1，因為P(E1|S1)=>P(E1)=，則有根據(jù)R2，因為P(E2|S2)=<P(E2)=，則有根據(jù)R2, 因為P(E2|S2)=<P(E2)=, 則有根據(jù)上面的計算，因為：則有根據(jù)上面的計算，因為則有 何謂可信度簡述可信度模型及其各部分含義。設有如下規(guī)則：R1: IF E1 THEN H R2: IF E2 THEN H R3: IF E3

21、 THEN H R4: IF E4 AND (E5 OR E6) THEN E1 已知CF(E2)=, CF(E3)=, CF(E4)=, CF(E5)=, CF(E6)=, 求CF(H)=解 由R4得到:CF(E1)=×max0,CF(E4 AND (E5 OR E6)=×max0,minCF(E4),CF(E5 OR E6) =×max0,minCF(E4),maxCF(E5),CF(E6)=×max0,min, =×max0,=由R1得到:CF1(H)=CF(H,E1)×max0,CF(E1)=×max0,=由R2得到

22、:CF2(H)=CF(H,E2)×max0,CF(E2)=×max0,=由R3得到:CF3(H)=CF(H,E3)×max0,CF(E3)=×max0,= 根據(jù)結(jié)論不確定性的合成算法得到:CF1,2(H)=CF1(H)+CF2(H)-CF1(H)×CF2(H)=+或者設有如下規(guī)則：R1: IF E1 THEN H R2: IF E2 THEN H R3: IF E3 THEN H R4: IF E4 AND (E5 OR E6) THEN E1 R5: IF E7 AND E8 THEN E3 在系統(tǒng)運行中已從用戶處得CF(E2)=, CF(E

23、4)=, CF(E5)=, CF(E6)=, CF(E7)=, CF(E8)=, 求H的綜合可信度CF(H)。解 (1)求證據(jù)E4,E5,E6邏輯組合的可信度(2)根據(jù)規(guī)則R4,求CF(E1) (3)求證據(jù)E7,E8邏輯組合的可信度(4)根據(jù)規(guī)則R5, 求CF(E3)(5)根據(jù)規(guī)則R1, 求CF1(H)(6)根據(jù)規(guī)則R2, 求CF2(H)(7)根據(jù)規(guī)則R3, 求CF3(H)(8)組合由獨立證據(jù)導出的假設H的可信度CF1(H),CF2(H)和CF3(H),得到H的綜合可信度:或者 設有如下規(guī)則：R1: A1B1 CF(B1,A1)=R2: A2B1 CF(B1,A2)=R3: B1A3B2 CF(B2,B1A3)=初始證據(jù)A1,A2,A3的CF值均設為1，而初始未知證據(jù)B1,B2的CF值均為0，即對B1,B2一無所知。求CF(B1),CF(B2)的更新值。解 (1) 對知識R1,R2，分別計算CF(B1)。CF1(B1)=CF(B1,A1)×max0,CF(A1)=×1=CF2(B1)=CF(B1,A2)×max0,CF(A2)=×1=(2) 計算B1的綜合可信度。CF1,2(B1)=CF1(B1)+CF2(B1)-CF1(B1)×CF2(B1) + 計算B2的可信度CF(B2)。這時，B1作為B2的證據(jù)，其可