本文格式為Word版，下載可任意編輯——國科大—人工智能課后答案國科大人工智能

第一章課后習(xí)題

1、對N＝5、k≤3時，求解傳教士和野人問題的產(chǎn)生式系統(tǒng)各組成部分進行描述（給出綜合數(shù)據(jù)庫、規(guī)則集合的形式化描述，給出初始狀態(tài)和目標條件的描述），并畫出狀態(tài)空間圖。

2、對量水問題給出產(chǎn)生式系統(tǒng)描述，并畫出狀態(tài)空間圖。

有兩個無刻度標志的水壺，分別可裝5升和2升的水。設(shè)另有一水缸，可用來向水壺灌水或倒出水，兩個水壺之間，水也可以相互傾灌。已知5升壺為滿壺，2升壺為空壺，問如何通過倒水或灌水操作，使能在2升的壺中量出一升的水來。

3、對梵塔問題給出產(chǎn)生式系統(tǒng)描述，并探討N為任意時狀態(tài)空間的規(guī)模。

相傳古代某處一廟宇中，有三根立柱，柱子上可套放直徑不等的N個圓盤，開始時所有圓盤都放在第一根柱子上，且小盤處在大盤之上，即從下向上直徑是遞減的。和尚們的任務(wù)是把所有圓盤一次一個地搬到另一個柱子上去（不許暫擱地上等），且小盤只許在大盤之上。問和尚們?nèi)绾伟岱ㄗ罱K能完成將所有的盤子都移到第三根柱子上（其余兩根柱子，有一根可作過渡盤子使用）。

求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)作為目標條件，試說明該產(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ù)目；游戲要達到的目標是使所有白將牌都處在黑將牌的左邊（左邊有無空格均可）。對這個問題，定義一個啟發(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ī)則如下：6→3，34→3，16→4，23→2，14→2，22→1，1

問如何用這些規(guī)則把數(shù)字6變換成一個由若干個1組成的數(shù)字串。試用算法AO*進行求解，并給出探尋圖。求解時設(shè)k-連接符的耗散值是k個單位，h函數(shù)值規(guī)定為：h（1）＝0，h（n）＝n（n≠1）。

2、余一棋的弈法如下：兩棋手可以從5個錢幣堆中輪番拿走一個、兩個或三個錢幣，揀起最終一個錢幣者算輸。試通過博弈證明，后走的選手必勝，并給出一個簡單的特征標記來表示取勝策略。

3、對下圖所示的博弈樹，以優(yōu)先生成左邊節(jié)點順序來進行α-β探尋，試在博弈樹上給出何處發(fā)生剪枝的標記，并標明屬于α剪枝還是β剪枝。

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分別表示兩選手棋子的標記，用0表示空格，試給出一字棋產(chǎn)生式系統(tǒng)的描述。

7、寫一個α-β探尋的算法。

8、用一個9維向量C來表示一字棋棋盤的格局，其分量根據(jù)相應(yīng)格內(nèi)的×，空或○的標記分別用+1，0，或-1來表示。試規(guī)定另一個9維向量W，使得點積C·W可作為MAX選手（棋子標記為×）估計非終端位置的一個有效的評價函數(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）]}}

y）[P（x，

（4）（x）（y）{[P（x，y）→Q（y，x）]∧[Q（y，x）→S（x，y）]}→（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）}

修改證明樹如下：

得到解答為：Food(Peanut)∧Eat(Sue,Peanut)第9題

答：該歸結(jié)過程存在錯誤。其原因是由于不同的子句用了一致的變量名引起的。如上圖中A、B兩個子句的歸結(jié)，兩個子句中的y應(yīng)當(dā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）目標取反：

~（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（cons（2，cons（1，NIL）），v）}歸結(jié)樹如下：

修改證明樹：

得到解答：LAST(cons(2，cons(1，NIL))，1)，表cons(2，cons(1，NIL))的最終一個元素為1。通過以上歸結(jié)過程，我們可以看出，該方法求解長表的最終一個元素的方法是，每次將長表去掉第一個元素，直到最終得到了只有一個元素的表，該元素就是長表的最終一個元素。第11題答：略第12題

答：我們用Skier(x)表示x是滑雪運動員，Alpinist(x)表示x是登山運動員，Alpine(x)表示x是Alpine俱樂部的成員。

問題用謂詞公式表示如下：已知：

(1)Alpine(Tony)(2)Alpine(Mike)(3)Alpine(John)

(4)(x){Alpine(x)→[Skier(x)∨Alpinist(x)]}(5)(x){Alpinist(x)→~Like(x,Rain)}(6)(x){~Like(x,Snow)→~Skier(x)}(7)(x){Like(Tony,x)→~Like(Mike,x)}(8)(x){~Like(Tony,x)→Like(Mike,x)}(9)Like(Tony,Snow)(10)Like(Tony,Rain)

目標：(){Alpine(x)∧Alpinist(x)∧~Skier(x)}化子句集：(1)Alpine(Tony)(2)Alpine(Mike)(3)Alpine(John)

(4)(x){Alpine(x)→[Skier(x)∨Alpinist(x)]}=(x){~Alpine(x)∨[Skier(x)∨Alpinist(x)]}=>~Alpine(x)∨Skier(x)∨Alpinist(x)

(5)(x){Alpinist(x)→~Like(x,Rain)}=(x){~Alpinist(x)∨~Like(x,Rain)}=>~Alpinist(x)∨~Like(x,Rain)(6)(x){~Like(x,Snow)→~Skier(x)}=(x){Like(x,Snow)∨~Skier(x)}=>Like(x,Snow)∨~Skier(x)(7)(x){Like(Tony,x)→~Like(Mike,x)}=(x){~Like(Tony,x)∨~Like(Mike,x)}=>~Like(Tony,x)∨~Like(Mike,x)

(8)(x){~Like(Tony,x)→Like(Mike,x)}=(x){Like(Tony,x)∨Like(Mike,x)}=>Like(Tony,x)∨Like(Mike,x)(9)Like(Tony,Snow)(10)Like(Tony,Rain)目標取反：

~(){Alpine(x)∧Alpinist(x)∧~Skier(x)}=(x){~Alpine(x)∨~Alpinist(x)∨Skier(x)}=>~Alpine(x)∨~Alpinist(x)∨Skier(x)經(jīng)變量換名后，得到子句集：

{Alpine(Tony),Alpine(Mike),Alpine(John),~Alpine(x1)∨Skier(x1)