人工智能經(jīng)典習題集及各章總結(jié)(期末考試必備)

人工智能各章小結(jié)及習題解答

第一部分緒論

習題解答：

1.什么是人工智能？發(fā)展過程中經(jīng)歷了哪些階段？

解：人工智能是計算機科學的一個重要分支，也是一門正在發(fā)展中的綜合性前沿學科，它是由計算機科學、

控制論、信息論、神經(jīng)生理學、哲學、語言學等多種學科相互滲透而發(fā)展起來的，目前正處于發(fā)展階段尚

未形成完整體系。

發(fā)展過程中經(jīng)歷的階段有：

第一階段(40年代中~50年代末)神經(jīng)元網(wǎng)絡(luò)時代

第二階段(50年代中~60年代中)通用方法時代

第三階段(60年代中~80年代初)知識工程時代

第四階段(80年代中~90年代初)新的神經(jīng)元網(wǎng)絡(luò)時代

第五階段(90年代初~現(xiàn)在)海量信息處理與網(wǎng)絡(luò)時代

2.人工智能研究的基本內(nèi)容是什么？

解：基本內(nèi)容是：搜索技術(shù)、知識表示、規(guī)劃方法、機器學習、認知科學、自然語言理解與機器翻譯、專

家系統(tǒng)與知識工程、定理證明、博弈、機器人、數(shù)據(jù)挖掘與知識發(fā)現(xiàn)、多Agent系統(tǒng)、復雜系統(tǒng)、足球機

器人、人機交互技術(shù)等.

3.人工智能主要有哪幾大研究學派？

解：(1)符號主義學派：由心理學途徑產(chǎn)生，符號主義認為人工智能起源于數(shù)理邏輯，人類認識(智

能)的基本元素是符號，而智能行為則是符號運算的結(jié)果.

(2)連接主義學派：由生理學途徑產(chǎn)生，連接主義又稱為仿生學派，認為人工智能的基本元素是神經(jīng)

元，智能產(chǎn)生于大量神經(jīng)元的并行分布式聯(lián)結(jié)之中，而智能行為則是聯(lián)結(jié)計算的結(jié)果。

(3)行為主義學派：由生物演化途徑產(chǎn)生，行為主義認為人工智能起源于控制論，提出智能取決于感

知和行為，取決于對外界復雜環(huán)境的適應(yīng)，而不是表示和推理.

4.人工智能有哪些主要的研究領(lǐng)域？

解：(1)問題求解

(2)邏輯推理與定理證明

(3)自然語言理解

(4)自動程序設(shè)計

(5)專家系統(tǒng)

(6)機器學習

(7)神經(jīng)網(wǎng)絡(luò)

(8)機器人學

(9)模式識別

(10)機器視覺

(11)智能控制

(12)智能檢索

(13)智能調(diào)度與指揮

(14)分布式人工智能與Agent

(15)計算智能與進化計算

(16)數(shù)據(jù)挖掘與知識發(fā)現(xiàn)

(17)人工生命

(18)系統(tǒng)與語言工具

第2部分知識與知識表示

本章小結(jié):

知識表示

習題解答：

1設(shè)有如下問題：

(1)有五個相互可直達且距離已知的城市A、B,C,D、E,如圖所示;

(2)某人從A地出發(fā)，去其它四個城市各參觀一次后回到A;

(3)找一條最短的旅行路線

請用產(chǎn)生式規(guī)則表示旅行過程.

解：①綜合數(shù)據(jù)庫(x)

(x)中x可以是一個字母，也可以是一個字符串。

②初始狀態(tài)(A)

③目標狀態(tài)(Axlx2x3x4A)

④規(guī)則集：

rl:IFL(S)=5THENGOTO(A)

r2:IFL(S)<5THENGOTO(B)

r3:IFL(S)<5THENGOTO(0

r4:IFL(S)<5THENGOTO(D)

r5:IFL(S)<5THENGOTO(E)

其中L(S)為走過的城市數(shù)，GOTO(x)為走向城市x

⑤路線如下圖所示:

(ACDEBA)

目標

最短旅行路線為：A->C->D->E->B->A

總距離為5+6+8+10+7=36

2神州大學和東方大學兩?；@球隊在東方大學進行一場比賽，結(jié)局的比分是85:89,用語義網(wǎng)絡(luò)表示.

比賽

是一種

神州大學，籃球賽85：89

客隊結(jié)局

主隊

東方1學

第3部分推理

本章小結(jié):

習題解答：

1張某被盜，公安局派出五個偵察員去調(diào)查.研究案情時，偵察員A說“趙與錢中至少有一人作案”；偵察

員B說“錢與孫中至少有一人作案”；偵察員C說“孫與李中至少有一人作案”；偵察員D說“趙與孫中至

少有一人與此案無關(guān)”；偵察員E說“錢與李中至少有一人與此案無關(guān)工如果這五個偵察員的話都是可信

的，試用歸結(jié)演繹推理求出誰是盜竊犯。

解：第一步：將5位偵察員的話表示成謂詞公式，為此先定義謂詞.

設(shè)謂詞P(x)表示是作案者，所以根據(jù)題意：

A:P(zhao)VP(qian)B:P(qian)VP(sun)

C:P(sun)VP(li)D:rP(zhao)V-1P(sun)

E:-P(qian)V「P(li)

以上每個偵察員的話都是一個子句.

第二步：將待求解的問題表示成謂詞.設(shè)y是盜竊犯，則問題的謂詞公式為P(y),將其否定并與

ANSWER(y)做析?。?/p>

-.P(y)VANSWER(y)

第三步：求前提條件及「P(y)VANSWER(y)的子句集，并將各子句列表如下:

(1)P(zhao)VP(qian)

(2)P(qian)VP(sun)

(3)P(sun)VP(li)

(4)—1P(zhao)V—iP(sun)

(5)-nP(qian)V「P(li)

(6)「P(y)VANSWER(y)

第四步:應(yīng)用歸結(jié)原理進行推理。

(7)P(qian)V—iP(sun)(1)與(4)歸結(jié)

(8)P(zhao)V—>P(1i)(1)與(5)歸結(jié)

(9)P(qian)V—?P(zhao)(2)與(4)歸結(jié)

(10)P(sun)V—>P(1i)(2)與(5)歸結(jié)

(11)—iP(zhao)VP(1i)(3)與(4)歸結(jié)

(12)P(sun)V—>P(qian)(3)與(5)歸結(jié)

(13)P(qian)⑵與⑺歸結(jié)

(14)P(sun)(2)與(12)歸結(jié)

(15)ANSWER(qian)(6)與(13)歸結(jié)，o={qian/y}

(16)ANSWER(sun)(6)與(14)歸結(jié)，o={sun/y)

所以，本題的盜竊犯是兩個人：錢和孫。

2任何兄弟都有同一個父親，John和Peter是兄弟，且John的父親是David,問Peter的父親是誰？

解：第一步：將已知條件用謂詞公式表示出來，并化成子句集。那么，要先定義謂詞。

(1)定義謂詞：

設(shè)Father(x,y)表示x是y的父親。

設(shè)Brother(x,y)表示x和y是兄弟。

(2)將已知事實用謂詞公式表示出來：

F1:任何兄弟都有同一個父親。

(%)(?(初(Brother(x,y)AFather(z,x)-*Father(z,y))

F2:John和Peter是兄弟。

Brother(John,Peter)

F3:John的父親是David。

Father(David,John)

(3)將它們化成子句集，得

Sl={—?Brother(x,y)V—?Father(z,x)VFather(z,y),Brother(John,Peter),Father(David,

John)}

第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER做析取。

設(shè)Peter的父親是u,則有：Father(u,Peter)

將其否定與ANSWER做析取，得

G:-.Father(u,Peter)VANSWER(u)

第三步：將上述公式G化為子句集S2,并將S1和S2合并到S。

S2=(「FatheMu,Peter)VANSWER(u)}

S=S1US2

將S中各子句列出如下：

(1)—.Brother(x,y)V「Father(z,x)VFather(z,y)

(2)Brother(John,Peter)

(3)Father(David,John)

(4)「FatheMu,Peter)VANSWER(u)

第四步：應(yīng)用歸結(jié)原理進行歸結(jié)。

(5)—iBrother(John,y)VFather(David,y)

(1)與(3)歸結(jié)，a={David/z,John/x}

(6)「Brother(John,Peter)VANSWER(David)

(4)與(5)歸結(jié)，o={David/u,Peter/y)

(7)ANSWER(David)(2)與(6)歸結(jié)

第五步：得到了歸結(jié)式ANSWER(David),答案即在其中，所以u=David,即Peter的父親是David。

第4部分搜索策略

本章小結(jié):

搜索策略

博弈問題：

極大極小各析豆：計算出端節(jié)點的估值，再推算出父節(jié)點的得分.

推算的方法是：對“或”節(jié)點，選其子節(jié)點中一個最大的得分作為父節(jié)點的得分，這是為了使自己在可供

選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點，選其子節(jié)點中一個最小的得分作為父節(jié)點的得

分，這是為了立足于最壞的情況.這樣計算出的父節(jié)點的得分稱為倒推值.

a-0剪枝技術(shù)：

對于一個“與”節(jié)點來說，它取當前子節(jié)點中的最小倒推值作為它倒推值的上界，稱此值為

。值。對于一個“或”節(jié)點來說，它取當前子節(jié)點中的最大倒推值作為它倒推值的下界，稱此值為a值.

其一般規(guī)律為：（1）任何“或”節(jié)點x的a值如果不能降低其父節(jié)點的0值，則對節(jié)點x以下的分枝可停

止搜索，并使x的倒推值為a.這種剪枝成為。剪枝.

（2）任何“與"節(jié)點x的|3值如果不能升高其父節(jié)點的a值，則對節(jié)點x以下的分枝可停止搜索，并使x

的倒推值為0.這種剪枝成為a剪枝.

習題解答：

1圖4-1是五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交通費用（代價）如

圖中數(shù)字所示.求從A到E的最小費用交通路線.

解：先將交通圖轉(zhuǎn)換為代價樹，如圖4-2所示.

若用g(x)表示從初始節(jié)點sO到節(jié)點x的代價，用c(xl,x2)表示從父節(jié)點xl到子節(jié)點x2的代價，則

有：

g(x2)=g(xl)+c(xl,x2)

方法一：代價樹的廣度優(yōu)先搜索

(擴展節(jié)點n,將其子節(jié)點放入open表中，計算各子節(jié)點的代價，并按各節(jié)點的代價對open表中全部節(jié)

點按從小到大的順序進行排序(隊列))

步驟如下：

9

9

圖4-3-5

所以，最優(yōu)路徑為A->C->D->E

方法二：代價樹的深度優(yōu)先搜索（不一定是最優(yōu)解）

（擴展節(jié)點n,將其子節(jié)點按代價從小到大的順序放到。pen表的首部（棧））

步驟如下：

雖然D1的代價大于B1的代價，但按照代價

樹的深度優(yōu)先搜索策略，要對D1進行擴展,

放入closed表中（若按代價樹的廣度優(yōu)先搜

索，要對Bl、D1排序，先擴展B1）

E為目標節(jié)點，E2->D1->C1->A

所以路徑為A->C->D->E

注：該題代價樹的深度優(yōu)先搜索與代價樹的廣度優(yōu)先搜索的結(jié)果相同，但這只是巧合.一般情況下，這兩

種方法得到的結(jié)果不一定相同。另外，由于代價樹的深度優(yōu)先搜索有可能進入無窮分支的路徑，因此它是

不完備的.

2如下圖4-5所示，分別用代價樹的廣度優(yōu)先搜索策略和代價樹的深度優(yōu)先搜索策略,

求A到E的最短費用路徑。

圖4一5

解:先將其化成代價樹，如圖4-6:

⑴代價樹的廣度優(yōu)先搜索，步驟如下:

圖4-7-1

A

E為目標節(jié)點，路徑為A->C->E,代價為15.

圖4-8-1

圖4-8-2

雖然C1代價低于D1,但按照代價樹的深度優(yōu)先搜索策略，對D1進行擴展，放入closed表中，因為B1擴

展的節(jié)點為D1,而C1是A節(jié)點擴展得到的.E出棧，為目標節(jié)點，結(jié)束.故解路徑為A->B->D->E,代價為

17,不是最優(yōu)解。

注：深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解.得到的解也不一定是最優(yōu)解（因為是

局部優(yōu)先搜索）.

3下圖是五城市間的交通費用圖，若從西安出發(fā)，要求把每個城市都訪問一遍，最后到達廣州，請找一條

最優(yōu)路線。邊上的數(shù)字是兩城市間的交通費用。

A西安上海D

S0

解：先畫出代價樹:

150

95

120

B1C1D1

1709070

7575

130130

圖4?10

按代價樹的廣度優(yōu)先搜索即可得出最優(yōu)路線，步驟如下:

圖4-11-1

圖4-11-2

圖4-11-3

圖4-11-4

2190

/25y/V240?26^風185/19Ar\

英）????

???c

380340285225340425WO295365355420340

375圖4-11-5

故由此得出最優(yōu)路線為A->B1->D2->C4->E12

即A->B->D->C->E,交通費用為375.

4設(shè)有如圖所示的一棵與/或樹，請分別用與/或樹的廣度優(yōu)先搜索及與/或樹的深度優(yōu)先搜索求出解樹。

解：(1)與/或樹的廣度優(yōu)先搜索

先擴展節(jié)點A,得到節(jié)點B和C,再擴展節(jié)點B,得節(jié)點tl、t2,因為tl、t2為可解節(jié)點，故節(jié)點B可解,

從而可節(jié)點A可解。

所以求得解樹為：

(2)與/或樹的深度優(yōu)先搜索

先擴展節(jié)點A,得到節(jié)點B和C,再擴展節(jié)點C,得節(jié)點D和t5,t5為可解節(jié)點，再擴展節(jié)D,得節(jié)點t3、

t4,因為t3、t4為可解節(jié)點，故節(jié)點D可解，因為節(jié)點D和t5可解，故節(jié)點C可解，從而可節(jié)點A可解。

所以求得解樹為：

5設(shè)有如圖所示的與/或樹，請分別按和代價法及最大代價法求解樹代價.

(1)按和代價法：h(B)=7,h(C)=3,h(A)=7+3+5+6=21

(2)按最大代價法：h(B)=5,h(C)=2,h(A)=5+5=10

1、談?wù)勀銓τ谌斯ぶ悄艿恼J識。

人工智能就是人造智能，目前指用計算機模擬或?qū)崿F(xiàn)的智能，因此人工智能又稱機器智

能。人工智能在我看來，應(yīng)該是像人一樣思考的系統(tǒng)、像人一樣行動的系統(tǒng)、理性地思

考的系統(tǒng)、理性地行動的系統(tǒng)，是像人一樣具有感知的系統(tǒng)，是可以獨立思考、獨立判

斷的系統(tǒng)

2、人工智能有哪些研究途徑和方法？它們的關(guān)系如何？

心理模擬，符號推演;生理模擬，神經(jīng)計算;行為模擬，控制進化;群體模擬，仿生計算;博采廣

鑒，自然計算;原理分析，數(shù)學建模；它們各有所長，也都有一定的局限性，因此這些研究途徑和

方法并不能互相取代，而是并存和互補的關(guān)系。

3、人工智能有哪些研究內(nèi)容？

搜索與求解、學習與發(fā)現(xiàn)、知識與推理、發(fā)明與創(chuàng)造、感知與交流、記憶與聯(lián)想、系統(tǒng)與建

造、應(yīng)用與工程等八個方面。

4、人工智能有哪些分支領(lǐng)域和研究方向？

從模擬的智能層次和所用的方法看，可分為符號智能和計算智能兩大領(lǐng)域；從模擬的腦

智能或腦功能看，可分為機器學習、機器感知、機器聯(lián)想、機器推理、機器行為等分支領(lǐng)域;

從應(yīng)用角度看，可分為難題求解、自動規(guī)劃、調(diào)度與配置、機器定理證明、自動程序設(shè)計、

機器翻譯、智能控制、智能管理、智能決策、智能通信、智能仿真、智能CAD、智能制造、

智能CAI、智能人機接口、模式識別、數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)現(xiàn)、計算機輔助創(chuàng)新、

計算機文藝創(chuàng)作、機器博弈、智能機器人；從系統(tǒng)角度看，可分為智能計算機系統(tǒng)和智能應(yīng)

用系統(tǒng)；從基礎(chǔ)理論看，可分為數(shù)理邏輯和多種非標準邏輯、圖論、人工神經(jīng)網(wǎng)絡(luò)、模糊集、

粗糙集、概率統(tǒng)計和貝葉斯網(wǎng)絡(luò)、統(tǒng)計學習理論與支持向量機、形式語言與自動機等領(lǐng)域;

5、人工智能有哪些應(yīng)用領(lǐng)域或課題？試舉例說明

難題求解、自動規(guī)劃、調(diào)度與配置、機器定理證明、自動程序設(shè)計、機器翻譯、智能控

制、智能管理、智能決策、智能通信、智能仿真、智能CAD、智能制造、智能CAL智

能人機接口、模式識別、數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)現(xiàn)、計算機輔助創(chuàng)新、計算機文

藝創(chuàng)作、機器博弈、智能機器人。

就機器博弈方面，在1997年IBM的“深藍”計算機以2勝3平1負的戰(zhàn)績擊敗了蟬聯(lián)

12年之久的直接國際象棋冠軍加里卡斯帕羅夫，比如先如今中的五子棋對弈，能實現(xiàn)

人與電腦之間的下棋，電腦自動搜索棋步，還可根據(jù)人們所選的電腦難度來決定電腦的

難易程度。

6、簡述人工智能的發(fā)展狀況

人工智能的現(xiàn)狀和發(fā)展呈現(xiàn)如下特點：多種途徑齊頭并進，多種方法寫作互補；新思想、新

技術(shù)不斷涌現(xiàn)，新領(lǐng)域、新方向不斷開括;理論研究更加深入，應(yīng)用研究更加廣泛;研究隊伍

日益壯大，社會影響越來越大;以上特點展現(xiàn)了人工智能學科的繁榮景象和光明前景。它表

明，雖然在通向其最終目標的道路匕還有不少困難、問題和挑戰(zhàn)，但前進和發(fā)展畢竟是大

勢所趨。

7、試編寫一個描述親屬關(guān)系的PROLOG程序，然后再給出一些事實數(shù)據(jù)，建立一個小型演

繹數(shù)據(jù)庫。

domains

name=symbol.sex=symbol.age=integer.

predicates

person(name,sex,age)mother(name,name)father(name,name)brother(name,name)

sister(namc,name)grandfather(name,name)grandmother(name,name)

goal

brother(Name1,Name2),write(Namc1is",Name2,'"sbrother!\n"),

sister(Name3,Name4),write(Name3,"is",Name4,'"ssister!\n"),

grandfathcr(Name5,Namc6),write(Name5is",Name6,"'sgrandfather!\n"),

grandmother(Name7,Name8),write(Name7,"is",Name8,"'sgrandmother!\n").

clauses

person(alan,m,21).person(john,m,22).person(marry,w,23).person(ann,w,24).

mothcr(alice,alan).mother(alice,john).mother(alice,marry).mothcr(alice,ann).

mother(marry,jane).father(alan,tom).father(tom,ben).

brother(Namel,Name2):-person(Namcl,m,Agel),pcrson(Namc2,m,Age2),

mother{Z,Namel),mother(Z,Name2),Agel>Age2.

sister(Name3,Name4):"person(Name3,w,Age3),person(Name4,w,Age4),

mother(Z,Name3),mother(Z,Name4),Age3>Age4.

grandfather(Name1,Name2):-father(Name1,Y),father(Y,Name2).

grandmother(Name7,Name8):-mother(Name7,X),mother(X,Name8).

8.何為狀態(tài)圖和與或圖？圖搜索與問題求解有什么關(guān)系？

狀態(tài)圖是描述尋找目標或路徑問題的有向圖，即描述一個實體基于事件反應(yīng)的動態(tài)行為,

顯示了該實體如何根據(jù)當前所處的狀態(tài)對不同的時間做出反應(yīng)的。與或圖是一-種系統(tǒng)地將

問題分解為互相獨立的小問題，然后分而解決的方法。與或圖中有兩種代表性的節(jié)點：

“與節(jié)點”和“或節(jié)點”，“與節(jié)點”指所有的后續(xù)節(jié)點都有解時它才有解；“或節(jié)

點”指各個后續(xù)節(jié)點均完全獨立，只要其中有一個有解它就有解。關(guān)系：問題求解就

是在一個圖中尋找一個從初始節(jié)點到目標節(jié)點的路徑問題，圖搜索模擬的實際是人腦

分析問題，解決問題的過程，它基于領(lǐng)域知識的問題求解過程。

9.綜述圖搜索的方式和策略。

答：圖搜索方式可分為樹式搜索和線式搜索。圖搜索策略可分為盲目搜索和啟發(fā)式搜索。

10.什么是問題的解？什么是最優(yōu)解？

答：能夠解決問題的方法或具體做法。其中最好的解決方法即代價最小的解稱為最優(yōu)解。

11.什么是與或樹？什么是可解節(jié)點？什么是解樹？

答：一棵樹中的弧線表示所連樹枝為“與”關(guān)系,不帶弧線的樹枝為或關(guān)系。這棵樹中既有

與關(guān)系又有或關(guān)系，因此被稱為與或樹。滿足下列條件的節(jié)點為可解節(jié)點。①終止節(jié)點是

可解節(jié)點；②一個與節(jié)點可解，當且僅當其子節(jié)點全都可解；③一個或節(jié)點可解，只要其子

節(jié)點至少有一個可解。解樹實際上是由可解節(jié)點形成的一棵子樹,這棵子樹的根為初始節(jié)點,

葉為終止節(jié)點，且這棵子樹一定是與樹。

12.設(shè)有三只琴鍵開關(guān)一字排開，初始狀態(tài)為“關(guān)、開、關(guān)“，問連按三次后是否會出現(xiàn)“開、

開、開''或"關(guān)、關(guān)、關(guān)''的狀態(tài)？要求每次必須按下一個開關(guān)，而且只能按一個開關(guān)。請畫

出狀態(tài)空間圖。

解：用（K1,K2,K3）表示三個開關(guān)的狀態(tài)，取值為0時表示閉合，為1時表示打開。則

初始狀態(tài)為（0,1,0）。根據(jù)題設(shè)要求，-一個狀態(tài)I的下一個狀態(tài)和I只能有一位取值不同

（此即狀態(tài)轉(zhuǎn)換規(guī)則），據(jù)此可以畫出狀態(tài)空間圖。

從此狀態(tài)圖不難看出：經(jīng)過連續(xù)三步有狀態(tài)（0,1,0）只能到達狀態(tài)（0,0,0）而不

能到達狀態(tài)（1,1,1）,即會出現(xiàn)狀態(tài)“關(guān)，關(guān)，關(guān)”，但不會出現(xiàn)“開，開，開”。

13.有一農(nóng)夫帶一只狼、一只羊和一筐菜欲從河的左岸乘船到右岸，但受下列條件限制:

（1）船太小，農(nóng)夫每次只能帶一樣東西過河。（2）如果沒有農(nóng)夫看管，則狼要吃羊，羊要吃菜。

請設(shè)計一個過河方案，使得農(nóng)夫、狼、羊、菜都能不受損失地過河。畫出相應(yīng)的狀態(tài)空間

圖。提示：（1）用四元組（農(nóng)夫、狼、羊、菜）表示狀態(tài),其中每個元素都可為0或1,用0

表示在左岸，用1表示在右岸。（2）把每次過河的一種安排作為一個算符，每次過河都必須

有農(nóng)夫，因為只有他可以劃船。

解：初始S=（0,0,0,0）,目標G=（l,1,1,1）

定義操作符L⑴表示農(nóng)夫帶東西到右岸：定義操作符R⑴表示農(nóng)夫帶東西到左岸:

i=0農(nóng)夫自己到右岸；i=0農(nóng)夫自己到左岸；

i=l農(nóng)夫帶狼到右岸；i=l農(nóng)夫帶狼到左岸；

i=2農(nóng)夫帶羊到右岸；i=2農(nóng)夫帶羊到左岸；

i=3農(nóng)夫帶菜到右岸；i=3農(nóng)夫帶菜到左岸；

約束狀態(tài)如下：

解二:：

（1,0,0,X）狼、羊在左岸；

L帶羊過河(b0,b0）

（1,X,0,0）羊、菜在左岸；

2.農(nóng)夫回來(0,0,1,0）

（0,1,1,X）狼、羊在右岸；3.程魁河(b1,b0)

（0,x,1,D羊、菜在右岸；4帶羊回來(0,b0,0)

5.帶菜過河(b1,0,1)

6.農(nóng)夫回來(0,1,0,1)

7.帶羊過河(1，bb1)

(0,0,0,0)+

/晨2)p

Y(I,，0u，,1，,u0廣)，

解二…

/凰0*

(0,0,1,0戶L帶羊過河(1,o,1,0>

/U1)\取3*2.農(nóng)夫回來（0,0,1,0州

(I,1,1,0)(1,0,1,1)，3.帶菜過河(b0,1,1>

及2)\氏2)?4.帶羊回來（0,0,0,

(0,1,0,0)(0,0,0,1W5.麴過洌（1，1，0,

,晨3)/L(l>6.農(nóng)夫回來（0,1,0,

a,1,o,a7.帶羊過河（b1,1,

\雙。?

(0,I,0,1”

(1,1,L1>'

14.請闡述狀態(tài)空間的一般搜索過程。OPEN表與CLOSED表的作用是什么？

答：先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問

題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。若出現(xiàn)，則搜索成功，找到了問題的解：若沒出現(xiàn),

則再按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過

程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進行“擴

展”是指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。

OPEN表用于存放剛生成的節(jié)點，對于不同的搜索策略，節(jié)點在OPEN表中的排序是不

同的。

CLOSED表用于存放將要擴展或者已擴展的節(jié)點。

15.廣度優(yōu)先搜索與深度優(yōu)先搜索各有什么特點？

答：廣度優(yōu)先搜索就是始終先在同一級節(jié)點中考查,只有當同一級節(jié)點考查完之后,才考

查下?級節(jié)點。或者說，是以初始節(jié)點為根節(jié)點，向下逐級擴展搜索樹。所以，廣度優(yōu)先策略

的搜索樹是自頂向下一層一層逐漸生成的。深度優(yōu)先搜索就是在搜索樹的每一層始終先只

擴展一個子節(jié)點,不斷地向縱深前進,直到不能再前進（到達葉子節(jié)點或受到深度限制）時,

才從當前節(jié)點返回到上一級節(jié)點，沿另一方向又繼續(xù)前進。這種方法的搜索樹是從樹根開始

一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮

分枝，深度優(yōu)先搜索如果誤入無窮分枝（即深度無限），則不可能找到目標節(jié)點。所以，深度

優(yōu)先搜索策略是不完備的。另外，應(yīng)用此策略得到的解不一定是最佳解（最短路徑）。廣度

優(yōu)先搜索與深度優(yōu)先搜索都屬于盲目搜索。

16.是五大城市間的交通示意圖，邊上的數(shù)字是兩城

北京

市間的距離。用圖搜索技術(shù)編寫程序，求解以下問

題：

解：domainsp=string

d=integerpp=p*

predicatesroad（p,p,d）

path（p,p,pp,d）member（p,pp）

clauses

path（X,Y,L,D）:-road（X,Y,D）,L=[X|[Y]].昆明廣州

path（X,Y,L,D）：-

1!^€1（乂2,口1）,%從當前點向前走到下一點2

not(member(Z,L)),

path(Z,Y,[Z[L],D2),D=D1+D2.%再找Z到出口Y的路徑

member(X,[X|_1).

member(X,[_|T])ifmember(X,T),

road(A,B,D):-road(B,A,D).%因為沒向圖/*交通圖*/

road(“西安“，”北京”,1165).road(“西安”，“上?！?1511).

road(“西安”，“廣州”,2129).road(“西安"，"昆明”,1942).

road(“昆明"，“北京“，3179).road(“昆明”，“上?！?2677).

road(“昆明”，“廣州”，2216).road(“北京”/廣州”,2510).

road(“上海"，“北京”，1462).road(“廣州”，“上?！?1511).

(1)path(“西安”，“北京"，L,D),write(L,D).

(2)path(“西安”，"北京"，L,D),

member("上海"，L),write(L,D).

(3)path(“西安”了北京”,L,D),

member("上海"，L),not(member("昆明"，L)),write(L,D).

17.何謂估價函數(shù)？在估價函數(shù)中,g(x)和/2(x)各起什么作用？

答：估價函數(shù)用來估計節(jié)點重要性的函數(shù)。估價函數(shù)f(x)被定義為從初始節(jié)點S0出發(fā)，

約束經(jīng)過節(jié)點x到達目標節(jié)點Sg的所有路徑中最小路徑代價的估計值。它的一般形式為：

f(x)=g(x)+h(x)

其中，g(x)是從初始節(jié)點S0到節(jié)點x的實際代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路

徑的估計代價。

18.局部擇優(yōu)搜索與全局擇優(yōu)搜索的相同處與區(qū)別各是什么？

答：局部擇優(yōu)搜索與全局擇優(yōu)搜索的區(qū)別是，擴展節(jié)點N后僅對N的子節(jié)點按啟發(fā)函數(shù)

值大小以升序排序，再將它們依次放入OPEN表的首部。故算法從略。

19.傳教士和野人問題。有三個傳教士和三個野人一起來到河邊準備渡河，河邊有一條空船,

且傳教士和野人都會劃船，但每次最多可供兩人乘渡。河的任何?岸以及船上一旦出現(xiàn)野人

人數(shù)超過傳教士人數(shù)，野人就會把傳教士吃掉。為安全地渡河，傳教士應(yīng)如何規(guī)劃渡河方案？

試給出該問題的狀態(tài)圖表示，并用PROLOG語言編程求解之。

若傳教士和野人的數(shù)目均為五人，渡船至多可乘三人，請定義一個啟發(fā)函數(shù)，并給出相應(yīng)

的搜索樹。

解：首先選取描述問題狀態(tài)的方法。在這個問題中，需要考慮兩岸的修道士人數(shù)和野

人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個三元組來表示狀態(tài)：S=(m,c,b)其

中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。

右岸的狀態(tài)可由下式確定：右岸修道士數(shù)：m'=3-m：右岸野人數(shù)：c，=3-c；右岸船數(shù)：b'=l-b

在這種表示方式下,m和c都可取0、1、2、3中之一,b可取0和1中之一。因此，共有4x4x2=32

種狀態(tài)。這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義

的狀態(tài)只有16種：

So=(3,3,1)Si=(3,2,1)52=⑶1,1)Ss=(2,2,1)

=

Si(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)

Sk(3,2,0)Ss=(3,1,0)Sio—(3,0,0)Su-(2,2,0)

S12=(l,1,0)S13=(0,2,0)Sii=(0,1,0)S15=(0,0,0)

有了這些狀態(tài)，還需要考慮可進行的操作。

操作是指用船把修道士或野人從河的左岸運到右岸，或從河的右岸運到左岸。

每個操作都應(yīng)當滿足如下條件：

一是船至少有一個人（m或c）操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達岸邊

的m和c的增加數(shù)目；二是每次操作船上一人數(shù)不得超過2個；三是操作應(yīng)保證不產(chǎn)生非法

狀態(tài)。因此，操作應(yīng)由條件部分和動作部分：條件：只有當其條件具備時才能使用動作：

刻劃了應(yīng)用此操作所產(chǎn)生的結(jié)果。操作的表示：用符號也表示從左岸到右岸的運人操

作用符號Q”表示從右岸到左岸的操作其中：i表示船上的修道士人數(shù)j表示船上的

野人數(shù)

操作集

本問題有10種操作可供選擇：

F={Poi,Pio,PH,P02,P20,Q01,Qio,Q11,Q02,Q20}

下面以Pw和為例來說明這些操作的條件和動作。

操作符號條件動作

Poib=l,m=0或3,c21b=0,c=c-l

Q01b=0,m=0或3,

cW2b=l,c=c+lD(x)x是不清潔的20.設(shè)(1)凡

Ux.y)x喜歡y

事清潔的東西

E：Vx(-.LXy)->L(x.y))凡是清潔的東西就fi人喜歡

就有人喜歡E:Vx-L(x,a)人們都不喜歡蒼蠅

G:D(a)臼蒼蠅是不清潔的

（2）人們都不喜歡蒼蠅

用歸結(jié)原理證明蒼蠅(DD(x)vL(x.y)

(2)-.L(x,a)

是不清潔的(3)D(a)

⑷L(x,a)(1)(3)

(5)0(2)(4)

所以原命2S成立

21.八皇后問題：

答案:用八元組褥0不1不2,*314）5,*6,*7）表示第1?8行的棋子，值（x0,xl,x2,x3,x4,x5,x6,x7）

表示其在列上的位置。狀態(tài)可表示為八元組的一組值。

DOMAINS*

list=integer九

range(M,N,[M|Ns])：-M<N,Ml=M+l,range(Ml,N,Ns)..

PREDICATES-

強則N,N,【N}),

queens(integer,list)

3afej[Q|Qs])safe(Qs),not(attack(Q,1,Qs)).-

range(inteaer,integer,listh1

safe(list)?■

attack(X,N,[Y|])：-X=Y+N.-

attack(integer,integer,list)，

attack(X,N,[Y|])X=Y-N.-

permutation(list,list)

atUckfX,^[^lYs])：-Nl=N+lrattack(X,Nl,Ys).-

delete(integer,list.list)*

permutation([],[]).?

GOAV

permutation([A|X],Y)delete(ArYrYl),permutation(X,Y1)

queens(8rX),write(X)rnl,fail.-

delete(Ar[A|X]rX|

CLAUSES^

deletefA,[B|X]r[B|Y])delete(A,X,Y)

queens(NrQs)range(1,N,Ns)rpermutation(gs7Na),safe(Qs).1

專家系統(tǒng)：所謂專家系統(tǒng)，就是基于人類專家知識的程序系統(tǒng)。專家系統(tǒng)的特點是擁

有大量的專家知識（包括領(lǐng)域知識和經(jīng)驗知識），能模擬專家的思維方式，面對領(lǐng)域中復雜

的實際問題，能作出專家水平級的決策，像專家一樣解決實際問題。

專家系統(tǒng)的特征：1）處理問題的性質(zhì)：善于解決不確定、非結(jié)構(gòu)化、沒有算法解或雖有算法

解但在現(xiàn)有機器上無法實施的困難問題。2）處理問題方法：靠知識和推理來解決問題3系統(tǒng)

結(jié)構(gòu)：強調(diào)知識與推理的分離，系統(tǒng)具有很好的靈活性和可擴充性。4具有解釋功能：在運

行中能回答用戶提出的問題，同時還能對輸出(結(jié)論)或處理問題的過程作出解釋。5具有

“自學習”能力：即不斷對已有知識進行擴充、完善和提煉。6專家系統(tǒng)它始終如一地以專

家級水平求解問題。

各部分功能：1知識庫：以某種表示形式存儲于計算機中的知識集合。知識庫中的知識一般

包括專家知識、領(lǐng)域知識和元知識。2推理機：推理機就是實現(xiàn)機器推理的程序，包括通常

的邏輯推理和基于產(chǎn)生式的操作。3動態(tài)數(shù)據(jù)庫：是存放初始證據(jù)事實、推理結(jié)果和控制信

息的場所。4。人機界面：最終用戶與專家系統(tǒng)的交互界面5解釋模塊：專門負責向用

戶解釋專家系統(tǒng)的行為和結(jié)果。6知識庫管理系統(tǒng)：是知識庫的支撐軟件。其功能包括知

識庫的建立、刪除、重組；知識的獲取、知識的檢查等。

專家系統(tǒng)的應(yīng)用和發(fā)展情況：醫(yī)學診斷/地質(zhì)勘探/物質(zhì)結(jié)構(gòu)分析/生物遺傳研究/市場決策/

生產(chǎn)管理。20世紀90年代模糊技術(shù)、神經(jīng)網(wǎng)絡(luò)和面向?qū)ο蟮刃录夹g(shù)迅速崛起，為專家系統(tǒng)

注入了新的活力。

知識獲取：知識獲取是建造專家系統(tǒng)的關(guān)鍵一步，也是較為困難的一步，被稱為建造專家系

統(tǒng)的“瓶頸”。知識獲取大體有三種途徑。1人工獲?。杭从嬎銠C人員與領(lǐng)域?qū)＜液献?，?/p>

有關(guān)領(lǐng)域知識和專家知識，進行挖掘、搜集、分析、綜合、整理、歸納，然后以某種表示形

式存入知識庫。2半自動獲取，即利用某種專門的知識獲取系統(tǒng)，采取提示、指導或問答的

方式，幫助專家提取、歸納有關(guān)知識，并自動記入知識庫。3自動獲取又可分為兩種形式：

一種是系統(tǒng)本身具有一種機制，使得系統(tǒng)在運行過程中能不斷地總結(jié)經(jīng)驗，并修改和擴充自

己的知識庫；另一種是開發(fā)專門的機器學習系統(tǒng)，讓機器自動從實際問題中獲取知識，并填

充知識庫。

22.有兩個最優(yōu)解樹

左解樹：為最優(yōu)解右解樹

^9so

X

2t3?

t5

按和代價法，代價為：按和代價法，代階為：p

g(S0)=12,g(A)=7g(D)=4.g(S0)=18,g(B)=ll,g(E)=2.^

按最大代價法，代價為:按最大代價法，代價為：，

g(S0)=10,g(A)=5g(D)=2.g(S0)=14,g(B)=7,g(E)=2.<P

第2章知識表示方法部分參考答案

2.8設(shè)有如卜語句，請用相應(yīng)的謂詞公式分別把他們表示出來：s

(1)有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。

解：定義謂詞d

P(x):X是人

L(x,y)：x喜歡y

其中，y的個體域是｛梅花，菊花｝。

將知識用謂詞表示為：

(三x)(P(x)fL(x,梅花)\/L(x,菊花)VL(x,梅花)八L(x,菊花))

(2)有人每天下午都去打籃球。

解：定義謂詞

P(x)：X是人

B(x)：x打籃球

A(y)：y是下午

將知識用謂詞表示為：a

(3x)(Vy)(A(y)-*B(x)AP(x))

(3)新型計算機速度又快，存儲容量又大。

解：定義謂詞

NC(x)：x是新型計算機

F(x)：x速度快

B(x)：x容量大

將知識用謂詞表示為：

(Vx)(NC(x)-*F(x)AB(x))

(4)不是每個計算機系的學生都喜歡在計算機上編程序。

解：定義謂詞

S(x)：x是計算機系學生

L(x,pragramming)：x喜歡編程序

U(x,computer)：x使用計算機

將知識用謂詞表示為：

r(Vx)(S(x)-"L(x,pragramming)AU(x,computer))

(5)凡是喜歡編程序的人都喜歡計算機。

解：定義謂詞

P(x)：x是人

L(x,y)：x喜歡y

將知識用謂詞表示為：

(Vx)(P(x)八L(x,pragramming)-"L(x,computer))

2.9用謂詞表示法求解機器人摞積木問題。設(shè)機器人有一只機械手，要處理的世界有，?

張桌子，桌上可堆放若干相同的方積木塊。機械手有4個操作積木的典型動作：從桌上揀起

一塊積木；將手中的積木放到桌之上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。

積木世界的布局如下圖所示。

A

圖機器人摞積木問題

解：(1)先定義描述狀態(tài)的謂詞

CLEAR(x)：積木x上面是空的。

ON(x,y)：枳木x在積木y的上面。

ONTABLE(x)：積木x在桌子上。

HOLDING(x)：機械手抓住X。

HANDEMPTY：機械手是空的。

其中，x和y的個體域都是｛A,B,C｝。

問題的初始狀態(tài)是：

ONTABLE(A)

ONTABLE(B)

ON(C,A)

CLEAR(B)

CLE