您的当前位置是：第三章 确定性推理>>学习内容>>知识点三

一、启发式搜索策略和估价函数

1．为什么需要启发式搜索

宽度优先搜索策略和深度优先搜索策略是盲目的搜索策略，因其OPEN中节点的排序盲目的而被称盲目搜索或无序搜索策略。状态空间搜索算法的任务在于搜寻状态空间中的目标节点。自然地，状态空间中，不同的节点导向目标节点的可能性是不同的。

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

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

启发式搜索（Heuristic Search）策略（一种有序搜索策略）试图利用问题的启发式信息帮助计算机更有效地求解问题，以表现出更强的智能特性。利用启发式信息的实际意义在于：

①缩小问题的搜索空间；

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

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

2．定义

搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。

有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活（但代价也较大）的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数（evalution function）。

3．估价函数

为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。

f（n）——表示节点n的估价函数值

定义估计函数没有固定模式，需要根据具体问题具体分析，可以参考的思路有：

①一个结点到目标结点的某种距离或差异的度量；

②一个结点处在最佳路径上的概率；

③根据经验主观打分。

例如8数码问题，目标状态如图3.16（a）所示，可以采用不同的启发式函数定义方法，例如，可以采用以下两种启发式函数定义方法，如图3.16（b）和图3.16（c）所示。

f1（T）=没有处在目标状态的字码数目（相当于粗略地给出了当前状态与目标的距离）

f2（T）=不在目标位置的数码距离目标位置水平距离和垂直距离之和。

1  2  3  4  5