搜索
《人工智能导论》试卷一、选择1、比起极小--极大法来，α-β剪枝法增大了找不到最佳走步的危险性，但其效率较高。A对B错2、在A算法中，满足单调条件的h必然满足A*算法的条件。A对B错3、设有机器人走迷宫问题，其入口坐标为(x0,y0)，出口坐标为(xt,yt)，当前机器人位置为(x,y)，若定义，当从入口到出口存在通路时，用A算法求解该问题，定能找到从入口到出口的最佳路径。A对B错答案：BAA二、填空题1、在修正的A算法中，fm的含义是2、对任意节点n，设m是n的子节点，当h满足条件时，称h是单调的。答案1、在修正的A算法中，fm的含义是到当前为止，扩展的节点中，f的最大值2、对任意节点n，设m是n的子节点，当h满足条件h(n)-h(m)≤C(n,m),h(t)=0时，称h是单调的。三、问答题1、简述用A*算法求解问题时为什么会出现重复扩展节点问题，解决的方法有哪些？2、简述回溯策略与深度优先策略的不同点。3、某问题由下列公式描述：(1)、试用归结法证明(x)R(x)；(2)、做出修改证明树，提取问题的回答。4、下图所示博弈树，按从左到右的顺序进行α-β剪枝搜索，试标明各生成节点的到推值，何处发生剪枝，及应选择的走步。5、某问题的状态空间图如下图所示，其中括号内标明的是各节点的h值，弧线边的数字是该弧线的耗散值，试用A算法求解从初始节点S到目标节点T的路径。要求给出搜索图，标明各节点的f值，及各节点的扩展次序，并给出求得的解路径。6、给1～9九个数字排一个序列，使得该序列的前n(n=1,...,9)个数字组成的整数能被n整除。(1)、讨论哪些知识可以帮助该问题的求解。(2)、用产生式系统描述该问题。(给出综合数据库，规则集，上述知识要在规则集中反映出来)重置问答题答案第1题答：当问题有解时，A*算法总是找到问题的最优解结束。如果h函数定义的不合理，则当扩展一个节点时，不一定就找到了从初始节点到该节点的最优路径，对于这样的节点，就有可能被多次扩展。特别是如果这样的节点处于问题的最优解路径上时，则一定会被多次扩展。解决的方法一是对h函数的定义给出限制，使得h满足单调性。对于满足单调性条件的h，则一定不会出现重复扩展节点问题。二是对A*算法加以改进，使用修正的A*算法进行搜索，则可以减少重复扩展节点问题。第2题答：回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索，而回溯搜索则不是图搜索。在回溯搜索中，只保留了从初始节点到当前节点的搜索路径。而深度优先搜索，则保留了所有的已经搜索过的路径。第3题答：化子句集如下：归结树如下：修改证明树：得到问题的解答：R(h(f(g(c,a))))第4题第5题答：搜索图如图所示，其中括号内标出的是节点的f值，圆圈内的数字是扩展的次序。F(16)得到的解路径为：S-B-F-J-T第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整除。