第2章人工智能原理及其應用》王萬森編著電子工業

出版社課后習題答案37

2.8設有如下語句，請用用應的謂詞公式分別把他們表示出來：

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

解：定義謂詞

P(x)：x是人

L(x,y)：x喜歡y

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

將知識用謂詞表示為：

(3x)(P(x)-*L(x,梅花)VL(x,菊花)VL(x,梅花)八L(x,菊花))

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

解：定義謂詞

P(x)：X是人

B(x)：x打籃球

A(y)：y是下午

將知識用謂詞表示為：

(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使用計算機

將知識用謂詞表示為：

「(Vx)(S(x)-*L(x,pragramming)AU(x,computer))

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

解：定義謂詞

P(x)：x是人

L(x,y)：x喜歡y

將知識用謂詞表示為：

(Vx)(P(x)AL(x,pragramming)L(x,computer))

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

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

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

世界的布局如下圖所示。

圖機器人摞積木問題

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

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

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

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

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

HANDEMPTY：機械手是空的。

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

問題的初始狀態是：

ONTABLE(A)

ONTABLE(B)

ON(C,A)

CLEAR(B)

CLEAR(C)

HANDEMPTY

問題的目標狀態是：

ONTABLE(C)

ON(B,C)

ON(A,B)

CLEAR(A)

HANDEMPTY

(2)再定義描述操作的謂詞

在本問題中，機械手的操作需要定義下列4個謂詞：

Pickup(x)：從桌面上揀起一塊積木x。

Putdown(x)：將手中的積木放到桌面上。

Stack(x,y)：在積木x上面再摞上一塊枳木y。

Upstack(x,y)：從積木x卜而揀起一塊積木y?

其中，每一個操作都可分為條件與動作兩部分，具體描述如下:

Pickup(x)

條件：ONTABLE(x),HANDEMPTY,CLEAR(x)

動作：冊IJ除表：ONTABLE(x),HANDEMPTY

添加表：HANDEMPTY(x)

Putdown(x)

條件：HANDEMPTY(x)

動作：刪除表：HANDEMPTY(x)

添力口表：ONTABLE(x),CLEAR(x),HANDEMPTY

Stack(x,y)

條件：HANDEMPTY(x),CLEAR(y)

動作：刪除表：HANDEMPTY(x),CLEAR(y)

添加表：HANDEMPTY,ON(x,y),CLEAR(x)

Upstack(x,y)

條件：HANDEMPTY,CLEAR(y),ON(y,x)

動作：刪除表：HANDEMPTY,ON(y,x)

添加表：HOLDING(y),CLEAR(x)

(3)問題求解過程

利用上述謂詞與操作，其求解過程為：

ONTABLE(A)

ONTABLE(A)ONTABLE(A)ONTABLE(B)

ONTABLE(B)

Upstack(A,C)ONTABLE(B)putdo\vn(C)ONTABLE(C)Pickup(B)

ON(C,A)1——>HOLDING(C)<=

CLHAR(A)1-----------c

CLEAR(B)CLEAR(A)

CLEAR(B)

CLEAR(C)CLEAR(B)

CLEAR(C)

HANDEMPTYCLEAR(C)

HANDEMPTY

ONTABLE(A)ONTABLE(A)

ONTABLE(C)ONTABLE(C)

ONTABLE(C)ONTABLE(C)

Stack(C,B)Pickup(A)ON(B,C)tack(B,A)ON(B,C)

HOLDING(B)ON(B,C)S

^^CLEARCA),0ON(A,B)

CLEAR(A)CLEAR(A)

CLEAR(B)CLEAR(A)

CLEAR(B)CLEAR(B)HANDEMPT

HOLDING(A)

CLEAR(C)HANDEMPT

2.10用謂詞表示法求解農夫、狼、山羊、白菜問題。農夫、狼、山羊、白菜全部放在一條

河的左岸，現在要把他們全部送到河的右岸去，農夫有一條船，過河時，除農夫外船上至多能

載狼、山羊、白菜中的一種。狼要吃山羊，山羊要吃白菜，除非農夫在那里。似規劃出一個確

保全部安全過河的計劃。請寫出所用謂詞的定義，并給出每個謂詞的功能及變量的個體域。

L-R（白菜）：農夫帶著白菜劃船從左岸到右岸

條件:AL（船），AL（農夫），AL（白菜）,「AL（狼）

動作：刪除表：AL（船），AL（農夫），AL（白菜）

添加表：」AL（船），「AL（農夫），「AL（白菜）

R-L：農夫劃船從右岸到左岸

條件：「AL（船），「AL（農夫），AL（狼）VAL（羊），AL（羊）VAL（白菜）

或者：「AL（船），「AL（農夫）,「AL（狼），「AL（白菜），AL（羊）

動作：刪除表：」AL（船），「AL儂夫）

添加表：AL（船），AL（農夫）

R-L（羊）：農夫帶著羊劃船從右岸到左岸

條件：[AL（船）,「AL（農夫），「AL（羊）,「AL（狼），「AL佯）,AL（白菜）

動作：刪除表：」AL（船），「AL（農夫），「AL（羊）

添加表：AL（船），AL（農夫），AL（羊）

（3）問題求解過程

墨鰲）AL（狼）AL（農夫）AL（白菜）

”（JL-R（羊）AL（白菜）R_LAL（船）L-R（狼）「AL（農夫）（羊）

AL（狠）]AL（農夫）|-------fAL（狼）?F「AI/M-------F

AL（1L（船）AL（白菜）「AL（狼）

AL（白菜）皿（羊）「AL（羊）”L（羊）

AL（農夫）AL（羊）AL（農夫）"L儂夫1

AL（船）L-R（白菜）”L（農夫）RIAL（船）L-R（羊）“L（即）

AL（中）1「AL（船）》AL（羊）1---------「AL（羊）

AL（白菜）「AL（白菜）「AL（白菜）“L（白菜）

「AL（狼）「AL（狼）「AL（狼）「AL（狼）

2.11用謂詞表示法求解修道士與野人問題。在河的北岸有三個修道士、三個野人與一條船,

修道士們想用這條船將所有的人都運過河去，但要受到下列條件限制：

（1）修道士與野人都會劃船，但船一次只能裝運兩個人。

（2）在任何岸邊，野人數不能超過修道士，否則修道士會被野人吃掉。

假定野人愿意服從任何一種過河安排，請規劃出一種確保修道士安全的過河方案。要求寫

出所用謂詞的定義、功能及變量的個體域。

解：（1）定義謂詞

先定義修道士與野人人數關系的謂詞：

G（x,y,S）：在狀態S下x大于y

GE（x,y,S）：在狀態S下x大于或者等于y

其中，x,y分別代表修道士人數與野人數，他們的個體域均為｛0,123｝。

再定義船所在岸的謂詞與修道士不在該岸上的謂詞：

Boat（z,S）：狀態S下船在z岸

EZ（x,S）：狀態S卜x等于（），即修道士不在該岸上

其中,z的個體域是{L,R},L表示左岸，R表示右岸c

再定義安全性謂詞：

Safety(z,x,y,S)三(G(x,O,S)AGE(x,y,S))V(EZ(x,S))

其中，z,x,y的含義同上。該謂詞的含義是：狀態S下，在z岸，保證修道士安全，當且僅當修

道士不在該岸上，或者者修道士在該岸上，但人數超過野人數。該謂詞同時也描述了相應的狀

態。

再定義描述過河方案的謂詞：

L-R(x,xl,y,yl,S)：xl個修道士與yl個野人渡船從河的左岸到河的右岸

條件:Safely(L,x-x1,y-y1,5')ASalely(R,3-x+x1,3-y+y1,S')ABoal(L,S)

動作:Safety(L,x-xI,y-y1,S')ASafety(R,3-x+x1,3-y+y1,S')八Boat(R,S,)

R-L(x,xl,y,yl,S)：x2個修道士與y2個野人渡船從河的左岸到河的右岸

條件：Safety(R,3-x-x2,3-y-y2,S5)ASafety(L,x+x2,y+y2,S*)ABoat(R,S)

動作：Safety(R,3-x-x2,3-y-y2,S')ASafety(L,x+x2,y+y2,S')ABoat(L,S')

(2)過河方案

Safety(L,3,3,S0)ASafety(R,0,0,SQ^ABoat(L,S0)

jL-R(3,1,3J,S0)JL-R(3,0,3,2,SO)

Safety(L,2,2,S1)ASafety(R,l,l,Sl)ABoat(R,S

Safety(L,3,I,S1')/\Safety(R,(),2,S1')八Boat(R,S1')

R-L(2,1,2,0,S1)1,S1')

Safety(L,3,2,S2)ASafety(R,0,1,S2)ABoat(L,S2)

1L-R(3,0,2,2,S2)

Safety(L,3,0,S3)ASafcty(R,0,3,S3)ABoat(R,S3)

-R-L(3,(),0,i,S3)

Safety(L,3,l,S4)ASafety(R,0,2,S1)ABoat(L,S4)

IL?R(3,2,1,0,S4)

Safety(L,l,LS5)ASafety(R,2,2,S5)ABoat(R,S5)

R-L(1,1,1,1,S5)

Safety(_22s6)ASafety(R,1,1,S6)ABoat(L,S6)

1L-R(2,2,2,(),S6)

Safety(L,0,2,S7)ASafety(R,3J,S7)ABoat(R,S7)

R-L(0,0,2,1,S7)

Safety(L,0,3,S8)ASafcty(R,3,0,S8)ABoat(L,S8)

L-R(0,0,3,2,S8)

Safety(L,0J,S9)ASafety(R,3,2,S9)ABoat(R,S9)

R-L(0,1,1,0,S9)

Safety(L,l,l,S10)ASafety(R,22s10)ABoat(L,S10)

L-R(1JJJ,S1O)

Safety(L,O,O,Sl1)ASatety(R,3,3,Sl1)ABoat(R,Sll)

2.18請對下列命題分別寫出它們的語義網絡:

(1)每個學生都有一臺計算機。

解：

(2)高老師從3月到7月給計算機系學生講《計算機網絡》課。

解：

(3)學習班的學員有男、有女、有研究生、有本科生。

解：參例2.14

(4)創新公司在科海大街56號，劉洋是該公司的經理，他32歲、碩士學位。

解：參例2.10

(5)紅隊與藍隊進行足球比賽，最后以3；2的比分結束。

解：

2.19請把下列命題用一個語義網絡表示出來:

(1)樹與草都是植物；

解.

(3)水草是草，且生長在水中;

解：

(4)果樹是樹，且會結果;

解：

(5)梨樹是果樹中的一種，它會結梨。

解；

2.25假設有下列一段天氣預報：“北京地區今天白天晴，偏北風3級，最高氣溫12°,最

低氣溫-2。，降水概率15機”請用框架表示這一知識。

解：

Frame〈天氣預報》

地域：北京

時段：今天白天

天氣：晴

風向：偏北

風力：3級

氣溫：最高：12度

最低：-2度

降水概率：15%

2.26按“師生框架”、“教師框架”、“學生框架”的形式寫出一個框架系統的描述。

解：師生框架

Frame<Teachers-Students>

Name：Unit(Last-name,First-name)

Sex：Area(male,female)

Default：male

Age：Unit(Years)

Telephone：HomeUnit(Number)

MobileUnit(Number)

教師框架

Frame<Teachers>

AKO<Teachers-Students>

Major：Unit(Major-Name)

Lectures：Unit(Course-Name)

Field：Unit(Field-Name)

Project：Area(National,Provincial,Other)

Default：Provincial

Paper：Area(SCLELCore,General)

Default：Core

學生框架

Frame<Students>

AKO<Teachers-Students>

Major：Unit(Major-Name)

Classes：Unit(Classes-Name)

Degree：Area(doctor,master,bachelor)

Default：bachelor

第3章確定性推理部分參考答案

3.8推斷下列公式是否為可合一，若可合一，則求出其最通常合一。

(I)P(a,b),P(x,y)

(2)P(f(x),b),P(y,z)

(3)P(f(x),y),P(y,f(b))

(4)P(f(y),y,x),P(x,f(a),f(b))

(5)P(x,y),P(y,x)

解：(1)可合一，其最通常與一為：。={a/x,b/y}。

(2)可合一，其最通常與一為：。={y/f(x),b/z}。

(3)可合一，其最通常與一為：。={f(b)/y,b/x}。

(4)不可合一。

(5)可合一，其最通常與一為：。={y/x}。

3.11把下列謂詞公式化成子句集：

(1)(Vx)(Vy)(P(x,y)AQ(x,y))

(2)(Vx)(Vy)(P(x,y)fQ(x,y))

(3)(Vx)(3y)(P(x,y)V(Q(x,y)-R(x,y)))

(4)(Vx)(Vy)(3z)(P(x,y)fQ(x,y)VR(x,z))

解：(1)由于(鼠x)(Vy)(P(x,y)八Q(x,y))已經是Skolem標準型,且P(x,y)/\Q(x,y)已經是

合取范式，因此可直接消去全稱量詞、合取詞，得

{P(x,y),Q(x,y)}

再進行變元換名得子句集：

S={P(x,y),Q(u,v))

(2)對謂詞公式(Vx)(Vy)(P(x,y)fQ(x,y)),先消去連接詞“一”得：

(Vx)(Vy)「P(x,y)VQ(x,y))

此公式已為Skolem標準型。

再消去全稱量詞得子句集：

S={^P(x,y)VQ(x,y)}

(3)對謂詞公式(Vx)Ty)(P(x,y)V(Q(x,y)fR(x,y))),先消去連接詞"f”得：

(Vx)(3y)(P(x,y)V(p(x,y)VR(x,y)))

此公式已為前束范式。

再消去存在量詞，即用Skolem函數f(x)替換y得：

(Vx)(P(x,f(x))V-Q(x,f(x))VR(x,f(x)))

此公式已為Skolem標準型。

最后消夫全稱量詞得子句集：

S={P(x,f(x))V-Q(x,f(x))VR(x,f(x))}

(4)對謂詞(Vx)(X/y)(mz)(P(x,y)fQ(x,y)VR(x,z)),先消去連接詞“一”得:

(Vx)(Vy)(3Z)「P(K,y)VQ(x,y)VR(x,z))

再消去存在量詞，即用Skolem函數f(x)替換y得：

(Vx)(Vy)(-P(x,y)VQ(x,y)VR(x,f(x,y)))

此公式已為Skolem標準型。

最后消去全稱量詞得子句集：

S=(-1P(x,y)VQ(x,y)VR(x,f(x,y)))

3-13推斷下列子句集中什么是不可滿足的：

(1){-PVQ,-Q,P「P}

(2){PVQ,「PVQ,PV-Q^PV-Q)

0){P(y)VQ(y),-P(f(x))VR(a))

(4)-P(x)VQ(x),「P(y)VR(y),P(a),S(a),「S(z)V「R⑵}

(5){-P(x)VQ(f(x),a),「P(h(y))VQ(f(h(y)),a)V[P(z)}

(6){P(x)VQ(x)VR(x),-P(y)VR(y),-Q(a),-R(b)}

解：(1)不可滿足，其歸結過程為：

「PVQp

NIL

(2)不可滿足，其歸結過程為：

(3)不是不可滿足的，原因是不能由它導出空子句。

(4)不可滿足，其歸結過程略

(5)不是不可滿足的，原因是不能由它導出空子句。

(6)不可滿足，其歸結過程略

3.14對卜列各題分別證明G是否為B,F2,…,Fn的邏輯結論:

(1)F：(AxX^lyXPCx,y)

G:(Vy)(3x)(P(x,y)

(2)F:(Vx)(P(x)A(Q(a)VQ(b)))

G:(3x)(P(x)AQ(x))

(3)F：(3x)(3y)(P(f(x))A(Q(f(y)))

G:P(f(a))AP(y)AQ(y)

(4)Fi：(Vx)(P(x)f(Vy)(Q(y)f「L(x.y)))

F2：(3x)(P(x)A(Vy)(R(y)fL(x.y)))

G:(Vx)(R(x)-)Q(x))

(5)Fi：(Vx)(P(x)->(Q(x)AR(x)))

F2:(3X)(P(X)AS(X))

G:(3x)(S(x)AR(x))

解：(1)先將F與-G化成子句集：

S={P(a,b),「P(x,b)}

再對S進行歸結：

因此，G是F的邏根結論

(2)先將F與P化成子句集

由F得:Si={P(x),(Q(a)VQ(b))}

由于P為：-(3x)(P(x)AQ(x)),即

(Vx)rP(x)V-Q(x)),

可得：S2={「P(X)V「Q(X)}

因此，擴充的子句集為：

S={P(x),(Q(a)VQ(b)),「P(x)V「Q(x)}

再對S進行歸結：

因此.G是F的邏輯結論

同理可求得(3)、(4)與(5),其求解過程略。

3.15設己知：

(1)假如x是y的父親，y是z的父親，則x是z的祖父；

(2)每個人都有一個父親。

使用歸結演繹推理證明：關于某人u,一定存在一個人v,v是u的祖父。

解：先定義謂詞

F(x,y):x是y的父親

GF(x,z)：x是z的祖父

P(x)：X是一個人

再用謂詞把問題描述出來：

己知Fl：(Vx)(Vy)(Vz)(F(x,y)AF(y,z))-*GF(x,z))

F2：(Vy)(P(x)-*F(x,y))

求證結論G：(3u)(3v)(P(u)->GF(v,u))

然后再將Fl,F2與-G化成子句集：

①「F(x,y)V「F(y,z)VGF(x,z)

②fP(r)VF(s,r)

③P(u)

④-GF(v,u))

對上述擴充的子句集，其歸結推理過程如下:

3.16假設張被盜，公安局派出5個人去調食。案情分析時，貞察員A說：“趙與錢中至

少有一個人作案”,貞察員B說：“錢與孫中至少有一個人作案”，貞察員C說：“孫與李中至少

有一個人作案”，貞察員D說：“趙與孫中至少有一個人與此案無關”，貞察員E說：“錢與李中

至少有一個人與此案無關二假如這5個偵察員的話都是可信的，使用歸結演繹推理求出誰是盜

竊犯。

解：(1)先定義謂詞與常量

設C(x)表示x作案，Z表示趙，Q表示錢，S表示孫，L表示李

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

趙與錢中至少有一個人作案：C(Z)VC(Q)

錢與孫中至少有一個人作案：C(Q)VC(S)

孫與李中至少有一個人作案：C(S)VC(L)

趙與孫中至少有一個人與此案無關：「(C(Z)八C(S)),即-c(Z)v-c(s)

錢與李中至少有一個人與此案無關：「(C(Q)八C(L)),即-C(Q)V-C(L)

(3)將所要求的問題用謂詞公式表示出來，并與其否定取析取。

設作案者為u,則要求的結論是C(u)。將其與其否)取析取，得：

「C(u)VC(u)

(4)對上述擴充的子句集，按歸結原理進行歸結，其修改的證明樹如下：

因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據歸結原理還能夠得出:

因此，孫也是盜竊犯。

3.18設有子句集：

{P(x)VQ(a,b),P(a)V-1Q(a,b),Q(a,f(a)),-1P(x)VQ(x,b)}

分別用各類歸結策略求出其歸結式。

解：支持集策略不可用，原因是沒有指明哪個子句是由目標公式的否定化簡來的。

刪除策略不可用，原因是子句集中沒是否具有重言式與具有包孕關系的子句。

單文字子句策略的歸結過程如下：

用線性輸入策略(同時滿足祖先過濾策略)的歸結過程如下:

3.19設已知：

(1)能閱讀的人是識字的；

(2)海豚不識字；

(3)有些海豚是很聰明的。

請用歸結演繹推理證明：有些很聰明的人并不識字。

解:第一步,先定義謂詞,

設R(x)表示x是能閱讀的:

K(y)表示y是識字的；

W⑵表示z是很聰明的；

第二步，將己知事實與目標用謂詞公式表示出來

能閱讀的人是識字的：(Vx)(R(x))-*K(x))

海豚不識字：(Vy)(-K(y))

有些海豚是很聰明的；(mz)W(z)

有些很聰明的人并不識字：(Bx)(W(z)八」K(x))

笫三步，將上述已知事實與目標的否定化成子句集：

-R(x))VK(x)

(y)

W⑵

「W(z)VK(x))

第四步，用歸結演繹推理進行證明

3.20對子句集：

{PVQ,QVR,RVW,「RViP,「WViQ,「QV-iR}

用線性輸入策略是否可證明該子句集的不可滿足性？

解：用線性輸入策略不能證明子句集

{PVQ,QVR,RVW,「RV-.P,」WV「Q「QV^R}

的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結過程。

3.21對線性輸入策略與單文字子句策略分別給出一個反例，以說明它們是不完備的。

3.22分別說明正向、逆向、雙向與/或者形演繹推理的基本思想。

3.23設已知事實為

((PVQ)AR)V(SA(TVU))

F規則為

S-*(XAY)VZ

試用正向演繹推理推出所有可能的子目標。

解：先給出已知事實的與/或者樹，再利用F規則進行推理，其規則演繹系統如下圖所示。

由該圖能夠直接寫出所有可能的目標子句如K：

PVQVTVU

PVQVXVZ

PVQVYVZ

RVTVU

RVXVZ

RVYVZ

3.24設有如下一段知識：

”張、王與李都屬于高山協會。該協會的每個成員不是滑雪運動員，就是登山運動員，其

中不喜歡雨的運動員是登山運動員，不喜歡雪的運動員不是滑雪運動員。王不喜歡張所喜歡的

一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨與雪

試用謂詞公式集合表示這段知識，這些謂詞公式要適合一個逆向的基于規則的演繹系統。

試說明這樣一個系統如何才能回答問題：

“高山俱樂部中是否具有一個成員，他是一個登山運動員，但不是一個滑雪運動員？”

解：(1)先定義謂詞

A(x)表示x是高山協會會員

S(x)表示x是滑雪運動員

C(x)表示x是登山運動員

L(x,y)表示x喜歡y

(2)將問題用謂詞表示出來

“張、王與李都屬于高山協會

A(Zhang)AA(Wang)AA(Li)

高山協會的每個成員不是滑雪運動員，就是登山運動員

(Vx)(A(x)A-,S(x)->C(x))

高山協會中不喜歡雨的運動員是登山運動員

(Vx)「L(x,Rain)-C(x))

高山協會中不喜歡雪的運動員不是滑雪運動員

(Vx)(「L(x,Snow)-*-1S(x))

王不喜歡張所喜歡的一切東西

(Vy)(L(Zhang,y)f「L(Wang,y))

王喜歡張所不喜歡的一切東西

(Vy)(「L(Zhang,y)-*L(Wang,y))

張喜歡雨與雪

L(Zhang,Rain)AL(Zhang,Snow)

(3)將問題要求的答案用謂詞表示出來

高山俱樂部中是否具有一個成員，他是一個登山運動員，但不是一個滑雪運動員？

(3x)(A(x)-C(x)A-S(x))

(4)為了進行推理，把問題劃分為己知事實與規則兩大部分。假設，劃分如下：

己知事實：

A(Zhang)AA(Wang)AA(Li)

L(Zhang,Rain)AL(Zhang,Snow)

規則：

(Vx)(A(x)A-S(x)-*C(x))

(Vx)(「L(x,Rain)->C(x))

(Vx)「L(x,Snow)-「S(x))

(Vy)(L(Zhang,y)->「L(Wang,y))

(Vy)rL(Zhang,y)-*L(Wang,y))

(5)把己知事實、規則與目標化成推理所需要的形式

事實已經是文字的合取形式；

fi：A億hang)AA(Wang)AA(Li)

L：L(Zhang,Rain)AL(Zhang,Snow)

將規則轉化為后件為單文字的形式：

口：A(x)八「S(x)fC(x))

「2：「L(x,Rain)->C(x)

口:-L(x,Snow)->-'S(x)

n：L(Zhang,y)f「L(Wang,y)

「5：「L(Zhang,y)-*L(Wang,y)

將目標公式轉換為與/或者形式

-A(x)V(C(x)A-1S(x))

(6)進行逆向推理

逆向推理的關鍵是要能夠推出L(Zhang,Rain)AL(Zhang,Snow),其逆向演繹過程如下圖

所示。

第4章搜索策略部分參考答案

4.5有一農夫帶一條狼，一只羊與一框青菜與從河的左岸乘船倒右岸，但受到下列條件的

限制：

(1)船太小，農夫每次只能帶一樣東西過河；

(2)假如沒有農夫看管，則狼要吃羊，羊要吃菜。

請設計一個過河方案，使得農夫、浪、羊都能不受缺失的過河，畫出相應的狀態空間圖。

題示：(1)用四元組(農夫，狼，羊，菜)表示狀態，其中每個元素都為()或者1,用()

表示在左岸，用1表示在右岸。

(2)把每次過河的一種安排作為一種操作，每次過河都務必有農夫，由于只有他能夠劃船。

解：第一步，定義問題的描述形式

用四元組S=(f,w,s,v)表示問題狀態，其中，f,w,s與v分別表示農夫，狼，羊與

青菜是否在左岸，它們都能夠取1或者0,取1表示在左岸，取0表示在右岸。

第二步，用所定義的問題狀態表示方式，把所有可能的問題狀態表示出來，包含問題的初

始狀態與目標狀態。

由于狀態變量有4個，每個狀態變量都有2種取值，因此有下列16種可能的狀態：

So二(l』,l,l),S|=(1,1J,O),S2=(l,l,o,l)，s3=(l,1,0,0)

S4=(l,0,1,1)，S5=(l,0,l,0),S6=(l,0,0,1),S7=(l,0,0,0)

S8=(0,l,l,l),S9=(0,l,l,0),Sio=(O,l,O,l)，S||=((),1,0,0)

Si2=(0,0,1,1)，Si3=(0,0,1,0),Si4=(0A0J),S15=(0,0,0.0)

其中，狀態S3，S6，S7，S8，S9,S12是不合法狀態，So與Si5分別是初始狀態與目標狀態。

第三步，定義操作，即用于狀態變換的算符組F

由于每次過河船上都務必有農夫，且除農夫外船上只能載狼，羊與菜中的i種，故算符定

義如下：

L(i)表示農夫從左岸將第i樣東西送到右岸(i=1表示狼，i=2表示羊，i=3表示菜，i=0表

示船上除農夫外不教任何東西)。由于農夫務必在船上，故對農夫的表示省略。

R(i)表示農夫從右岸將第i樣東西帶到左岸(i二l表示狼，i=2表示羊，i=3表示菜，i=0表

示船上除農夫外不載任何東西)。同樣，對農夫的表示省略。

這樣，所定義的算符組F能夠有下列8種算符：

L(0),L(l),L(2),L(3)

R(0),R(l),R(2),R(3)

第四步，根據上述定義的狀態與操作進行求解。

該問題求解過程的狀態空間圖如下：

(1,1,U)

L⑵I

(0,1,0,1)

R(o)I

(U,o,l)

HI)/\L(3)

(0,0,0,1)(OJ,0,0)

R(2)1JR⑵

(1,0,1,0)

L(2)|

(0,0,0,0)

4.7圓盤問題。設有大小不等的三個圓盤A、B、C套在一根軸上，每個盤上都標有數字1、

2、3、4,同時每個圓盤都能夠獨立的繞軸做逆時針轉動，每次轉動90°,其初始狀態So與目

標狀態又如圖4-31所示，請用廣度優先搜索與深度優先搜索，求出從So到Sg的路徑。

初始狀態so目標狀態Sg

圖4-31圓盤問題

解：設用qA，qB與qc分別表示把A盤，B盤與C盤繞軸逆時針轉動90°,這些操作（算

符）的排列順序是C]A，qB，qco

應用廣度優先搜索.可得到如下搜索樹.在該搜索樹中?重復出現的狀態不再劃出,節點

旁邊的標識Si，i=0,l,2,…，為按節點被擴展的順序給出的該節點的狀態標識。

由該圖能夠看出，從初始狀態So到目標狀態Sg的路徑是

So-*2-*5-*13(Sg)

2

A2事

4

4

4

22

2

34

4

43.

3

44

qB

22"~^\S5.S6

2

2

1

3IH34qc

444

2

4

qc4

2

2、

12即Sg

2I

4

222

4

3

3

4

4.7題的廣度優先搜索機

其深度優先搜索略。

4.8圖4-32是5個城市的交通圖，城市之間的連線旁邊的數字是城市之間路程的費用。要

求從A城出發，通過其它各城市一次且僅一次，最后回到A城，請找出一條最優線路。

解：這個問題又稱之旅行商問題(travellingsalesman

problem,TSP)或者貨郎擔問題，是一個較有普遍性的

實際應用問題。根據數學理論，對n個城市的旅行商問

題，其封閉路徑的排列總數為：

(n!)/n=(n-l)!

其計算量相當大。比如，當n=20時，要窮舉其所有路

徑，即使用一個每秒一億次的計算機來算也需要350年

的時間。因此，對這類問題只能用搜索的方法來解決。

下圖是對圖4-32按最小代價搜索所得到的搜索樹，樹中的節點為城市名稱，節點邊上的數

字為該節點的代價g。其計算公式為

g(ni+i)=g(ni)+c(ni,%+i)

其中，cgiii+i)為節點m到m+i節點的邊代價。

9-

8

BO2E

/C1

/I-A八

zM_A

3/9/-T

,6698

96J8

I—2(+L

A—r

9Vqvt

C1c22l6DB.J

EBII.

v^—20C25

-—IBtIVJ

26D25172d24|

14C20E26

899I

—12

--I66

III6?%-3

VVV6I

—>

98V

D‘

EDE26B26

3127l28,—

B34

2723C32

E30c350C28EB2（）E28

210

A30A30

圖4.32的最小代價搜索樹

能夠看出，其最短路經是

ACDEBA

或者

A-B-E-D-C-A

事實上，它們是同一條路經。

4.11設有如下結構的移動將牌游戲:

BWWE

其中，B表示黑色將牌，W表是白色將牌，E表示空格。游戲的規定走法是:

(1)仟意一個將牌可移入相鄰的空格，規定其代價為1:

(2)任何一個將牌可相隔1個其它的將牌跳入空格，其代價為跳過將牌的數目加lo

游戲要達到的目標什是把所有W都移到B的左邊。對這個問題，請定義一個啟發函數h(n),

并給出用這個啟發函數產生的搜索樹。你能否判別這個啟發函數是否滿足下解要求？再求出的

搜索樹中，對所有節點是否滿足單調限制？

解：設h(x)=每個W左邊的B的個數，f(x)=d(x)+3*h(x),其搜索樹如下：

f（x）=l+12=13

f（x）=6+3=9

BWEB

f（x）=7+O=7

WBWEB

4.14設有如圖4-34的與/或者/樹，請分別按與代價法及最大代價法求解樹的代價。

圖4.34習題4.14的與/或者樹

解：若按與代價法，則該解樹的代價為：

h(A)=2+3+2+5+2+1+6=21

若按最大代價法，則該解樹的代價為：

h(A)=max{h(B)+5,h(C)+6)=max{(h(E)+2)+5,h(C)+6)

=max{(max(2,3)+2)+5,max(2,1)+6}

=max((5+5,2-6)=10

4.15設有如圖4-35所示的博弈樹，其中最下面的數字是假設的估值，請對該博弈樹作如

F工作：

(1)計算各節點的倒推值；

(2)利用a-B剪枝技術剪去不必耍的分枝。

解：各節點的倒推值與剪枝情況如下圖所示:

>4So

A

<0B

<4

>3D>4E

<3<4

<-3

36-2354-3

習題4.15的倒推值與剪枝情況

第5章計算智能部分參考答案

5.15對遺傳法的選擇操作：設種群規模為4,個體使用二進制編碼，習慣度函數為

初始種群情況如下表所示：

編號個體串X習慣值百分比累計百分比選中次數

Soi101010

S0201004

S03110012

S()401117

若規定選擇概率為100%,選擇算法為輪盤賭算法,且依次生成的4個隨機數為0.42,0.16,0.89,

0.71,請填寫上表中的全部內容，并求出經本次選擇操作后所得到的新的種群。

解，表格的完整內容為:

編號個體串X習慣值百分比累計百分比選中次數

Soi10101010032.3632.361

S0201004165.1837.540

So311001214444.6084.142

S04011174915.861001

本次選擇后所得到的新的種群為:

Soi=1100

S()2=1010

S03=0111

So4=l100

5.18設某小組有5個同學，分別為Si,S2,S3,S4,S5。若對每個同學的“學習好”程度打分:

Si：95S2：85S3:80S4：70S5：90

這樣就確定了一個模糊集F,它表示該小組同學對“學習好”這一模糊概念的隸屬程度，請寫

出該模糊集。

解：對模糊集為F,可表示為：

F=95/SI+85/S2+80/S3+7O/S4+9O/S5

或者

F={95/Sh85/S2,80/S3,70/S4,90/S5}

5.19設有論域

U={U1,U2,U3,U4,U5)

并設F、G是U上的兩個模糊集，且有

F=0.9/ui+O.7/U2+O.5/U3+O.3/U4

G=0.6/U3+0.8/IU+1/U5

請分別計算FAG,FUG,「F。

解：FnG=(0.9A0)/ui+(().7A0)/U2+(O.5AO.6)/U3+(O.3A0.8)/U4+(0A1)/U5

=0/ui+0/U2+O.5/U3+O.3/U4+O/U5

=0.5/U3+0.3/U4

FUG=(0.9V0)/ui+(0.7V0)/u2+(0.5V0.6)/u3+(0.3V0.8)/u4+(0Vl)/u5