人工智能答案 第二章

b,启发式搜索{全局择优、局部择优，分支界限、最近择优、A算法、A*算法}

线式搜索：a,盲目搜索{随即碰撞、回溯穷举} b,启发式搜索{不回溯、智能回溯}

2. 盲目搜索，也就是无导向搜索。在搜索过程中，没有任何背景知识作指导不

考虑任何与解有关的信息，随机的或按预定顺序机械地搜索，并判断是否为所求的解，直到找到解或是证明问题无解为止。盲目搜索效率太低，一般只适用于求解比较简单的问题。

3. 启发式搜索，即为有导向的搜索，利用“启发性信息”引导搜索。所谓的启

发性信息就是与问题有关的有利于找到问题解的信息或知识。启发函数，是用来估计搜索树上节点与目标节点接近程度的一种函数，通常即为h(x)。

4. OPEN表：动态数据结构，登记记录当前待考察的节点。

CLOSED表：动态数据结构，记录考察过得节点。 5. 深度优先搜索算法的特点是

① 般不能保证找到最优解；

② 当深度不合理时，可能找不到解，可以将算法改为可变深度限

制；

③ 法与问题无关，具有通用性； ④ 于图搜索方法

广度优先搜索算法的特点是

② 问题有解时，一定能找到解；

②当问题为单位耗散值，并且问题有解时，一定能找到最优解； ③效率低； ④方法与问题无关，具有通用性； ⑤属于图搜索方法。

6.解：用四元组(f、w、s、g)表示状态， f 代表农夫，w 代表狼，s

代表羊，g 代表菜，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸 。

初始状态S0：(0,0,0,0) 目标状态：(1,1,1,1) 不合法的状态:(1,0,0,*),(1,*,0,0),(0,1,1,*),(0,*,1,1) 操作集F={P1，P2，P3，P4，Q1，Q2，Q3，Q4}

操作符 条件 动作 p1 p2 p3 q0 f=0，w=0，s和g相异 f=1，w=1 f=0，s=0， f=1，s=1 f=0，g=0，w和s相异 f=1，g=1 f=1，s和g相异，w和f=0 s相异 q1 q2 q3 (0,0,0,0)q2p2f=1，w＝1，s和g相异 f=0，w＝0 f=1，s＝1， f=0，s＝0 f=1，g＝1，w和s相异 f=0，g＝0 (1,0,1,0)q0p3q2(0,0,1,0)q1p1q3q2p2(1,0,1,1)p2p3(0,0,0,1)q2p2q0p2(1,1,1,0)(0,1,0,0)(1,1,0,1)q3(0,1,0,1)q2(1,1,1,1)

方案有两种：p2→ q0 → p3→ q2 → p2 → q0 → p2 p2→ q0 → p1→ q2 → p3→ q0→ p2 7题和9题参考第8题。 8.琴键翻动

（供参考）解：引入一个三元组(q0,q1,q2)来描述总状态，开状态为

0，关状态为1，全部可能的状态为 ：

Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0)

Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。

翻动琴键的操作抽象为改变上述状态的算子，即F＝{a, b, c} a:把第一个琴键q0翻转一次 b:把第二个琴键q1翻转一次 c:把第三个琴键q2翻转一次

问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}>

问题的状态空间图如下页所示：从状态空间图，我们可以找到Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此，初始状态“关、开、关”连按三次琴键后只会出现“关、关、关”的状态。

a

（0，0，0）

c

（1，0，0）

b

（0，0，1） a

（1，0，1）

c

b

（1，1，0）

a

b

（0，1，0）

c

c

b

（1，1，1）

a

（0，1，0）

10.设用二元组(SA,SB)表示问题的状态, SA表示金盘A所在的杆号, SB表示金盘B所在的杆号, 这样, 全部可能的状态有9种, 可表示如下：

二阶梵塔的全部状态

这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘从第i号杆移到第j号杆上;B(i,j)表示把B盘从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是：A(1,2), A(1,3), A(2,1), A(2,3), A(3,1), A(3,2)

B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)

这样由题意,问题的初始状态为(1, 1),目标状态为(3, 3), 则二阶梵塔

问

题

可

用

状

态

图

表

示

为

由这9种可能的状态

和12种操作, 二阶梵塔问题的状态空间图如图：

三阶同理可得。

11代价树如下图所示：分别给出宽度优先及深度优先搜索策略下的搜索过程和解。其中，F、I、 J、L是目标节点。

A3B2D1H3I2J1E3K5F3L3O2C2G1M2P

宽度优先搜索过程：A－﹥ C－﹥ B－﹥ G－﹥E

－﹥D－﹥ M－﹥ J，G（J）=6， 解为：A－﹥ B－﹥ E－﹥ J 深度优先搜索过程为：A－﹥ C－﹥ G－﹥M－﹥P－﹥O－﹥L，G（L）

=7，

解为：A－﹥ C－﹥G－﹥L 12

13.用极小极大方法求N的最佳走步。

N4B44CD-1-2344114A41-41424 6 9 -1 -2 1 4 3 4 6 4 4 1 -4 6 1 6 5 4 2 5最佳路径为N-〉A-〉B-〉C-〉D

14.

≥2 N ≤2 A B ≥2 C ≤-2 H ≤3 I ≥4 J ≥1 ≤1 E L ≤1 F ≤3 N N ≤2 ≤-1 K ≤-5 ≤2 3 2 3 -1 -2 3 1 4 3 4 6 5 4 1 -5 6 1 7 5 3 2 6 习题14 博弈树

1.基于谓词逻辑的机器推理方法：自然演绎推理，归结演绎推理，基于规则的演绎推理。 2. 求下列谓词公式的子句集 (1) xy(P(x,y) Q(x,y))

解：去掉存在量词变为：P(a,b)Q(a,b) 变成子句集{ P(a,b),Q(a,b)} (2) 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)}

(3) x{P(x)y[zQ(x,z)zR(x,y,z)]}

P(x)Q(x,z)R(x,f(x),z)

(4)xyzuvw(P(x,y,z,y,v,w)Q(x,y,z,y,v,w)R(x,y,z,u,v,w)) {p(a,y,f(y),y,v,g(y,v)) Q(a,y,f(y),y,v,g(y,v)),

p(a,x,f(x),x,z,g(x,z)) R(a,x,f(x),h(x),z,g(x,z))}

3. 试判断下列子句集中哪些是不可满足的 （1）使用删除策略 （2）归结

4.用合一算法求下列公式集的最一般合一。

（1）W={Q(a,x),Q(y,b)} 最一般合一为:{a/y,b/y}

（2）W{Q(x，y，z)，Q(u，h(v,v)，u)}

最一般合一为：{z/u,h(v,v)/y,z/x}或{x/u,h(v,v)/y,x/z}

5.用归结原理证明，G是否可肯定是F的逻辑结果。

(1) F1 (x)(P(x)(Q(x)∧R(x))

F2 (x) (P(x) ∧S(x) G (x)(S(x) ∧R(x))

证明：利用归结反演法，先证明F1 ∨ F2 ∨¬G是不可满足的。

求子句集： (1) ¬P(x) ∨Q(x) (2) ¬P(z) ∨R(z) (3)P(a) (4)S(a)

(5) ¬S(y) ∨ ¬ R(y) (¬G)

F2

F1

S

利用归结原理进行归结

(6)R(a) [(2),(3), σ1={a/z}]

(7) ¬ R(a) [(4),(5), σ2 ={a/y}] (8)Nil [(6),(7)]

所以S是不可满足得，从而G是F1和F2的逻辑结果。

（2）F (x) ( (y)P(x，y) ∧ Q(y)) (y)（R(y) ∧ T(x,y)））

G ¬ (x) R(x)  (x) (y) P(x，y) ¬ Q(y)) 证明：利用归结反演法证明，先证明F  ¬G是不可满足的。

把F、¬G化成子句集： (1) ¬P(x，y) ∨¬Q(y) ∨R(f(x)) (2) ¬P(v，u) ∨¬Q(u) ∨T(v, f(u)) (3) Q(b) (4) P(a，b) (5) ¬R(z)

对上述式子进行归结：

（6） ¬P(x，b) ∨R(f(x)) （1）和（3）归结，{b/y} （7）R(f(x)) （4）和（6）归结，{a/x} （8）NIL （5）和（7）归结{f(x)/z} 所以G是F、的逻辑结论。

（3）F1 (x) (A(x)∧¬B(x)( y) (D(x，y)∧C(y)))

F2 (x) (E(x)∧A(x) ∧ (y) (D(x，y)E(y)))

F3 (x) (E(x) ¬B(x)) G (x) (E(x) ∧C (x))

证明：利用归结反演法证明，先证明F1  F2  F3  ¬G是不可满足的。 求子句集： F1： （1）¬A(x)∨B(x) ∨D(x，w) （2）¬A(y)∨B(y) ∨C(t) F2

（3）E(a) （4）A(a) （5）¬ D(a，z) ∨E(z)

F3 （6）¬E(u) ∨¬B(u) ¬G （7）¬E(v) ∨¬C(v) 对子句集进行归结： （8）¬B(a) [（3）（6）{a/u}] （9）¬C(a) [（3）（7）{a/v}] （10）B(a) ∨C(t) [（2）（4）{a/y}] （11）C(a) [（8）（10）{a/t}] （12）Nil [（9）（11）] 6 用归结原理证明下述推理正确。

已知：狗都会吠叫和咬人。

任何动物吠叫时总是吵人的。 松狮是狗。

结论：松狮是吵人的。 证明：首先定义如下谓词： B(x):x是咬人的。 F(x):x是吠叫的。 D(x):x是狗。

N(x):x是吵人的。 G(x):x是松狮。

将上述各语句翻译成谓词公式：

F1: x (D(x) (B(x)  F(x))) F2: x (F(x)N(x)) F3:  x (G(x)  D(x)) G: x (G(x) N(x))

利用归结反演法，先证明F1  F2  F3  ¬G是不可满足的。 F1  F2  F3  ¬G的子句集为 （1）¬D(x)  B(x) （2）¬D(y)  F(y) （3）¬F(z)  N(z) （4）¬G(u)  D(u) （5）G（a） （6）¬N（a） 进行归结得：

（7）B（a） [（1）（5）{a/x}] （8）F（a） [（2）（5）{a/y}] （9）¬F(a) [（3）（6）{a/z}] （10）NIL [（8）（9）] 得证。

7.Sam、Clyde、Oscar是三只大象，关于它们，已知如下事实：

（1）Sam是粉红色的；

（2）Clyde是灰色的且喜欢Oscar；

（3）Oscar是粉红色或者是灰色（但不是两种颜色）且喜欢Sam。 用归结反演方法证明一只灰色大象喜欢一只粉红色大象。 解 首先定义如下谓词：

Pink(x)表示x是粉红色的大象。

Gray(x) 表示x是灰色的大象。 Likes（x，y）表示喜欢y。 已知条件可以表示成如下谓词公式： （1）Pink（Sam）

（2）Gray（Clyde）Likes（Clyde，Oscar） （3）（Gray（Oscar）Pink（Oscar）） Likes（Oscar，Sam） 设求证的公式为：

G： x y（Gray（x） Pink（y） Likes（x，y）） 把其否定化为子句形式 (1) Pink（Sam）

(2) Gray（Clyde） (3) Likes（Clyde，Oscar）

(4) Gray（Oscar）Pink（Oscar） (5) Likes（Oscar，Sam） (6) ¬Gray（x）¬ Pink（y）¬Likes（x，y） 进行归结： （7）¬Gray（x）¬Likes（x，Sam） （1）（6）归结{Sam/y}

（8）¬Gray（Oscar） （5）（7）{Oscar/x} （9）Pink(Oscar) （4）（8） （10）¬Gray（x）¬Likes（x，Oscar） （6）（9）归结{Oscar/y} （11）¬Likes（Oscar，Sam） （2）（10）归结{Oscar/y} （12）Nil （3）（11）归结{Sam/y}

8张某被盗，派五个侦察员去调查，研究案情时，侦察员A说：“赵与钱中至少有一人作案”；侦察员B说：“钱与孙至少有一人作案”；侦察员C说：“孙与李中至少有一人作案”；侦察员D说：“赵与孙中至少有一人与此案无关”；侦察员E说：“钱与李中至少有一人与此案无关”。如果这五个侦察员说的都可信，试用消解原理求出谁是盗窃犯。

解：定义谓词用P（x）表示x作案，a，b，c，d分别代表赵、钱、孙、李，则五个侦察员

得话可用谓词公式表示为 （1） P（a）∨P（b） （2） P（b）∨P（c） （3） P（c）∨P（d） （4） ¬P（a）∨¬P（c） （5） ¬P（b）∨¬P（d） 要求的公式为

G： xP(x) (即存在x，x是罪犯) 将其化为否定形式再析取一个辅助谓词PA(x) 得 （6）P（x）∨PA（x） 对上面式子进行归结得 （7） ¬P（d）∨P（c） (2)(5)归结 （8）P（c） (3)(5)归结

（9）PA（c） (8)(6)归结，{c/x} （10）¬P（c）∨P（d） (1)(4)归结 （11）P（b） (3)(5)归结

（12）PA（b） (8)(6)归结，{b/x} 所以，罪犯为钱和孙两个人。

9.归结策略：

删除策略 支持集策略 线性归结策略 单元归结策略 语义归结策略 祖先过滤型策略 10.见第5题 11. ￢S(a)

r1{x/a}

￢P(x)

F{a/x}

￢P(a)

N(a) r2{x/a} Q(x) F{a/x} Q(a)^R(a) R(x) ￢P(a) V (Q(a)^R(a))