启发式算法

电脑科学中所谓的heuristic，除了有经验法则的意思外（见启发式），它还有另外两个技术上的意义。

启发式算法[编辑]

电脑科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一个或全部目标。例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据结构，也许永远不会在现实世界出现。因此现实世界中启发式算法很常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。

有一类的通用启发式策略称为元启发算法（metaheuristic），通常使用随机数搜索技巧。他们可以应用在非常广泛的问题上，但不能保证效率。

启发式算法与最短路径问题[编辑]

所谓的最短路径问题有很多种意思，在这里启发式指的是在一个搜索树的节点上定义的函数 $h(n)$ ，用于评估从此节点到目标节点成本最小的路径。启发式通常用于资讯充份的搜索算法，例如最好优先贪心算法与A*。最好优先贪心算法会为启发式函数选择最低代价的节点；A*则会为 $g(n)+h(n)$ 选择最低代价的节点，此 $g(n)$ 是从起始节点到目前节点的路径的确实代价。如果 $h(n)$ 是可接受的（admissible）意即 $h(n)$ 未曾付出超过达到目标的代价，则A*一定会找出最佳解。

最能感受到启发式算法好处的经典问题是n-puzzle。此问题在计算错误的拼图图形，与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时，使用了本算法。注意，上述两条件都必须在可接受的范围内。

启发式算法对运算性能的影响[编辑]

任何的搜索问题中，每个节点都有 $b$ 个选择以及到达目标的深度 $d$ ，一个毫无技巧的算法通常都要搜索 $b^{d}$ 个节点才能找到答案。启发式算法借由使用某种切割机制降低了分支因子（branching factor）以改进搜索效率，由 $b^{d}$ 降到较低的 $b'$ 。分叉率可以用来定义启发式算法的偏序关系，例如：若在一个 $n$ 节点的搜索树上， $h_{1}(n)$ 的分叉率较 $h_{2}(n)$ 低，则 $h_{1}(n)<h_{2}(n)$ 。启发式为每个要解决特定问题的搜索树的每个节点提供了较低的分叉率，因此它们拥有较佳效率的计算能力。