[科普中国]-启发式搜索

简介

启发式策略可以通过指导搜索向最有希望的方向前进，降低了复杂性。通过删除某些状态及其延伸，启发式算法可以消除组合爆炸，并得到令人能接受的解(通常并不一定是最佳解)。

然而，启发式策略是极易出错的。在解决问题的过程中启发仅仅是下一步将要采取措施的一个猜想，常常根据经验和直觉来判断。由于启发式搜索只有有限的信息(比如当前状态的描述)，要想预测进一步搜索过程中状态空间的具体行为则很难。一个启发式搜索可能得到一个次最佳解，也可能一无所获。这是启发式搜索固有的局限性。这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来消除。一般说来，启发信息越强，扩展的无用节点就越少。引入强的启发信息，有可能大大降低搜索工作量，但不能保证找到最小耗散值的解路径(最佳路径)。因此，在实际应用中，最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路径的保证。1

估价函数用于评价节点重要性的函数称为估价函数，其一般形式为

式中：g(x)为从初始节点到节点x付出的实际代价；h(x)为从节点x到目标节点的最优路径的估计代价。启发性信息主要体现在h(x)中，其形式要根据问题的特性来确定。

虽然启发式搜索有望能够很快到达目标节点，但需要花费一些时间来对新生节点进行评价。因此，在启发式搜索中，估计函数的定义是十分重要的。如定义不当，则上述搜索算法不一定能找到问题的解，即使找到解，也不一定是最优的。

有序搜索算法（A算法）在启发式搜索算法中，根据估价函数值，按由小到大的次序对Open表中的节点进行重新排序，这就是有序搜索法。因此，此时的Open表是一个按节点的启发估价函数值的大小为序排列的一个优先队。

有序搜索算法如下：

①将初始节点S0放入Open表中；

②如Open表为空，则搜索失败，退出；

③把Open表的第一个节点取出，放入到Closed表中，并把该节点记为节点n；

④如果节点n是目标节点，则搜索成功，求得一个解，退出；

⑤扩展节点n，生成一组子节点，对既不在Open表中也不在Closed表中的子节点，计算出

相应的估价函数值；

⑥把节点n的子节点放到Open表中；

⑦对Open表中的各节点按估价函数值从小到大排列；

⑧转到②。

对上述算法分析可以发现，如果取估价函数等于节点深度，则它将退化为广度优先搜索。

A*算法在A*算法中，启发性信息用一个特别的估价函数f*来表示：f*(x)=g*(x)+h*(x)

式中：g*(x)为从初始节点到节点x的最佳路径所付出的代价；h*(x)是从x到目标节点的最佳路径所付出的代价；f*(x)是从初始节点出发通过节点x到达目标节点的最佳路径的总代价。

基于上述g*(x)和h*(x)的定义，对启发式搜索算法中的g(x)和h(x)做如下限制：

①g(x)是对g*(x)的估计，且g(x)>0；

②h(x)是h*(x)的下界，即对任意节点x均有h(x)≤h*(x)。

在满足上述条件情况下的有序搜索算法称为A*算法。

对于某一搜索算法，当最佳路径存在时，就一定能找到它，则称此算法是可纳的。可以证明，A*算法是可纳算法。也就是说，对于有序搜索算法，当满足h(x)≤h*(x)条件时，只要最佳路径存在，就一定能找出这条路径。2