人工智能教程答案

1、第一章緒論1.1 答：人工智能就是讓機(jī)器完成那些如果由人來(lái)做則需要智能的事情的科學(xué)。人工智能是相對(duì)于人的自然智能而言， 即用人工的方法和技術(shù)， 研制智能機(jī)器或智能系統(tǒng)來(lái)模仿延伸和擴(kuò)展人的智能， 實(shí)現(xiàn)智能行為和 “機(jī)器思維 ”，解決需要人類專家才能處理的問題。1.2 答： “智能 ”一詞源于拉丁 “Legere ”，意思是收集、匯集，智能通常用來(lái)表示從中進(jìn)行選擇、理解和感覺。所謂自然智能就是人類和一些動(dòng)物所具有的智力和行為能力。智力是針對(duì)具體情況的，根據(jù)不同的情況有不同的含義?！爸橇?”是指學(xué)會(huì)某種技能的能力，而不是指技能本身。1.3 答：專家系統(tǒng)是一個(gè)智能的計(jì)算機(jī)程序，他運(yùn)用知識(shí)和推理步驟來(lái)解

2、決只有專家才能解決的復(fù)雜問題。 即任何解題能力達(dá)到了同領(lǐng)域人類專家水平的計(jì)算機(jī)程序度可以稱為專家系統(tǒng)。1.4 答：自然語(yǔ)言處理語(yǔ)言翻譯系統(tǒng)，金山詞霸系列機(jī)器人 足球機(jī)器人模式識(shí)別 Microsoft Cartoon Maker博弈 圍棋和跳棋第二章知識(shí)表達(dá)技術(shù)2.1 解答：（ 1）狀態(tài)空間 (State Space)是利用狀態(tài)變量和操作符號(hào)，表示系統(tǒng)或問題的有關(guān)知識(shí)的符號(hào)體系，狀態(tài)空間是一個(gè)四元組（S，O，S0， G）：S 狀態(tài)集合 ;O 操作算子集合;S0初始狀態(tài) ,S0S;G目的狀態(tài) ,GS,(G 可若干具體狀態(tài)，也可滿足某些性質(zhì)的路徑信息描述)從 S0 結(jié)點(diǎn)到 G 結(jié)點(diǎn)的路徑被稱為求解路

3、徑。狀態(tài)空間一解是一有限操作算子序列，它使初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)：O1O2O3OkS0S1S2G其中 O1 ， ， Ok 即為狀態(tài)空間的一個(gè)解(解往往不是唯一的 )（ 2）謂詞邏輯是命題邏輯的擴(kuò)充和發(fā)展，它將原子命題分解成客體和謂詞兩個(gè)部分。與命題邏輯中命題公式相對(duì)應(yīng)，謂詞邏輯中也有謂詞（命題函數(shù)）公式、原子謂詞公式、復(fù)合謂詞公式等概念。一階謂詞邏輯是謂詞邏輯中最直觀的一種邏輯。（ 3）語(yǔ)義網(wǎng)絡(luò)是一種采用網(wǎng)絡(luò)形式表示人類知識(shí)的方法。即用一個(gè)有向圖表示概念和概念之間的關(guān)系， 其中節(jié)點(diǎn)代表概念，節(jié)點(diǎn)之間的連接弧(也稱聯(lián)想弧 )代表概念之間的關(guān)系。常見的語(yǔ)義網(wǎng)絡(luò)形式有命題語(yǔ)義網(wǎng)絡(luò)、數(shù)據(jù)語(yǔ)義網(wǎng)絡(luò)：E-

4、R圖（實(shí)體-關(guān)系圖）、語(yǔ)言語(yǔ)義網(wǎng)絡(luò)等。2.2 解答：（ 1）GSMANAREMORTALISAFgISAISAISAM動(dòng) 作A動(dòng) 作H主體對(duì)象（ 2）GSCLOUDHASISALININGSILVERFISAISAISAcolorg動(dòng) 作動(dòng) 作CHW主體對(duì)象(3)DECPLANMANAGERISAbelongISABRANCHPROFIT-SHARINGGSMANAGERSPARTICIPATEPLANISAFgISAISAISAM動(dòng) 作動(dòng) 作SP對(duì)象主體2.3 解答：設(shè)有如下四個(gè)謂詞：HUMAN(X)X 是人LAWED(X)X 受法律管制COMMIT(X)X 犯法PUNISHED(X) X受

5、法律制裁前兩個(gè)謂詞可以變?yōu)椋篐UMAN(X)LAWED(X)，表示：人人都要受法律的管制；后兩個(gè)謂詞可以變?yōu)椋篊OMMIT(X)PUNISHED(X)到懲罰；進(jìn)一步，還可以把上述兩個(gè)謂詞聯(lián)結(jié)成如下形式：，表示只要X 犯了罪，X 就要受HUMAN(X)LAWED(X)COMMIT(X)PUNISHED(X)本公式的含義是：如果由于某個(gè) X 是人而受到法律管制，則這個(gè)人犯了罪就一定要受到懲罰。晁蓋是人，受法律的管制（老百姓受法律的管制） ；所以晁蓋劫了生辰綱，違反了宋王朝的法律，一定要受到官府的追究。高衙內(nèi)是人， 卻不受法律的管制 （達(dá)官貴人和惡少不受法律的管制） ；所以高衙內(nèi)強(qiáng)搶民女，同樣是違反

6、了宋王朝的法律，卻可以橫行無(wú)忌。2.4 解答：題中提供的條件可記為，依次利用這些條件可得到如下結(jié)果：推得：李、徐、周、錢是同一性別（1）條件：周和錢是同一性別；條件：李、徐、周是同一性別；條件：李的愛人是陳的愛人的表哥，則李的愛人性別是男，而李的性別是女這樣可以初步推出：李、徐、周、錢均是女的，對(duì)應(yīng)的王、陳、孫、吳均是男的。推得：陳與錢是夫妻（2）條件：陳與徐、周俊不構(gòu)成夫妻， 則陳選擇的余地為錢或李；條件：李與陳不構(gòu)成夫妻；條件：吳與徐、周均不構(gòu)成夫妻，則吳選擇的余地為李；推得：吳與李是夫妻條件：王與周不構(gòu)成夫妻，則王選擇的余地為徐；推得：王與徐是夫妻排除上述已經(jīng)成立的條件，顯然可推得：孫與

7、周是夫妻。2.5 解答：符號(hào)微積分基本公式為baf ( x)F (b)F (a)F (x)|ba用產(chǎn)生式表示為：If f(x) and (a,b) Then F(b)-F(a)2.6 解答：題中描述的情況用謂詞形式可表達(dá)如下：DOG(X)X 是狗SOUND(X)X 會(huì)吠叫BIT(X,Y)X 咬 YANIMAL(X) X是動(dòng)物題中各條推理則可以表示為：P1:xDOG(X)yBIT(X,Y ) SOUND(X)P2: :x（ ANIMAL(X)SOUND(X) ）yBIT(X,Y)P3:獵犬是狗， 即DOG(X)種 X的謂詞樣品是獵犬，同時(shí)也可得ANIMAL(獵犬 )將 P3 帶入 P1 可得 S

8、OUND( 獵犬 )，再將 SOUND( 獵犬 )和 ANIMAL( 獵犬 )帶入 P2 可得yBIT( 獵犬 ,Y) ，即可以得到結(jié)果：獵犬是咬人的。2.7解答：題中的三條規(guī)則側(cè)重點(diǎn)不同：R1 規(guī)則的重點(diǎn)在于我?guī)煹娜蝿?wù)；R2 規(guī)則的重點(diǎn)在于敵團(tuán)的配置； R3 規(guī)則的重點(diǎn)在于我?guī)煹娜蝿?wù)和敵團(tuán)的配置同時(shí)滿足。它們之間的關(guān)系為R1R2R3。所以根據(jù)沖突解決規(guī)則中的規(guī)模排序，可知首先應(yīng)該選擇規(guī)則R3，系統(tǒng)執(zhí)行才最有效。2.8解答：鴕鳥非是鳥會(huì)飛ISAISAISAISAZ動(dòng) 作I動(dòng) 作BCF主體對(duì)象ISA知更鳥CL-1HNISACLYDEISAISATIME占有巢STAISAISAISA春天到秋天2.

9、9解答：（1）搖動(dòng) 作主體動(dòng) 作對(duì)象動(dòng) 作方式海浪戰(zhàn)艦輕輕地（2）2.10解答：圖書館框架TB一般工業(yè)技術(shù)ABTTD礦業(yè)工程Z書名工業(yè)技術(shù)自動(dòng)化技術(shù)、作者TP計(jì)算機(jī)技術(shù)TV水利工程ISBN出版時(shí)間出版社2.11解答：在產(chǎn)生式系統(tǒng)中， 隨著產(chǎn)生式規(guī)則的數(shù)量的增加， 系統(tǒng)設(shè)計(jì)者難以理解規(guī)則間的相互作用，究其原因， 在于每條規(guī)則的自含性使得知識(shí)表示的力度過于細(xì)微。因此要提高產(chǎn)生式系統(tǒng)的可理解性， 就應(yīng)當(dāng)按照軟件工程的思想，通過對(duì)規(guī)則的適當(dāng)劃分，將規(guī)則組織誠(chéng)易于管理的功能模塊。 由于框架系統(tǒng)具有組織成塊知識(shí)的良好特性，因此將兩者進(jìn)行有機(jī)結(jié)合，可以為產(chǎn)生式系統(tǒng)的開發(fā)、調(diào)試和管理提供有益的幫助?；诳蚣艿?/p>

10、表示機(jī)制可以用作產(chǎn)生式語(yǔ)言和推理機(jī)制設(shè)計(jì)的一個(gè)重要構(gòu)件。另外，框架可以直接用于表示規(guī)則，如果將每一個(gè)規(guī)則作為一個(gè)框架處理，一組用于解決特定問題的規(guī)則可組織成一類，且在這一類框架中表示這組規(guī)則的各種特性。2.12解答：略2.13解答：（1）題目描述可轉(zhuǎn)換為如下問題（N 階漢諾塔問題）有編號(hào)為A、 B、C 的三個(gè)柱子和標(biāo)識(shí)為1、 2、 、 N 的尺寸依次從小到大的N 個(gè)有中心孔的金片；初始狀態(tài)下N 個(gè)金片按1、2、 、N 順序堆放在A 號(hào)柱子上，目標(biāo)狀態(tài)下N 個(gè)金片以同樣次序順序堆放在B 號(hào)柱子上，金片的搬移須遵守以下規(guī)則：每次只能搬一個(gè)金片，且較大金片不能壓放在較小金片之上，可以借助于C 針。（

11、2）假設(shè)基本操作為move(x,A,C,B)，表示將 x 個(gè)金片從A 移到 B 上，中間可借助于C。當(dāng) N=1時(shí)，則無(wú)需借助中間的C針，就可以直接實(shí)現(xiàn)將問題的最簡(jiǎn)操作，可表示為move-one(1,A,B)；1 個(gè)金片從A 移到B 上，這也是當(dāng) N>1 時(shí)，需要用中間的C 針作輔助。其操作又可分為以下三步：將 N-1 個(gè)金片從A 移到 C 上，中間可借助于B，轉(zhuǎn)換為基本操作就是move(N-1,A,B,C)；將 1 個(gè)金片直接從A 移到B 上，轉(zhuǎn)換為基本操作就是move-one(1,A,B)；將 N-1個(gè)金片從C 移到B 上，中間可借助于A，轉(zhuǎn)換為基本操作就是move(N-1, C,A,

12、 B)；這樣，就將問題的規(guī)模減小為N-1 ，依次遞歸求解就可以得到相應(yīng)的結(jié)果。（3）設(shè)M(x) 表示移動(dòng)x 個(gè)金片所需要的操作次數(shù)，則上述N 階漢諾塔問題可以表示成如下形式：M(1)=1M(N)=2M(N-1)+1最后可以解得M(N)=2N-1下面給出對(duì)梵塔問題給出產(chǎn)生式系統(tǒng)描述，并討論N 為任意時(shí)狀態(tài)空間的規(guī)模。（1）綜合數(shù)據(jù)庫(kù)定義三元組： (A, B, C) ，其中 A, B, C 分別表示三根立柱，均為表，表的元素為間的整數(shù)，表示N 個(gè)不同大小的盤子，數(shù)值小的數(shù)表示小盤子，數(shù)值大的數(shù)表示大盤子。表的第一個(gè)元素表示立柱最上面的柱子，其余類推。1 N之（ 2）規(guī)則集為了方便表示規(guī)則集，引入以

13、下幾個(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) 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 (firs

14、t(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) 初

15、始狀態(tài)：（ 1， 2， .， N ），（），（）(4) 結(jié)束狀態(tài)：（），（），（ 1， 2， .， N）問題的狀態(tài)規(guī)模：每一個(gè)盤子都有三種選擇：在A 上、或者在B 上、或者在C 上，共N 個(gè)盤子，所以共有種可能。即問題的狀態(tài)規(guī)模為。2.14解答：(1) 定義謂詞 G(x,y):x 比 y 大，個(gè)體有張三（ zhang）、李四（ li ），將這些個(gè)體帶入謂詞中，得到G(zhang,li)和G(zhang,li),根據(jù)語(yǔ)義用邏輯連接詞將它們聯(lián)結(jié)起來(lái)就得到表示上述知識(shí)的謂詞公式：G(zhang,li)G(zhang,li)。(2)定義謂詞 Marry(x,y):x和 y 結(jié)婚， Male(x):x是

16、男的， Female(x) ： x 是女的。個(gè)體有甲(A) 、乙(B) ，將這些個(gè)體帶入謂詞中， 得到 Marry(A,B) 、Male(A) 、Female(B) 以及 Male(A) 、Female(B), 根據(jù)語(yǔ)義用邏輯連接詞將它們聯(lián)結(jié)起來(lái)就得到表示上述知識(shí)的謂詞公式：Marry(A,B)(Male(A) Female(B) (Male(B) Female(A)(3) 定義謂詞 Honest 個(gè)體帶入謂詞中，得到(x):x是誠(chéng)實(shí)的，Honest(x) 、Lying Lying(x):x會(huì)說謊。 個(gè)體有張三 （zhang ），將這些(x) 、Lying(zhang) 、Honest(zha

17、ng),根據(jù)語(yǔ)義用邏輯連接詞將它們聯(lián)結(jié)起來(lái)就得到表示上述知識(shí)的謂詞公式：x(Honest(x)Lying(x) )(Lying(zhang)Honest(zhang)第三章問題求解方法3.1 答：深度優(yōu)先搜索與廣度優(yōu)先搜索的區(qū)別在于：在對(duì)節(jié)點(diǎn)n 進(jìn)行擴(kuò)展時(shí)，其后繼節(jié)點(diǎn)在OPEN 表中的存放位置不同。廣度優(yōu)先搜索是將后繼節(jié)點(diǎn)放入OPEN 表的末端， 而深度優(yōu)先搜索則是將后繼節(jié)點(diǎn)放入OPEN 表的前端。廣度優(yōu)先搜索是一種完備搜索，即只要問題有解就一定能夠求出，而深度優(yōu)先搜索是不完備搜索。在不要求求解速度且目標(biāo)節(jié)點(diǎn)的層次較深的情況下，廣度優(yōu)先搜索優(yōu)于深度優(yōu)先搜索；在要求求解速度且目標(biāo)節(jié)點(diǎn)的層次較淺的

18、情況下，深度優(yōu)先搜索優(yōu)于廣度優(yōu)先搜索。廣度優(yōu)先的正例：積木問題；深度優(yōu)先的正例：郵遞員問題，反例：國(guó)際象棋。3.2 答：衡量標(biāo)準(zhǔn)為：這組子狀態(tài)中有沒有目標(biāo)狀態(tài)，如果有，則選擇該節(jié)點(diǎn)并且搜索成功；若沒有，則按照某種控制策略從已生成的狀態(tài)中再選擇一個(gè)狀態(tài)作為當(dāng)前狀態(tài)重復(fù)搜索過程。3.3 答： (1) 廣度優(yōu)先搜索：該程序必須找到解，并且最好是最優(yōu)解；(2) 廣度優(yōu)先搜索：醫(yī)生要根據(jù)病人的各種病狀判斷病人的病；(3) 深度優(yōu)先搜索：該程序要求一定要找到目標(biāo)路徑；(4) 深度優(yōu)先搜索：該程序要求找到最優(yōu)解；(5) 廣度優(yōu)先搜索：不能確定它們是否等同，既不能確定它們是否有等同解。3.4 答：對(duì)于四皇后問

19、題，如果放一個(gè)皇后的耗散值為1 的話，則任何一個(gè)解的耗散值都是4。因此如果h 是對(duì)該耗散值的估計(jì)，是沒有意義的。對(duì)于像四皇后這樣的問題，啟發(fā)函數(shù)應(yīng)該是對(duì)找到解的可能性的評(píng)價(jià)。利用一個(gè)位置放皇后后，消去的對(duì)角線的長(zhǎng)度來(lái)進(jìn)行評(píng)價(jià)。3.5 答：定義h1=M+C-2B ，其中 M ， C 分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。B 1表示船在左岸，B 0 表示船在右岸。也可以定義h2=M+C 。 h1 是滿足 A* 條件的，而h2 不滿足。要說明 h2 M+C 不滿足 A* 條件是很容易的，只需要給出一個(gè)反例就可以了。比如狀態(tài)(1, 1, 1) ，h2=M+C=1+1=2 ，而實(shí)際上只要一次擺渡就可以

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

21、數(shù)，需要向上取整，這個(gè)用符號(hào)表示。而乘以"2" 是因?yàn)橐粋€(gè)來(lái)回相當(dāng)于兩次擺渡，所以要乘以2。而最后的" 1" ，則表示將剩下的3 個(gè)運(yùn)過去，需要一次擺渡?；?jiǎn)有：再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個(gè)人將船運(yùn)到左岸。因此對(duì)于狀態(tài) (M ， C，0)來(lái)說，其所需要的最少擺渡數(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è)

22、人，而最后邊的" 1"，表示送船到左岸時(shí)的一次擺渡。化簡(jiǎn)有：(M+C+1)-2+1=M+C。綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個(gè)式子表示為：M+C-2B 。其中 B 1 表示船在左岸， B 0 表示船在右岸。 由于該擺渡次數(shù)是在不考慮限制條件下， 推出的最少所需要的擺渡次數(shù)。因此， 當(dāng)有限制條件時(shí)，最優(yōu)的擺渡次數(shù)只能大于等于該擺渡次數(shù)。所以該啟發(fā)函數(shù) h 是滿足 A* 條件的。3.6 答：在搜索期間改善h 函數(shù)，是一種動(dòng)態(tài)改變h 函數(shù)的方法。像改進(jìn)的A* 算法中，對(duì)NEXT 中的節(jié)點(diǎn)按g 值的大小選擇待擴(kuò)展的節(jié)點(diǎn)，相當(dāng)于令這些節(jié)點(diǎn)的h0，就是動(dòng)態(tài)修改

23、 h 函數(shù)的一種方法。由定理 2：若 h(n)滿足單調(diào)限制，則由A* 所擴(kuò)展的節(jié)點(diǎn)序列，其f 值是非遞減的，即f(ni) f(nj)），當(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)修改函數(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)的可能性。h3.7 答：67AB5314E658CD2像這種類型的問題， 由于

24、涉及到城市距離或旅行費(fèi)用，所以利用代價(jià)樹廣度優(yōu)先搜索求解。為此，首先必須將旅行交通圖轉(zhuǎn)換為代價(jià)樹，轉(zhuǎn)換方法為：從初始節(jié)點(diǎn)A 開始，把與它直接相鄰的節(jié)點(diǎn)作為他的后繼節(jié)點(diǎn)，對(duì)其他節(jié)點(diǎn)也作同樣的擴(kuò)展，但若一個(gè)節(jié)點(diǎn)以作為某節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，則它就不能再作為該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。另外，圖中節(jié)點(diǎn)除了初始節(jié)點(diǎn)A之外，其它的節(jié)點(diǎn)都有可能在代價(jià)樹中多次出現(xiàn)，為了區(qū)分它們的多次出現(xiàn)，分別用下標(biāo)1,2 標(biāo)出。但他們卻是圖中的同一個(gè)節(jié)點(diǎn)。設(shè)估價(jià)函數(shù)f(n)=d(n)+w(n) ，其中 d(n) 為狀態(tài)的深度， w(n) 為城市間的距離。代價(jià)樹如下所示：A(10)B1C1D1E1(2)(6(8)(7)B2D2E2(8)(10

25、)(4)B3D3(6) (8)D4(8)ACEBDA定義 h1=n*k ，其中 n 是還未走過的城市數(shù)， k 是還未走過的城市間距離的最小值。h2，其中 n 是還未走過的城市數(shù)， ki 是還未走過的城市間距離中 n 個(gè)最小的距離。 顯然這兩個(gè) h 函數(shù)均滿足 A* 條件。3.8 答：可定義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 或 W 走到了相鄰的一個(gè)空格位置，此時(shí)：h(i)-h(j)=0, C(i,j)=1 ；（2） W 跳過了 1 或 2 個(gè) W ，此時(shí) h(i)-h(j

26、)=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（可能同時(shí)包含一個(gè)B ），此時(shí)：h(i)-h(j

27、)=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 ；縱上所述， 無(wú)論是哪一種情況，具有 :h(i)- h(j) C(i,j)。且容易驗(yàn)證h(t)=0 ，所以該 h 是單調(diào)的。由于 h 滿足單調(diào)條件，所以也一定有h(n) h*(n)，即滿足A* 條件。3.9 答：(),(),(),(),()(1)(S,S),S,(S,S)(2)(A

28、,A),A,(A,A)(3)(A),A,(A)(4)(S,A,S)(2)(A,A,A)(3)(A,A)(3)(A)(4)3.10 答：(1) 余一棋的弈法 如下：兩棋手可以從 5 個(gè)錢幣堆中輪流拿走一個(gè)、兩個(gè)或三個(gè)錢幣，揀起最后一個(gè)錢幣者算輸。 試通過博弈證明， 后走的選手必勝， 并給出一個(gè)簡(jiǎn)單的特征標(biāo)記來(lái)表示取勝策略。為了方便起見，用 (AB)()() 這樣的表表示一個(gè)狀態(tài)。這樣得到搜索圖如下：(2) 八數(shù)碼問題空格： Up,Left,Down,Right3.11 答：(1) 與 /或圖的解圖： 那些可解結(jié)點(diǎn)的子圖，包含一結(jié)點(diǎn)到目的結(jié)點(diǎn)集的、連通的可解結(jié)點(diǎn)的子圖。在問題的完整的隱含圖中擴(kuò)展生

29、成出包含初始結(jié)點(diǎn)和目的結(jié)點(diǎn)集合的連通的明顯子圖。(2) 算法 AO* ：必須對(duì)當(dāng)前已生成出的與或圖中的所有結(jié)點(diǎn)實(shí)施其每解點(diǎn)是否為可解結(jié)點(diǎn)的標(biāo)注過程， 如果起始結(jié)點(diǎn)被標(biāo)注為可解的， 則搜索過程可成功地結(jié)束； 如果起始結(jié)點(diǎn)還不能被標(biāo)注為可解的，則應(yīng)當(dāng)繼續(xù)擴(kuò)展生成結(jié)點(diǎn)（盡可能地記錄， 所有生成的結(jié)點(diǎn)中， 哪些結(jié)點(diǎn)被標(biāo)注了可解的， 以便減少下一次標(biāo)注過程的工作量） ；同樣地， 對(duì)不可解結(jié)點(diǎn)也同樣如此。利用結(jié)點(diǎn)的可解/不可解性質(zhì)， 能從搜索圖中刪去可解結(jié)點(diǎn)的任何不可解結(jié)點(diǎn)的子結(jié)點(diǎn)；同樣地， 能刪去不可解結(jié)點(diǎn)的所有的子結(jié)點(diǎn)（搜索這些被刪除的結(jié)點(diǎn)是沒有意義的，而只會(huì)降低搜索的效率） 。兩個(gè)主要過程的反復(fù)：自

30、上而下的圖生長(zhǎng)過程，并通過跟蹤有標(biāo)記的連接符尋找一個(gè)候選局部解圖自下而上的估價(jià)函數(shù)值的修正、連接符的標(biāo)記和SOLVED 的標(biāo)注過程(3)3.12 答：此題要求按照課中例題的方式，給出算法，以下是每個(gè)循環(huán)結(jié)束時(shí)的搜索圖。上面這種做法比較簡(jiǎn)單，也可以如下做：3.13 答：略3.14 答：博弈搜索通常被限制在一定的范圍，搜索的目標(biāo)是確定一步好的走法（好棋）對(duì)手回手后，再繼續(xù)搜索。因此，博弈搜索過程總是由當(dāng)前狀態(tài)向目標(biāo)狀態(tài)搜索，目標(biāo)狀態(tài)向當(dāng)前狀態(tài)搜索。這類博弈的實(shí)例有西洋跳棋等。，等而不是由3.15 答： 8 （ 3， 0， 8） （ 7， 8， 3）、（ 0，6）、（ 8， 9） （ 7,6）、（

31、8,6,5）、（2,3）、（ 0,-2）、（ 6,2）、（ 5,8）、（ 9,2） 88（3，0，8）869583.16 答： 見上圖3.17 答：略3.18 答： 剪裁算法 .剪裁若極小層的 <=(先輩層 )則中止這個(gè)MIN 以下的搜索 .剪裁若極大層的 >(先輩層 )則中止這個(gè)MAX以下的搜索算法如下：double alphabeta( int depth, double alpha, double beta, Position p);/* alpha 是 MAX 的當(dāng)前值 beta 是 MIN 的當(dāng)前值 ,depth 是在搜索樹中的深度 ,p 是所求結(jié)點(diǎn)的位置 */doubl

32、et;if( depth=0 ) return evaluate(p); /* 如果 P 是葉結(jié)點(diǎn) ,算出 P 的值 */ for( i=1; i <= w; i+ ) t = alphabeta( depth - 1, beta,alpha, pi ); if( t> alpha&&MAX)if(t> beta)returnt;/* 直接返回 */elsealpha=t;if( t<alpha&&MIN)if(t< beta)returnt;/* 直接返回 */elsealpha=t;returnalpha;3.19-3.22 答

33、：略第四章基本的推理技術(shù)4.1 答：(1) 推理 ：按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過程。(2) 正向推理正向推理（事實(shí)驅(qū)動(dòng)推理）是由已知事實(shí)出發(fā)向結(jié)論方向的推理?；舅枷胧牵?系統(tǒng)根據(jù)用戶提供的初始事實(shí)， 在知識(shí)庫(kù)中搜索能與之匹配的規(guī)則即當(dāng)前可用的規(guī)則，構(gòu)成可適用的規(guī)則集 RS，然后按某種沖突解決策略從 RS 中選擇一條知識(shí)進(jìn)行推理， 并將推出的結(jié)論作為中間結(jié)果加入到數(shù)據(jù)庫(kù) DB 中作為下一步推理的事實(shí)， 在此之后，再在知識(shí)庫(kù)中選擇可適用的知識(shí)進(jìn)行推理， 如此重復(fù)進(jìn)行這一過程， 直到得出最終結(jié)論或者知識(shí)庫(kù)中沒有可適用的知識(shí)為止。正向推理簡(jiǎn)單、 易實(shí)現(xiàn)， 但目的性不強(qiáng)， 效率低。 需要用

34、啟發(fā)性知識(shí)解除沖突并控制中間結(jié)果的選取， 其中包括必要的回溯。 由于不能反推， 系統(tǒng)的解釋功能受到影響。(3) 反向推理反向推理是以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理，又稱為目標(biāo)驅(qū)動(dòng)推理或逆向推理。反向推理的基本思想是：首先提出一個(gè)假設(shè)目標(biāo)，然后由此出發(fā)， 進(jìn)一步尋找支持該假設(shè)的證據(jù)， 若所需的證據(jù)都能找到，則該假設(shè)成立，推理成功；若無(wú)法找到支持該假設(shè)的所有證據(jù)，則說明此假設(shè)不成立，需要另作新的假設(shè)。與正向推理相比，反向推理的主要優(yōu)點(diǎn)是不必使用與目標(biāo)無(wú)關(guān)的知識(shí)，目的性強(qiáng)， 同時(shí)它還有利于向用戶提供解釋。反向推理的缺點(diǎn)是在選擇初始目標(biāo)時(shí)具有很大的盲目性，若假設(shè)不正確，就有可能要多次提出假設(shè)，影響了

35、系統(tǒng)的效率。反向推理比較適合結(jié)論單一或直接提出結(jié)論要求證實(shí)的系統(tǒng)。(4) 推理方式分類演繹推理、歸納推理、默認(rèn)推理確定性推理、不精確推理單調(diào)推理、非單調(diào)推理啟發(fā)式推理、非啟發(fā)式推理4.2 答：(1) 在推理過程中，系統(tǒng)要不斷地用數(shù)據(jù)庫(kù)中的事實(shí)與知識(shí)庫(kù)中的規(guī)則進(jìn)行匹配，當(dāng)有一個(gè)以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫(kù)相匹配時(shí)，就需要有一種策略來(lái)決定首先使用哪一條規(guī)則，這就是沖突解決策略。 沖突解決策略實(shí)際上就是確定規(guī)則的啟用順序。(2) 沖突解決策略：專一性排序、規(guī)則排序、數(shù)據(jù)排序、就近排序、上下文限制、按匹配度排序、按條件個(gè)數(shù)排序4.3 答：歸結(jié)反演就是利用歸結(jié)和反演實(shí)現(xiàn)定理的證明。具體過程如下：(1)

36、將定理證明的前提謂詞公式轉(zhuǎn)化為子句集F。(2)將求證的目標(biāo)表示成合適的謂詞公式G（目標(biāo)公式） 。(3) 將目標(biāo)公式的否定式G 轉(zhuǎn)化成子句的形式，并加入到子句集F 中，得到子句集 S。(4) 應(yīng)用歸結(jié)原理對(duì)子句集 S 中的子句進(jìn)行歸結(jié)， 并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若歸結(jié)得到一個(gè)空子句NIL ，則停止歸結(jié)，證明了G 為真。4.4 答：略4.5 答：（ 1） (x) (y) P(x,y ) Q(x,y)=(x) (y) P(x,y) Q(x,y)=P(x,y) Q(x,y)子句集為 P(x,y) Q(x,y)（ 2） (x)(y)P(x,y)Q(x,y) R(x,y)=(x)

37、 )(y) P(x,y) Q(x,y)R(x,y)=P(x)P(x)=(x)P(x,f(x) Q(x,f(x)R(x,f(x)=P(x,f(x) Q(x,f(x)R(x,f(x)=P(x,f(x)R(x, f(x) Q(x, f(x)R(x, f(x)= P(x,f(x)R(x, f(x) Q(y, f(y)R(y,f(y)子句集為P(x,f(x)R(x, f(x) 和 Q(y, f(y)R(y, f(y)（3）(x)(y)P(x,y ) (y)Q(x,y) R(x,y)=( x)(R(x,y)=( x) (y) P(x,y) ( y)Q(x,y) R(x,y)=(R(x, f(x)= P(x

38、,f(x) Q(x, f(x) R(x, f(x)子句集為 P(x,f(x) Q(x, f(x) R(x, f(x)4.6 答：(1)(2)A/x, A/y, A/z, A/w, A/u(3)y) P(x,y) ( y)Q(x,y) x) P(x,f(x) Q(x, f(x) 4.7 答：（ 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（

39、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） 得子句集：1, P(x1)2, P(A) Px23, P(x3) P(B)4, P(A) P(B)（ 2）（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)

40、 (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)4.8 答：4.9 答：答：我們用Skier(x) 表示 x 是滑雪運(yùn)動(dòng)員，Alpinist(x) 表示 x 是登山運(yùn)動(dòng)員，Alpine(x) 表示 x是 Alpine 俱樂部的成員。問題用謂詞公式表示如下：已知：(1) Alpine(Tony)(2) Alpine(Mike)(3) Alpine(John)(4) (x)Alpin

41、e(x) Skier(x)Alpinist(x)(5) (x)Alpinist(x) Like(x, Rain)(6) (x)L ike(x, Snow) Skier(x)(7) (x)Like( Tony, x) Like(Mike, x)(8) (x)Li ke(Tony, x) Like(Mike, x)(9) Like(Tony, Snow)(10) Like(Tony, Rain)目標(biāo)： (x)Alpine(x) Alpinist(x) Skier(x)化子句集：(1) Alpine(Tony)(2) Alpine(Mike)(3) Alpine(John)(4)(x) Alpine

42、(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)Li ke(Tony,x) Like(Mike,x)=(x)Like(Tony,x) Like(Mike,x)=>Like(Tony, x) Like(Mike, x)(8) (x)Like(Tony, x) Lik