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

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

　　一、回答下列问题（20分）
　　1、什么是可交换产生式系统？
　　2、影响A算法启发能力的因素有哪些？
　　3、叙述α-β过程的剪枝规则。
　　4、归结原理有哪几种重要的改进？
　　5、描述基于规则的正向演绎系统的初始状态、规则和目标的一般形式。

　　二、请用估价函数：f(n)=d(n)+W(n) 求解八数码问题，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。
　　3 2 1
　　4  8
　　5 6 7
　　3 8 2
　　4 6 1
　　5  7

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

　　三、叙述合一算法，并用该算法寻找表达式集W={R(x, x), R(f(a), g(y))}的最一般合一。（20分）

　　四、使用AO*算法，启发函数应满足什么条件？下图是已给出的与/或图，其中n0是初始节点，{n7, n8}是目标节点集，h是启发函数，并假定k-连接符的费用是k。请用AO*算法求解其最优解图。（20分）
　　n n0 n1 n2 n3 n4 n5 n6 n7 n8
　　h(n) 0 2 4 4 1 1 2 0 0

　　五、证明下述归结方法的完备性定理：如果基子句集S是不可满足的，则存在从S推出空子句的归结演绎。（20分）