人工智能课程习题与部分解答 - 图文

在上面确定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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4