张仰森 - 人工智能原理及其应用（第二版）习题答案(4)

P∨Q∨Ｘ∨Ｚ P∨Q∨Y∨Ｚ

R∨T∨U R∨X∨Z R∨Y∨Z 所有子所有 目标 目标 P Q R X Y Z T U X Y X∧Y S Z F 规 则 P Q R T S U 已 知 事 实

(P∨Q) T∨U (S∧(T∨U)) ((P∨Q)∧R) ((P∨Q)∧R) ∨(S∧(T∨U)) 3.24 设有如下一段知识：

“张、王和李都属于高山协会。该协会的每个成员不是滑雪运动员，就是登山运动员，其中不喜欢雨的运动员是登山运动员，不喜欢雪的运动员不是滑雪运动员。王不喜欢张所喜欢的一切东西，而喜欢张所不喜欢的一切东西。张喜欢雨和雪。”

试用谓词公式集合表示这段知识，这些谓词公式要适合一个逆向的基于规则的演绎系统。试说明这样一个系统怎样才能回答问题：

“高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？” 解：(1) 先定义谓词

A(x) 表示x是高山协会会员 S(x) 表示x是滑雪运动员 C(x) 表示x是登山运动员 L(x,y) 表示x 喜欢y

16

(2) 将问题用谓词表示出来 “张、王和李都属于高山协会

A(Zhang)∧A(Wang)∧A(Li)

高山协会的每个成员不是滑雪运动员，就是登山运动员

(?x)(A(x)∧?S(x)→C(x))

高山协会中不喜欢雨的运动员是登山运动员

(?x)(?L(x, Rain)→C(x))

高山协会中不喜欢雪的运动员不是滑雪运动员

(?x)(?L(x, Snow)→? S(x)) 王不喜欢张所喜欢的一切东西

(?y)( L(Zhang, y)→? L(Wang ,y))

王喜欢张所不喜欢的一切东西

(?y)(? L(Zhang, y)→L(Wang, y)) 张喜欢雨和雪

L(Zhang , Rain)∧L(Zhang , Snow) (3) 将问题要求的答案用谓词表示出来

高山俱乐部中有没有一个成员，他是一个登山运动员，但不是一个滑雪运动员？ (?x)( A(x)→C(x)∧? S(x))

(4) 为了进行推理，把问题划分为已知事实和规则两大部分。假设，划分如下：

已知事实：

A(Zhang)∧A(Wang)∧A(Li) L(Zhang , Rain)∧L(Zhang , Snow) 规则：

(?x)(A(x)∧?S(x)→C(x)) (?x)(?L(x, Rain)→C(x)) (?x)(?L(x, Snow)→? S(x)) (?y)( L(Zhang, y)→? L(Wang ,y)) (?y)(? L(Zhang, y)→L(Wang, y))

(5) 把已知事实、规则和目标化成推理所需要的形式

事实已经是文字的合取形式：

f1: A(Zhang)∧A(Wang)∧A(Li) f2: L (Zhang , Rain)∧L(Zhang , Snow) 将规则转化为后件为单文字的形式：

r1: A(x)∧?S(x)→C(x)) r2: ?L(x, Rain)→C(x) r3: ?L(x, Snow)→? S(x) r4: L(Zhang, y)→? L(Wang ,y) r5: ? L(Zhang, y)→L(Wang , y)

将目标公式转换为与/或形式

? A(x)∨(C(x)∧? S(x))

17

(6) 进行逆向推理

逆向推理的关键是要能够推出L(Zhang , Rain)∧L(Zhang , Snow)，其逆向演绎过程如下图所示。

第4章

4.5 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制： (1) 船太小，农夫每次只能带一样东西过河； (2) 如果没有农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。

题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。

(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。 解：第一步，定义问题的描述形式

用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。

第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。

由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态： S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0) S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0) S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0) S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)

18

搜索策略部分参考答案

? A(x)∨(C(x)∧? S(x)) ? A(x) C(x) r2 ?L(x, Rain) {Wang/x, y/Rain} ?L(Wang, y) r4 L(Zhang, y) {Rain/y} L(Zhang, Rain) {Snow/y} L(Zhang, Snow) r4 L(Zhang, y) {Wang /x, y/Snow} ?L(Wang, y) r3?L(x, Snow) C(x)∧? S(x) ? S(x) 其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。

第三步，定义操作，即用于状态变换的算符组F

由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下： L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。由于农夫必须在船上，故对农夫的表示省略。

R (i)表示农夫从右岸将第i样东西带到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。同样，对农夫的表示省略。

这样，所定义的算符组F可以有以下8种算符： L (0)，L (1)，L (2)，L (3) R(0)，R(1)，R (2)，R (3)

第四步，根据上述定义的状态和操作进行求解。 该问题求解过程的状态空间图如下：

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

(0,0,1,0) R(0)

(1,0,1,0) L(2) (0,0,0,0)

4.7 圆盘问题。设有大小不等的三个圆盘A、B、C套在一根轴上，每个盘上都标有数字1、2、3、4，并

L(3) (0,1,0,0)

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

且每个圆盘都可以独立的绕轴做逆时针转动，每次转动90°，其初始状态S0和目标状态Sg如图4-31所示，请用广度优先搜索和深度优先搜索，求出从S0到Sg的路径。

19

2 C B 2 A 2 3 3 3 1 1 1 4 4 4 1 C 2 B 4 A 2 3 1 3 1 4 2 4 3

初始状态S0 目标状态Sg

图 4-31 圆盘问题

解：设用qA，qB和qC分别表示把A盘，B盘和C盘绕轴逆时针转动90o，这些操作（算符）的排列顺序是qA，qB，qC。

应用广度优先搜索，可得到如下搜索树。在该搜索树中，重复出现的状态不再划出，节点旁边的标识Si，i=0,1,2,…，为按节点被扩展的顺序给出的该节点的状态标识。

由该图可以看出，从初始状态S0到目标状态Sg的路径是 S0→2→5→13(Sg)

20