人工智能課后答案

1、第一章課后習(xí)題1、對(duì)N= 5、k£3時(shí)，求解傳教士和野人問題的產(chǎn)生式系統(tǒng)各組成部分進(jìn)行描述 （給出綜合數(shù)據(jù)庫(kù)、規(guī)則集合的形式化描述，給出初始狀態(tài)和目標(biāo)條件的描述）， 并畫出狀態(tài)空間圖。2、對(duì)量水問題給出產(chǎn)生式系統(tǒng)描述，并畫出狀態(tài)空間圖。有兩個(gè)無刻度標(biāo)志的水壺，分別可裝5升和2升的水。設(shè)另有一水缸，可用來向 水壺灌水或倒出水，兩個(gè)水壺之間，水也可以相互傾灌。已知 5開壺為滿壺，2 開壺為空壺，問如何通過倒水或灌水操作，使能在 2升的壺中量出一升的水來。3、對(duì)梵塔問題給出產(chǎn)生式系統(tǒng)描述，并討論 N為任意時(shí)狀態(tài)空間的規(guī)模。相傳古代某處一廟宇中，有三根立柱，柱子上可套放直徑不等的N個(gè)圓盤，開

2、始 時(shí)所有圓盤都放在第一根柱子上， 且小盤處在大盤之上，即從下向上直徑是遞減 的。和尚們的任務(wù)是把所有圓盤一次一個(gè)地搬到另一個(gè)柱子上去（不許暫擱地上等），且小盤只許在大盤之上。問和尚們?nèi)绾伟岱ㄗ詈竽芡瓿蓪⑺械谋P子都移 到第三根柱子上（其余兩根柱子，有一根可作過渡盤子使用）。求N= 2時(shí)，求解該問題的產(chǎn)生式系統(tǒng)描述，給出其狀態(tài)空間圖。討論N為任意時(shí)，狀態(tài)空間的規(guī)模。4、對(duì)猴子摘香蕉問題，給出產(chǎn)生式系統(tǒng)描述。一個(gè)房間里，天花板上掛有一串香蕉，有一只猴子可在房間里任意活動(dòng)（到處走 動(dòng)，推移箱子，攀登箱子等）。設(shè)房間里還有一只可被猴子移動(dòng)的箱子，且猴子 登上箱子時(shí)才能摘到香蕉，問猴子在某一狀態(tài)下（設(shè)

3、猴子位置為a,箱子位置為b,香蕉位置為c）,如何行動(dòng)可摘取到香蕉。5、對(duì)三枚錢幣問題給出產(chǎn)生式系統(tǒng)描述及狀態(tài)空間圖。設(shè)有三枚錢幣，其排列處在"正、正、反”狀態(tài)，現(xiàn)允許每次可翻動(dòng)其中任意一個(gè) 錢幣，問只許操作三次的情況下，如何翻動(dòng)錢幣使其變成 "正、正、正"或"反、 反、反”狀態(tài)。6、說明怎樣才能用一個(gè)產(chǎn)生式系統(tǒng)把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)，并通過轉(zhuǎn)換 141.125這個(gè)數(shù)為二進(jìn)制數(shù)，闡明其運(yùn)行過程。7、設(shè)可交換產(chǎn)生式系統(tǒng)的一條規(guī)則 R可應(yīng)用于綜合數(shù)據(jù)庫(kù)D來生成出D',試證 明若R存在逆，則可應(yīng)用于D'的規(guī)則集等同于可應(yīng)用于D的規(guī)則集。8、一個(gè)

4、產(chǎn)生式系統(tǒng)是以整數(shù)的集合作為綜合數(shù)據(jù)庫(kù)，新的數(shù)據(jù)庫(kù)可通過把其中 任意一對(duì)元素的乘積添加到原數(shù)據(jù)庫(kù)的操作來產(chǎn)生。設(shè)以某一個(gè)整數(shù)子集的出現(xiàn)作為目標(biāo)條件，試說明該產(chǎn)生式系統(tǒng)是可交換的。第二章課后習(xí)題第二章課后習(xí)題1、用回溯策略求解如下所示二階梵塔問題，畫出搜索過程的狀態(tài)變化示意圖。對(duì)每個(gè)狀態(tài)規(guī)定的操彳順序?yàn)椋合劝?柱的盤，放的順序是先 2柱后3柱；再搬2柱的盤,放的順序是先3柱后1柱；最后搬3柱的盤，放的順序是先 1柱后2柱。2、滑動(dòng)積木塊游戲的棋盤結(jié)構(gòu)及某一種將牌的初始排列結(jié)構(gòu)如下:其中B表示黑色將牌， W表示白色將牌，E表示空格。游戲的規(guī)定走法是：(1)任意一個(gè)將牌可以移入相鄰的空格，規(guī)定其耗散

5、值為1;(2)任意一個(gè)將牌可相隔 1個(gè)或2個(gè)其他的將牌跳入空格，規(guī)定其耗散值等于跳過將牌的 數(shù)目；游戲要達(dá)到的目標(biāo)是使所有白將牌都處在黑將牌的左邊(左邊有無空格均可)。對(duì) 這個(gè)問題，定義一個(gè)啟發(fā)函數(shù)h(n),并給出利用這個(gè)啟發(fā)函數(shù)用算法A求解時(shí)所產(chǎn)生的搜索樹。你能否辨別這個(gè) h(n)是否滿足下界圍？在你的搜索樹中，對(duì)所有的節(jié)點(diǎn)滿足不滿足 單調(diào)限制？3、對(duì)1.4節(jié)中的旅行商問題，定義兩個(gè)h函數(shù)(非零)，并給出利用這兩個(gè)啟發(fā)函數(shù)用算法A求解1.4節(jié)中的五城市問題。討論這兩個(gè)函數(shù)是否都在h*的下界圍及求解結(jié)果。4、2.1節(jié)四皇后問題表述中，設(shè)應(yīng)用每一條規(guī)則的耗散值均為1,試描述這個(gè)問題 h*函數(shù)的一

6、般特征。你是否認(rèn)為任何h函數(shù)對(duì)引導(dǎo)搜索都是有用的？5、對(duì)N= 5, k<3的Mk C問題，定義兩個(gè)h函數(shù)(非零)，并給出用這兩個(gè)啟發(fā)函數(shù)的A算法搜索圖。討論用這兩個(gè)啟發(fā)函數(shù)求解該問題時(shí)是否得到最佳解。6、證明OPENH上具有f(n) vf*(s)的任何節(jié)點(diǎn)n,最終都將被 A*選擇去擴(kuò)展。7、如果算法A*從OPEN表中去掉任一節(jié)點(diǎn) n,對(duì)n有f(n) >F (F>f*(s)，試說明為什么 算法A*仍然是可采納的。8、用算法A逆向求解圖2.7中的八數(shù)碼問題，評(píng)價(jià)函數(shù)仍定義為f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相會(huì)。9、討論一個(gè)h函數(shù)在搜索期間可以得到改善的幾

7、種方法。每個(gè)圓盤可單獨(dú)轉(zhuǎn)動(dòng)。問如何轉(zhuǎn)動(dòng)圓盤使得八個(gè)徑10、四個(gè)同心圓盤的扇區(qū)數(shù)字如圖所示, 向的4個(gè)數(shù)字和均為12。第三章課后習(xí)題1、數(shù)字重寫問題的變換規(guī)則如下:6一3, 343, 16一4, 232, 14一2, 22 1, 1問如何用這些規(guī)則把數(shù)字 6變換成一個(gè)由若干個(gè) 1組成的數(shù)字串。試用算法AO*a行求 解，并給出搜索圖。求解時(shí)設(shè) k-連接符的耗散值是 k個(gè)單位，h函數(shù)值規(guī)定為：h (1) =0, h (n) = n (nw 1)。2、余一棋的弈法如下：兩棋手可以從5個(gè)錢幣堆中輪流拿走一個(gè)、兩個(gè)或三個(gè)錢幣，揀起最后一個(gè)錢幣者算輸。試通過博弈證明，后走的選手必勝，并給出一個(gè)簡(jiǎn)單的特征 標(biāo)

8、記來表示取勝策略。3、對(duì)下圖所示的博弈樹，以優(yōu)先生成左邊節(jié)點(diǎn)順序來進(jìn)行a - 3搜索，試在博弈樹上給出何處發(fā)生剪枝的標(biāo)記，并標(biāo)明屬于a剪枝還是3剪枝。4、AO*算法中，第7步從S中選一個(gè)節(jié)點(diǎn)，要求其子不在 S中出現(xiàn)，討論應(yīng)如何實(shí)現(xiàn)對(duì) S的控制使得能有效地選出這個(gè)節(jié)點(diǎn)。如下圖所示，若E的耗散值發(fā)生變化時(shí)，所提出的對(duì)S的處理方法應(yīng)能正確工作。5、如何修改AO*B法使之能處理出現(xiàn)回路的情況。如下圖所示，若節(jié)點(diǎn)C的耗散值發(fā)生變化時(shí)，所修改的算法能正確處理這種情況。6、對(duì)3X3的一字棋，設(shè)用+1和-1分別表小兩選手棋子的標(biāo)記，用。表布空格，試給出一字棋產(chǎn)生式系統(tǒng)的描述。7、寫一個(gè) .3搜索的算法。8、用

9、一個(gè)9維向量C來表示一字棋棋盤的格局，其分量根據(jù)相應(yīng)格的X,空或。的標(biāo)記分別用+1, 0,或-1來表示。試規(guī)定另一個(gè) 9維向量 W 使得點(diǎn)積C-W可作為MAX 選手（棋子標(biāo)記為X） 估計(jì)非終端位置的一個(gè)有效的評(píng)價(jià)函數(shù)。用這個(gè)評(píng)價(jià)函數(shù)來完成幾步極小-極大搜索，并分析該評(píng)價(jià)函數(shù)的效果。第四章課后習(xí)題1、化下列公式成子句形式：(1) ( Vx) P (x) -P (x)(2) (Vx) P (x) 一(mx) P (x)(3) (Vx) P (x) 一 (Vy) P (y) -P (f (x, y) ) A (Vy) Q (x, y) -P (y) (4) ( Vx) (my) P (x, y) -

10、 Q ( y, x) A Q (y, x) - S ( x, y) 一(x) (|Vy) P (x, y) -S (x, y)2、以一個(gè)例子證明置換的合成是不可交換的。3、找出集P (x, z, y) , P (w, u, w) , P (A, u, u) 的 mgui4、說明下列文字集不能合一的理由：(1) P (f (x, x) , A) , P (f (y, f (y, A) ) , A) (2) P (A) , P (x) (3) P (f (A) , x) , P (x, A) 5、已知兩個(gè)子句為L(zhǎng)oves (father (a) , a)Loves (y, x) V Loves (

11、x, y)試用合一算法求第一個(gè)子句和第二個(gè)子句的第一個(gè)文字合一時(shí)的結(jié)果。6、用歸結(jié)反演法證明下列公式的永真性：(1) (Ex) P (x) -P (A) AP(x) -P (B) (2) ( Vz)Q (z) - P (z) 一(叫)Q(x) - P (A) AQ (x)- P ( B) (3) (Ex)(Ry) P (f (x) ) A Q (f(B) 一P ( f(A) A P(y) A Q (y)(4) (cox) ( Vy) P (x, y) 一(忖y) (ex) P (x, y)(5) ( Vx) P (x) A Q (A) V Q (B) 一(ex) P (x) A Q (x)7、

12、以歸結(jié)反演法證明公式 (x) P (x)是P (Ai) VP (4)的邏輯推論，然而, P (x)的Skolem形即P (A)并非P (A) V P (AO 的邏輯推論，請(qǐng)加以證明。8、給定下述語句：John likes all kinds of food.Apples are food.Anything anyone eats and isn't killed by is food.Bill eats peanuts and is still alive.Sue eats everything Bill eats.(1)用歸結(jié)法證明"John likes peanuts 。

13、"(2)用歸結(jié)法提取回答 "What food does Sue eat?"9、已知事實(shí)公式為(|Vx) ( Vy) ( Vz) (Gt (x, y) A Gt (y, z) 一Gt (x, z)(|Vu) ( Wv) ( Succ (u, v) 一Gt ( u, v)(Mx) ( Gt (x, x)求證 Gt (5, 2)試判斷下面的歸結(jié)過程是否正確？若有錯(cuò)誤應(yīng)如何改進(jìn)：10、設(shè)公理集為(Vu) LAST (cons (u, NIL) , u) (cons 是表構(gòu)造函數(shù))(Vx) (|Wy) (Vz) (LAST (y, z) -LAST( cons (x, y

14、) , z) ) (LAST (x, y)代表y是表x的最末元素)(1)用歸結(jié)反演法證明如下定理：(v) LAST (cons (2, cons (1, NIL) ) , v)(2)用回答提取過程求表(2, 1)的最末元素v。(3)簡(jiǎn)要描述如何使用這個(gè)方法求長(zhǎng)表的最末元素。11、對(duì)一個(gè)基于規(guī)則的幾何定理證明系統(tǒng)，把下列語句表示成產(chǎn)生式規(guī)則：(1)兩個(gè)全等的三角形的對(duì)應(yīng)角相等。(2)兩個(gè)全等的三角形的對(duì)應(yīng)邊相等。(3)如果兩個(gè)三角形對(duì)應(yīng)邊是相等的，則這兩個(gè)三角形全等。(4) 一個(gè)等腰三角形的底角是相等的。12、我們來考慮下列一段知識(shí)：Tony、Mike和John屬于Alpine俱樂部，Alpin

15、e俱樂部的每個(gè)成員不是滑雪運(yùn)動(dòng)員就是一個(gè)登山運(yùn)動(dòng)員，登山運(yùn)動(dòng)員不喜歡雨而且任一不喜歡雪的人不是滑雪運(yùn)動(dòng)員，Mike討厭Tony所喜歡的一切東西，而喜歡 Tony所討厭的一切東西，Tony喜歡雨和雪。以謂詞演算語句的集合表示這段知識(shí)，這些語句適合一 個(gè)逆向的基于規(guī)則的演繹系統(tǒng)。試說明這樣一個(gè)系統(tǒng)怎樣才能回答問題"有沒有Alpine俱樂部的一個(gè)成員，他是一個(gè)登山運(yùn)動(dòng)員但不是一個(gè)滑雪運(yùn)動(dòng)員呢？"13、一個(gè)積木世界的狀態(tài)由下列公式集描述：ONTABLEA)CLEAR( E)ONTABLE QCLEAR( D)ON (D, C)HEAVY( D)ON (B, A)WOODENB)HE

16、AVY(B)ON (E, B)繪出這些公式所描述的狀態(tài)的草圖。 下列語句提供了有關(guān)這個(gè)積木世界的一般知識(shí)： 每個(gè)大的藍(lán)色積木塊是在一個(gè)綠色積木塊上。 每個(gè)重的木制積木塊是大的。 所有頂上沒有東西的積木塊都是藍(lán)色的。 所有木制積木塊是藍(lán)色的。以具有單文字后項(xiàng)的蘊(yùn)涵式的集合表示這些語句。繪出能求解"哪個(gè)積木塊是在綠積木塊上"這個(gè)問題的一致解圖(用B規(guī)則)。答案第一章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題答：1,綜合數(shù)據(jù)庫(kù)定義三元組：( m, c, b )其中：卜加M5,表示傳教士在河左岸的人數(shù)。表示野人在河左岸的認(rèn)輸。匕b=l,表示船在左岸，

17、b=0,表示船在右岸。2,規(guī)則集規(guī)則集可以用兩種方式表示，兩種方法均可。第一種方法：按每次渡河的人數(shù)分別寫出每一個(gè)規(guī)則，共 (3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八種渡河的可能(其中(x y)表示x個(gè)傳教士和y個(gè)野人上船渡河): 因此共有16個(gè)規(guī)則(從左岸到右岸、右岸到左岸各八個(gè))。注意：這里沒有(1 2),因?yàn)樵摻M合在船上的傳教士人數(shù)少于野人人數(shù)。規(guī)則集如下：門：IF (m, c, 1) THEN (m-3, c, 0)r2： IF (m, c, 1) THEN (m, c-3, 0)r3 : IF (m, c, 1) THEN (m-

18、2, c-1,0)r4： IF (m, c, 1) THEN (m-1, c-1,0)r5: IF (m, c, 1) THEN (m-1, c, 0)r6: IF (m, c, 1) THEN (m, c-1,0)r7: IF (m, c, 1) THEN (m-2, c, 0)r8: IF (m, c, 1) THEN (m, c-2, 0)r9 : IF (m, c, 0) THEN (m+3, c, 1)r10 ： IF (m, c, 0) THEN (m, c+3, 1)r11 ： IF (m, c, 0) THEN (m+2, c+1, 1)r12 ： IF (m, c, 0) T

19、HEN (m+1, c+1, 1)r13 : IF (m, c, 0) THEN (m+1, c, 1)r14： IF (m, c, 0) THEN (m, c+1, 1)r15 ： IF (m, c, 0) THEN (m+2, c, 1)r16 : IF (m, c, 0) THEN (m, c+2, 1)第二種方法：將規(guī)則集綜合在一起，簡(jiǎn)化表示。規(guī)則集如下：門：IF (m, c, 1) and 0< i+j=3 and (i>= j or i=0) THEN (m-i, c-j, 0)r2 ： IF (m, c, 0) and 0< i+j=3 and (i>=

20、j or i=0) THEN (m+i, c+j, 1)3,初始狀態(tài):(5, 5,1)4,結(jié)束狀態(tài)：(0, 0, 0)答：1 ,綜合數(shù)據(jù)庫(kù)5升的壺的當(dāng)前水量。2升的壺的當(dāng)前水量。將L5灌滿水*/將L2灌滿水*/將L5水到光*/將L2水到光*/定義兩元組：(L5, L2 ) 其中：0<=L5<=5,表示容量為0<=L2<=2,表示容量為2,規(guī)則集ri : IF (L5, L2) THEN (5, L2) /* r2 : IF (L5, L2) THEN (L5, 2) /* r3 : IF (L5, L2) THEN (0, L2) /* r4 : IF (L5, L2)

21、 THEN (L5, 0) /*到入L5中*/到入L5中*/到入L2中*/到入L2中*/r5 : IF (L5, L2) and L5+L2<=5 THEN (L5+L2, 0) /* L2 r6 : IF (L5, L2) and L5+L2>5 THEN (5, L5+L2-5) /* L2 r7 : IF (L5, L2) and L5+L2<=2 THEN (0, L5+L2) /* L5 r8 : IF (L5, L2) and L5+L2>5 THEN (L5+L2-2, 2) /* L5 3,初始狀態(tài)：(5, 0)4,結(jié)束條件：(x, 1)，其中x表示不定

22、。當(dāng)然結(jié)束條件也可以寫成：(0,1)第3題答：1 ,綜合數(shù)據(jù)庫(kù)定義三元組：(A, B, C)其中A, B, C 分別表示三根立柱，均為表，表的元素為1N之間的整數(shù)，表示N個(gè)不同大小的盤子，數(shù)值小的數(shù)表示小盤子，數(shù)值大的數(shù)表示大盤子。表的第一個(gè)元素表示立柱最上面的柱子，其余類推。2,規(guī)則集為了方便表示規(guī)則集，引入以下幾個(gè)函數(shù)：first(L):取表的第一個(gè)元素，對(duì)于空表， first得到一個(gè)很大的大于N的數(shù)值。tail(L):取表除了第一個(gè)元素以外，其余元素組成的表。cons(x, L):將x加入到表L的最前面。規(guī)則集：r1: IF(A,B, C)and(first(A)< first(B

23、) THEN(tail(A), cons(first(A), B), C)r2: IF(A,B, C)and(first(A)< first(C) THEN(tail(A), B, cons(first(A), C)r3: IF(A,B, C)and(first(B)< first(C) THEN(A, tail(B), cons(first(B), C)r4: IF(A,B, C)and(first(B)< first(A) THEN(cons(first(B), A), tail(B), C)r5: IF(A,B, C)and(first(C)< first(A)

24、THEN(cons(first(C), A), B, tail(C)r6: IF(A,B, C)and(first(C)< first(B) THEN(A, cons(first(C), B), tail(C)3,初始狀態(tài)：(1, 2,，N),(),()4,結(jié)束狀態(tài)：()，()，(1,2, . , N)問題的狀態(tài)規(guī)模：每一個(gè)盤子都有三中選擇：在A上、或者在B上、或者在C上，共N個(gè)盤子，所以共有3加種可能。即問題的狀態(tài)規(guī)模為|3耳。答：1 ,綜合數(shù)據(jù)庫(kù)定義 5 元組：(M, B, Box, On, H ) 其中：M:猴子的位置B:香蕉的位置Box：箱子的位置On=0:猴子在地板上On=1:

25、猴子在箱子上H=0:猴子沒有抓到香蕉H=1:猴子抓到了香蕉2,規(guī)則集r1: IF (x,y,z, 0,0) THEN(w, y, z,0, 0)r2: IF (x,y,x, 0,0) THEN(z, y, z,0, 0)z處r3: IF (x,y,x, 0,0) THEN(x, y, x,1,0)r4: IF (x,y,x, 1,0) THEN(x, y, x,0, 0)r5: IF (x,x,x, 1,0) THEN(x, x, x,1, 1)摘到香蕉其中x, y, z, w 為變量3,初始狀態(tài)(c, a, b, 0, 0)猴子從x處走到w處如果猴子和箱子在一起，猴子將箱子推到如果猴子和箱子

26、在一起，猴子爬到箱子上如果猴子在箱子上，猴子從箱子上下來如果箱子在香蕉處，猴子在箱子上，猴子4,結(jié)束狀態(tài)(x1, x2, x3, x4, 1)其中x1x4為變量。第5題答：1 ,綜合數(shù)據(jù)庫(kù)定義四元組：(x, y, z, n )其中x,y,x C 0,1 , 1表示錢幣為正面，0表示錢幣為方面。n=0,1,2,3 ,表示當(dāng)前狀態(tài)是 經(jīng)過n次翻錢幣得到的。2,規(guī)則庫(kù)r1: IF (x,y,z, n)THEN(x, y, z,n+1)r2: IF (x,y,z, n)THEN(x, y, z,n+1)r3: IF (x,y,z, n)THEN(x, y, z,n+1)其中x表不對(duì)x取反。3,初始狀態(tài)

27、(1, 1,0, 0)4,結(jié)束狀態(tài)(1,1,1, 3) 或者(0, 0, 0, 3)第6題提示：將十進(jìn)制數(shù)分為整數(shù)部分和小數(shù)部分兩部分。用四元組(a, b, c, d)表示綜合數(shù)據(jù)庫(kù),其中a, b表示到目前為止還沒有轉(zhuǎn)換的十進(jìn)制數(shù)的整數(shù)部分和小數(shù)部分，c, d表示已經(jīng)轉(zhuǎn)換得到的二進(jìn)制數(shù)的整數(shù)部分和小數(shù)部分。然后根據(jù)十進(jìn)制數(shù)轉(zhuǎn)換二進(jìn)制數(shù)的原理，分別定義整數(shù)的轉(zhuǎn)換規(guī)則和小數(shù)的轉(zhuǎn)換規(guī)則，一次規(guī)則的執(zhí)行，轉(zhuǎn)換得到二進(jìn)制數(shù)的一位。第7題答：設(shè)規(guī)則R的逆用R'表示。由題意有 R應(yīng)用于D后，得到數(shù)據(jù)庫(kù) D',由可交換系統(tǒng)的性 質(zhì)，有：rule(D) rule(D')其中rule(D)

28、表示可應(yīng)用于D的規(guī)則集合。由于R'是R'的逆，所以R'應(yīng)用于D'后，得到數(shù)據(jù)庫(kù) Do同樣由可交換系統(tǒng)的性質(zhì)， 有：rule(D') = rule(D)綜合上述兩個(gè)式子，有 rule(D') = rule(D)。第8題答：說明一個(gè)產(chǎn)生式系統(tǒng)是可交換的，就是要證明該產(chǎn)生式系統(tǒng)滿足可交換產(chǎn)生式系統(tǒng)的三條性質(zhì)。(1)該產(chǎn)生式系統(tǒng)以整數(shù)的集合為綜合數(shù)據(jù)庫(kù)，其規(guī)則是將集合中的兩個(gè)整數(shù)相乘后加入 到數(shù)據(jù)庫(kù)中。由于原來數(shù)據(jù)庫(kù)是新數(shù)據(jù)庫(kù)的子集，所以原來的規(guī)則在新數(shù)據(jù)庫(kù)中均可以使用。所以滿足可交換產(chǎn)生式系統(tǒng)的第一條性質(zhì)。(2)該產(chǎn)生式系統(tǒng)以某個(gè)整數(shù)的子集的出現(xiàn)為目標(biāo)

29、條件，由于規(guī)則執(zhí)行的結(jié)果只是向數(shù)據(jù) 庫(kù)中添加數(shù)據(jù)，如果原數(shù)據(jù)庫(kù)中已經(jīng)滿足目標(biāo)了，即出現(xiàn)了所需要的整數(shù)子集，規(guī)則的執(zhí)行結(jié)果不會(huì)破壞該整數(shù)子集的出現(xiàn)，因此新的數(shù)據(jù)庫(kù)仍然會(huì)滿足目標(biāo)條件。滿足可交換產(chǎn)生式系統(tǒng)的第二個(gè)性質(zhì)。(3)設(shè)D是該產(chǎn)生式系統(tǒng)的一個(gè)綜合數(shù)據(jù)庫(kù)。對(duì)D施以一個(gè)規(guī)則序列后，得到一個(gè)新的數(shù)據(jù)庫(kù)D'。該規(guī)則序列中的有些規(guī)則有些是可以應(yīng)用于D的，這些規(guī)則用 R1表示。有些規(guī)則是不能應(yīng)用于 D的，這些規(guī)則用 R2表示。由于R1中的規(guī)則可以直接應(yīng)用與D,所以R1中規(guī)則的應(yīng)用與 R2中規(guī)則的執(zhí)行結(jié)果無關(guān)，也與R 1中其他的規(guī)則的執(zhí)行無關(guān)。所以可以認(rèn) 為，先將R1中所有的規(guī)則對(duì) D應(yīng)用，然后再

30、按照原來的次序應(yīng)用R2中的規(guī)則。因此對(duì)于本題的情況，這樣得到的綜合數(shù)據(jù)庫(kù)與D'是相同的。而由于 R1中一條規(guī)則的執(zhí)行與其他的規(guī)則無關(guān)，所以R1中規(guī)則的執(zhí)行順序不會(huì)影響到最終的結(jié)果。因此滿足可交換產(chǎn)生式系統(tǒng)的 第三個(gè)條件。因此這樣一個(gè)產(chǎn)生式系統(tǒng)是一個(gè)可交換的產(chǎn)生式系統(tǒng)。第1題答：為了方便起見，我們用(AB)()() 這樣的表表示一個(gè)狀態(tài)。這樣得到搜索圖如下：第2題提示：可定義h為：h=B右邊的W勺數(shù)目設(shè)j節(jié)點(diǎn)是i節(jié)點(diǎn)的子節(jié)點(diǎn)，則本據(jù)走法不同，h(i)-h(j) 的值和C(i, j)分為如下幾種情況：(1) B或Wt到了相鄰的一個(gè)空格位置，此時(shí)： h(i)-h(j)=0, C(i,j)=1

31、;(2) WB過了 1 或 2 個(gè) W 此時(shí) h(i)-h(j)=0, C(i,j)=1或 2;(3) W向右跳過了一個(gè) B (可能同時(shí)包含一個(gè)W ,此時(shí)：h(i)-h(j)=-1,C(i,j)=1 或2;(4) W向右跳過了兩個(gè) B,此時(shí)：h(i)-h(j)=-2, C(i,j)=2;(5) W向左跳過了一個(gè) B (可能同時(shí)包含一個(gè)W ,此時(shí)：h(i)-h(j)=1, C(i,j)=1 或2;(6) W向左跳過了兩個(gè) B,此時(shí)：h(i)-h(j)=2, C(i,j)=2;(7) B跳過了 1 或 2 個(gè) B,此時(shí) h(i)-h(j)=0, C(i,j)=1或 2;(8) B向右跳過了一個(gè) W

32、(可能同時(shí)包含一個(gè)B),此時(shí)：h(i)-h(j)=1, C(i,j)=1 或2;(9) B 向右跳過了兩個(gè) W 此時(shí)：h(i)-h(j)=2, C(i,j)=2;(10) B向左跳過了一個(gè) W(可能同時(shí)包含一個(gè)B),此時(shí)：h(i)-h(j)=-1,C(i,j)=1 或2;(11) B 向左跳過了兩個(gè) W 此時(shí)：h(i)-h(j)=-2, C(i,j)=2;縱上所述，無論是哪一種情況，具有 ：h(i)- h(j) wC(i,j)且容易驗(yàn)證h(t)=0，所以該h是單調(diào)的。由于h滿足單調(diào)條件，所以也一定有h(n)wh*(n), 即滿足A*條件。答：定義h1=n*k,其中n是還未走過的城市數(shù)，k是還未

33、走過的城市間距離的最小值。h2=Gl ，其中n是還未走過的城市數(shù)，ki是還未走過的城市間距離中n個(gè)最小的距離。顯然這兩個(gè)h函數(shù)均滿足A*條件。提示：對(duì)于四皇后問題，如果放一個(gè)皇后的耗散值為 1的話，則任何一個(gè)解的耗散值都 是4。因此如果h是對(duì)該耗散值的估計(jì)，是沒有意義的。對(duì)于像四皇后這樣的問題，啟發(fā)函 數(shù)應(yīng)該是對(duì)找到解的可能性的評(píng)價(jià)。比如像課上講到的， 利用一個(gè)位置放皇后后， 消去的對(duì)角線的長(zhǎng)度來進(jìn)行評(píng)價(jià)。答：定義h1=M+C-2R其中M, C分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。21表示船在左岸，B=。表示船在右岸。也可以定義h2=M+Chl是滿足A*條件的，而h2不滿足。要說明h(n)

34、=M+C不滿足A*條件是很容易的，只需要給出一個(gè)反例就可以了。比如狀態(tài) (1, 1,1) , h(n尸M+C=1+1=2,而實(shí)際上只要一次擺渡就可以達(dá)到目標(biāo)狀態(tài)，其最優(yōu)路徑的耗散 值為1。所以不滿足A*的條件。下面我們來證明 h(n) =M+C-2B是滿足A*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運(yùn)到右岸，然后再有一個(gè)人將船送回來。這樣，船一個(gè)來回可以運(yùn)過河2人，而船仍然在左岸。而最后剩下的三個(gè)人， 則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。 所以，在不考慮限制條件的情況下，也至少需要擺渡次。其中分子上的"-3"表示

35、剩下三個(gè)留待最后一次運(yùn)過去。除以"2"是因?yàn)橐粋€(gè)來回可以運(yùn)過去2人，需要2個(gè)來回，而"來回"數(shù)不能是小數(shù)，需要向上取整，這個(gè)用符號(hào)1表示。而乘以"2"是因?yàn)橐粋€(gè)來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的"+ 1”,則表示將剩下的3個(gè)運(yùn)過去，需要一次擺渡?；?jiǎn)有：再考慮船在右岸的情況。 同樣不考慮限制條件。船在右岸，需要一個(gè)人將船運(yùn)到左岸。因此對(duì)于斗犬態(tài)(M, C, 0)來說，其所需要的最少擺渡數(shù)， 相當(dāng)于船在左岸時(shí)狀態(tài)(M+1, C, 1)或(M, C+1, 1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)

36、。因此所需要的最少擺渡數(shù)為：(M+C+1)-2+1 。其中(M+C+1)的"+ 1”表示送船回到左岸的那個(gè)人，而最后邊的"+ 1”,表示送船到左岸時(shí)的一次擺渡?；?jiǎn)有：(M+C+1)-2+1=M+G綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個(gè)式子表示為：M+C-2B其中B= 1表示船在左岸，B=0表示船在右岸。由于該擺渡次數(shù)是在不考慮限制條件下，推 出的最少所需要的擺渡次數(shù)。因此，當(dāng)有限制條件時(shí)，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù) h是滿足A*條件的。第6題答：題目的另一個(gè)說法是：當(dāng)A*結(jié)束時(shí)，OPEN!中任何一個(gè)具有f(n)<f*(

37、s) 的節(jié)點(diǎn)都被擴(kuò)展了。用反證法證明。假設(shè)在A*結(jié)束的時(shí)候，OPENa中有一個(gè)節(jié)點(diǎn)n沒有被擴(kuò)展，且f(n)<f*(s)。A*算法每次從OPEN!中取出f值最小的節(jié)點(diǎn)擴(kuò)展，當(dāng)該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)，算法結(jié)束。并且由可采納性定理，知道這時(shí)A*找到了從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑，即f(t尸f*(s)。如果這時(shí)OPEN中存在f(n)<f*(s) 的節(jié)點(diǎn)n,由于f(n)<f(t),則這時(shí)A*算法應(yīng)選擇n擴(kuò)展，而不是目標(biāo)t, 與A*已經(jīng)結(jié)束矛盾。第7題答：因?yàn)锳*選作擴(kuò)展的任彳5'一個(gè)節(jié)點(diǎn) n,均有f(n) wf*(s),因此f鏟(s) 的節(jié)點(diǎn), 不會(huì)被A*所擴(kuò)展。所以如果從 OP

38、EN1中去掉f(n)>f*(s) 的節(jié)點(diǎn)，不會(huì)影響 A*的可采納性。 而F是f*(s)的上界圍，因此去掉 f(n)>F的節(jié)點(diǎn)也同樣不會(huì)影響 A*的可采納性。第8題提示：對(duì)于8數(shù)碼問題，逆向搜索和正向搜索是完全一樣的，只是把目標(biāo)狀態(tài)和初始狀態(tài)對(duì)調(diào)就可以了。第9題提示：在搜索期間改善 h函數(shù)，是一種動(dòng)態(tài)改變h函數(shù)的方法。像改進(jìn)的 A*算法中，對(duì)NEST中的節(jié)點(diǎn)按g值的大小選擇待擴(kuò)展的節(jié)點(diǎn)，相當(dāng)于令這些節(jié)點(diǎn)的 h=0,就是動(dòng)態(tài)修 改h函數(shù)的一種方法。由定理6,當(dāng)h滿足單調(diào)條件時(shí)，A*所擴(kuò)展的節(jié)點(diǎn)序列，其 f是非遞減的。對(duì)于任何節(jié)點(diǎn) i , j ,如果j是i的子節(jié)點(diǎn)，則有f(i) <

39、f(j)。利用該性質(zhì)，我們可以提出另一種動(dòng)態(tài)修改h函數(shù)的方法：f(j)=max(f(i), f(j)以f(j)作為節(jié)點(diǎn)j的f值。f值的改變，隱含了 h值的改變。當(dāng)h不滿足單調(diào)條件時(shí)，經(jīng)過這樣修正后的h具有一定的單調(diào)性質(zhì)，可以減少重復(fù)節(jié)點(diǎn)的可能性。第10題很多情提示：很多知識(shí)對(duì)求解問題有好處，這些知識(shí)并不一定要寫成啟發(fā)函數(shù)的形式,況下，也不一定能清晰的寫成一個(gè)函數(shù)的形式。為了敘述方便，我們將兩個(gè)相對(duì)的扇區(qū)稱為相對(duì)扇區(qū)，圖中陰影部分的扇區(qū)稱為陰影扇區(qū)，非陰影部分的扇區(qū)稱為非陰影扇區(qū)。由題意，在目標(biāo)狀態(tài)下，一個(gè)扇區(qū)的數(shù)字之和等于12, 一個(gè)相對(duì)扇區(qū)的數(shù)字之和等于24,而一個(gè)陰影扇區(qū)或者非陰影扇區(qū)的數(shù)

40、字之和為48。為此，我們可以將目標(biāo)進(jìn)行分解，首先滿足陰影扇區(qū)的數(shù)字之和為48 （這時(shí)非陰影部分的數(shù)字和也一定為 48）。為了這個(gè)目標(biāo)我們可以通過每次轉(zhuǎn)動(dòng)圓盤45o實(shí)現(xiàn)。在第一個(gè)目標(biāo)被滿足的情況下，我們?cè)倏紤]第二個(gè)目標(biāo)：每一個(gè)相對(duì)扇區(qū)的數(shù)字和為24。在實(shí)現(xiàn)這個(gè)目標(biāo)的過程中，我們希望不破壞第一個(gè)目標(biāo)。為此我們采用轉(zhuǎn)動(dòng)90o的方式實(shí)現(xiàn)，這樣即可以調(diào)整相對(duì)扇區(qū)的數(shù)字和， 又不破壞第一個(gè)目標(biāo)。 在第二個(gè)目標(biāo)實(shí)現(xiàn)之后， 我們就可以實(shí)現(xiàn)最終 目標(biāo)：扇區(qū)的數(shù)字和為 12。同樣我們希望在實(shí)現(xiàn)這個(gè)目標(biāo)的時(shí)候，不破壞前兩個(gè)目標(biāo)。為 此我們采用轉(zhuǎn)動(dòng) 180o的方式實(shí)現(xiàn)。這樣同樣是即可以保證前兩個(gè)目標(biāo)不被破壞，又可以實(shí)

41、 現(xiàn)第三個(gè)目標(biāo)。經(jīng)過這樣的分析以后， 我們發(fā)現(xiàn)該問題就清晰多了。當(dāng)然，是否每一個(gè)第一、第二個(gè)目標(biāo)的實(shí)現(xiàn)，都能夠?qū)崿F(xiàn)第三個(gè)目標(biāo)呢？有可能不一定。在這種情況下，就需要在發(fā)現(xiàn)第三個(gè)目標(biāo)不能實(shí)現(xiàn)時(shí)，重新試探其他的第一、第二個(gè)目標(biāo)。第三章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題答：此題要求按照課中例題的方式，給出算法，以下是每個(gè)循環(huán)結(jié)束時(shí)的搜索圖。4上面這種做法比較簡(jiǎn)單，也可以如下做:C 5)這里選 獷展也M kJ第七步第2題答：從該搜索圖可以看出，無論先走者選擇哪個(gè)走步，后走者都可以走到標(biāo)記為A的節(jié)點(diǎn)，該節(jié)點(diǎn)只剩下一枚錢幣，所以先走者必輸。對(duì)于一般的具有n個(gè)錢幣的情況

42、，當(dāng)n=4Xm+1時(shí)，后走者存在取勝策略。因?yàn)楹笞哒呖梢愿鶕?jù)先走者的走法，選擇自己的走法，使得雙方拿走的錢幣數(shù)為 4,這樣經(jīng)過 m個(gè)輪回后，共拿走了 4Xm個(gè)錢幣，只剩下了一枚錢幣， 而此時(shí)輪到先走者走棋。所以在這種情況下，后走者存在取勝的策略。對(duì)于錢幣數(shù)不等于4Xm+ 1的情況，先走者可以根據(jù)實(shí)際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢幣數(shù)為4Xm+ 1個(gè)，此時(shí)先走者相當(dāng)于 4Xm+ 1個(gè)錢幣時(shí)的后走者了。因此在這種情況下，先走者 存在獲勝的策略。第3題答：10 5 3 3 3-3 0 2-2 3 5 七 5 至 口 I 5 1 -3 0 -5 5 F 3 E 爭(zhēng) 一3 0 一卜£。

43、1 4 5 1 -1-： 3 -3E-2第四章課后習(xí)題答案第1題答：（1）(2)(Wx)P(x) - P(x)(Vx)P(x) V P(x) P(x) VP(x)( iVx)P(x) 一(際 x)卜P(x) ( Vx)P(x) V (mx)P(x) ( Vx)P(x) V(my)P(y) ( tx)(my)P(x) V P(y) P(x) VP(f(a)(3)( Wx)P(x) 一( Vy)P(y) (Vx)P(x) 一( |Vy)P(y) (Vx)P(x) 一( |Vy)P(y) (Vx)P(x) 一( |Vy)P(y) (Vx)P(x) V( Vy)P(y)一 P(f(x ,V P(f(x

44、V P(f(xV P(f(xV P(f(xy) y) y) y)A (| . |y)Q(xA (| - ly)Q(xy) - P(y)，y) V P(y)A (匚 y)Q(xA (匚 z)Q(xy) A ( z)Q(x(Rx)P(x) A (國(guó)y)P(y) A P(f(x , y) V (z)卜Q(x (Rx)( Ry)( Vz)P(x) A P(y) A P(f(x , y) V Q(x(mx)( Ry)( Vz)P(x) A P(y) V Q(x, z) V P(z) A P(f(xy) A P(y)z) A P(z)z) A P(z)z) V P(z)z) V P(z),y) VQ(x,

45、z) V P(z)P(a) A P(b) V Q(a, z) V P(z) A P(f(a , b) VQ(a, z) V P(z)P(a), P(b) VQ(a, z1) V P(z1), P(f(a , b) VQ(a, z2) V P(z2)(4) (Wx)(y)P(x , y)-Q(y, x) A Q(y ,x) -S(x, y) 一(x)( V y)P(x , y)-S(x, y)(Vx)( my)P(x ,y)-Q(y, x) A Q(y ,x) -S(x, y) -( x)( V y)P(x ,y)-S(x, y)(Vx)( my)卜P(x , y)VQ(y, x) A Q(y

46、, x) V S(x , y) 一( u)( W|v)P(u , v) VS(u, v)( Vx)( my)P(x , y)VQ(y, x) A Q(y , x)VS(x, y) V (m u)( V v)P(u , v)VS(u, v)(mx)( |V y)P(x , y) A Q(y , x) V Q(y , x) A S(x , y) V ( u)( V|v)P(u , v) VS(u, v)(mx)( My)( mu)( Vv)P(x , y) A Q(y, x) V Q(y , x) A S(x , y) V P(u , v) VS(u, v)(mx)(|Vy)( mu)( Wv)P

47、(x , y) VQ(y, x) A P(x , y) V S(x, y) A Q(y , x) V S(x , y) V P(u , v) V S(u, v)(mx)( |Vy)( mu)( Vv)P(x , y) VQ(y, x) VP(u, v) VS(u, v) A P(x , y) VS(x, y) V P(u , v) V S(u , v) A Q(y , x) V S(x , y) V P(u , v) V S(u , v)P(a , y) V Q(y,a)V P(f(y), v) V S(f(y), v)A P(a, y) V S(a, y) V P(f(y),v) VS(f(

48、y) , v) A Q(y,a) V S(a ,y) VP(f(y), v)V S(f(y), v)P(a , y1) V Q(y1, a) V P(f(y1), v) VS(f(y1) , v),P(a , y2)V S(a,y2)VP(f(y2), v2) V S(f(y2),v2), Q(y3, a)V S(a,y3)V P(f(y3) , v3) VS(f(y3),v3)第2題答：設(shè)有兩個(gè)置換s1=a/x和s2=x/y,合適公式P(x, y)。則：P(x, y)s1s2=P(a, x)P(x, y)s2s1=P(a, a)二者不相等。所以說，置換的合成是不可交換的。第3題答：A/x,

49、A./y, A/z, A/w, A/u第4題答：(1) P(f(x , x) , A), P(f(y , f(y , A) , A)在合一時(shí)，f(x,x)要與f(y,f(y,a)進(jìn)行合一，x置換成y后，y要與f(y,a)進(jìn)行合一，出現(xiàn)了嵌套的情況，所以不能進(jìn)行合一。(2) P (A) , P (x) 一個(gè)是謂詞P, 一個(gè)是P的反，不能合一。(3) P (f (A) , x) , P (x, A) 在合一的過程中，x置換為f(A),而f(A)與A不能合一。第5題 答：略第6題答：(1) (ux) P (x) -P (A) AP(x) -P (B) 目標(biāo)取反化子句集： (mx) P (x) -P

50、(A) AP (x) -P ( B) (mx) P (x) V P (A) A -P (x) V P (B) (Hx) P (x) A P (A) VP (x) A P (B) (Wx)P (x) A -P(A) V P (x) AP (x) A -P (A) V -P (B) (寸x)P(x) A P(A)V P (x) A P (x) V -P (B) A -P (A) V -P ( B)P (x)A -P(A)V P (x) A P(x)V -P(B) A-P(A)V -P(B)得子句集：1, P(x1)2, -P(A) V Px23, P(x3) V -P(B)4, -P(A) V -

51、P(B)(2) (Vz) Q (z) - P (z) 一( x) Q (x) - P (A) AQ (x) - P ( B) 目標(biāo)取反化子句集：( Vz)Q(z) - P(z) 一( mx)Q(x) - P(A) A Q(x) - P(B)( Vz)卜Q(z) VP(z) 一( x)Q(x) V P(A) AQ(x) V P(B)( Vz)Q(z) V P(z) V(mx)Q(x) V P(A) A -Q(x) V P(B)(Vz)( |Vx)-Q(z)V P(z) A Q(x) A -P(A) V Q(x) A -P(B)(V z)( V x)Q(z) V P(z) A Q(x) A Q(x

52、) V P(B) A 卜P(A) V Q(x) A P(A) V P(B)Q(z) V P(z) A Q(x) A Q(x) V P(B) A 卜P(A) V Q(x) A 卜P(A) V P(B)得子句集：1, -Q(z) V P(z)2, Q(x2)3, Q(x3) V -P(B)4, -P(A) V Q(x4)5, -P(A) V -P(B)(3) (mx)(y) P (f (x) ) A Q (f (B) ) -P (f (A) ) A P (y) A Q (y) 目標(biāo)取反化子句集：(x)(y)P(f(x)AQ(f(B) 一 P(f(A ) A P(y) A Q(y)(戲 Ey)P(f

53、(x)A Q(f(B) V P(f(A) A P(y) A Q(y)(x)( y)P(f(x) A Q(f(B) A P(f(A) V P(y) V Q(y)P(f(x) F Q(f(B) F P(f(A) V P(y) V Q(y)得子句集：1, P(f(x1)2, Q(f(B)3, P(f(A) V P(y3) V Q(y3)(4)(匹)(My) P (x, y) 一(Hy) 0) P (x, y)目標(biāo)取反化子句集：(x)( |Wy)P(x , y)-( By)(x)P(x , y)( Rx)( Vy)P(x , y) V(Vy)(x)P(x , y)(田x)( Vy)P(x , y) V (Vv)( Uu)P(u , v)(5X)( Vy)P(x , y) A (mv)(同u)P(u , v) (®x)(忖y)(v)( Vu)P(x , y) AP(u, v) P(a , y) F P(u, f(y)得子句集：1, P(a, y1)2, P(u, f(y2)(5) ( Vx) P (x) A