人工智能課后答案0001

第一章課后習(xí)題1、對N＝5、k≤3時，求解傳教士和野人問題的產(chǎn)生式系統(tǒng)各組成部分進行描述（給出綜合數(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個圓盤，開始時所有圓盤都放在第一根柱子上，且小盤處在大盤之上，即從下向上直徑是遞減的。和尚們的任務(wù)是把所有圓盤一次一個地搬到另一個柱子上去（不許暫擱地上等），且小盤只許在大盤之上。問和尚們?nèi)绾伟岱ㄗ詈竽芡瓿蓪⑺械谋P子都移到第三根柱子上（其余兩根柱子，有一根可作過渡盤子使用）。求N＝2時，求解該問題的產(chǎn)生式系統(tǒng)描述，給出其狀態(tài)空間圖。討論N為任意時，狀態(tài)空間的規(guī)模。4、對猴子摘香蕉問題，給出產(chǎn)生式系統(tǒng)描述。一個房間里，天花板上掛有一串香蕉，有一只猴子可在房間里任意活動（到處走動，推移箱子，攀登箱子等）。設(shè)房間里還有一只可被猴子移動的箱子，且猴子登上箱子時才能摘到香蕉，問猴子在某一狀態(tài)下（設(shè)猴子位置為 a，箱子位置為b，香蕉位置為c），如何行動可摘取到香蕉。5、對三枚錢幣問題給出產(chǎn)生式系統(tǒng)描述及狀態(tài)空間圖。設(shè)有三枚錢幣，其排列處在"正、正、反"狀態(tài)，現(xiàn)允許每次可翻動其中任意一個錢幣，問只許操作三次的情況下，如何翻動錢幣使其變成"正、正、正"或"反、反、反"狀態(tài)。6、說明怎樣才能用一個產(chǎn)生式系統(tǒng)把十進制數(shù)轉(zhuǎn)換為二進制數(shù)，并通過轉(zhuǎn)換141.125這個數(shù)為二進制數(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、一個產(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)任意一個將牌可以移入相鄰的空格，規(guī)定其耗散值為 1；(2)任意一個將牌可相隔1個或2個其他的將牌跳入空格，規(guī)定其耗散值等于跳過將牌的數(shù)目；游戲要達到的目標(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*函數(shù)的一般特征。你是否認為任何h函數(shù)對引導(dǎo)搜索都是有用的？5、對N＝5，k≤3的M－C問題，定義兩個h函數(shù)(非零)，并給出用這兩個啟發(fā)函數(shù)的 A算法搜索圖。討論用這兩個啟發(fā)函數(shù)求解該問題時是否得到最佳解。6、證明OPEN表上具有f(n)<f*(s)的任何節(jié)點n，最終都將被A*選擇去擴展。7、如果算法A*從OPEN表中去掉任一節(jié)點n，對n有f(n)>F(F>f*(s))，試說明為什么算法A*仍然是可采納的。8、用算法A逆向求解圖2.7中的八數(shù)碼問題，評價函數(shù)仍定義為f(n)=d(n)+w(n)。逆向搜索在什么地方和正向搜索相會。9、討論一個h函數(shù)在搜索期間可以得到改善的幾種方法。10、四個同心圓盤的扇區(qū)數(shù)字如圖所示，每個圓盤可單獨轉(zhuǎn)動。問如何轉(zhuǎn)動圓盤使得八個徑向的4個數(shù)字和均為12。第三章課后習(xí)題1、數(shù)字重寫問題的變換規(guī)則如下：TOC\o"1-5"\h\z6→3，3 4→3，16→4，2 3→2，14→2，2 2→1，1問如何用這些規(guī)則把數(shù)字6變換成一個由若干個1組成的數(shù)字串。試用算法AO*進行求解，并給出搜索圖。求解時設(shè)k-連接符的耗散值是k個單位，h函數(shù)值規(guī)定為：h(1)＝0，h(n)＝n(n≠1)。2、余一棋的弈法如下：兩棋手可以從5個錢幣堆中輪流拿走一個、兩個或三個錢幣，揀起最后一個錢幣者算輸。試通過博弈證明，后走的選手必勝，并給出一個簡單的特征標(biāo)記來表示取勝策略。3、對下圖所示的博弈樹，以優(yōu)先生成左邊節(jié)點順序來進行 α-β搜索，試在博弈樹上給出何處發(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、如何修改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)記分別用+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，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，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、給定下述語句：Johnlikesallkindsoffood.Applesarefood.Anythinganyoneeatsandisn'tkilledbyisfood.Billeatspeanutsandisstillalive.SueeatseverythingBilleats.（1）用歸結(jié)法證明"Johnlikespeanuts。"（2）用歸結(jié)法提取回答"WhatfooddoesSueeat?"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)如何改進：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的最末元素）（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俱樂部的每個成員不是滑雪運動員就是一個登山運動員，登山運動員不喜歡雨而且任一不喜歡雪的人不是滑雪運動員，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)這個積木世界的一般知識：每個大的藍色積木塊是在一個綠色積木塊上。每個重的木制積木塊是大的。所有頂上沒有東西的積木塊都是藍色的。所有木制積木塊是藍色的。以具有單文字后項的蘊涵式的集合表示這些語句。繪出能求解 "哪個積木塊是在綠積木塊上"這個問題的一致解圖（用B規(guī)則）。答案第一章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題答：1，綜合數(shù)據(jù)庫定義三元組：(m,c,b)其中：，表示傳教士在河左岸的人數(shù)。，表示野人在河左岸的認輸。，b=1，表示船在左岸，b=0，表示船在右岸。2，規(guī)則集規(guī)則集可以用兩種方式表示，兩種方法均可。第一種方法：按每次渡河的人數(shù)分別寫出每一個規(guī)則，共 (30)、(03)、(21)、(11)、(10)、(01)、(20)、(02)八種渡河的可能(其中(xy)表示x個傳教士和y個野人上船渡河)，因此共有16個規(guī)則(從左岸到右岸、右岸到左岸各八個)。注意：這里沒有(12)，因為該組合在船上的傳教士人數(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：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)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ī)則集綜合在一起，簡化表示。規(guī)則集如下：r1：IF(m,c,1)and0<i+j〈=3and(i>=jori=0)THEN(m-i,c-j,0)r2：IF(m,c,0)and0<i+j〈=3and(i>=jori=0)THEN(m+i,c+j,1)3，初始狀態(tài)：(5,5,1)4，結(jié)束狀態(tài)：(0,0,0)第2題5升的壺的當(dāng)前水量。2升的壺的當(dāng)前水量。將L5灌滿水*/將5升的壺的當(dāng)前水量。2升的壺的當(dāng)前水量。將L5灌滿水*/將L2灌滿水*/將L5水到光*/將L2水到光*/到入L5中*/到入L5中*/到入L2中*/到入L2中*/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)/*r5：IF(L5,L2)andL5+L2<=5THEN(L5+L2,0)/*L2r6：IF(L5,L2)andL5+L2>5THEN(5,L5+L2-5)/*L2r7：IF(L5,L2)andL5+L2<=2THEN(0,L5+L2)/*L5r8：IF(L5,L2)andL5+L2>5THEN(L5+L2-2,2)/*L53，初始狀態(tài)：(5,0)(0,1)4，結(jié)束條件：(x,1)，其中x表示不定。當(dāng)然結(jié)束條件也可以寫成：第3題(0,1)答：1，綜合數(shù)據(jù)庫定義三元組：(A,B,C)其中A,B,C分別表示三根立柱，均為表，表的元素為 1～N之間的整數(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)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))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ī)模：每一個盤子都有三中選擇：在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：猴子抓到了香蕉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)如果箱子在香蕉處，猴子在箱子上，猴子摘到香蕉其中x,y,z,w為變量3，初始狀態(tài)(c,a,b,0,0)4，結(jié)束狀態(tài)(x1,x2,x3,x4,1)其中x1～x4為變量。第5題答：1，綜合數(shù)據(jù)庫定義四元組：(x,y,z,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,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表示對x取反。3，初始狀態(tài)(1,1,0,0)4，結(jié)束狀態(tài)(1,1,1,3)或者(0,0,0,3)第6題提示：將十進制數(shù)分為整數(shù)部分和小數(shù)部分兩部分。用四元組(a,b,c,d)表示綜合數(shù)據(jù)庫，其中a,b表示到目前為止還沒有轉(zhuǎn)換的十進制數(shù)的整數(shù)部分和小數(shù)部分，c,d表示已經(jīng)轉(zhuǎn)換得到的二進制數(shù)的整數(shù)部分和小數(shù)部分。然后根據(jù)十進制數(shù)轉(zhuǎn)換二進制數(shù)的原理，分別定義整數(shù)的轉(zhuǎn)換規(guī)則和小數(shù)的轉(zhuǎn)換規(guī)則，一次規(guī)則的執(zhí)行，轉(zhuǎn)換得到二進制數(shù)的一位。第7題答：設(shè)規(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)綜合上述兩個式子，有rule(D')＝rule(D)。第8題答：說明一個產(chǎn)生式系統(tǒng)是可交換的，就是要證明該產(chǎn)生式系統(tǒng)滿足可交換產(chǎn)生式系統(tǒng)的三條性質(zhì)。該產(chǎn)生式系統(tǒng)以整數(shù)的集合為綜合數(shù)據(jù)庫，其規(guī)則是將集合中的兩個整數(shù)相乘后加入到數(shù)據(jù)庫中。由于原來數(shù)據(jù)庫是新數(shù)據(jù)庫的子集，所以原來的規(guī)則在新數(shù)據(jù)庫中均可以使用。所以滿足可交換產(chǎn)生式系統(tǒng)的第一條性質(zhì)。該產(chǎn)生式系統(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)。所以可以認為，先將R1中所有的規(guī)則對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為：h＝B右邊的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,j)=1；(2)W跳過了1或2個W，此時h(i)-h(j)=0,C(i,j)=1或2；W向右跳過了一個B(可能同時包含一個W)，此時：h(i)-h(j)=-1,C(i,j)=1或2；W向右跳過了兩個B，此時：h(i)-h(j)=-2,C(i,j)=2；W向左跳過了一個B(可能同時包含一個W)，此時：h(i)-h(j)=1,C(i,j)=1或2；W向左跳過了兩個B，此時：h(i)-h(j)=2,C(i,j)=2；B跳過了1或2個B，此時h(i)-h(j)=0,C(i,j)=1或2；B向右跳過了一個W(可能同時包含一個B)，此時：h(i)-h(j)=1,C(i,j)=1或2；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＝ ，其中n是還未走過的城市數(shù)，ki是還未走過的城市間距離中n個最小的距離。顯然這兩個h函數(shù)均滿足A*條件。第4題提示：對于四皇后問題，如果放一個皇后的耗散值為1的話，則任何一個解的耗散值都是4。因此如果h是對該耗散值的估計，是沒有意義的。對于像四皇后這樣的問題，啟發(fā)函數(shù)應(yīng)該是對找到解的可能性的評價。比如像課上講到的，利用一個位置放皇后后，消去的對角線的長度來進行評價。第5題答：定義h1=M+C-2B，其中M，C分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。 B＝1表示船在左岸，B＝0表示船在右岸。也可以定義h2=M+C。h1是滿足A*條件的，而h2不滿足。要說明h(n)＝M+C不滿足A*條件是很容易的，只需要給出一個反例就可以了。比如狀態(tài) (1,1,1)，h(n)=M+C=1+1=2，而實際上只要一次擺渡就可以達到目標(biāo)狀態(tài)，其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。下面我們來證明h(n)＝M+C-2B是滿足A*條件的。我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運到右岸，然后再有一個人將船送回來。這樣，船一個來回可以運過河2人，而船仍然在左岸。而最后剩下的三個人，則可以一次將他們?nèi)繌淖蟀哆\到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡次。其中分子上的"－3"表示剩下三個留待最后一次運過去。除以個來回，而表示剩下三個留待最后一次運過去。除以個來回，而"來回"數(shù)不能是小數(shù)，"2"是因為一個來回可以運過去2人，需要需要向上取整，這個用符號表示。而乘以"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)的"＋1"表示送船回到左岸的那個人，而最后邊的"＋1"，表示送船到左岸時的一次擺渡。化簡有：(M+C+1)-2+1=M+C。綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個式子表示為：M+C-2B。其中B＝1表示船在左岸，B＝0表示船在右岸。由于該擺渡次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡次數(shù)。因此，當(dāng)有限制條件時，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù)h是滿足A*條件的。第6題答：題目的另一個說法是：當(dāng)A*結(jié)束時，OPEN表中任何一個具有f(n)<f*(s)的節(jié)點都被擴展了。用反證法證明。假設(shè)在A*結(jié)束的時候，OPEN表中有一個節(jié)點n沒有被擴展，且f(n)<f*(s)。A*算法每次從OPEN表中取出f值最小的節(jié)點擴展，當(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擴展，而不是目標(biāo)t，與A*已經(jīng)結(jié)束矛盾。第7題答：因為A*選作擴展的任何一個節(jié)點n，均有f(n)≤f*(s)，因此f(n)>f*(s)的節(jié)點，不會被A*所擴展。所以如果從OPEN表中去掉f(n)>f*(s)的節(jié)點，不會影響A*的可采納性。而F是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ù)的方法。像改進的A*算法中，對NEST中的節(jié)點按g值的大小選擇待擴展的節(jié)點，相當(dāng)于令這些節(jié)點的 h＝0，就是動態(tài)修改h函數(shù)的一種方法。由定理6，當(dāng)h滿足單調(diào)條件時，A*所擴展的節(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)作為節(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)進行分解，首先滿足陰影扇區(qū)的數(shù)字之和為48（這時非陰影部分的數(shù)字和也一定為48）。為了這個目標(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)呢？有可能不一定。在這種情況下，就需要在發(fā)現(xiàn)第三個目標(biāo)不能實現(xiàn)時，重新試探其他的第一、第二個目標(biāo)。第三章課后習(xí)題答案說明：由于人工智能的很多題目都很靈活，以下解答僅供參考。第1題答：此題要求按照課中例題的方式，給出算法，以下是每個循環(huán)結(jié)束時的搜索圖。

第2題答：從該搜索圖可以看出，無論先走者選擇哪個走步，后走者都可以走到標(biāo)記為A的節(jié)點，該節(jié)點只剩下一枚錢幣，所以先走者必輸。對于一般的具有n個錢幣的情況，當(dāng)n＝4×m＋1時，后走者存在取勝策略。因為后走者可以根據(jù)先走者的走法，選擇自己的走法，使得雙方拿走的錢幣數(shù)為4，這樣經(jīng)過m個輪回后，共拿走了4×m個錢幣，只剩下了一枚錢幣，而此時輪到先走者走棋。所以在這種情況下，后走者存在取勝的策略。對于錢幣數(shù)不等于4×m＋1的情況，先走者可以根據(jù)實際的錢幣數(shù)選擇取走的錢幣數(shù)，使得剩下的錢幣數(shù)為4×m＋1個，此時先走者相當(dāng)于4×m＋1個錢幣時的后走者了。因此在這種情況下，先走者存在獲勝的策略。第3題答：報儀P」OAA宀(cxlz)d>(cxlz,)0?>((qd?-(N)d>(N?e)0?>(cod-(e)d)0(z)d>(z,)0?>((q?e=)d=<_(z)d>(z,)o?>(q)cn<sd}

0(z)d>(z?x)0?>((A?x=)d丄<_(z)d>(z?x)o?>(A)Gn<(x)dHZA)(Ae(xd

a(z)d>(z?x)0丄>_((A?x=)d?<(A)dD<(x)dH_NA)(A0)(x色

asd>(z.x)0?一(zA)>_((A.x=)d?<sd一(A色}<(x)d)(x巳

asd?<(z?x)o=z曰)<((A?x=)d>(A)d?=A>))>(x)d?HXA)?

asd?<(z?x)o=zd<_((Ax=)d>sd?一(A>*(x)dHXA)?

asd?<(A.x)0交色<_((Ax=)d>sd丄(AA)*(x)d)(XA)?

asd>(A.x)0?一(AAi<_((Ax=)d>sd?一(A>*(x)dHXA)?

克壬匸(>?><0=>>?<((1><汙匸(壬=￡)*(><匕(點)?0)宀§=)d?>(x)d}_(A)d?>(x)d一(A邑(XA)_sd丄(A0)>(x)d(x>}-(x)d?=X0)>(x)d(x>}_(x)d?=xd丄宀(x)d(XAr}(2)宀(x)d>(x)d?}-(x)d>(x)d?=XA)_(x)df(x)d=x>(L)還GTnu077（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，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，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））進行合一，x置換成y后，y要與f（y,a）進行合一，出現(xià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）∨~P（B）]得子句集：P(x1)~P(A)∨P{x2}P(x3)∨~P(B)~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)]得子句集：~Q(z)∨P(z)Q(x2)Q(x3)∨~P(B)~P(A)∨Q(x4)~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)取反化子句集：~{(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)]}∧(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)}該子句集不能進行歸結(jié)，故P(A)不是[P(A1)∨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(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)}(x){Eat(Bill,x)→Eat(Sue,x)}=(x){~Eat(Bill,x)∨Eat(Sue,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é)樹如下：修改證明樹如下：得到解答為：Food（Peanut）∧Eat（Sue,Peanut）第9題答：該歸結(jié)過程存在錯誤。其原因是由于不同的子句用了相同的變量名引起的。如上圖中A、B兩個子句的歸結(jié)，兩個子句中的y應(yīng)該是不同的變量，在歸結(jié)時，如果用不同的變量分別表示，就不會出現(xiàn)這樣的問題了。比如 B中的y用y1代替，則歸結(jié)結(jié)果如下：第10題答：化子句集：（u）LAST（cons（u，NIL），u）=>LAST（cons（u，NIL），u）（x）（y）（z）（LAST（y，z）→LAST（cons（x，y），z））=（x）（y）（z）（~LAST（y，z）∨LAST（cons（x，y），z））=>~LAST（y，z）∨LAST（cons（x，y），z）目標(biāo)取反：~（v）LAST（cons（2，cons（1，NIL）），v）=（v）~LAST（cons（2，cons（1，NIL）），v）=>~LAST（cons（2，cons（1，NIL）），v）經(jīng)變量換名后，得子句集：{LAST（cons（u，NIL），u）,~LAST（y，z）∨LAST（cons（x，y），z）,~LAST（cons2，cons（1，NIL）），v）}歸結(jié)樹如下：修改證明樹：得到解答：LAST(cons(2，cons(1，NIL))，1)，表cons(2，cons(1，NIL))的最后一個元素為1。通過以上歸結(jié)過程，我們可以看出，該方法求解長表的最后一個元素的方法是，每次將長表去掉第一個元素，直到最