人工智能課后答案學(xué)習(xí)資料

1、人工智能課后答案第一章課后習(xí)題1、對(duì)N = 5、k<3時(shí)，求解傳教士和野人問題的產(chǎn)生式系統(tǒng)各組成部分進(jìn)行描 述（給出綜合數(shù)據(jù)庫、規(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ī)模。 相傳古代某處一廟宇中，有三根立柱，柱子

2、上可套放直徑不等的 N 個(gè)圓盤，開 始時(shí)所有圓盤都放在第一根柱子上，且小盤處在大盤之上，即從下向上直徑是 遞減的。和尚們的任務(wù)是把所有圓盤一次一個(gè)地搬到另一個(gè)柱子上去（不許暫 擱地上等），且小盤只許在大盤之上。問和尚們?nèi)绾伟岱ㄗ詈竽芡瓿蓪⑺械?盤子都移到第三根柱子上（其余兩根柱子，有一根可作過渡盤子使用）。求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í)

3、才能摘到香蕉，問猴子在某一狀態(tài)下（設(shè)猴子位置為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ù)庫D來生成出D'，試 證明若R存在逆

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

5、v7|wIweI其中B表示黑色將牌，W表示白色將牌，E表示空格。游戲的規(guī)定走法是：（1） 任意一個(gè)將牌可以移入相鄰的空格，規(guī)定其耗散值為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é)中的五城市問題。討論

6、這兩個(gè)函數(shù)是否都在h*的下界范圍及求解結(jié)果。4、2.1節(jié)四皇后問題表述中，設(shè)應(yīng)用每一條規(guī)則的耗散值均為1,試描述這個(gè) 問題h*函數(shù)的一般特征。你是否認(rèn)為任何 h函數(shù)對(duì)引導(dǎo)搜索都是有用的?5、對(duì)N = 5, k<3的 M C問題，定義兩個(gè)h函數(shù)(非零)，并給出用這兩個(gè) 啟發(fā)函數(shù)的A算法搜索圖。討論用這兩個(gè)啟發(fā)函數(shù)求解該問題時(shí)是否得到最佳 解。6證明OPEN表上具有f(n) v f*(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中的

7、八數(shù)碼問題，評(píng)價(jià)函數(shù)仍定義為 f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相會(huì)。9、討論一個(gè)h函數(shù)在搜索期間可以得到改善的幾種方法。10、四個(gè)同心圓盤的扇區(qū)數(shù)字如圖所示，每個(gè)圓盤可單獨(dú)轉(zhuǎn)動(dòng)。問如何轉(zhuǎn)動(dòng)圓 盤使得八個(gè)徑向的4個(gè)數(shù)字和均為12。第三章課后習(xí)題1、數(shù)字重寫問題的變換規(guī)則如下:63，364, 242 , 243, 132 , 121 , 1問如何用這些規(guī)則把數(shù)字6變換成一個(gè)由若干個(gè)1組成的數(shù)字串。試用算 法AO*進(jìn)行求解，并給出搜索圖。求解時(shí)設(shè) k-連接符的耗散值是k個(gè)單 位，h 函數(shù)值規(guī)定為：h (1)= 0 , h (n)= n (nJ)。2、余一棋的弈法如下：兩棋手

8、可以從 5個(gè)錢幣堆中輪流拿走一個(gè)、兩個(gè)或 三個(gè)錢幣，揀起最后一個(gè)錢幣者算輸。試通過博弈證明，后走的選手必 勝，并給出一個(gè)簡(jiǎn)單的特征標(biāo)記來表示取勝策略。3、對(duì)下圖所示的博弈樹，以優(yōu)先生成左邊節(jié)點(diǎn)順序來進(jìn)行a B搜索，試在博弈樹上給出何處發(fā)生剪枝的標(biāo)記，并標(biāo)明屬于a剪枝還是B剪枝。2 S 31 & 4.點(diǎn)擊看大圖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*算法使之能處理出現(xiàn)回路的情況。如下圖所示，若節(jié)點(diǎn)C的耗散值發(fā)生變化時(shí)

9、，所修改的算法能正確處理這種情況。C6、對(duì)3X3的一字棋，設(shè)用+1和-1分別表示兩選手棋子的標(biāo)記，用 0表示空 格，試給出一字棋產(chǎn)生式系統(tǒng)的描述。7、寫一個(gè)a B搜索的算法。&用一個(gè)9維向量C來表示一字棋棋盤的格局，其分量根據(jù)相應(yīng)格內(nèi)的 X,空或0的標(biāo)記分別用+1, 0,或-1來表示。試規(guī)定另一個(gè)9維向量W, 使得點(diǎn)積CW可作為MAX選手（棋子標(biāo)記為X估計(jì)非終端位置的一個(gè)有 效的評(píng)價(jià)函數(shù)。用這個(gè)評(píng)價(jià)函數(shù)來完成幾步極小-極大搜索，并分析該評(píng)價(jià) 函數(shù)的效果。第四章課后習(xí)題1、化下列公式成子句形式:(1)(")P (x)-P (x)(2( 'X) P (x)-(工x) P

10、(x)(3) ( - x) P (x)-門( y) P (y) -p(f (x,y) a C y) Q(x,y) -P (y) (4)(")(二y) P(x, y) Q (y, x)A Q(y, x) s(x,y) - Lx)( y) P (x, y) -S (x, y)2、以一個(gè)例子證明置換的合成是不可交換的3、找出集P (x, z, y) , P (w, u, w) , P (A, u, u) 的 mgu。4、說明下列文字集不能合一的理由：(1) P (f (x, x), A), P (f (y, f (y, A), A) P (A), P (x) (3) P (f (A), x

11、), P (x, A) 5、已知兩個(gè)子句為Loves (father (a), a)Loves (y, x)V Loves (x, y)試用合一算法求第一個(gè)子句和第二個(gè)子句的第一個(gè)文字合一時(shí)的結(jié)果6、用歸結(jié)反演法證明下列公式的永真性:(1) 0x) P (x) 3 (A) A P (x) 3 (B) (2) (z)Q(z)-P(z)-(匸x) Q(x)-P (A) A Q (x) -P(B) (3) Lx)(刊)P (f (x)A Q (f (B) - P (f (A )A P(y)A Q (y) (4) 0x)(y) P (x, y) - (y)嚴(yán)x) P (x, y)(5) ("

12、) P (x)A Q (A)V Q (B) -(工x) P (x)A Q (x)7、以歸結(jié)反演法證明公式(5) P (x)是P (A1)V P (A2)的邏輯推 論，然而，(二x) P (x)的 Skolem形即 P (A)并非P (A1)V P (A2) 的邏輯推論，請(qǐng)加以證明。&給定下述語句：Joh n likes all kinds of food.Apples are food.Anything anyone eats and isn't killed by is food.Bill eats pea nuts and is still alive.Sue eats e

13、veryth ing Bill eats.(1) 用歸結(jié)法證明"John likes pea nuts "(2) 用歸結(jié)法提取回答"What food does Sue eat?"9、已知事實(shí)公式為(C- X)(' y) (-dz)( Gt (x, y)A Gt (y, z) Gt (x, z)( i)()(Succ (u, v) Gt (u, v)C-jx)( Gt (x, x)求證 Gt (5, 2)試判斷下面的歸結(jié)過程是否正確？若有錯(cuò)誤應(yīng)如何改進(jìn)：10、設(shè)公理集為(“u) LAST (cons (u, NIL ) , u)( cons是表構(gòu)

14、造函數(shù))(" x )(| |y)(riz)( LAST ( y, z) f LAST (cons (x, y), z)( LAST (x, y)代表y是表x的最末元素)(1用歸結(jié)反演法證明如下定理：(hv) LAST (cons (2, cons (1, NIL ), v)(2) 用回答提取過程求表(2, 1)的最末元素V。(3) 簡(jiǎn)要描述如何使用這個(gè)方法求長表的最末元素。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) 一

15、個(gè)等腰三角形的底角是相等的。12、我們來考慮下列一段知識(shí)：Tony、Mike和John屬于Alpine俱樂部，Alpine俱樂部的每個(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)由下列公式集描述:ONTABLE (A)

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

17、數(shù)。-,b=1，表示船在左岸，b=0,表示船在右岸。2, 規(guī)則集(3 0)、(0 3)、(2 1)、(1 1)、(1規(guī)則集可以用兩種方式表示，兩種方法均可。第一種方法：按每次渡河的人數(shù)分別寫出每一個(gè)規(guī)則，共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ī)則集如下:r1:IF (m, c, 1) THEN (m-3, c, 0)r2：IF (m, c, 1) THEN (m, c-3, 0)r3：IF (m, c,

18、 1) THEN (m-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

19、) THEN (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ī)則集如下：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>

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

21、將 L2 灌滿水 */將 L5 水到光 */將 L2 水到光 */到入 L5 中 */r5：IF (L5, L2) and L5+L2<=5 THEN (L5+L2, 0) /* L2r6:IF (L5,L2) andL5+L2>5 THEN (5, L5+L2-5) /* L2到入 L5 中 */r7：IF (L5,L2) andL5+L2<=2 THEN (0, L5+L2) /* L5到入 L2 中 */r8:IF (L5,L2) andL5+L2>5 THEN (L5+L2-2, 2) /* L5到入 L2 中 */3，初始狀態(tài)：(5, 0)(0, 1)4，結(jié)束

22、條件： (x, 1)，其中 x 表示不定。當(dāng)然結(jié)束條件也可以寫成：答：1綜合數(shù)據(jù)庫定義三元組：(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(

23、A) <first(B) 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(firs

24、t(C) <first(A) THEN(con s(first(C), A), B, tail(C)r6: IF (A, B,C)and(first(C) <first(B) THEN(A, con s(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è)盤子，所以共有 "種可能。即問題的狀態(tài)規(guī)模為八。第4題答： 1，綜合數(shù)據(jù)庫定義 5元組：( M, B, Box, On, H ) 其中：M ：猴子的位置

25、B :香蕉的位置Box ：箱子的位置On=0 :猴子在地板上On=1 :猴子在箱子上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) 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,

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

27、x, y,乙 n) THEN (x, y, z, n+1)r3: IF (x, y,乙 n) THEN (x, y, z, n+1)其中x表示對(duì)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ù)的一位。答：設(shè)

28、規(guī)則R的逆用R'表示。由題意有 R應(yīng)用于D后，得到數(shù)據(jù)庫 D'，由可交換系統(tǒng)的 性質(zhì)，有:rule(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)綜合上述兩個(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ù)庫，其規(guī)則是將集合中的兩個(gè)整數(shù)相乘后

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

30、些規(guī)則用 R2表示。由于 R1中的規(guī)則可以直接應(yīng)用與D，所以R1中規(guī)則的應(yīng)用與 R2中規(guī)則的執(zhí)行結(jié)果無關(guān)，也與R1中其他的規(guī)則的執(zhí)行無關(guān)。所以可以認(rèn)為，先將 R1中所有的規(guī)則對(duì) D應(yīng)用，然后再按照原來的次序應(yīng)用R2中的規(guī)則。因此對(duì)于本題的情況，這樣得到的綜合數(shù)據(jù)庫與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)。這樣得到搜索圖如下：)0)第2題提示：可定義h為：h=

31、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或W走到了相鄰的一個(gè)空格位置，此時(shí)：h(i)-h(j)=0, C(i,j)=1 ；(2) W 跳過了 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

32、；(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 (可能同時(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 ；縱上所述，無論是哪一種情況

33、，具有：h(i)-h(j) < C(i,j)且容易驗(yàn)證h(t)=0 ,所以該h是單調(diào)的。由于h滿足單調(diào)條件，所以也一定有h(n) < h*(n)即滿足A*條件。答：定義h1= n*k,其中n是還未走過的城市數(shù)，k是還未走過的城市間距離的最小n£燈值。h2=，其中n是還未走過的城市數(shù)，ki是還未走過的城市間距離中n個(gè)最小的距離。顯然這兩個(gè)h函數(shù)均滿足A*條件。第4題提示：對(duì)于四皇后問題，如果放一個(gè)皇后的耗散值為1的話，則任何一個(gè)解的耗散值都是4。因此如果h是對(duì)該耗散值的估計(jì)，是沒有意義的。對(duì)于像四皇后這樣的問題，啟 發(fā)函數(shù)應(yīng)該是對(duì)找到解的可能性的評(píng)價(jià)。比如像課上講到的，禾U

34、用一個(gè)位置放皇后后，消 去的對(duì)角線的長度來進(jìn)行評(píng)價(jià)。答：定義h仁M+C-2B，其中M, C分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。B =1表示船在左岸，B = 0表示船在右岸。也可以定義h2=M+C。h1是滿足A*條件的，而h2不滿足。要說明h(n) = 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*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次

35、可以將三人從左岸運(yùn)到右岸，然后再有一個(gè)人將船送回來。這樣，船一個(gè)來回可以運(yùn)過河 2人，而船仍然在左岸。而最后剩下的三個(gè)人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。叱斗+ 1所以，在不考慮限制條件的情況下，也至少需要擺渡$ I次。其中分子上的"-3"表示剩下三個(gè)留待最后一次運(yùn)過去。除以"2"是因?yàn)橐粋€(gè)來回可以運(yùn)過去2人，需要 2 個(gè)來回，而”來回"數(shù)不能是小數(shù)，需要向上取整，這個(gè)用符號(hào)表示。而乘以"2"是因?yàn)橐粋€(gè)來回相當(dāng)于兩次擺渡，所以要乘以2。而最后的"+ 1"，則表示將剩下的3個(gè)運(yùn)過去，需要一次擺渡。化簡(jiǎn)有

36、:|皿十(7-勻丄+GJ_丄2x 2 *1 i+1 =+ M + C - 22再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個(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ù)。因此所需要的最少擺渡數(shù)為：(M+C+1)-2+1 。其中(M+C+1)的” + 1"表示送船回到左岸的那個(gè)人，而最后邊的"+ 1"，表示送船到左岸時(shí)的一次擺渡。化簡(jiǎn)有：(M+C+1)-2+ 仁M+C 。綜合船在左岸和船在

37、右岸兩種情況下，所需要的最少擺渡次數(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*(s)的節(jié)點(diǎn)都被擴(kuò)展了。用反證法證明。假設(shè)在 A* 結(jié)束的時(shí)候， OPEN 表中有一個(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í)，算法

38、結(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)?A*選作擴(kuò)展的任何一個(gè)節(jié)點(diǎn)n,均有f(n) <f*(s)因此f(n)>f*(s)的節(jié)點(diǎn)，不會(huì)被A*所擴(kuò)展。所以如果從OPEN表中去掉f(n)>f*(s)的節(jié)點(diǎn)，不會(huì)影響A*的可采納性。而F是f*(s)的上界范圍，因此去掉f(n)>F的節(jié)點(diǎn)也同樣不會(huì)影響A*的可采納性。第8題提示：對(duì)于 8 數(shù)碼問題

39、,逆向搜索和正向搜索是完全一樣的,只是把目標(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) < 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)條

40、件時(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ù)字之和為48。為此，我們可以將目標(biāo)進(jìn)行分解，首先滿足陰影扇區(qū)的數(shù)字之和為48 （這時(shí)非陰影部分的數(shù)字和也一定為 48）。為了這個(gè)目標(biāo)我們可以通過每次轉(zhuǎn)動(dòng)圓盤45。實(shí)現(xiàn)

41、。在第一個(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)90。的方式實(shí)現(xiàn)，這樣即可以調(diào)整相對(duì)扇區(qū)的數(shù)字和，又不破壞第一個(gè)目標(biāo)。在第二個(gè)目標(biāo)實(shí)現(xiàn)之后，我們就可 以實(shí)現(xiàn)最終目標(biāo)：扇區(qū)內(nèi)的數(shù)字和為12。同樣我們希望在實(shí)現(xiàn)這個(gè)目標(biāo)的時(shí)候，不破壞前兩個(gè)目標(biāo)。為此我們采用轉(zhuǎn)動(dòng)180。的方式實(shí)現(xiàn)。這樣同樣是即可以保證前兩個(gè)目標(biāo)不被破壞，又可以實(shí)現(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è)目

42、標(biāo)不能實(shí)現(xiàn)時(shí)，重新試探其他的第一、第二個(gè)目標(biāo)。第三章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題 答：此題要求按照課中例題的方式，給出算法，以下是每個(gè)循環(huán)結(jié)束時(shí)的搜索圖。9從該搜索圖可以看出，無論先走者選擇哪個(gè)走步，后走者都可以走到標(biāo)記為A的節(jié)點(diǎn)，該節(jié)點(diǎn)只剩下一枚錢幣，所以先走者必輸。對(duì)于一般的具有n個(gè)錢幣的情況，當(dāng) n =4 >m +1時(shí)，后走者存在取勝策略。因?yàn)楹笞哒呖梢愿鶕?jù)先走者的走法，選擇自己的走法， 使得雙方拿走的錢幣數(shù)為 4,這樣經(jīng)過 m個(gè)輪回后，共拿走了 4Xm個(gè)錢幣，只剩下了一枚 錢幣，而此時(shí)輪到先走者走棋。所以在這種情況下，后走者存在取勝的

43、策略。對(duì)于錢幣數(shù) 不等于4Xm+ 1的情況，先走者可以根據(jù)實(shí)際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢 幣數(shù)為4Xm + 1個(gè)，此時(shí)先走者相當(dāng)于+ 1個(gè)錢幣時(shí)的后走者了。因此在這種情況下，先走者存在獲勝的策略。答:10 5 -3 3-3 0 2-2 3 5 E 5 書口 i 5 1-30-55-33 2 5 -5 " l-£ 1 4 5 1 -1-： 3 -3E-2第四章課后習(xí)題答案答：(1) C x)P(x) T P(x)(x)P(x) V P(x)P(x) V P(x)(2) ( ：x)P(x) t(x)P(x)(. k)P(x) V px)P(x)x)P(x) V py

44、)P(y)(x)(y)P(x) V P(y)P(x) V P(f(a)(3) C Jx)P(x) t( Jy)P(y) t P(f(x y) A C y)Q(x , y) t P(y)C'X)P(X)TKy)卜P(y) V P(f(x , y) A G y)卜Q(x , y) V P(y)C x)P(x) t( .y)P(y) V P(f(x , y) A (二 y)Q(x , y) A P(y)0 x)P(x) t( .y)P(y) V P(f(x , y) A (二 z)Q(x , z) A P(z)C x)P(x) V (I 1y)P(y) V P(f(x, y) A (二 z)

45、Q(x , z) A P(z)Cx)P(x) A (=y)P(y) A P(f(x , y) V (z)Q(x , z)V P(z)rx)y)(z)P(x) A P(y) A P(f(x , y) V Q(x , z)V P(z)Gx)(二y)(Az)P(x) A P(y) V Q(x , z) V P(z) A P(f(x , y) V Q(x , z) V P(z)P(a) A P(b) V Q(a, z) V P(z) A P(f(a , b) V Q(a, z) V P(z)P(a), P(b) V Q(a, z1)V P(z1), P(f(a , b) V Q(a, z2) V P(

46、z2)(4) (' x)(二y)P(x , y) tQ(y, x) A Q(y , x) tS(x, y) t( x)( y)P(x , y) tS(x, y)( x)( y)P(x , y) tQ(y, x) A Q(y , x) tS(x, y) T(x)y)P(x , y) tS(x, y)(h'lx)(二y)P(x , y) V Q(y , x) A Q(y , x) V S(x, y) t( u)(，v)P(u , v) V S(u, v)( ' *)( Hy)P(x , y) V Q(y , x) A Q(y , x) V S(x, y) V (二 u)(&

47、#39; v)P(u , v) V S(u, v)Px)dy)P(x , y) A Q(y , x) V Q(y , x) A S(x , y) V G u)v)P(u , v) V S(u, v)(")(【)(二 u)(Flv)P(x , y) A Q(y , x) V Q(y , x) A S(x, y) V P(u , v) V S(u, v)Gx)( y)pu)e< v)P(x , y) V Q(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)Cx)(y)pu)C-v)P(x ,

48、y) V Q(y , x) V P(u, v) V S(u, v) A P(x ,y) V S(x,y) VP(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(y) , v) A Q(y , a)V S(a, y) V P(f(y) , v) V S(f(y), v)P(a , y1) V Q(y1 , a) V P(f(y1) , v) V S(f(y1) , v),

49、 P(a, y2) V S(a, y2) V P(f(y2) , v2) V S(f(y2) , v2), Q(y3 , a)V S(a, y3) V P(f(y3) , v3)V S(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, 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

50、(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題 答：略答：(1)Ox) P (x) F (A) A P (x) F ( B) 目標(biāo)取反化子句集： (rx) P (x) TP (A) A P (x) TP ( B) (二 x) P (x )V P (A) A P (x )V P ( B) (、 x) P (x)A P (A) V P (x)A P ( B) (、 x)

51、P (x)A P (A) V P (x) A P (x)A P (A) V P ( B) C- 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 P(B)(2)(|z) Q ( z) tp (z) t(二x) Q (x) tp ( A) A Q ( x) tp (B) 目標(biāo)取反化子句集:( ' z)Q(z) tP(z)

52、 t(x)Q(x) tP(A) A Q(x) tP(B)( ' z)Q(z) V P(z) tfx)Q(x) V P(A) A Q(x) V P(B)( . z)卜Q(z) V P(z) V(It ：x)卜Q(x) V P(A) A 卜Q(x) V P(B)( z)( ' x)Q(z) V P(z) A Q(x) A P(A) V Q(x) A P(B)C z)C x)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)Q(z) V P(z) A Q(x) A Q(x) V P(B) A P(A) V Q(x)

53、 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)(二 x )(1： W) P ( f ( x )A Q ( f ( B) P ( f (A )A P ( y)A Q(y) 目標(biāo)取反化子句集：(工X)(工y)P(f(x) A Q(f(B) TP(f(A) A P(y) A Q(y)(工刈(工 y)P(f(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

54、) A Q(f(B) A 卜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)(7ix)(ny) P (x, y) T('.|y)(二x) P (x, y)目標(biāo)取反化子句集:(")( y)P(x , y) t( y)(二 x)P(x, y) (匚x)( - y)P(x , y) V Ly)Gx)P(x, y) C"x)( - y)P(x , y) V (*v)fu)P(u, v) px)C )P(x , y) A (=v)C u)P(u, v) (匸x)(rHy)(二 v)(| ' |u)P(x, y) A P(u, v)P(a, y) A P(u, f(y)得子句集：1 , P(a , y1)2 , P(u , f(y2)(