人工智能交大题目及答案（精编版）.pdf

. 1 / 8 人工智能导论全真试题一、 判断题（在单项选择框选择）1、只有在单位耗散值的情况下，当问题有解时，宽度优先算法才能保证找到最优解2、在 A*算法完毕之前， OPEN 表中任何满足 f(n)f*(s)的节点 n，一定被扩展3、设有机器人走迷宫问题，其入口坐标为(x0, y0) ，出口坐标为 (xt, yt)，当前机器人位置为(x, y)，若定义， 当从入口到出口存在通路时，用A算法求解该问题，定能找到从入口到出口的最正确路径4、在 A算法中，满足单调条件的h 必然满足 A*算法的条件5、比起极小 - 极大法来，- 剪枝法增大了找不到最正确走步的危险性，但其效率较高二、 填空题（在横线上作答）1、基于规则的正向演绎系统使用的条件是（1）事实表达式是（2）规则形式为， 其中（3） 目标公式为2、基于规则的逆向演绎系统使用的条件是（1）事实表达式是（2）规则形式为， 其中（3）目标公式为3、归结法中，可以通过的方法得到问题的解答三、 问答题（在每题下面的空白框上作答）1、某问题状态图如右图所示假定k 连接符的耗散值为k 各节点的 h 值假定为：h(A)=3, h(B)=2, h(C)=6, h(D)=3, h(E)=4, h(F)=2, h(G)=3, h(H)=h(I)=0 (目标节点 ) 用 AO* 算法求解该问题，给出每次循环后的搜索图，并给出求得的解图。

. 2 / 8 3、有四人过河，只有一条船，最多可乘坐两人若单个过，各需1，1，5，9分钟，若两人一起过， 则需要的时间以多的为准 （如需要 5 分和 9 分的两人同时乘坐，则需要 9 分）问最少需要多少分钟1) 、用产生式系统描述该问题，要求给出综合数据库的定义，规则集，初始状态和完毕状态2) 、定义一个 h 函数，并说明是否满足A*条件3) 、用 A算法求解该问题，给出状态搜索图，标出扩展次序、各节点的f值、解路径与解路径的耗散值4、某问题由以下公式描述：(1) 、（ s）P（s）(2) 、（s）（P（g（s）(3) 、（ x）（s）（ y）（ P（s）Q （b，x，s）H （y）(4) 、（x）（s）（Q （b，x，s）Q （b，x，g（s）(5) 、（x）（s）（ y）（P（s）Q （b，x，y）求证： ( x)H(x) 请用基于规则的逆向演绎系统求解( x)H(x)成立要求给出一个求得的一致解图，并说明为什么它是一致的；给出目标的解答5、简述为什么修正的A*算法有可能会减少重复节点的扩展，而又不会比 A*多扩展节点6、给 19 九个数字排一个序列，使得该序列的前n(n=1,.,9) 个数字组成的整数能被 n 整除。

1) 、讨论哪些知识可以帮助该问题的求解2) 、用产生式系统描述该问题 给出综合数据库，规则集，上述知识要在规则集中反映出来 ) . . 3 / 8 7、某问题的状态空间图如以下图所示，其中括号标明的是各节点的h 值，弧线边的数字是该弧线的耗散值， 试用 A算法求解从初始节点S到目标节点 T的路径要求给出搜索图， 标明各节点的 f 值，与各节点的扩展次序， 并给出求得的解路径三、 问答题答案第 1 题答：. . 4 / 8 得解图：. . 5 / 8 第 3 题答： 综合数据库：(m1, m5, m9, b) 设从河的左岸到右岸，其中m1, m5,m9分别表示过河时间需要 1 分钟，5 分钟和 9 分钟的人，在河左岸的人数 b1 表示船在左岸， b0表示船在右岸规则集：初始状态：(2, 1, 1, 1) 完毕状态(0, 0, 0, 0) h 函数：h(n) = m - b，其中 m为在左岸的人数， b 为船是否在左岸对于任意两个节点ni 和 nj ，其中 nj 是 ni 的子节点当 ni 中 b1 时，则 nj 中 b0，因此： max(h(ni)-h(j)=(m-1)-(m-1)=0, 而C(ni, nj)最小为 1，因此 h(ni)-h(nj)C(ni, nj); 当 ni 中 b0 时，则 nj 中 b1，因此：max(h(ni)-h(j)=m-m=0, 而 C(ni, nj). . 6 / 8 最小为 1，因此 h(ni)-h(nj)C(ni, nj)。

而对于目标节点 t ，h(t)=0 因此该 h 函数满足单调性条件所以h 满足 A*条件第 4 题答： 对事实和规则进行 skolem 化：（1）( s) P(a) （2）(s)(P(g(s) P(g(s) （3）( x)(s)(y)(P(s)Q(b，x，s) H(y)(P(s) Q(b，c，s) H(f(s) （4）(x)(s)(Q(b ，x，s) Q(b，x，g(s) Q(b，x，s) Q(b，x，g(s) （5）(x)(s)(y)(P(s) Q(b，x，y) P(s) Q(b，x，h(x, s) 经变量换名后，有事实和规则如下：P(a) P(g(s1) r1: (P(s2)Q(b，c，s2) H(f(s2)r2: Q(b ，x3，s3)Q(b，x3，g(s3) r3: P(s4)Q(b，x4，h(x4, s4) 用对偶形式对目标skolem 化：( x)H(x) H(x) 演绎图如以下图 (这里只给出了一个一致解图) . 7 / 8 由置换集构造 U1和 U2 ：U1 = (x, s2, x3, s2, x4, s3, s4) U2 = (f(s2), g(s1), c, g(s3), c, h(x4, s4), a) 由于 U1和 U2是可合一的，因此该解图是一致解图。

合一复合为：f(g(h(c, a)/x, g(h(c, a)/s2, c/x3, h(c, a)/s3, c/x4, h(c, a)/s1, a/s4 将该合一复合带入目标中，得到解答：x = f(g(h(c, a) 第 5 题答：1、 由于修正的 A*算法对与 OPEN 表中 f 值小于 fm的节点按照 g 值的大小排序，优先扩展 g 值小的节点对于这部分节点来说，相当于h0而 h0 满足单调条件，因此至少对于这部分节点来说，减少了重复扩展节点的可能性因此修正的 A*算法有可能减少重复节点的扩展 . 8 / 8 2、由于 A*扩展的节点， 其 f 值总是小于等于 f*(s)，而 fm 是到目标为止扩展过的节点的最大 f 值， 因此必有 fm小于等于 f*(s) 又由于 OPEN 表中 f 值小于 f*(s)的节点，总是被 A*扩展的，因此从OPEN 表中选择那些 f 值小于 fm 的节点（这些节点的 f 值也必然小于 f*(s)），按照 g 值的大小优先扩展，只是改变了部分节点的扩展次序，不会多扩展节点第 6 题答：如下的知识可以帮助求解该问题：（1）序列中，偶数在偶数位置，奇数在奇数位置；（2）第五个数为 5。

综合数据库：用一个 1 到 9 的序列表示： N = x ，其中 x 为 1 到 9 的数字之一规则集：r1: IF len(N)=4 THEN x5 r2: IF len(N)为偶数 and n=In(1, 3, 7, 9) THEN xn r3: IF len(N)为奇数 and n=In(2, 4, 6, 8) THEN xn 其中 len(N) 为求序列的长度， In(a, b, c, d)为取 a、b、c、d 之一初始状态： 完毕条件：得到的序列N前 i 个数组成的整数能被i 整除第 7 题答：搜索图如下图，其中括号标出的是节点的f 值，圆圈的数字是扩展的次序F(16) 得到的解路径为： S-B-F-J-T 。