人工智能課后答案(共35頁)

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

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

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

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

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

6、函數(shù)的一般特征。你是否認(rèn)為任何h函數(shù)對引導(dǎo)搜索都是有用的？5、對N5，k3的MC問題，定義兩個h函數(shù)（非零），并給出用這兩個啟發(fā)函數(shù)的A算法搜索圖。討論用這兩個啟發(fā)函數(shù)求解該問題時是否得到最佳解。6、證明OPEN表上具有f(n)f*(s)的任何節(jié)點n，最終都將被A*選擇去擴(kuò)展。7、如果算法A*從OPEN表中去掉任一節(jié)點n，對n有f(n)F（Ff*(s)），試說明為什么算法A*仍然是可采納的。8、用算法A逆向求解圖2.7中的八數(shù)碼問題，評價函數(shù)仍定義為f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相會。9、討論一個h函數(shù)在搜索期間可以得到改善的幾種方法。10、四個同心圓盤的扇區(qū)數(shù)字如

7、圖所示，每個圓盤可單獨轉(zhuǎn)動。問如何轉(zhuǎn)動圓盤使得八個徑向的4個數(shù)字和均為12。窗體底端第三章 課后習(xí)題窗體頂端1、數(shù)字重寫問題的變換規(guī)則如下：63，343，164，232，142，221，1問如何用這些規(guī)則把數(shù)字6變換成一個由若干個1組成的數(shù)字串。試用算法AO*進(jìn)行求解，并給出搜索圖。求解時設(shè)k-連接符的耗散值是k個單位，h函數(shù)值規(guī)定為：h（1）0，h（n）n（n1）。 2、余一棋的弈法如下：兩棋手可以從5個錢幣堆中輪流拿走一個、兩個或三個錢幣，揀起最后一個錢幣者算輸。試通過博弈證明，后走的選手必勝，并給出一個簡單的特征標(biāo)記來表示取勝策略。3、對下圖所示的博弈樹，以優(yōu)先生成左邊節(jié)點順序來進(jìn)行-搜

8、索，試在博弈樹上給出何處發(fā)生剪枝的標(biāo)記，并標(biāo)明屬于剪枝還是剪枝。4、AO*算法中，第7步從S中選一個節(jié)點，要求其子孫不在S中出現(xiàn)，討論應(yīng)如何實現(xiàn)對S的控制使得能有效地選出這個節(jié)點。如下圖所示，若E的耗散值發(fā)生變化時，所提出的對S的處理方法應(yīng)能正確工作。5、如何修改AO*算法使之能處理出現(xiàn)回路的情況。如下圖所示，若節(jié)點C的耗散值發(fā)生變化時，所修改的算法能正確處理這種情況。6、對3×3的一字棋，設(shè)用+1和-1分別表示兩選手棋子的標(biāo)記，用0表示空格，試給出一字棋產(chǎn)生式系統(tǒng)的描述。7、寫一個-搜索的算法。8、用一個9維向量C來表示一字棋棋盤的格局，其分量根據(jù)相應(yīng)格內(nèi)的×，空或的標(biāo)記

9、分別用+1，0，或-1來表示。試規(guī)定另一個9維向量W，使得點積C·W可作為MAX選手（棋子標(biāo)記為×）估計非終端位置的一個有效的評價函數(shù)。用這個評價函數(shù)來完成幾步極小-極大搜索，并分析該評價函數(shù)的效果。窗體底端第四章 課后習(xí)題窗體頂端1、化下列公式成子句形式：（1）（x）P（x）P（x） （2）（x）P（x）（x）P（x） （3）（x）P（x）（y）P（y）P（f（x，y）（y）Q（x，y）P（y）（4）（x）（y）P（x，y）Q（y，x）Q（y，x）S（x，y）（x）（y）P（x，y）S（x，y） 2、以一個例子證明置換的合成是不可交換的。3、找出集P（x，z，y），P（w

10、，u，w），P（A，u，u）的mgu。4、說明下列文字集不能合一的理由：（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、已知兩個子句為Loves（father（a），a）Loves（y，x）Loves（x，y）試用合一算法求第一個子句和第二個子句的第一個文字合一時的結(jié)果。 6、用歸結(jié)反演法證明下列公式的永真性：（1）（x）P（x）P（A）P（x）P（B）（2）（z）Q（z）P（z）（x）Q（x）P（A）Q（x）P（B）（3）（x）（y）P（f（x）Q（f（B）P（f（A）P（y）Q（y） （4）（x）（y）P（x，

11、y）（y）（x）P（x，y）（5）（x）P（x）Q（A）Q（B）（x）P（x）Q（x） 7、以歸結(jié)反演法證明公式（x）P（x）是P（A1）P（A2）的邏輯推論，然而，（x）P（x）的Skolem形即P（A）并非P（A1）P（A2）的邏輯推論，請加以證明。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

12、. （1）用歸結(jié)法證明"John likes peanuts。" （2）用歸結(jié)法提取回答"What food does Sue eat?" 9、已知事實公式為 （x）（y）（z）（Gt（x，y）Gt（y，z）Gt（x，z） （u）（v）（Succ（u，v）Gt（u，v） （x）（Gt（x，x）求證Gt（5，2） 試判斷下面的歸結(jié)過程是否正確？若有錯誤應(yīng)如何改進(jìn)：10、設(shè)公理集為（u）LAST（cons（u，NIL），u）（cons是表構(gòu)造函數(shù)）（x）（y）（z）（LAST（y，z）LAST（cons（x，y），z）（LAST（x，y）代表y是表x的最末元

13、素） （1）用歸結(jié)反演法證明如下定理： （v）LAST（cons（2，cons（1，NIL），v）（2）用回答提取過程求表（2，1）的最末元素v。（3）簡要描述如何使用這個方法求長表的最末元素。 11、對一個基于規(guī)則的幾何定理證明系統(tǒng)，把下列語句表示成產(chǎn)生式規(guī)則： （1）兩個全等的三角形的對應(yīng)角相等。（2）兩個全等的三角形的對應(yīng)邊相等。（3）如果兩個三角形對應(yīng)邊是相等的，則這兩個三角形全等。（4）一個等腰三角形的底角是相等的。 12、我們來考慮下列一段知識：Tony、Mike和John屬于Alpine俱樂部，Alpine俱樂部的每個成員不是滑雪運動員就是一個登山運動員，登山運動員不喜歡雨而且任

14、一不喜歡雪的人不是滑雪運動員，Mike討厭Tony所喜歡的一切東西，而喜歡Tony所討厭的一切東西，Tony喜歡雨和雪。 以謂詞演算語句的集合表示這段知識，這些語句適合一個逆向的基于規(guī)則的演繹系統(tǒng)。試說明這樣一個系統(tǒng)怎樣才能回答問題"有沒有Alpine俱樂部的一個成員，他是一個登山運動員但不是一個滑雪運動員呢？" 13、一個積木世界的狀態(tài)由下列公式集描述：ONTABLE（A）CLEAR（E）ONTABLE（C）CLEAR（D）ON（D，C）HEAVY（D）ON（B，A）WOODEN（B）HEAVY（B）ON（E，B）繪出這些公式所描述的狀態(tài)的草圖。 下列語句提供了有關(guān)這個積

15、木世界的一般知識：每個大的藍(lán)色積木塊是在一個綠色積木塊上。每個重的木制積木塊是大的。所有頂上沒有東西的積木塊都是藍(lán)色的。所有木制積木塊是藍(lán)色的。以具有單文字后項的蘊涵式的集合表示這些語句。繪出能求解"哪個積木塊是在綠積木塊上"這個問題的一致解圖（用B規(guī)則）。 窗體底端答案第一章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題答： 1，綜合數(shù)據(jù)庫定義三元組：（m, c, b） 其中：，表示傳教士在河左岸的人數(shù)。，表示野人在河左岸的認(rèn)輸。，b=1，表示船在左岸，b=0，表示船在右岸。2，規(guī)則集 規(guī)則集可以用兩種方式表示，兩種方法均可。第一種方法： 按每

16、次渡河的人數(shù)分別寫出每一個規(guī)則，共(3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八種渡河的可能（其中(x y)表示x個傳教士和y個野人上船渡河），因此共有16個規(guī)則（從左岸到右岸、右岸到左岸各八個）。注意：這里沒有(1 2)，因為該組合在船上的傳教士人數(shù)少于野人人數(shù)。規(guī)則集如下：r1：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-2, c-1, 0)r4：IF (m, c, 1) THEN (m-1, c-1, 0)r5：I

17、F (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) THEN (m+1, c+1, 1)r13：IF (m, c, 0) THEN (m+1, c, 1)r14：

18、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ī)則集綜合在一起，簡化表示。規(guī)則集如下：r1：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>= j or i=0) THEN (m+i, c+j, 1) 3，初始狀態(tài)：(5, 5, 1)4，結(jié)束狀態(tài)：(0, 0, 0

19、) 第2題答： 1，綜合數(shù)據(jù)庫定義兩元組：（L5, L2）其中：0<=L5<=5，表示容量為5升的壺的當(dāng)前水量。0<=L2<=2，表示容量為2升的壺的當(dāng)前水量。2，規(guī)則集r1：IF (L5, L2) THEN (5, L2) /* 將L5灌滿水 */ r2：IF (L5, L2) THEN (L5, 2) /* 將L2灌滿水 */r3：IF (L5, L2) THEN (0, L2) /* 將L5水到光 */r4：IF (L5, L2) THEN (L5, 0) /* 將L2水到光 */ r5：IF (L5, L2) and L5+L2<=5 THEN (L5+L

20、2, 0) /* L2到入L5中 */r6：IF (L5, L2) and L5+L2>5 THEN (5, L5+L2-5) /* L2到入L5中 */ r7：IF (L5, L2) and L5+L2<=2 THEN (0, L5+L2) /* L5到入L2中 */ r8：IF (L5, L2) and L5+L2>5 THEN (L5+L2-2, 2) /* L5到入L2中 */3，初始狀態(tài)：(5, 0) 4，結(jié)束條件：(x, 1)，其中x表示不定。當(dāng)然結(jié)束條件也可以寫成：(0, 1) 第3題答： 1，綜合數(shù)據(jù)庫定義三元組：(A, B, C) 其中A, B, C分別表示

21、三根立柱，均為表，表的元素為1N之間的整數(shù)，表示N個不同大小的盤子，數(shù)值小的數(shù)表示小盤子，數(shù)值大的數(shù)表示大盤子。表的第一個元素表示立柱最上面的柱子，其余類推。2，規(guī)則集為了方便表示規(guī)則集，引入以下幾個函數(shù)：first(L)：取表的第一個元素，對于空表，first得到一個很大的大于N的數(shù)值。tail(L)：取表除了第一個元素以外，其余元素組成的表。cons(x, L)：將x加入到表L的最前面。規(guī)則集：r1: IF (A, B, C) and (first(A) < first(B) THEN (tail(A), cons(first(A), B), C)r2: IF (A, B, C) a

22、nd (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) THEN (cons(first(C), A), B, tai

23、l(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ī)模： 每一個盤子都有三中選擇：在A上、或者在B上、或者在C上，共N個盤子，所以共有種可能。即問題的狀態(tài)規(guī)模為。 第4題答： 1，綜合數(shù)據(jù)庫定義5元組：（M, B, Box, On, H）其中：M：猴子的位置 B：香蕉的位置Box：箱子的位置On=0：猴子在地板上 On=1：猴子在箱子上 H=0：猴子沒有抓到香蕉 H=1：猴子抓到

24、了香蕉 2，規(guī)則集r1: IF (x, y, z, 0, 0) THEN (w, y, z, 0, 0) 猴子從x處走到w處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) 如果箱子在香

25、蕉處，猴子在箱子上，猴子摘到香蕉 其中x, y, z, w為變量3，初始狀態(tài) （c, a, b, 0, 0）4，結(jié)束狀態(tài) （x1, x2, x3, x4, 1） 其中x1x4為變量。第5題答： 1，綜合數(shù)據(jù)庫定義四元組：（x, y, z, n） 其中x,y,x0,1，1表示錢幣為正面，0表示錢幣為方面。n=0,1,2,3，表示當(dāng)前狀態(tài)是經(jīng)過n次翻錢幣得到的。2，規(guī)則庫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+

26、1) 其中x表示對x取反。3，初始狀態(tài) (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ù)庫，其中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ù)庫D'，由可交換系統(tǒng)的性質(zhì)，有： rule(

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

28、系統(tǒng)以某個整數(shù)的子集的出現(xiàn)為目標(biāo)條件，由于規(guī)則執(zhí)行的結(jié)果只是向數(shù)據(jù)庫中添加數(shù)據(jù)，如果原數(shù)據(jù)庫中已經(jīng)滿足目標(biāo)了，即出現(xiàn)了所需要的整數(shù)子集，規(guī)則的執(zhí)行結(jié)果不會破壞該整數(shù)子集的出現(xiàn)，因此新的數(shù)據(jù)庫仍然會滿足目標(biāo)條件。滿足可交換產(chǎn)生式系統(tǒng)的第二個性質(zhì)。 （3）設(shè)D是該產(chǎn)生式系統(tǒng)的一個綜合數(shù)據(jù)庫。對D施以一個規(guī)則序列后，得到一個新的數(shù)據(jù)庫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)，也與1中其他的規(guī)則的執(zhí)行無關(guān)。所以可以認(rèn)為，先將R1中所有的規(guī)則

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

30、j)=1；（2）W跳過了1或2個W，此時 h(i)-h(j)=0, C(i,j)=1或2； （3）W向右跳過了一個B（可能同時包含一個W），此時： h(i)-h(j)=-1, C(i,j)=1或2；（4）W向右跳過了兩個B，此時： h(i)-h(j)=-2, C(i,j)=2； （5）W向左跳過了一個B（可能同時包含一個W），此時： h(i)-h(j)=1, C(i,j)=1或2； （6）W向左跳過了兩個B，此時： h(i)-h(j)=2, C(i,j)=2； （7）B跳過了1或2個B，此時 h(i)-h(j)=0, C(i,j)=1或2； （8）B向右跳過了一個W（可能同時包含一個B），此時

31、： h(i)-h(j)=1, C(i,j)=1或2；（9）B向右跳過了兩個W，此時： h(i)-h(j)=2, C(i,j)=2；（10）B向左跳過了一個W（可能同時包含一個B），此時： h(i)-h(j)=-1, C(i,j)=1或2； （11）B向左跳過了兩個W，此時： h(i)-h(j)=-2, C(i,j)=2；縱上所述，無論是哪一種情況，具有:h(i)-h(j)C(i,j)且容易驗證h(t)=0，所以該h是單調(diào)的。由于h滿足單調(diào)條件，所以也一定有h(n)h*(n)，即滿足A*條件。 第3題答： 定義h1=n*k，其中n是還未走過的城市數(shù)，k是還未走過的城市間距離的最小值。 h2，其中

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

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

34、;是因為一個來回可以運過去2人，需要個來回，而"來回"數(shù)不能是小數(shù)，需要向上取整，這個用符號表示。而乘以"2"是因為一個來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的"1"，則表示將剩下的3個運過去，需要一次擺渡。化簡有：再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運到左岸。因此對于狀態(tài)(M，C，0)來說，其所需要的最少擺渡數(shù)，相當(dāng)于船在左岸時狀態(tài)(M+1，C，1)或(M，C+1，1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)。因此所需要的最少擺渡數(shù)為：(M+C+1)-2+1 。其中(M+C+1)

35、的"1"表示送船回到左岸的那個人，而最后邊的"1"，表示送船到左岸時的一次擺渡。化簡有：(M+C+1)-2+1=M+C。綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個式子表示為：M+C-2B。其中B1表示船在左岸，B0表示船在右岸。 由于該擺渡次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡次數(shù)。因此，當(dāng)有限制條件時，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。第6題答：題目的另一個說法是：當(dāng)A*結(jié)束時，OPEN表中任何一個具有f(n)<f*(s)的節(jié)點都被擴(kuò)展了。用反證法證明。假設(shè)在A*結(jié)束的時候，OPE

36、N表中有一個節(jié)點n沒有被擴(kuò)展，且f(n)<f*(s)。A*算法每次從OPEN表中取出f值最小的節(jié)點擴(kuò)展，當(dāng)該節(jié)點是目標(biāo)節(jié)點時，算法結(jié)束。并且由可采納性定理，知道這時A*找到了從初始節(jié)點到目標(biāo)節(jié)點的最佳路徑，即f(t)=f*(s)。如果這時OPEN中存在f(n)<f*(s)的節(jié)點n，由于f(n)<f(t)，則這時A*算法應(yīng)選擇n擴(kuò)展，而不是目標(biāo)t，與A*已經(jīng)結(jié)束矛盾。第7題答： 因為A*選作擴(kuò)展的任何一個節(jié)點n，均有f(n)f*(s)，因此f(n)>f*(s)的節(jié)點，不會被A*所擴(kuò)展。所以如果從OPEN表中去掉f(n)>f*(s)的節(jié)點，不會影響A*的可采納性。而F

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

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

39、。為了這個目標(biāo)我們可以通過每次轉(zhuǎn)動圓盤45o實現(xiàn)。在第一個目標(biāo)被滿足的情況下，我們再考慮第二個目標(biāo)：每一個相對扇區(qū)的數(shù)字和為24。在實現(xiàn)這個目標(biāo)的過程中，我們希望不破壞第一個目標(biāo)。為此我們采用轉(zhuǎn)動90o的方式實現(xiàn)，這樣即可以調(diào)整相對扇區(qū)的數(shù)字和，又不破壞第一個目標(biāo)。在第二個目標(biāo)實現(xiàn)之后，我們就可以實現(xiàn)最終目標(biāo)：扇區(qū)內(nèi)的數(shù)字和為12。同樣我們希望在實現(xiàn)這個目標(biāo)的時候，不破壞前兩個目標(biāo)。為此我們采用轉(zhuǎn)動180o的方式實現(xiàn)。這樣同樣是即可以保證前兩個目標(biāo)不被破壞，又可以實現(xiàn)第三個目標(biāo)。 經(jīng)過這樣的分析以后，我們發(fā)現(xiàn)該問題就清晰多了。當(dāng)然，是否每一個第一、第二個目標(biāo)的實現(xiàn)，都能夠?qū)崿F(xiàn)第三個目標(biāo)呢？有可

40、能不一定。在這種情況下，就需要在發(fā)現(xiàn)第三個目標(biāo)不能實現(xiàn)時，重新試探其他的第一、第二個目標(biāo)。 第三章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題答：此題要求按照課中例題的方式，給出算法，以下是每個循環(huán)結(jié)束時的搜索圖。上面這種做法比較簡單，也可以如下做：第2題答：從該搜索圖可以看出，無論先走者選擇哪個走步，后走者都可以走到標(biāo)記為A的節(jié)點，該節(jié)點只剩下一枚錢幣，所以先走者必輸。 對于一般的具有n個錢幣的情況，當(dāng)n4×m1時，后走者存在取勝策略。因為后走者可以根據(jù)先走者的走法，選擇自己的走法，使得雙方拿走的錢幣數(shù)為4，這樣經(jīng)過m個輪回后，共拿走了4×m

41、個錢幣，只剩下了一枚錢幣，而此時輪到先走者走棋。所以在這種情況下，后走者存在取勝的策略。 對于錢幣數(shù)不等于4×m1的情況，先走者可以根據(jù)實際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢幣數(shù)為4×m1個，此時先走者相當(dāng)于4×m1個錢幣時的后走者了。因此在這種情況下，先走者存在獲勝的策略。第3題答：第四章課后習(xí)題答案第1題答：（1）(x)P(x)P(x)(x)P(x)P(x)P(x)P(x)（2）(x)P(x)(x)P(x) (x)P(x)(x)P(x) (x)P(x)(y)P(y)(x)(y)P(x)P(y) P(x)P(f(a) （3）(x)P(x)(y)P(y)P(f

42、(x，y)(y)Q(x，y)P(y)(x)P(x)(y)P(y)P(f(x，y)(y)Q(x，y)P(y)(x)P(x)(y)P(y)P(f(x，y)(y)Q(x，y)P(y)(x)P(x)(y)P(y)P(f(x，y)(z)Q(x，z)P(z)(x)P(x)(y)P(y)P(f(x，y)(z)Q(x，z)P(z)(x)P(x)(y)P(y)P(f(x，y)(z)Q(x，z)P(z) (x)(y)(z)P(x)P(y)P(f(x，y)Q(x，z)P(z)(x)(y)(z)P(x)P(y)Q(x，z)P(z)P(f(x，y)Q(x，z)P(z) P(a)P(b)Q(a，z)P(z)P(f(a，b

43、)Q(a，z)P(z)P(a), P(b)Q(a，z1)P(z1), P(f(a，b)Q(a，z2)P(z2) （4）(x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(x)(y)P(x，y)S(x，y) (x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(x)(y)P(x，y)S(x，y) (x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(u)(v)P(u，v)S(u，v)(x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(u)(v)P(u，v)S(u，v) (x)(y)P(x，y)Q(y，x)Q(y，x)S(x，y)(u)(v)P(u，v)S(u，

44、v) (x)(y)(u)(v)P(x，y)Q(y，x)Q(y，x)S(x，y)P(u，v)S(u，v) (x)(y)(u)(v)P(x，y)Q(y，x)P(x，y)S(x，y)Q(y，x)S(x，y)P(u，v)S(u，v) (x)(y)(u)(v)P(x，y)Q(y，x)P(u，v)S(u，v)P(x，y)S(x，y)P(u，v)S(u，v)Q(y，x)S(x，y)P(u，v)S(u，v)P(a，y)Q(y，a)P(f(y)，v)S(f(y)，v)P(a，y)S(a，y)P(f(y)，v)S(f(y)，v)Q(y，a)S(a，y)P(f(y)，v)S(f(y)，v) P(a，y1)Q(y1，

45、a)P(f(y1)，v)S(f(y1)，v), P(a，y2)S(a，y2)P(f(y2)，v2)S(f(y2)，v2), Q(y3，a)S(a，y3)P(f(y3)，v3)S(f(y3)，v3) 第2題答：設(shè)有兩個置換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, A./y, A/z, A/w, A/u第4題答： （1）P(f(x，x)，A)，P(f(y，f(y，A)，A) 在合一時，f(x,x)要與f(y,f(y,a)進(jìn)行合一，x置換成y后

46、，y要與f(y,a)進(jìn)行合一，出現(xiàn)了嵌套的情況，所以不能進(jìn)行合一。 （2）P（A），P（x）一個是謂詞P，一個是P的反，不能合一。 （3）P（f（A），x），P（x，A）在合一的過程中，x置換為f(A)，而f(A)與A不能合一。 第5題答： 略第6題答： （1）（x）P（x）P（A）P（x）P（B）目標(biāo)取反化子句集：（x）P（x）P（A）P（x）P（B） （x）P（x）P（A）P（x）P（B） （x）P（x）P（A）P（x）P（B） （x）P（x）P（A）P（x）P（x）P（A）P（B）（x）P（x）P（A）P（x）P（x）P（B）P（A）P（B）P（x）P（A）P（x）P（x）P（B）P（A

47、）P（B）得子句集：1, P(x1)2, P(A)Px2 3, P(x3)P(B)4, P(A)P(B)（2）（z）Q（z）P（z）（x）Q（x）P（A）Q（x）P（B）目標(biāo)取反化子句集：(z)Q(z)P(z)(x)Q(x)P(A)Q(x)P(B)(z)Q(z)P(z)(x)Q(x)P(A)Q(x)P(B)(z)Q(z)P(z)(x)Q(x)P(A)Q(x)P(B)(z)(x)Q(z)P(z)Q(x)P(A)Q(x)P(B)(z)(x)Q(z)P(z)Q(x)Q(x)P(B)P(A)Q(x)P(A)P(B)Q(z)P(z)Q(x)Q(x)P(B)P(A)Q(x)P(A)P(B) 得子句集： 1

48、, Q(z)P(z)2, Q(x2) 3, Q(x3)P(B) 4, P(A)Q(x4) 5, P(A)P(B) （3）（x）（y）P（f（x）Q（f（B）P（f（A）P（y）Q（y）目標(biāo)取反化子句集：(x)(y)P(f(x)Q(f(B)P(f(A)P(y)Q(y) (x)(y)P(f(x)Q(f(B)P(f(A)P(y)Q(y) ( x)( y)P(f(x)Q(f(B)P(f(A)P(y)Q(y)P(f(x)Q(f(B)P(f(A)P(y)Q(y) 得子句集：1，P(f(x1)2，Q(f(B) 3，P(f(A)P(y3)Q(y3)（4）（x）（y）P（x，y）（y）（x）P（x，y）目標(biāo)取反

49、化子句集：(x)(y)P(x，y)(y)(x)P(x，y)(x)(y)P(x，y)(y)(x)P(x，y) (x)(y)P(x，y)(v)(u)P(u，v)(x)(y)P(x，y)(v)(u)P(u，v) (x)(y)(v)(u)P(x，y)P(u，v)P(a，y)P(u，f(y)得子句集：1，P(a，y1) 2，P(u，f(y2) （5）（x）P（x）Q（A）Q（B）（x）P（x）Q（x） 目標(biāo)取反化子句集：(x)P(x)Q(A)Q(B)(x)P(x)Q(x)(x)P(x)Q(A)Q(B)(x)P(x)Q(x) (x)P(x)Q(A)Q(B)(x)P(x)Q(x)(x)P(x)Q(A)Q(B

50、)(y)P(y)Q(y) (x)(y)P(x)Q(A)Q(B)P(y)Q(y) P(x)Q(A)Q(B)P(y)Q(y)得子句集：1，P(x) 2，Q(A)Q(B) 3，P(y)Q(y) 第7題答： （1）將（x）P（x）取反化為子句：（x）P（x） =（ x）P（x）與條件P（A1）P（A2）合在一起得子句集：P（x）, P（A1）P（A2）所以，公式（x）P（x）是P（A1）P（A2）的邏輯推論。（2）對于（x）P（x）的Skolem形，即P（A），取反后為P（A），與條件P（A1）P（A2）合在一起得子句集：P（A）, P（A1）P（A2） 該子句集不能進(jìn)行歸結(jié)，故P（A）不是P（A1）

51、P（A2）的邏輯推論。 第8題答： 該問題用謂詞公式描述如下： 已知： （1）(x)Food(x)Like(John, x)（2）Food(Apple)（3）(x)(y)Eat(y, x)Kill(x, y)Food(x) （4）Eat(Bill, Peanut)Kill(Penut, Bill) （5）(x)Eat(Bill, x)Eat(Sue, x)目標(biāo)1：Like(John, Peanut)目標(biāo)2：(x)Food(x)Eat(Sue, x) 已知條件化子句集： （1）(x)Food(x)Like(John, x)= (x)Food(x)Like(John, x) => Food(

52、x)Like(John, x) （2）Food(Apple) （3）(x)(y)Eat(y, x)Kill(x, y)Food(x)= (x)(y)Eat(y, x)Kill(x, y)Food(x) = (x)(y)Eat(y, x)Kill(x, y)Food(x) => Eat(y, x)Kill(x, y)Food(x) （4）Eat(Bill, Peanut)Kill(Penut, Bill)=> Eat(Bill, Peanut), Kill(Penut, Bill) （5）(x)Eat(Bill, x)Eat(Sue, x)= (x)Eat(Bill, x)Eat(S

53、ue, x) => Eat(Bill, x)Eat(Sue, x) 目標(biāo)1取反化子句集：Like(John, Peanut) 目標(biāo)2取反化子句集：(x)Food(x)Eat(Sue, x) = (x)Food(x)Eat(Sue, x) => Food(x)Eat(Sue, x) 對于目標(biāo)1，經(jīng)變量換名后，得子句集：Food(x1)Like(John, x1)，F(xiàn)ood(Apple)，Eat(y2, x2)Kill(x2, y2)Food(x2)，Eat(Bill, Peanut), Kill(Penut, Bill), Eat(Bill, x3)Eat(Sue, x3), Like(John, Peanut) 歸結(jié)樹如下：對于目標(biāo)2，經(jīng)變量換名后，得子句集：Food(x1)Like(John, x1)，F(xiàn)ood(Apple)，Eat(y2, x2)Kill(x2, y2)Food(x2)，Eat(Bill, Peanut), Kill(Penut, Bill), Eat(Bill, x3)Eat(Sue, x3), Food(x)Eat(Sue, x) 歸結(jié)樹如下：