人工智能基础及应用 习题及参考答案 周军

人工智能教材习题参考答案

目录

第1章习题参考答案..........................................................2

第2章习题参考答案..........................................................2

第3章习题参考答案.........................................................10

第4章习题参考答案........................................................14

第5章习题参考答案.........................................................16

第6章习题参考答案.........................................................29

第7章习题参考答案.........................................................31

第8章习题参考答案.........................................................42

第9章习题参考答案.........................................................48

第10章习题参考答案........................................................50

第11章习题参考答案........................................................51

1

第1章习题参考答案

1、简述衡量机器智能的图灵准则。

衡量智能机器的准则虽然多有争论，但“图灵测试”却是影响最大的i个方法，看机器能

否通过“图灵测试

2、人工智能研究的主要内容有哪些？

人工智能的主要研究内容至少应包括：机器感知、机器思维、机器学习、机器行为、智

能系统及其构造技术。

3、人工智能的主要研究领域有哪些？

主要研究领域有：问题求解.、机器学习、专家系统、自然语言理解、自动定理证明、自

动程序设计、机器人学、神经网络，还有机器视觉、模式派别、智能决策支持、人工生命等。

4、请通过查阅资料了解“深蓝”计算机的相关内容及其在人工智能发展史上的影响。

这是一个开放的问题，目的是让读者了解人工智能历史上的大事。解答这个问题时，首

先要搜索关于“深蓝”的相关资料，回答它是什么，有什么用等问题，进而总结它在人工智

能发展史上的影响。

5、调研最近一年国家关于“人工智能”的相关规划、政策或相关的新闻，同时，谈谈你的感

想。

略

第2章习题参考答案

1、设有如下语句，请用相应的谓词公式分别把他们表示出来：

（1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。

解：定义谓词d

P（x）:X是人

L（x,y）：x喜欢y

其中，y的个体域是「梅花，菊花）。

将知识用谓词表示为：

（3x）（P（x）-*L（x,梅花）VL（x,菊花）VL（x,梅花）/\L（x,菊花））

（2）西安市的夏天既干燥又炎热。

2

解：设XrANSUMMER(x)：x是西安市的夏天

DRY(x)：x是干燥的

HOT(x)：x是炎热的,

(Vx)(XrANSUMMER(x)->DRY(x)AHOT(x))

(3)有人每天下午都去打篮球。

解：定义谓词

P(x)：x是人

B(x)：x打篮球

A(y)：y是下午

将知识用谓词表示为：a

(3x)(Vy)(A(y)^B(x)AP(x))

2、用谓词表示法求解机器人摞积木问题。设机器人有一只机械手，耍处理的世界有一张桌

子，桌上可堆放若干相同的方积木块。机械手有4个操彳勺积木的典型动作：从桌上拣起一块

积木；将手中的积木放到桌之上；在积木上再摞上一块积木；从积木上面拣起一块积木。积

木世界的布局如图2-7所示。

解：(1)先定义描述状态的谓词

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

ON(x,y)：积木x在积木y的上面.

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

HOLDING(x)：机械手抓住Xo

HANDEMPTY：机械手是空的。

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

问题的初始状态是：

ONTABLE(A)

3

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)

动作：删除表：ONTABLE(x),HANDEMPTY

添加表：HANDEMPTY(x)

Putdown(x)

条件：HANDEMPTY(x)

动作：删除表：HANDEMPTY(x)

添力I俵：ONTABLE(x),CLEAR(x),HANDEMPTY

Stack(x,y)

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

动作：删除表：HANDEMPTY(x),CLEAR(y)

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

4

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)ONTABLE(B)

ONTABLE(C)

ON(C,A)UpsUck(A,C)HOLDING(C)PUTDOWN(C)

CLEAR(A)Pickup(B)

CLEAR(B)CLEAR(A)________

CLEAR(B),a

CLEAR(C)二一CLEAR(B)

CLEAR(C)

HANDEMPTYCLEAR(C)

HANDEMPTY

ONTABLE(A)ONTABLE(A)

ONTABLE(C)ONTABLE(C)ONTABLE(C)ONTABLRC)

HOLDING(B)ON(B,C)ON(B,C)

Stack(C.B)Pickup(A)

CLEAR(A)CLEAR(A)CLEAR(A)Stack(B,A)ON(A,B)

CLEAR(B)=CLEAR(B)CLEAR(B)=CLEAR(A)

CLEAR(C)HANDEMPTHOLDING(A)HANDEMPT

3、请大家思考，在机器人搬积木的问题中，当某一状态可同时满足多个操作的条件时，应

选用哪一个操作？在进行变审代换时，如果存在多种代换的可能性，如何确定用哪一个?

略。

4、设已知如下事实：R,S,R->T,SAT->P,P->Q

求证：Q为真。

证明：因为R,R->T=>T假言推理

T,S=>SAT引入合取词

SAT,S/\T->P=>P假言推理

P,P->Q=>Q假言推理

所以Q为真。

5、已知有如下事实：

（1）只要是需要室外活动的课，王程都喜欢。

（2）所有的公共体育课都是需要室外活动的课。

（3）羽毛球是一门公共体育课。

求证：王程喜欢羽毛球这门课。（要求：定义相关谓词和常量：用谓词公式表示已知事

5

实；用自然演绎方法进行推理)

证明：首先定义谓词：(第一部分)

Outdoor(x)x是需要室外活动的课。

Like(x,y)x喜欢y。

Sport(x)x是一门公共课

把已知事实及待求解问题用谓词公式表示如下：(第二部分)

Outdoor(x)—>Like(Wang,x)

(Vx)(Sport(x)—♦Outdoor(x))

Sport(Ball)

应用推理规则进行推理：(第三部分)

Sport(y)—>Outdoor(y)全称固化

Sport(Ball),Sport(y)—*Outdoor(y)=>Outdoor(Ball)假言推理{Ball/y}

Outdoor(Ball),Outdoor(x)—►Like(Wang,x)=>Like(Wang,Ball)假言推理{Ball/x}

因此，王程喜欢羽毛球这门课。

6、所谓肯定后件的错误，是指当PTQ为真时希望通过肯定后件Q来推出前件P为真。这

显然是错误的推理逻辑，请问为什么？举例说明。

解：从真值表中可以看出，当PTQ为真时，若Q为真，无论P的真值是什么，PTQ为

均为真，也就是，当PTQ、Q为真，并不能确定P为真3

例如：PTQ表示：如果屋里的茉莉花开了，则满屋香气。

“PTQ”是真的，

肯定后件Q，即“满屋香气”，并不能推出“屋里的茉莉花开了”，“满屋香气”也有可

能是点了熏香造成的。

7、所谓否定前件的错误，是指当P-Q为真时希望通过否定前件P来推出后件Q为假，这

也是不允许的，请问为什么？举例说明。

解：从真值表中可以看出，当PTQ为真时，若P为假，不能推出Q是为假的，也就是，

当PTQ、」P为真，并不能确定Q为假。

例如：P-Q表示：如果屋里的茉莉花开了，则满屋香气。

“PTQ”是真的，

否定前件P,即“屋里的茉莉花没开”，并不能推出“没有满屋香气”，因为也有可能是

点熏香造成“满屋香气工

6

8、判断下列公式是否为可合一，若可合一，则求出其最一般合一。

(1)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))

解：(I)可合一，其最一般和一为:G={a/x,b/y}«,

(2)可合一，其最一般和一为：a={y/f(x),b/z}o

(3)可合一,其最一般和一为：c={f(b)/y,b/x}o

(4)不可合一。

9、对下列各题分别证明G是否为FhF2,...,Fn的逻辑结论:

(1)F:("ix)(Ty)(p(x,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)F,:(Vx)(P(x)->(Vy)(Q(y)->「L(x.y)))

F2:(3x)(P(x)A(VyXR(y)->L(x.y)))

G:(Vx)(R(x)->-iQ(x))

解：(1)先将F和「G化成子句集：

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

再对S进行归结:

所以，G是F的逻辑结论

(2)先将F和「G化成子句集

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

7

由于「G为：1(3x)(P(x)AQ(x)),即

(Vx)(「P(x)V-Q(x)),

可得：S2={-IP(X)V-Q(X)}

因此，扩充的子句集为：

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

再对S进行归结：

所以，G是F的逻辑结论

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

10、把下列合适公式化简为合取范式的子句集

(1)(x)lP(x)[(y)[P(y)P(f(x,y))JA-)(y)[Q(x,y)P(y)]]]

解:(Vx)[iP(x)V[(Vy)[iP(y)VP(f(x,y))JA-|(Vy)[qQ(x,y)VP(y)]]j

(Vx)[-|P(x)V[(Vy)[-]P(y)VP(f(x,y))]A(By)[Q(x,y)P(y)]]]

(Vx)[qP(x)V[(Vy)[-|P(y)VP(f(x,y))JA(3w)[Q(x,w)AqP(w)]]]

(Vx)[qP(x)V[(Vy)[-|P(y)VP(f(x,y))]AlQ(x,g(x))AqP(g(x))]]]

(Vx)(Vy)[iP(x)V[[-|P(y)VP(f(x,y))]A[Q(x,g(x))AnP(g(x))]]]

-]P(x)V[[-]P(y)VP(f(x,y))]A[Q(x,g(x))AqP(g(x))]]

[-]P(x)V-1P(y)VP(f(x.y))]AhP(x)VQ(x.g(x))JA[qP(x)VnP(g(x))]

8

••・子句集S={>|P(x)V1P(y)VP(f(x,y)),iP(x)VQ(x,g(x))，~]P(x)ViP(g(x))}

(2)[(x)P(x)V(x)Q(x)](x)[P(x)VQ(x)]

解:i[(3x)P(x)V(3x)Q(x)]V(3x)[P(x)VQ(x)]

[(Vx)-|P(x)A(Vx)qQ(x)]V(3x)[P(x)VQ(x)]

[(Vx)qP(x)A(Vy)qQ(y)]V(3z)[P(z)VQ(z)]

[(VxhP(x)A(VyhQ(y)]V[P(A)VQ(A)]

[-|P(x)A-|Q(y)]V[P(A)VQ(A)]

[-1P(x)AVP(A)VQ(A)lV[-|Q(y)VP(A)VQ(A)l

，子句集S={iP(x)AVP(A)VQ(A),-|Q(y)VP(A)VQ(A)}

11、判断下列子句集中哪些是不可满足的：

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

(2)(PVQ.-PVQ.PV-Q.-PV-Q)

(3){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(z)}

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

解：(1)不可满足，其归结过程为：

(2)不可满足，其归结过程为:

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

(4)不可满足，其归结过程略。

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

9

12、应用归结原理进行归结时\存在很大的盲目性，不仅会产生许多无用的归结式，更严重

的是会产生组核爆炸问题，请大家思考，在归结过程中可采用哪些策略能够提高归结效率？

请简要说明。

可以采用剪枝技术、新子句优先、单文字策略等，简要介绍至少一种归结策略即可。

第3章习题参考答案

1.产生式系统由哪儿部分构成，各部分的主要工作是什么？

产生式系统主要由规则库、综合数据库、控制系统（推理机）三部分构成。

规则库：用于描述相应领域知识的产生式的集合。包含将问题从初始状态转换成目标状

态（或解状态）的依据或规则。

综合数据库：又称事实库，用于存放问题求解过程中各种信息的工作区，如问题的初始

状态，已知的事实，推理过程中得到的中间结论以及最终的结论等。当规则库中某条产生式

的前提可与综合数据库中的某些已知的事实进行匹配时，该产生式被激活，并把它推出的结

论放入到综合数据库中，作为后面推理的已知事实。因此综合数据库中的内容是不断变化的，

是动态的。

控制系统：又称推理机，由一组程序组成，用于控制和协调规则库和综合数据库的运行，

实现对问题的求解。其具体的工作包括：

（1）将综合数据库中的已知事实与规则库中规则的前件进行匹配。

（2）当匹配成功的规则不止一条时，进行冲突消解。

（3）执行某一规则时，如果其右部是一个或多个结论，则把这些结论加入到综合数据

库中：如果其右部是一个或多个动作，则执行这些动作。

（4）对于不确定性知识,在执行每一条规则时还要按一定的算法计算结论的不确定性。

（5）检查综合数据库中是否包含了最终结论，决定是否停止系统的运行。

2.简述用产生式推理方法的工作流程。

（1）初始化综合数据库，把问题的初始已知事实送入综合数据库中。

（2）判定规则库是否还有未使用的规则？若没有，则终止问题的求解，失败退出。若

有，则考察综合数据库中的已知事实与规则的前提是否匹配？若不匹配，则要求用户进一步

提供关于问题的已知事实，如果用户能够提供，则返【可到（2）处继续执行；否则终止问题

的求解，失败退出。

10

(3)若综合数据库中的已知事实与规则的前提匹配，则执行当前选中的规则，把该规

则执行后得到的结论送入综合数据库中。若该规则的结论部分指出的是动作，则执行动作。

(4)检查综合数据库中是否包含了结论，即问题的解，若已包含，则终止问题的求解

过程，成功退出：否则，返回到(2)处继续执行。

直到成功或失败退出时为止。

3.用产生式表示下列不确定性：

(1)如果证据A成立，则可以得出结论B的可能性是70%。

A—B(0.7)或者

IFATHENB(0.7)

(2)今天下雨的可能性是60%。

(Today,weather,snowy,0.6)

4.在产牛式推理过程中.哪些因素将影响其推理的性能？如推理的准确性、推理的效率

等？

匹配原则、规则冲突消解的方法等都会影响性能。

5.什么是不确定性推理？

不确定推理就是从具有不确定性的证据出发，运用不确定性的知识(或规则)库中的知

识，最终推出具有•定程度的不确定性，但却是合理的或近乎合理的结论的思维过程。

6.在不确定性推理方法的设计和实现中，必须解决3大基本问题是什么？

在不确定性推理方法的设计和实现中，必须解决3大基本问题是：

(1)不确定性的度量问题：证据的不确定性度量利知识的不确定性度量。

(2)不确定性的表示问题：证据的不确定性表示和知识的不确定性的表示。

(3)不确定性的计算问题：组合证据的不确定性算法、结论不确定性的传递算法、结

论不确定性的合成与更新算法。

7.多条知识下，合成法求结论可信度

已知

RI:IFAiTHENBiCF(BhAi)=0.8

R2:IFA2THENBICF(Bi,A2)=0.5

R3:IFBiAA3THENB2CF(B2,BIAA3)=0.8

初始证据AiAA的可信度CF均设为1，即CF(AI)=CF(A2)=CF(A3)=1O而对Bt,B2一

无所知。

11

求CF(BI),CF(B2)。

解：使用合成法进行计算

(1)对于R1,R2,分别计算CF(B1)

CF,(Bi)=CF(Bi,A,)xmax{O,CF(Ai)}=0.8xl=0.8

CF2(B|)=CF(BI,A2)xmax{O,CF(A2)}=0.5x1=0.5

(2)利用合成算法计算Bl的综合可信度

CF1,2(B1)=CF1(B1)+CF2(B1)-CFI(BI)XCF2(BI)=0.8+05-0.8x0.5=0.9

(3)计算B2的可信度

CF(B2尸CF(B2,B1AA3)xmax{0,CF(BiAA3))

=CF(Bz,BiAA3)xmax{0,min{CF(Bi),CF(A3)(}

=0.8xmax{0,0.9}=0.8x0.9=0.72

所以CF(BI)=0.9.CF(B2)=0.72O

8.多条知识下，更新法求结论可信度

已知：规则可信度为

Ri:A—XCF(X,A)=0.8

R2:B—XCF(X,B)=0.6

R3:B—XCF(X,C)=0.4

R4：XAD—YCF(Y,X/\D尸0.3

证据可信度为CF(A)=CF(B)=CF(C)=0.5oX,Y的初始可信度CF()(X)=0.l,CF()(Y)=0.2o

要求用MYCIN的方法计算：

(1)结论X的可信度CF(X);

(2)结论Y的可信度CF(Y).

解：考虑X.Y具有初始可信度，所以使用更新法计算结论可信度。

X的可信度更新值“算：

由规则R1:

CF(X/A)=CFo(X)4-CF(A)xCF(X,A)-CFo(X)xCF(A)xCF(X,A)

=0.1+0,5x0.8-0.1x0.5x0.8=0.46

由规则R2:

CF(X/A.B)=CF(X/A)-|-CF(B)xCF(X,B)-CF(X/A)xCF(B)xCF(X,B)

=0.46+0.6x0.5-0.46x0.6x0.5=0.622

12

由规则R3:

CF(X/A,B,C)=CF(X/A,B)+CF(C)xCF(X,C)-CF(X/A3)xCF(C)xCF(X,C)

=0.622+0.5x0.4-0.622x0.5x0.4=0.698

Y的可信度更新值计算：

由规则R4：首先求出CF(XAD)=min{CF(X),CF(D)}

=min{0.698,0.5}=0.5o

CF(Y/XAD)=CFo(Y)+CF(X八D)xCF(Y,XAD)-CF0(Y)xCF(XAD)xCF(Y,XAD)

=0.2+0.5x0.3-0.2x0.5x0.3=0.32

所以，结论X更新后的可信度CF(X)=0.698;

结论Y更新后的可信度CF(Y)=0.32o

9.B

10.0.4,0.06

II.设有如下知识：

RI：IFA1THEN(20,1)B

R2：IFA2THEN(300J)B

R3：IFA3THEN(75,1)B

R4：IFA4THEN(4,1)B

已知结论B的先脸概率P(B)-0.03。当证据A”A2.A、,A4必然发生后，求结论B的

概率变化。

解：利用更新算法计算结论B的后验概率。

由题意可得

P(B/Ai)=(LSixP(B)/[(LSi-1)xP(B)+l]=20x0.03/[(20-1)x0.03+l]=0.382

同理有

P(B/AIA2)=(LS2XP(B/AI)/[(LS2-1)XP(B/AI)+1]

=300x0.382/[(300-1)x0.382+1]=0.9946

IXI

P(B/A1A2A3)=(LS3XP(B/AA2)/[(LS3-I)P(B/AA2)+1]

=75x0.9946/((75-1)x0.9946+1]=0.9999

P(B/A1A2A3A4)=(LS』xP(B/A1A2A3)/[(LS4-l)xP(B/A1A2A3)+1]

=4x0.9999/[(4-1)x0.9999+1]-1

13

第4章习题参考答案

1.什么是盲目搜索，什么是启发式搜索？

盲H搜索：是按照预定的控制策略进行搜索，与搜索过程中获得的中间的信息无关。即

搜索过程中控制策略不变，

启发式搜索：在搜索过程中加入了与问题有关的中间信息，用于指导搜索朝着最有希望

的方向前进，来加速问题的求解过程并找到最优解。即搜索过程中，其控制策略依据所获得

中间信息做出相应的改变以使问题朝着最有希望得解的方向搜索。

2.什么是状态空间表示法？什么是状态空间，如何表示？

状态空间表示法是用“状态”和“算符”来表示问题的一种方法。把由问题的全部状态

和一切可用算符所构成的集合，称为状态空间。状态空间一般用三元组（S,F,G）表示，其

中，S表示初始状态集，F表示算符的集合，G表示目标状态集。

3.应用状态空间表示方法进行问题求解的过程是什么？

在采用状态空间法进行问题描述的基础上，进行问题求解的过程就是：从初始状态S

出发经过一系列的算符运算，到达目标状态G。问题的解就是由初始状态到目标状态所用算

符的序列。

4.在状态空间搜索方法中，需要的辅助数据结构有哪些？

需要两个辅助的数据结构分别是OPEN表和CLOSED表。

OPEN表：存放未扩展的节点，记录当前节点及父节点；

CLOSED表：存放已扩展的节点，记录编号、当前节点及其父节点；

其中父节点用于记录生成该节点的前驱节点。

5.宽度优先搜索方法的基本思想是什么？

基本思想是：从初始节点SO开始，逐层对节点进行扩展（或搜索）并考察被扩展几点

是否为目标节点，在第n层的节点没有被全部扩展（或搜索）之前，不能对第n+1层的节

点进行扩展（或搜索）。在搜索过程中未扩展的节点在OPEN表中的排列规则为：排放在

OPEN表的末端。

6.宽度优先搜索方法的特点有哪些？

宽度优先搜索方法具有一盲目性大，搜索效率低等缺点。优点是一只要有解，一定能找

到最优解。

7.深度优先搜索方法的基本思想是什么？

14

基本思想是：每次扩展最新生成的节点。从初始节点so开始，对so节点进行扩展，

然后在其新生成的后继节点中选择一个节点扩展，考察被扩展的节点是否为FI标节点若其不

是目标节点，则对该节点进行扩展并再从其后继节点中选择一个节点进行考察。以此类推,

一直搜索下去，当到达某个即不是目标节点又无法继续扩展的节点时，才选择其兄弟节点进

行考察。在搜索过程中新生成的节点在OPEN表中的排列规则为：排放在OPEN表的首部。

8.深度优先搜索方法的特点有哪些？

深度优先搜索方法具有一盲目性，不完备性。同时，求得的解不一定是最优解等特点。

9.有界深度优先搜索的特点与存在的问题有哪些？

深度界限的选择是非常重要的。如果深度界限过大，则得到解的可能性越大，但搜索过

程中将产生许多无用的节点，降低搜索的性能与效率。如果深度界限太小，则可能得不到问

题的解。在实际的选择中应结合问题本身和上述两点综合考虑，选择适合的深度界限。

10.什么是代价树：

代价树是代价搜索树的简称，是指有向边上标有代价（或费用）的搜索树，是在搜索过

程中逐渐形成的。

11.代价树宽度与深度优先搜索方法的区别是什么？

代价树的宽度优先搜索方法和深度优先搜索方法，这两种方法类似，都是按照代价值进

行排序，并将代价最小的节点放入到OPEN表的首部，不同的是：代价树的宽度优先搜索

方法要对所有未扩展节点按代价值进行排序。代价树的深度优先搜索方法只对新生成的节点

按代价值进行排序，并放入OPEN表的首部。应用代价树的宽度优先搜索方法对问题进行

求解时，只要有解，一定能找到最优解可获得最优解，是完备的。而代价树的深度优先搜索

方法得到的解不一定是最优的，且存在不完备性（搜索更能会进入到无限分支路径而得不到

问题的解）。

12.什么是启发式搜索方法？

启发式搜索方法利用问题本身的某些特性信息，考亘节点在解的路径上的可能性（重要

性），指导搜索向最有利于问题求解的方向进行。即选择那些在解的路径上的可能性（重要

性）大的节点，这样就会缩小搜索空间，提高效率。在启发式搜索方法中用启发性信息和估

价函数去衡量和计算节点在解的路径上的这种可能性。

13.局部最佳优先搜索方法的基本思想是什么？全局最佳优先搜索方法与其有何不同？

局部最佳优先搜索方法是对深度优先搜索方法的一种改进，其基本思想是：当一个节点

15

被扩展以后，按估价函数/（处对每个子节点计算估价值，并选择估价值最小者作为下一个

要考察的节点。由于它每次只是在子节点的范围内选择下一个要考察的节点，所以称为局部

最优搜索方法。又因为其按照估价值对节点进行排序，所以，是后发式搜索方法。

全局最佳优先搜索是在OPEN表中的全部节点中选择一个估价函数值/（©最小的节点,

作为下一个被考察的节点，因为其选择的范围是OPEN表中的全部节点，所以称全局最佳

优先搜索方法。

14.什么是博弈树？博弈树有什么特点？

在博弈过程中，当选择各个子节点的估价值最大的格局时，各个子节点之间可以认为是

“或”的关系，对应的父节点称为“或节点”；当选择各个子节点的估价值最小的格局时，各个

子节点之间可以认为是“与'’的关系，对应的父节点称为“与节点”。这样就形成了一棵梃，这

就是博弈树。

博弈树的特点：

博弈的初始格局是初始节点；

“与”、“或”节点是逐层交替出现的；

所有使自己获胜的终局都是本原问题，相应的节点是可解节点：所有使对方获胜的终局

都是不可解节点。

博弈树最突出的特点就是：“与”、“或”节点是逐层交替出现的。

15.在博弈树的极大极小分析方法中，如何计算倒推值？如何选择倒推值作为节点的估价

值？

定义估价函数，用于计算端节点的估价值（称为静杰估值）利用端节点的估价值，逐层

倒推推算父节点、祖父节点等前辈节点的估价值直至初始节点的估价值。

对于"或''节点，选择各个子节点中最大估价值作为父节点的估价值，这是对自己最有利

的方案；对于“与”节点，选择各个子节点中最小估价值作为父节点的估价值，这是对自己最

坏的情况。

第5章习题参考答案

1.简述一下，你理解的监督学习和无监督学习是什么样的学习方法，请举例说明。

一、监督学习

16

监督学习就像是有一位老师在旁边指导学生学习。模型在训练过程中，会得到大量带有

明确标记或答案的示例数据，即输入特征和对应的输出标签。模型通过不断地分析这些示例，

学习输入与输出之间的映射关系，从而在面对新的输入数据时，能够根据已学到的映射规则

准确地预测出相应的输出，

应用实例：手写数字识别：训练数据是大量手写数字的图像，每个图像都有对应的数字

标签，如0、I、2等。模型可以是卷积神经网络等，通过学习图像的像索特征与数字标签

之间的关系，当输入一个新的手写数字图像时，能够准确地识别出该数字。比如，在邮政系

统中对手写邮政编码的识别，就是利用这种方法，快速准确地将信件分类到不同的地区。

二、无监督学习

无监督学习是使用未标记的数据进行学习，数据集中只有输入特征，没有明确的输出标

签或目标值。模型需要自动从数据中发现潜在的结构、模式或规律，例如对数据进行聚类、

降维、寻找数据的分布特征等。

应用实例：客户聚类分析：假设一家大型零售企业收集了大量客户的购买记录、浏览历

史、年龄、性别等数据，但没有对客户进行任何预先的分类。通过无监督学习中的聚类算法，

如K-Means算法，可以将客户划分为不同的群体。例如，可能会发现一个群体主要是年轻

女性，经常购买时尚服装和化妆品；另一个群体是中年男性，对电子产品和家居用品更感兴

趣。企'也可•以根据这些聚类结果制定更有针对性的营销策略。

2.己知一组包含X和Y的二维数据，如下表所示。

表5-8包含x和y的数据集

Xi3456

y54.5322.5

用线性问归方法计算V=a+Bx中的参数a和比

步骤一：计算相关统计量

首先，我们需要计算X、丁的均值，以及X、的乘积之和、x平方之和等统计量。设

给定的数据点有〃个（这里〃=5）,对于数据（4升）（，=12…，叽

1”1+3+4+5+619与。

-----------=—=3.8

55

5+45+3+2+2.517-

---------------=—=3.4

5--5

222222

^X.=1+3+4+5+6=1+9+16+25+36=87

/=1

17

gx/=1x5+3x4.5+4x3+5x2+6x2.5=5+13.5+12+10+15=55.5

步骤二：计算斜率6

根据线性I可归中斜率’的计算公式：

a_ZL(x，-f)(»-1)_产/一及5_55.5-5x3.8x3.4_-9.1

Z"*87-5x3814.8

步骤三：计算

根据线性I可归中。的计算公式：

a=y-Px=3.4-(-0.615)x3.8=5.737

所以在线性回归方程ka+外中，a«5.737,£=-0.615。

3.请用K-mean方法将下列数据聚类，K=3,完成算法设计，并用程序实现。

算法设计：

输入：原始数据，聚成的类数k

输出:聚类的结果

第1步初始化质心

第2步随机选择3个初始质心

第3步根据质心分配簇

计算每个数据点到每个质心的距离(常用欧氏距离：欧式距离，也称为欧几里得距离

(Euclideandistance),是一个在n维空间中两点之间的直线距离。它是一个常用于几何度量、

统计学和机器学习中的概念。欧式距离的定义基于平面几何中的毕达哥拉斯定理，即在二维

空间中，两点A(X1,力)和B(X2,y2)之间的距离d可以通过以下公式计算：

d=-西)'+(外-匕丫k

第4步将每个数据点分配给最近的质心，形成K个簇。

第5步更新质心

计算每个簇中所有点的均值，作为新的质心.

第6步判断质心是否发生变化或者达到最大迭代次数？

若是，输出各个类，即聚类结果

若否，转第3步，重复执行3-6

程序实现:

18

importnumpyasnp#导入numpy库，用于数组和数学运算

importrandom#导入random库，用于生.成随机数

#数据集(二维点数组)

data=np.array([

[9,5],[2,6],[3,2],[7,4],[3,8],[5,7],[U5],[6,6],[4,8],

[5JL[3,6],[4,1],[2,4],[6,3],[8,9J

1)

#1＜值设定要将数据分成的簇的数量

K=3

#最大迭代次数

max_iterations=100

#初始化质心

definitialize_centroids(data,K):

#从数据集中随机选择K个点作为初始质心

random_indices=random.sample(range(data.shape[01),K)

#返回由这曲索引对应的点组成的初始质心数组

returndata[random_indices]

#计算欧氏距离

defeuclidean_distance(point1,point2):

#计算两个二维点之间的欧氏距离

returnnp.sqrt(np.sum((pointI-poin(2)**2))

#分配簇函数

defassign_clusters(data,centroids):

#初始化K个空簇列表

clusters=[[\for_inrange(K)J

#遍历数据集中的每个点

fbrpointindata:

#计算点到每个质心的距离列表

distances=[euclidean_distance(point,centroid)forcentroidincentroidsl

#找到距离最小的质心的索引

19

cluster_idx=np.argmin(distances)

#将点添加到对应的簇列表中

clusters[cluster_idx].append(point)

returnclusters

#更新质心函数

defupdate_centroids(clusters):

#初始化新的质心列表

new_cen(roids=[]

#遍历每个簇

forclusterinclusters:

iflen(cluster)>0:

#计算簇内所有点的均值作为新的质心

new_centroid=np.mean(cluster,axis=0)

else:

#如果簇为空，可以重新随机选择一个点作为质心，或保持上一个质心

new_centroid=centroids[clusters.index(cluster)]#这里简单地保持上一个

质心

ncw_ccntroids.appcnd(ncw_ccntroid)

returnnp.array(new_centroids)

#K-means算法

defkmeans(data,K.max_iterations):

#初始化质心

centroids=initialize_centroi(Js(data,K)

并开始迭代

for_inrange(max_itcrations):

clusters=assign_clusters(data,centroids)

new_ceniroids=update_centroids(clusters)

#检查质心是否发生变化

ifnp.allclose(centroids,new_centroids,atol=le-6):

break

20

centroids=new_centroids

returnclusters,centroids

#执行K-means聚类

clusters,centroids=kmeans(data,K,max_iterations)

#打印结果

print("质心位置:")

prinl(centroids)

print(“簇分配：”)

fori,clusterinenumerate(clusters):

print⑴簇{i+1}:{cluster}")

4.下面给出了一组数据(如表5-10)和对应的图像(如图2-27),请仔细观察下列数据的

图像，请分别用凝聚层次聚类方法、密度聚类方法和K-mean方法完成聚类，聚成2类、4

类时的情况。同时，完成各种聚类方法的时空分析和聚类效果分析。

K-mean方法完成聚类

聚成2类的步骤：

步骤1：初始化聚类中心

随机选取两个数据点作为初始聚类中心。这里我们选取序号为I的数据点(-130.9501)

作为聚类中心序号为31的数据点(-2.6,2.4468)作为聚类中心

步骤2：计算距离并分配数据点

对于每个数据点(X1,yp(i=l,2,…,60),计算其到。和C2的欧几里得距离。欧几里得距离

公式为d=J(XLCx)2+[yiCy)2,其中为Cx，Cy。聚类中心坐标。

例如，对于数据点(X2，y?)=(-1.2125,0.2311),到C]、C2的距离分别是：

22

d21=7(-12125-(-I.3))+(0.2311-().9501)x0.724

d22=，(-1.2125一(-2.6))2+(0.2311-2.4468尸工2.603

因为d21Vd22,所以将序号2的数据点分配到C1所属的类。按照同样的方法计算其他

数据点到C1和C?的距离，并进行分配。

步骤3：更新聚类中心：假设经过第一次分配后，分配到C1类的数据点集合为S1,分配

到C2类的数据点集合为S2。

计算新的聚类中心C1坐标:

21

S|

Cnew

lx|S1|

23，)Si

z-inew_

5y—ISd

例如,假设S］中有数据点G1.3,0.9501),(-1.2125,0.2311),(-1.125,0.6068),则:

new_-1.3-1.2125-1.125

clx—x-1.212

3

「new_0.9501+0.23)1+0.6068_

C-1y="aun.jQybA

同理更新C2的坐标。

步骤4：重复步骤2、3

不断重复上述过程，直到聚类中心的坐标变化小于一个极小值(如0.001)或者达到预设

的最大迭代次数(如50次)

步骤5：输出聚类结果

聚成2类的结果：

聚类C1(类)：

序号：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、

21、22、23、24、25、26、27、28、29、30、41、42、43、44、45、46、47、48、49、50

聚类C2(类)：

序号：31、32、33、34、35、36、37、38、39、40、51、52、53、54、55、56、57、58、

59、60

聚成4类的步骤及结果：

步骤1：初始化聚类中心

随机选取序号为1的数据点(-130.9501)、序号为21的数据点(0.45,0.0579)、序号为

31的数据点(-2.6,2.4468)、序号为41的数据点(-0.85,3.4925)作为聚类中心C】、C2、C3、C4。

步骤2：计算距离并分配数据点

对于序号为2的数据点(-1.2125,0.2311),分别计算到Ci、C2.C3>C4的距离：

到C1的距离(计算过程同聚成2类时到C1的距离计算)%0.724

到的距离：d22=J(-1.2125-(-045))2+(0.2311-0.0579)2、1.672

到C3的距离(计算过程同聚成2类时到C2的距离计算)-2.603

22

到的距离：d24=^(-1.2125-(-0.85))+(0.2311-3.4925)^3.283

22

因为dzi<d22<d23<d24,所以将序号2的数据点分配到C1所属的类

按照同样的方法计算其他数据点到四个聚类中心的距离，并进行分配。

步骤3：更新聚类中心

假设经过第•次分配后，分配到C1类的数据点集合为S1,分配到C2类的数据点集合为S2。

分配到C3类的数据点集合为S3,分配到C4类的数据点集合为S4。

计算新的聚类中心C1坐标：

rnew_

,x-ISJ

_£区无）3

,yisj

同理更新C2、C3sC4的坐标。

步骤4：重复步骤2、3

持续迭代，直到满足停止条件（如聚类中心坐标变化极小或达到最大迭代次数）。

聚成4类的结果：

聚类1（类）：

序号：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20

聚类2（类）：

序号：21、22、23、24、25、26、27、28、29、30

聚类3（类）：

序号：31、32、33、34、35、36、37、38、39、40

聚类4（类）：

序号：41、42、43、44、45、46、47、48、49、50、51、52、53、54、55、56、57、58、

59、60

层次聚类

层次聚类是一种基「簇间的相似度在不同层次上分析数据，形成树形的聚类结构的方法。

以下是对给定数据进行层次聚类聚成2类和4类的情况分析：

步骤1：计算数据点间的距离

通常使用欧几里得距离来度量数据点之间的相似度。对于数据集中的每两个点（%,yj和

（Xj,yp,欧几里得距离公式为由=-Xj）2+（%_y/。

例如，对于点（-1.3,0.9501）和G1.2125,0.2311），其距离为：

23

d=7(-13-(-1.2125))2+(0.9501-0.2311)2^0.724

步骤2：构