第三章 本章练习参考答案

一、填空题（每空5分，共50分）

1．目标状态

2．最优性

3．广（宽）度

4．深度界限

5．优先搜索

6．评价函数

7．与或

8．β

9．子句

10．析取

二、简答题（本题50分）

1．①定义

如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。

②基本思想

从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。OPEN表中的节点总是按进入的先后排序排列，先进入的节点排在前面，后进入的节点排在后面。

③特点

这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

2．盲目的搜索策略或无序策略，没有任何先验信息可被用于OPEN表中节点的排序，只能盲目地选择被扩展的节点，因而，在状态空间中盲目地搜索目标。

任何问题都有与之相关的某些先验的信息，这些信息对于问题求解具有指导或启发的作用，因而被称之为启发式信息（Heuristic Information）。在问题求解过程中，人的智能行为很大程度上体现在人对启发式信息的利用方面。

利用启发式信息的实际意义在于：

①缩小问题的搜索空间；

②获得问题某种意义上的最优解。

启发信息的强度会影响搜索的结果，如果太强会降低搜索工作量，但可能导致找不到最优解；如果太弱一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。

3．①以当前考察的态势P为根节点，生成指定深度的博弈树。

②根据静态估计函数f计算各叶节点的估计值。

③自底向上计算各个非叶节点的估计值，计算的方法是MAX节点取其子节点的最大值，MIN节点取其子节点的最小值。

④将根节点的倒推值对应的策略作为当前的最佳策略。

4．①把谓词公式转化为子句集S（所有子句的变量名不同）；

②如空子句成为子句集的子句，则算法结束；

③在子句集中选取两个不同的可以消解的子句c_i，c_j；

④计算c_i，c_j的消解式r_ij；

⑤把r_ij加到子句集中，形成新的子句集S；

⑥转到②。