搜索
《人工智能导论》全真试题一、判断题（在单选框内选择）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*算法求解该问题，给出每次循环后的搜索图，并给出求得的解图。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、给1～9九个数字排一个序列，使得该序列的前n(n=1,...,9)个数字组成的整数能被n整除。(1)、讨论哪些知识可以帮助该问题的求解。(2)、用产生式系统描述该问题。(给出综合数据库，规则集，上述知识要在规则集中反映出来)7、某问题的状态空间图如下图所示，其中括号内标明的是各节点的h值，弧线边的数字是该弧线的耗散值，试用A算法求解从初始节点S到目标节点T的路径。要求给出搜索图，标明各节点的f值，及各节点的扩展次序，并给出求得的解路径。三、问答题答案第1题答：得解图：第3题答：综合数据库：(m1,m5,m9,b)设从河的左岸到右岸，其中m1,m5,m9分别表示过河时间需要1分钟，5分钟和9分钟的人，在河左岸的人数。b＝1表示船在左岸，b＝0表示船在右岸。规则集：初始状态：(2,1,1,1)结束状态(0,0,0,0)h函数：h(n)=m-b，其中m为在左岸的人数，b为船是否在左岸。对于任意两个节点ni和nj，其中nj是ni的子节点。当ni中b＝1时，则nj中b＝0，因此：max(h(ni)-h(j))=(m-1)-(m-1)=0,而C(ni,nj)最小为1，因此h(ni)-h(nj)C(ni,nj);当ni中b＝0时，则nj中b＝1，因此：max(h(ni)-h(j))=m-m=0,而C(ni,nj)最小为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)演绎图如下图(这里只给出了一个一致解图)。由置换集构造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值小的节点。对于这部分节点来说，相当于h＝0。而h＝0满足单调条件，因此至少对于这部分节点来说，减少了重复扩展节点的可能性。因此修正的A*算法有可能减少重复节点的扩展。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:IFlen(N)=4THEN{x}∪{5}r2:IFlen(N)为偶数andn=In(1,3,7,9)THEN{x}∪{n}r3:IFlen(N)为奇数andn=In(2,4,6,8)THEN{x}∪{n}其中len(N)为求序列的长度，In(a,b,c,d)为取a、b、c、d之一。初始状态：{}结束条件：得到的序列N前i个数组成的整数能被i整除。第7题答：搜索图如图所示，其中括号内标出的是节点的f值，圆圈内的数字是扩展的次序。F(16)得到的解路径为：S-B-F-J-T