人工智能导论全真试题窗体顶端一、 判断题（在单选框内选择）、只有在单位耗散值的状况下,当问题有解时,宽度优先算法才干保证找到最优解。、在A算法结束之前,OPEN表中任何满足（n)f*(s)的节点n,一定被扩展。3、设有机器人走迷宫问题，其入口坐标为(x，0）,出口坐标为(xt, yt)，目前机器人位置为（x, y）,若定义, 当从入口到出口存在通路时，用算法求解该问题，定能找到从入口到出口的最佳途径。4、在算法中，满足单调条件的h必然满足A*算法的条件。5、比起极小- 极大法来，-剪枝法增大了找不到最佳走步的危险性，但其效率较高。 窗体底端窗体顶端二、 填空题(在横线上作答)、基于规则的正向演绎系统使用的条件是(1)事实体现式是(2）规则形式为，其中(3)目的公式为、基于规则的逆向演绎系统使用的条件是()事实体现式是（2)规则形式为， 其中(3）目的公式为3、归结法中，可以通过的措施得到问题的解答。三、 问答题(在每题下面的空白框上作答)1、某问题状态图如右图所示。假定k连接符的耗散值为k。 各节点的h值假定为：h(A)3, h(B)=2, h(C)=6, h(D)=3,(），（)=, (G)=, h（）（I)=0 (目的节点)用AO算法求解该问题， 给出每次循环后的搜索图， 并给出求得的解图。3、有四人过河,只有一条船，最多可乘坐两人。若单个过，各需，,5，9分钟，若两人一起过，则需要的时间以多的为准(如需要分和9分的两人同步乘坐，则需要9分）。问至少需要多少分钟。 (1)、用产生式系统描述该问题,规定给出综合数据库的定义，规则集，初始状态和结束状态。 (2)、定义一种h函数,并阐明与否满足A*条件。(3)、用算法求解该问题，给出状态搜索图，标出扩展顺序、各节点的f值、解途径及解途径的耗散值。4、某问题由下列公式描述:（1)、（s)P（）(2）、（s)（g()）) (3)、（)（）（y）（(P(s）Q（b，x,s）（y） (4)、(x)()(Q(b,x,s）（b，x，（s)） (）、（x）()（y）（P（）Q（b,x，y)）求证：()H(） 请用基于规则的逆向演绎系统求解( x)（x)成立。规定给出一种求得的一致解图,并阐明为什么它是一致的；给出目的的解答。5、简述为什么修正的A算法有也许会减少反复节点的扩展，而又不会比A*多扩展节点。窗体底端6、给1九个数字排一种序列,使得该序列的前n(n=，.,) 个数字构成的整数能被整除。 (1)、讨论哪些知识可以协助该问题的求解。(2)、用产生式系统描述该问题。(给出综合数据库，规则集，上述 知识要在规则集中反映出来)7、某问题的状态空间图如下图所示，其中括号内标明的是各节点的h值，弧线边的数字是该弧线的耗散值，试用A算法求解从初始节点S到目的节点T的途径。规定给出搜索图，标明各节点的值，及各节点的扩展顺序,并给出求得的解途径。三、 问答题答案第1题答:得解图：第题答： 综合数据库:(1, 5， m， b）设从河的左岸到右岸,其中m1,m,分别表达过河时间需要1分钟,5分钟和9分钟的人,在河左岸的人数。b=1表达船在左岸,=表达船在右岸。 规则集： 初始状态:(，1， 1，)结束状态(0， , , )h函数：（n) = m -,其中m为在左岸的人数,b为船与否在左岸。对于任意两个节点n和j,其中nj是ni的子节点。当ni中b=1时,则nj中b=0，因此：max(（n)-h（j)=(m-)-(m-1)， 而C(， nj)最小为1,因此h(ni)-(n)(ni,n);当ni中b0时，则n中b=1，因此：mx(h(i)（j）)=-m0，而（i, j)最小为,因此(ni)h（nj）(ni, j)。而对于目的节点t，h()0。因此该h函数满足单调性条件。因此h满足条件。第4题答: 对事实和规则进行sole化：(1）(s)（a) (2)(s）(（s)P(g（) (3）()(s）(y)（(s)Q(,x,)H(y） (P(s)Q(b,c，s)）(f(s)（4)（x）(s）(Q（b，,s)Q(，x,g() Q(b，,s)Q（b，g(s) (5)(x)(s)(y）(P()(b,y）) P(s）Q（b，x,h(,s)经变量换名后，有事实和规则如下: (a)P（g(1） r1： （P（2)(b,c，s2)）H(f（2）)r: Q(b,x3,3)(,x3，g(s3)r3: P(s4)(b，x4，h(x， s)用对偶形式对目的som 化:(）()H(x)演绎图如下图(这里只给出了一种一致解图)。由置换集构造U1和U2:U1 = (x, s2，s2， x4， s3,s4）U2 （f(2）,g(s), , g（s3),c, h(4, s4), a） 由于U1和是可合一的，因此该解图是一致解图。合一复合为:f(g（h(， a）)x,g(h(,a)2, cx3，h（,a）/s3,c4,h（c,)/s1, a/s4 将该合一复合带入目的中，得到解答:x = f（g(h(c, ) 第5题答: 1、由于修正的*算法对与OPE表中f值不不小于m的节点按照值的大小排序，优先扩展g值小的节点。对于这部分节点来说,相称于h0。而h=0满足单调条件，因此至少对于这部分节点来说,减少了反复扩展节点的也许性。因此修正的A*算法有也许减少反复节点的扩展。 、由于扩展的节点，其值总是不不小于等于f(s),而f是到目的为止扩展过的节点的最大f值，因此必有fm不不小于等于f(s)。又由于OPN表中f值不不小于f(s)的节点,总是被A扩展的，因此从ON表中选择那些f值不不小于fm的节点（这些节点的f值也必然不不小于f*（s），按照g值的大小优先扩展,只是变化了部分节点的扩展顺序，不会多扩展节点第6题答：如下的知识可以协助求解该问题:（1）序列中,偶数在偶数位置,奇数在奇数位置;()第五个数为。综合数据库:用一种1到9的序列表达:N = x,其中x为1到的数字之一。规则集：r:Ile（N)=4 TEN x2: IF len(N）为偶数and =In(, , 7，) THN r:F len(N)为奇数andnn（， 4,6,8） THN xn其中le(N)为求序列的长度,In(a，b, d)为取a、b、c、d之一。初始状态：结束条件:得到的序列N前个数构成的整数能被i整除。第7题答:搜索图如图所示，其中括号内标出的是节点的f值，圆圈内的数字是扩展的顺序。（16) 得到的解途径为:S-F-J-