一、 选择


1、只有在单位耗散值的情况下，当问题有解时，宽度优先算法才能保证找到最优解。

A 对

B 错

2、在A*算法结束之前，OPEN表中任何满足f(n)<f*(s)的节点n，一定被扩展。

A 对

B 错

二、 填空题

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、下图所示博弈树，按从左到右的顺序进行α-β剪枝搜索，试标明各生成节点的到推值，何处发生剪枝，及应选择的走步。

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*多扩展节点。