2004年吉大博士入学考试试题人工智能原理

2004年吉大博士入学考试试题人工智能原理

一、回答下列问题（30分）
1、什么叫宽度优先搜索？宽度优先搜索的优点在何处？缺点在何处？
2、试说明逻辑符号“ ”、“→”的含义和差别。
3、请举出输入归结演绎不完备的例子。
4、设S={P(x),Q(f(a))}是子句集，请举出I是S的普通解释，而不是其Herbrand解释的例子。
5、请举出公式与其Skolem范式不等价的例子。
6、什么叫A算法？什么叫A*算法？什么叫A*算法是可采纳的？两个A*算法如何比较好坏？

二、求解下列问题（30分）
1、设八数码问题有估价函数：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
2 1 7

2、将公式G化为Skolem范式，并给出G的子句集S。
   
3、使用基于规则的正向演绎系统证明下面问题：
已知事实 ；规则两条 ， ；目标 。画出演绎过程与/或图。

三、证明第一种形式的Herbrand定理：设S是子句集，则S是不可满足的，当且仅当对应于S的每一个完全语义树都存在一个有限的封闭语义树。（15分）

四、总结α-β过程，并以下述博弈树为例，以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化。图中□表示极大点，○表示极小点。（15分）
 

五、什么叫支架集归结演绎，试证明基子句集支架集归结演绎的完备性。（10分）