一、 选择


1、比起极小 -- 极大法来，α-β剪枝法增大了找不到最佳走步的危险性，但其效率较高。

A 对

B 错


2、在A算法中，满足单调条件的h必然满足A*算法的条件。

A 对

B 错


3、设有机器人走迷宫问题，其入口坐标为(x₀, y₀)，出口坐标为(x_t, y_t)，当前机器人位置为(x, y)，若定义， 当从入口到出口存在通路时，用A算法求解该问题，定能找到从入口到出口的最佳路径。

A 对

B 错

二、 填空题


1、在修正的A算法中，fm的含义是

2、对任意节点n，设m是n的子节点，当h满足条件时，称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)、用产生式系统描述该问题。(给出综合数据库，规则集，上述 知识要在规则集中反映出来)