启发式算法

计算机科学中所谓的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)$ 。启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率，因此它们拥有较佳效率的计算能力。