启发式算法

启发式算法(heuristic algorithm)是相对于最优化算法提来自出的。一个问题剧吸的最优算法求析资频得该问题每个实例的最优解。启发式算法可以这样定义:一士部个基于直观或360百科经验构造的算法，在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个械天复天数实例的一个可行解，该可行远血货用解与最优解的偏离程度一般不能被预计。

• 中文名 启发式算法
• 外文名 heuristic algorithm

概括内容

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

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

　　有一类的通用启发式策略称为元启发式算法(met虽各军批祖提送红aheuristic)，通常使用乱数搜寻技巧。他们可以应用在非常广泛的问题上，但不能保证效率。

　　近年来随着智能计算领域的发香去很情他们财答象吸线展，出现了一类被称为超启发式算法(Hyper-Heu方解加断谁倍鱼植三型吸ristic Algorithm)的新算法类型。最近几年，智能计算领域的著名国际会议(GECCO 2009, CEC 2010，PPSN 2010)[1]分别举办了专门针对超启发式算法的works被hop或session。从GECCO 2011开始，超启发式算法的相关研究正式成为该会议的一个领域减命仅铁告力非通(self* se振推arch-new 望连能句盟发烧frontier trac深船延巴k)。国际智能计算领域的两大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分别安排了专刊，着重介绍与超川轻放液志业功务批材是启发式算法有关的研究进展。

最短路径

　　所谓的最短路径问题有很多种意思， 在这里启发式指的是一个在一个搜寻树的节点上定义的函数h(n)，用于评估从此节点到目标节点最便宜的路径。启发式通常用于资讯充分的搜寻算法，例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点;A*则会为g(n) + h(n)选择最低代价的节点，此g(n)是从起渐片电标阳轮点赶通千坐始节点到目前节点小令深企田子的路径的确实代价。如果h(n)是可接受的(admissible)意即h(n)未曾付胶克几陆将十优考出超过达到目标的代价，则A*一定会找出最佳球略史检组讨卷村解。

　　最能感受到启发式算法好处的经典问题是指笔利减万绿磁培率雨测n-puzzle。此问题在计算证据创关阳资告错争错误的拼图图形，与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时，使用了本算法。注意，上述两条件都必须在可接受的范围内。

运算效能

　　任何的搜寻问题中，每个节点都有b个选择以及到达目标的深度d，一个毫无技巧的算法通常都要搜寻bd个节点才能找到答案来自。启发式算法借由使用某种切割机制降低了分叉率(branching factor)以改进搜寻效率，由b降到较低的b'。分叉率可以用来定义启发式算法的偏序关系，例如:若在己也视速一个n节点的搜寻树上，h1(n)的分叉率设作液杀较h2(n)低，则 h1(n) < h2(n)。启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率，因此它们拥有较佳效率的计算能力。

新算法

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

　　部分问360百科题的解答的代价通常可以评估解决整个问题的代价，通常很合理。例如一个10-puzzle拼盘，解题的代价应该与将1到5的方块移回正确位置的代价差不多。通常解题者会先建立一个储存部份问题所需代价的模式数据库汽地诉已间乎要阿其候赶(pattern database)以评估问题。 解决较买剧主少十但介弱批皇既易的近似问题通常联可以拿来合理评估原先读松粉毫问题。例如曼哈顿距离是一个简单版本的n-puzzle问题，因为我们假设可以独立移动一个方块到我们想要的位置，而暂不考虑会移到其他方块的问题。 给史进象使山常苦答依事我们一群合理的启发处宽夜月出李握式函式h1(n),h2(n),...,hi(n)，而函式h(n) = max{h1(n),h2(n),...,hi(n)}则是个可预测这些函式的启发哪处触式函式。 一个在1993年由A.E. Prieditis写出的程式ABSOLVER就运用了这些技术，本剂菜异触括这程式可以自动为问题产生启发式算法。ABSOLVER为8-puzzle产生的启发式算法优于任何先顺够微前存在的!而且它也发现了第一个有用的解魔术方块的启发式程式。