启发式算法

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

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

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

启发式算法与最短路径问题

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

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

启发式算法对运算性能的影响

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

找寻新的启发式算法

如何找到一个分叉率较少又通用的合理启发式算法，已被人工智能社区深入探究过。他们使用几种常见技术：

部分问题的解答的代价通常可以评估解决整个问题的代价，通常很合理。例如一个10-puzzle拼盘，解题的代价应该与将1到5的方块移回正确位置的代价差不多。通常解题者会先创建一个存储部分问题所需代价的模式数据库（pattern database）以评估问题。

解决较易的近似问题通常可以拿来合理评估原先问题。例如曼哈顿距离是一个简单版本的n-puzzle问题，因为我们假设可以独立移动一个方块到我们想要的位置，而暂不考虑会移到其他方块的问题。

给我们一群合理的启发式函数h1(n),h2(n),...,hi(n){\displaystyle h_{1}(n),h_{2}(n),...,h_{i}(n)}，而函数h(n)=max{h1(n),h2(n),...,hi(n)}{\displaystyle h(n)=\max\{h_{1}(n),h_{2}(n),...,h_{i}(n)\}}则是个可预测这些函数的启发式函数。

一个在1993年由A.E. Prieditis写出的程序ABSOLVER就运用了这些技术，这程序可以自动为问题产生启发式算法。ABSOLVER为8-puzzle产生的启发式算法优于任何先前存在的！而且它也发现了第一个有用的解魔术方块的启发式程序。

参阅

人工智能

专家系统

Heuristic evaluation

推理机

Inquiry

解决问题

爬山算法

模拟退火算法

遗传算法

Tabu算法

最好优先

通用图

A*搜寻算法

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。