博士入学考试：2002年人工智能原理

博士入学考试：2002年人工智能原理

一、简要回答下列问题（24分）
1、以八数码问题为例，说明产生式系统的基本组成。
2、什么叫A*算法？A*算法的主要性质是什么？
3、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？
4、在基于规则的正向演绎系统中，规则和目标各要求怎样的形式？
5、基于规则的正向演绎系统是否完备？反向演绎是否完备？双向演绎是否完备？
6、在启发式搜索中，估价函数一般定义为f(n)＝g(n)＋h(n)，指明定义中各部分的含义，并说明为什么使用这种定义方式。
7、在合一算法中，设W是非空表达式集合，D是W的差异集合，则当D具有怎样的形式时，W是不可合一的？
8、常用的知识表示方法有哪几种，简要回答各自的特点。

二、判断对错（14分）
1、OPEN表上任一具有f(n)≤f*(s)的点，最终都将被A*算法选作扩展的节点。
2、若满足单调限制，则A*算法所扩展的节点序列的f值是单调递增的。
3、设θ，λ是两个替换，则θ?λ=λ?θ。
4、表达式集合W={P(f(x), g(y, z), z), P(y, h(k(x)), f(z))}是可合一的。
5、渗透度和有效分枝系数都是关于图搜索方法启发能力的空间复杂性度量标准。
6、子句集S恒假，当且仅当对每一个解释I，使S中的每个子句C的基例C’被I弄假。
7、一阶逻辑中任一公式是否是恒假的，可用归结方法判定。

三、（12分）
1、若E=Q(y, f(y, g(x))), θ={a/x, b/y, y/z},λ={a/x, z/y, f(x)/z}, 求Eθ, Eλ, Eθ?λ
2、使用回溯搜索策略求解四皇后问题。其中规则排序使用对角线函数diag(i, j)，若diag(i, j)＜diag(m, n)，则在排序中把规则Rij放在规则Rmn的前面。diag (i, j)定义为用过单元(i, j)的最长对角线的长度。若diag函数值相同则规则随机排序。

四、使用归结方法证明下述子句集是不可满足的（写出整个归结过程和每一步归结使用的合一替换）。
 （10分）

五、设产生式系统PS，其状态集合DB={a, b, c, d, e, f, g, h, i, m}，产生式规则为：
a→b，c→m，g→h，a→c，d→e，h→i，a→d，e→f，m→i，b→g，f→m
设a为初始状态，规则应用费用为1，各状态的启发函数值为：
状态 a b c d e f g h i m
h值 1 1 8 2 2 2 4 4 10 4
用A算法画出节点c扩展前与扩展后的搜索图与搜索树，要求标出图中节点的扩展次序、估价函数值，写出节点c扩展前CLOSED表与OPEN表中的元素。（15分）

六、已知子句集S={P(g(x), z), ~P(f(y), h(a))}，求S的原子集、S的语义树。若给定S的一个解释I如下：

D={1, 2}  a   g(1)   g(2)   f(1)   f(2)   h(1)   h(2)   P(1, 1)   P(2, 2)   P(2, 1)   P(1, 2)

         2    2      1      1     2     2     1      F       F        T        T
请构造S对应与I的H解释I*。（15分）