吉林大学博士入学考试试题计算智能2001答案

回答下列问题(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分)

4.总结一下α-β的过程，以下面的博弈树为例，按照优先于左边子节点的顺序进行α-β剪枝，指出剪枝发生在哪里，α剪枝在哪里，β剪枝在哪里？指示发生修剪的节点和初始节点的返回值的变化。图中□代表最大点，○代表最小点。(15分)

5.什么是脚手架集合决议推演？尝试证明基本子句集的支架集归结演绎的完备性。(10分)

2003年人工智能原理

1.描述图搜索算法的过程；八字问题有两个评价函数:f 1(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

2.总结博弈搜索的minimax过程和α-β过程，以下面的博弈树为例给出两个过程的每个节点的返回值和搜索到的路径(请画两个过程图)。对于α -β过程，α -β剪枝是按照优先于左侧子节点的顺序进行的，哪里剪枝，α剪枝哪里，β剪枝哪里？指示发生修剪的节点和初始节点的返回值的变化。图中□代表最大点，○代表最小点。(20分)

三。(27分)

1.设一个子句集，求S的H域，S的原子集，子句的基本例集。

2.用unity算法判断表达式集w = {q (f (a)，g (x))和q (y，y)}是否可以统一，如果可以，求最一般的unity。

3.用表格推演证明* * *有相同蕴涵。

4.设S是一组命题逻辑分句，P是S中出现的原子符号，所以S中的分句可以分为三部分:含有P这个词的部分，含有~P这个词的部分，没有P或~ P这个词的S3部分..请证明S不可满足当且仅当S1 '和S2 '不可满足。(8分)

5.请举例说明不完整的基于规则的正向演绎系统。(5分)

人工智能原理2002

一、简要回答以下问题(24分)

1.以八位数问题为例，说明产生式系统的基本组成。

2.什么是A*算法？A*算法的主要性质是什么？

3.在基于规则的演绎系统中，什么是一中复合替换？为什么要考虑替换的兼容性？

4.在基于规则的正向推演系统中，规则和目标需要什么形式？

5.基于规则的正向推演系统是否完整？反向推导完成了吗？双向推演完成了吗？

6.在启发式搜索中，评价函数一般定义为f (n) = g (n)+h (n)，表示定义中各部分的含义，解释为什么使用这个定义。

7.在unity算法中，如果W是一组非空表达式，D是W的一组差，那么当D具有什么形式时，W不能被统一？

8.常用的知识表示方法有哪些？简单回答一下各自的特点。

二、判断对错(14分)

1，开表中任何f(n)≤f*(s)的点最终都会被A*算法选为扩展节点。

2.如果满足单调约束，则A*算法扩展的节点序列的F值是单调递增的。

3.设θ和λ是两个代换，那么θ？λ=λ?θ。

4.表达式集合w = {p (f (x)，g (y，z)，z)，p (y，h (k (x))，f (z)}是统一的。

5.渗透率和有效分支系数都是关于图搜索方法启发式能力的空间复杂性度量。

6.子句集S总是假的，当且仅当I被解释为每个子句，所以S中每个子句C的基格C '被I证伪..

7.一阶逻辑中任何一个公式是否总是假，都可以用归结方法来确定。

三。(12分)

1，若e = q (y，f (y，g (x))，θ = {a/x，b/y，y/z}，λ = {a/x，z/y，f (x)/z}，求eθ，eλ。λ

2.用回溯策略解决四皇后问题。其中，对角线函数diag(i，j)用于规则排序。如果Diag (i，j) < Diag (m，n)，则在排序中，规则Rij放在规则Rmn之前。Diag (i，j)定义为所用单元(I，j)的最长对角线的长度。如果诊断函数值相同，则规则随机排序。

第四，用归结方法证明下面的子句集是不可满足的(写出整个归结过程和归结的每一步用到的一一替换)。

(10分)

5.设产生式系统PS有状态集DB={a，b，c，d，e，f，g，h，I，m}，产生式规则为:

a→b，c→m，g→h，a→c，d→e，h→i，a→d，e→f，m→i，b→g，f→m

设A为初始状态，规则应用代价为1，各状态的启发式函数值为:

国家a b c d e f g h m

h值1 1 8 2 2 2 4 4 10 4

用算法a画出节点C扩展前后的搜索图和搜索树，要求在图中标出节点的扩展顺序和评价函数值，并在节点C扩展前写出封闭表和开放表中的元素..(15分)

6.给定子句集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)

2 2 1 1 2 2 1

请构造S对应于I的H解释I*..(15分)

人工智能原理2002

7.按照优先生成左子节点的顺序对下面的博弈树进行α-β剪枝，指出剪枝发生在哪里，α剪枝在哪里，β剪枝在哪里？指示发生修剪的节点和初始节点的返回值的变化，以及搜索到的路径。图中□代表最大点，○代表最小点。解释一下一般的α -β剪枝过程中什么效率最高？(10分)

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分)

四、描述unity算法，用unity算法求w = {p (a，x，f (g (y))，p (z，f (z)，f (u))}的最一般的unity。(写下算法的执行步骤，20分)

5.对一个有解的图搜索问题尝试A*算法，尝试证明在A*算法终止前的任意时刻，开表中总有一个节点n’，其中n’在最优解路径上，且满足f(n’)≤f *(s)，其中s为初始节点。(15分)

6.在归结推理方法中，如果不考虑因素，只使用二元归结是不完整的。请举个反例。(5分)

人工智能原理xxxx年

一、回答下列问题(20分)

1.什么是可交换生产系统？

2.影响一个算法启发式能力的因素有哪些？

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分)

第三，描述unity算法，用这个算法求表达式集w = {r (x，x)，r (f (a)，g (y)}的最一般的unity。(20分)

4.使用AO*算法时，启发式函数需要满足什么条件？下图是给定的与或图，其中n0是初始节点，{n7，n8}是目标节点集，h是启发式函数，假设k- connector的代价为k..请用AO*算法求解其最优解图。(20分)

n n0 n1 n2 n3 n4 n5 n6 n7 n8

h(n) 0 2 4 4 1 1 2 0 0

5.证明以下归结方法的完备性定理:如果基子句集合S不可满足，则存在从S推导空子句的归结演绎..(20分)

人工智能原理xxxx年a

首先，简要回答以下问题

1.人工智能的主要研究领域有哪些？

2.生产系统由哪些部分组成？各部分的作用是什么？

3.生产系统的控制策略有哪些？

4.什么是深度优先搜索？什么是宽度优先搜索？

5.什么是鼓舞人心的信息？如何使用？

6.影响一个算法启发式能力的因素有哪些？

7.衡量搜索方法启发式能力的基本方法有哪些？

8.子句集S中子句C的归结推导是什么？

9.什么是可交换生产系统？

10，在推演中，最一般的统一替换是什么？

第二，试描述可分解生产系统的基本过程。

3.已知八位数字谜的初始状态和目标状态是:

1 2 3

8 4

7 6 5

2 8 3

1 6 4

7 5

设评价函数为f(n)=d(n)+W(n)，其中d(n)为搜索树中节点n的深度，W(n)为节点n中“不到位”的位数，用此函数画出一个搜索树，一个解决问题的算法，并标明每个节点的评价函数值和在树上选择扩展节点的顺序。

4.已知与或图，其中n0为初始节点，{n7，n8}为目标节点集，h为启发式函数，假设k- connector的代价为k..请用AO*算法求解其最优解图。

n n0 n1 n2 n3 n4 n5 n6 n7 n8

h(n) 0 2 4 4 1 1 2 0 0

第五，尝试证明公式是由演绎法设定的公式。

的逻辑结果。

人工智能原理xxxx年b

首先，简要回答以下问题

1，无信息图搜索的两种主要方法是什么？

2.简述各种搜索策略的优缺点。

3.影响一个算法启发式能力的因素有哪些？

4.一阶逻辑中，公式是如何定义的？

5.在一阶逻辑中，公式的解释是如何定义的？

6.命题逻辑中常用哪两种公式范式？

7.一阶逻辑常用哪两种公式范式？

8.子句集的Herbrand域是什么？

其次，尝试描述GRAPHSEARCH算法。

3.已知八位数字谜的初始状态和目标状态是:

1 2 3

8 4

7 6 5

2 8 3

1 6 4

7 5

设评价函数为f(n)=d(n)+W(n)，其中d(n)为搜索树中节点n的深度，W(n)为节点n中“不到位”的位数，用此函数画出一个搜索树，一个解决问题的算法，并标明每个节点的评价函数值和在树上选择扩展节点的顺序。

第四，写出以下公式的斯科勒姆范式:

5.请用归结方法证明子句集不可满足。

6.请用回溯策略解决四皇后问题。其中，对角线函数diag(i，j)用于规则排序。如果Diag (i，j) < Diag (m，n)，则在排序中，规则Rij放在规则Rmn之前。Diag (i，j)定义为所用单元(I，j)的最长对角线的长度。