在上面确定h(x)时，尽管并不知道h*(x)具体为多少，但当采用单位代价时，通过对不在目标状态中相应位置的数码个数的估计，可以得出至少需要移动h(x)步才能够到达目标，显然h(x)≤h*(x)。因此它满足A*算法的要求。

最优搜索路径: 如图粗线所示。 (2) 此时8数码搜索图可表示为：

这时，显然有h(x)≤p(x)≤h*(n)，相应的搜索过程也是A*算法。然而，p(x)比h(n)有更强的启发式信息，由w(x)=p(x)构造的启发式搜索树，比w(x)=h(x)构造的启发式搜索树节点数要少。

（3）若w(x)=0，该问题就变为宽度优先搜索问题。

3.9 如图3.3所示，是5个城市之间的交通路线图，A城市是出发地，E城市是目的地，两城市之间的交通费用（代价）如图中的数字，求从A到E的最小费用交通路线。

5

4 A 3 4 B 5 2 3 D C E

图3.3 旅行交通图

本题是考察代价树搜索的基本概念，了解这种搜索方法与深度优先和宽度优先的不同。首先将旅行交通图转换为代价树如图3.4所示。

图3.4 交通图的代价树

(1) 如果一个节点已经成为某各节点的前驱节点，则它就不能再作为该节点的后继节点。例如节点B相邻的节点有A和D，但由于在代价树中，A已经作为B的前驱节点出现，则它就不再作为B的后继节点。

(2) 除了初始节点A外，其它节点都有可能在代价树中多次出现，为了区分它们的多次出现，分别用下标1、2、3…标出，但它们都是图中同一节点。例如C1和C2都代表图中节点C。

对上面所示的代价树做宽度优先搜索，可得到最优解为：

A→C1→D1→E2

代价为8。由此可见，从A城市到E城市的最小费用路线为：

A→C→D→E

如果采用代价树的深度优先搜索，也会得到同样的结果：

A→C→D→E

但注意：这只是一种巧合，一般情况下，这两种方法得到的结果不一定相同。再者，代价树的深度优先搜索可能进入无穷分支路径，因此也是不完备的。

3.10 对于图3.4所示的状态空间图，假设U是目标状态，试给出宽度优先搜索与深度优搜索的OPEN表和CLOSED表的变化情况。

6

图3.5 状态空间图

[解] 宽度优先搜索的OPEN表和CLOSED表的变化情况：

1. OPEN=[A]; CLOSED=[ ] 2. OPEN=[B,C,D]; CLOSED=[A] 3. OPEN=[C,D,E,F]; CLOSED=[B,A] 4. OPEN=[D,E,F,G,H]; CLOSED=[C,B, A] 5. OPEN=[E,F,G,H,I,J]; CLOSED=[D,C,B, A] 6. OPEN=[F,G,H,I,J,K,L]; CLOSED=[E,D,C,B,A] 7. OPEN=[G,H,I,J,K,L,M]（由于L已在OPEN中）;

CLOSED=[F,E,D,C,B,A] 8. OPEN=[H,I,J,K,L,M,N]; CLOSED=[G,F,E,D,C,B,A] 9. 以此类推，直到找到了U或OPEN=[ ]。 深度优先搜索的OPEN表和CLOSED表的变化情况：

1. OPEN=[A]; CLOSED=[ ] 2. OPEN=[B,C,D]; CLOSED=[A] 3. OPEN=[E,F,C,D]; CLOSED=[B,A] 4. OPEN=[K,L,F,C,D]; CLOSED=[E,B, A] 5. OPEN=[S,L,F,C,D]; CLOSED=[K,E,B, A] 6. OPEN=[L,F,C,D]; CLOSED=[S,K,E,B,A] 7. OPEN=[T,F,C,D]; CLOSED=[L,S,K,E,B,A] 8. OPEN=[F,C,D]; CLOSED=[T,L,S,K,E,B,A] 9. OPEN=[M,C,D]（由于L已经在CLOSED中;

CLOSED=[F,T,L,S,K,E,B,A]

10. OPEN=[C,D]; CLOSED=[M,F,T,L,S,K,E,B,A] 11. OPEN=[G,H,D]; CLOSED=[C,M,F,T,L,S,K,E,B,A] 12. 以此类推，直到找到了U或OPEN=[ ]。

第4章 自动推理

4.1什么是推理的控制策略？有哪几种主要的推理驱动模式？

7

4.2自然演绎推理的基本概念与基本的推理规则。

4.3 什么是合取范式? 什么是析取范式? 什么是Skolem标准化? 如何将一个公式化为这些形式?

4.4 将下列公式化为Skolem标准型:

?x?y?z?u?v?wP(x,y,z,u,v,w)

[解] 在公式中，(?x)的前面没有全称量词，(?u)的前面有全称量词(?y)和(?z), 在

(?w)的前面有全称量词(?y),(?z)和(?v)。所以，在P(x,y,z,u,v,w)中，用常数a代替

x, 用二元函数f(y,z)代替u, 用三元函数g(y,z,v)代替w,去掉前缀中的所有存在量词之后得出Skolem标准型：

?y?z?vP(a,y,z,f(y,z),v,g(y,z,v))

4.5化为子句形有哪些步骤?

[解]

(1)利用等价谓词关系消去谓词公式中的蕴涵符“→ ”和双条件符“←→ ”。 (2)利用等价关系把否定符号“┐”移到紧靠谓词的位置上。 (3)重新命名变元名，使不同量词约束的变元有不同的名字。 (4)消去存在量词。 (5)将公式化为前束形。

(6)把公式化为Skolem标准形。 (7)消去全称量词。 (8)消去合取词。

(9)对变元更名，使不同子句中的变元不同名。 4.6将下列谓词公式化为子句集:

(1) (?x)[~P(x)?~Q(x)]→(?y)[S(x,y)?Q(x)]?(?x)[P(x)?B(x)] (2)?x[P(x)?[?y[P(y)?P(f(x,y))]?~?y[Q(x,y)?P(y)]]]

[解] (1) 转换过程遵照下列9个步骤依此为: A. 消去蕴涵符符号：

(?x){~[~p(x)?~Q(x)]?(?y)[S(x,y)?Q(x)]}?(?x)[P(x)?B(x)] B.减少否定符号的辖域：

(?x){[p(x)?Q(x)]?(?y)[S(x,y)?Q(x)]}?(?x)[P(x)?B(x)] C. 变量标准化：

(?x){[p(x)?Q(x)]?(?y)[S(x,y)?Q(x)]}?(?w)[P(w)?B(w)] D. 消去存在量词：

(?x){[p(x)?Q(x)]?[S(x,f(x))?Q(x)]}?(?w)[P(w)?B(w)] E. 化为前束型：

(?x)(?w){[p(x)?Q(x)]?[S(x,f(x))?Q(x)]}?[P(w)?B(w)] F. 把母式化为合取范式：

(?x)(?w){[p(x)?S(x,f(x))]?Q(x)?[P(w)?B(w)]} G. 消去全称量词：

[p(x)?S(x,f(x))]?Q(x)?[P(w)?B(w)] H. 消去合取词：

8