博士入学考试试题2003年人工智能原理

博士入学考试试题2003年人工智能原理

一、叙述图搜索算法GRAPHSEARCH过程；设八数码问题有两个估价函数：f1(n)=d(n)+W(n)；f2(n)=d(n)+P(n)+3S(n)。其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数，P(n)是每个数码离开目标位置的距离的和。S(n)是由如下方式得到的序列分：对于非中心的外圈上的数码沿顺时针方向走一圈，如果一个数码后面的数码不是它在目标状态下的后继者，则给这个数码记2分，否则记0分；对于中心位置，有数码的记1分，没有的话记0分。然后把所有上述得分加起来，就得到序列分S(n)。现有初始状态和目标状态描述如下：请画出各自的启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。计算出各自的渗透度和有效分枝系数。（40分）
3 4 5
2  6
1 8 7
3 4 5
8 6
2 1 7

二、总结博弈搜索的极小极大过程和α-β过程，并以下述博弈树为例，给出两个过程的各节点返回值和搜索到的路径（请画出两个过程图）。对于其中的α-β过程以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化。图中□表示极大点，○表示极小点。（20分）
 
三、（27分）
1、设子句集 ，求S的H域，S的原子集，子句 的基例集合。
2、使用合一算法判断表达式集合W={Q(f(a), g(x)), Q(y, y)}是否可合一，若可合一，则求出最一般合一。
3、试用表推演方法证明 共同蕴含 。

四、设S是命题逻辑子句集，P是S中出现的一个原子符号，于是可将S中子句分为三部分：含有文字P的部分 ，含有文字～P的部分 ，和不含文字P或~P的部分S3。令 ， ，请证明S是不可满足的当且仅当S1’ , S2’ 都是不可满足的。（8分）

五、请举出基于规则的正向演绎系统不完备的例子。（5分）