博士入学考试:2000年人工智能原理

博士入学考试:2000年人工智能原理

一、简要回答下列问题（24分）
1、请叙述产生式系统的过程。
2、回答产生式系统的分类，并说明各自的优缺点。
3、叙述什么样的产生式系统是可交换的产生式系统。
4、说明无信息的图搜索过程与启发式图搜索过程的差异，并举出两种典型的无信息图搜索方法。
5、叙述一阶逻辑解释的定义。
6、在语义上证明子句集恒假时，仅考虑该子句集的Herbrand解释是否够用？为什么？
7、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？
8、机器学习一般分为哪几种类型？

二、设八数码问题有估价函数：f(n)=d(n)+W(n)；其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。现有初始状态描述和目标状态描述如下：
3 4 5
2  6
1 8 7
3 4 5
8 6 7
2 1

请画出启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。（20分）

三、试用表推演方法证明 共同蕴含 。（16分）

四、叙述合一算法，并用合一算法求出W={P(a, x, f(g(y))), P(z, f(z), f(u))}的最一般合一。（写出算法的执行步骤，20分）

五、欲对某一有解的图搜索问题试用A*算法，试证明A*算法终止前的任何时刻OPEN表中总存在节点n’，n’在最佳解路径上，满足f(n’)≤f*(s)，其中s为初始节点。（15分）

六、在归结推理方法中，若不取因子而仅使用二元归结式是不完备的，请举出一个反例。（5分）