吉林大学计算机学院博士入学考试题, 计算智能

1、人工智能原理2004年一、回答下列问题(30分)1、什么叫宽度优先搜索？宽度优先搜索的优点在何处？缺点在何处？2、试说明逻辑符号“ n ”、”的含义和差别。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中“不在位” 数码的个数；试给出

2、以下面为初始节点和目标节点的图搜索过程，指明各节点估价函数值和整体解路径，并计算 该搜索过程的渗透度是多少？有效分枝系数是多少？2、将公式G化为Skolem范式，并给出G的子句集S。G = V 乂E(xa) T(3y ( E (y,g ( x)Vz (E (z , gGx ) )E(yz3、使用基于规则的正向演绎系统证明下面问题：已知事实A v B ;规则两条A T C a D，B T E a 6;目标C v G。画出演绎过程与/或图。三、证明第一种形式的Herbrand定理：设S是子句集，则S是不可满足的，当且仅当对应于S的每一个完全语 义树都存在一个有限的封闭语义树。(15分)四、总结a

3、-8过程，并以下述博弈树为例，以优先产生左边子节点的次序进行a -8剪枝，指出在何处发生剪枝、 何处为a修剪、何处为8修剪？标明发生剪枝的节点和初始节点返回值的变化。图中表示极大点，。表示极小 点。(15分)30 -3-1-2014125-11-1-13-3236-2五、什么叫支架集归结演绎，试证明基子句集支架集归结演绎的完备性。(10分)人工智能原理2003年一、叙述图搜索算法GRAPHSEARCH过程；设八数码问题有两个估价函数：fi(n)=d(n)+W(n)； f2(n)=d(n)+P(n)+3S(n)。其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数，P(n

4、)是每 个数码离开目标位置的距离的和。S(n)是由如下方式得到的序列分：对于非中心的外圈上的数码沿顺时针方向走 一圈，如果一个数码后面的数码不是它在目标状态下的后继者，则给这个数码记2分，否则记0分；对于中心位 置，有数码的记1分，没有的话记0分。然后把所有上述得分加起来，就得到序列分S(n)。现有初始状态和目标 状态描述如下：请画出各自的启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。计 算出各自的渗透度和有效分枝系数。(40分)3452 I 1 I 7初始状态1 I 8 | 7目标状态二、总结博弈搜索的极小极大过程和a -p过程，并以下述博弈树为例，给出两个过程的各节

5、点返回值和搜索到 的路径(请画出两个过程图)。对于其中的a -p过程以优先产生左边子节点的次序进行a -p剪枝，指出在何处 发生剪枝、何处为a修剪、何处为p修剪？标明发生剪枝的节点和初始节点返回值的变化。图中表示极大点， 。表示极小点。(20分)3-30-1-201451-1-1332-2三、(27分)1、设子句集S = P (x), Q (f (y) v R (y)，求S的H域，S的原子集，子句C = Q (f (y) v R (y)的基例集合。2、使用合一算法判断表达式集合W=Q(f(a), g(x), Q(y, y)是否可合一，若可合一，则求出最一般合一。3、试用表推演方法证明Vx(P

6、(x) T Q (x), Vy (Q (y) T R (y), 3z( R (z)共同蕴含 3 u ( P (u)。四、设S是命题逻辑子句集，P是S中出现的一个原子符号，于是可将S中子句分为三部分：含有文字P的部分S = C v P,., C v P，含有文字P的部分S = B v P,., B v P，和不含文字P 或P的部分S。令 11n21m3S = C，C uS，S = B ,., B u S，请证明S是不可满足的当且仅当S1，S2 都是不可满足的。(8 11n 321m3分)五、请举出基于规则的正向演绎系统不完备的例子。(5分)By W01F STUDIO 人工智能原理2002年一、

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

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

9、, b/y, y/z,入=a/x, z/y, f(x)/z,求 Ee, Ex, Ee .入2、使用回溯搜索策略求解四皇后问题。其中规则排序使用对角线函数diag(i, j)，若diag(i, j)Vdiag(m, n)，则在排 序中把规则放在规则Rmn的前面。diag (i, j)定义为用过单元(i, j)的最长对角线的长度。若diag函数值相同则规 则随机排序。四、使用归结方法证明下述子句集是不可满足的(写出整个归结过程和每一步归结使用的合一替换)。S = A(a, f (c), f (b), B (a), A(x, x, f (x), 口 A(x, y, z) v C (x, z), 口

10、B (x) v 口 A(y, z, u) v 口 C (x, u) v C (x, y) v C (x, z), 口 C (a,b) (10 分)五、设产生式系统PS，其状态集合DB=a, b, c, d, e, f, g, h, i, m，产生式规则为:ab，c m，gh，ac，de，hi，ad，ef，mi，bg，fm状态abcdefghimh值11822244104状态abcdefghimh值11822244104设a为初始状态，规则应用费用为1，各状态的启发函数值为:用A算法画出节点c扩展前与扩展后的搜索图与搜索树，要求标出图中节点的扩展次序、 点c扩展前CLOSED表与OPEN表中的元

11、素。(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)2211221 F F请构造S对应与I的H解释I*。(15分)人工智能原理2002年七、对下面的博弈树以优先产生左边子节点的次序进行a -8剪枝，指出在何处发生剪枝、何处为a修剪、何处 为8修剪？标明发生剪枝的节点和初始节点返回值的变化，以及搜索到的路径。图中表示极大点，。表示极小 点。说明一般的a -8剪枝过程中，什么情况下

12、效率最高。（10分）-1332-23-30-1-201451-1人工智能原理2000年一、简要回答下列问题(24分)1、请叙述产生式系统的过程。2、回答产生式系统的分类，并说明各自的优缺点。3、叙述什么样的产生式系统是可交换的产生式系统。4、说明无信息的图搜索过程与启发式图搜索过程的差异，并举出两种典型的无信息图搜索方法。5、叙述一阶逻辑解释的定义。6、在语义上证明子句集恒假时，仅考虑该子句集的Herbrand解释是否够用？为什么？7、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？8、机器学习一般分为哪几种类型？二、设八数码问题有估价函数：f(n)=d(n)+W(n)；

13、其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在 位”数码的个数。现有初始状态描述和目标状态描述如下：初始状态目标状态请画出启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。(20分)、试用表推演方法证明(V X (P (x) T Q (x), V y (Q (y) T R (y), 3 z ( R (z)共同蕴含 3 u ( P (u)。(16 分)四、叙述合一算法，并用合一算法求出W=(P(a, x, f(g(y), P(z, f(z), f(u)的最一般合一。(写出算法的执行步骤， 20分)五、欲对某一有解的图搜索问题试用A*算法，试证明A*算法终止前的

14、任何时刻OPEN表中总存在节点n，n在 最佳解路径上，满足f(n)Wf*(s)，其中s为初始节点。(15分)六、在归结推理方法中，若不取因子而仅使用二元归结式是不完备的，请举出一个反例。(5分)人工智能原理xxxx年一、回答下列问题(20分)1、什么是可交换产生式系统？2、影响A算法启发能力的因素有哪些？3、叙述a -8过程的剪枝规则。4、归结原理有哪几种重要的改进？5、描述基于规则的正向演绎系统的初始状态、规则和目标的一般形式。二、请用估价函数：f(n)=d(n)+W(n)求解八数码问题，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不 在位”数码的个数。n1nn%n6七nh(n

15、)024411200n4初始状态目标状态画出启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。(20分)三、叙述合一算法，并用该算法寻找表达式集W=R(x, x), R(f(a), g(y)的最一般合一。(20分)四、使用AOT算法，启发函数应满足什么条件？下图是已给出的与/或图，其中n0是初始节点，n7 n8是目标节 点集，h是启发函数，并假定k-连接符的费用是k。请用Ab算法求解其最优解图。(20分) n0n8n3n5n7 *五、证明下述归结方法的完备性定理：如果基子句集S是不可满足的，则存在从S推出空子句的归结演绎。(20 分)人工智能原理xxxx年A一、简要回答下列

16、问题1、人工智能的主要研究领域有哪些？2、产生式系统由哪几部分组成？各部分的作用是什么？3、产生式系统的控制策略有哪几种方式？4、什么是深度优先搜索？什么是宽度优先搜索？5、什么叫启发信息？它是如何使用的？6、影响A算法启发能力的要素有哪些？7、搜索方法的启发能力有哪几种基本的度量方法？8、什么是从子句集S推出子句C的归结演绎？9、什么是可交换产生式系统？10、在归结演绎中，什么叫最一般的合一替换？二、试述可分解产生式系统的基本过程。三、已知八数码难题的初始状态和目标状态为:n1nn%n6七%h(n)024411200n4初始状态目标状态设估价函数：f(n)=d(n)+W(n)，其中d(n)是

17、节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。画出使用此函数A算法解题的搜索树，在树上标明各节点的估价函数值及选择扩展节点的次序。四、已知与/或图，其中n0是初始节点，n7 %是目标节点集，h是启发函数，并假定k-连接符的费用是k。请 用A。算法求解其最优解图。n0n8n3n5n7 bJ五、试用归结演绎证明公式Vx(R (x) 口 Q(x)是公式集 (3x3 j(P(x) a Q (y) a S (x, j), 3x(P(x) a V j(R (j) - S (x, j)的逻辑结果。人工智能原理xxxx年B一、简要回答下列问题1、无信息的图搜索方法主要有哪两种？2、简述各种搜索策略各自的优缺点。3、影响A算法启发能力的要素有哪些？4、一阶逻辑中，公式是怎样定义的？5、一阶逻辑中，公式的解释是怎样定义的?6、命题逻辑中，常用哪两种公式范式？7、一阶逻辑中，常用哪两种公式范式？8、什么叫子句集的Herbrand域？、试述图搜索算法GRAPHSEARCH。三、已知八数码难题的初始状态和目标状态为:初始状态目标状态设估价函数：f(n)=d(n)+W(n)，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。画出使用此函数A算法解题的搜索树，在树