2.4 启发式图搜索过程

　　启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。这种利用启发信息的搜索过程都称为启发式搜索方法。在研究启发式搜索方法时，先说明一下启发信息应用，启发能力度量及如何获得启发信息这几个问题，然后再来讨论算法及一些理论问题。
　　一般来说启发信息过弱，产生式系统在找到一条路径之前将扩展过多的节点，即求得解路径所需搜索的耗散值（搜索花费的工作量）较大；相反引入强的启发信息，有可能大大降低搜索工作量，但不能保证找到最小耗散值的解路径（最佳路径），因此实际应用中，希望最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路径的保证。这是一个重要而又困难的问题，从理论上要研究启发信息和最佳路径的关系，从实际上则要解决获取启发信息方法的问题。
　　比较不同搜索方法的效果可用启发能力的强弱来度量。在大多数实际问题中，人们感兴趣的是使路径的耗散值和求得路径所需搜索的耗散值两者的某种组合最小，更一般的情况是考虑搜索方法对求解所有可能遇见的问题，其平均的组合耗散值最小。如果搜索方法1的平均组合耗散值比方法2的平均组合耗散值低，则认为方法1比方法2有更强的启发能力。实际上很难给出一个计算平均组合耗散值的方法，因此启发能力的度量也只能根据使用方法的实际经验作出判断，没有必要去追求严格的比较结果。
　　启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度，我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。一种最常用的方法是定义一个评价函数f（Evaluation function）对各个子节点进行计算，其目的就是用来估算出"有希望"的节点来。如何定义一个评价函数呢？通常可以参考的原则有：一个节点处在最佳路径上的概率；求出任意一个节点与目标节点集之间的距离度量或差异度量；根据格局（博弈问题）或状态的特点来打分。即根据问题的启发信息，从概率角度、差异角度或记分法给出计算评价函数的方法。