Loading AI tools
来自维基百科,自由的百科全书
计算机科学中所谓的heuristic,除了有经验法则的意思外(见启发式),它还有另外两个技术上的意义。
![]() | 此条目的语调或风格或许不合百科全书。 (2019年8月24日) |
此条目没有列出任何参考或来源。 (2013年9月30日) |
电脑科学的两大基础目标,就是发现可证明其执行效率良好且可得最佳解或次佳解的演算法。而启发式演算法则试图一次提供一个或全部目标。例如它常能发现很不错的解,但也没办法证明它不会得到较坏的解;它通常可在合理时间解出答案,但也没办法知道它是否每次都可以这样的速度求解。
有时候人们会发现在某些特殊情况下,启发式演算法会得到很坏的答案或效率极差,然而造成那些特殊情况的资料结构,也许永远不会在现实世界出现。因此现实世界中启发式演算法很常用来解决问题。启发式演算法处理许多实际问题时通常可以在合理时间内得到不错的答案。
有一类的通用启发式策略称为元启发算法(metaheuristic),通常使用乱数搜寻技巧。他们可以应用在非常广泛的问题上,但不能保证效率。
所谓的最短路径问题有很多种意思,在这里启发式指的是在一个搜寻树的节点上定义的函数,用于评估从此节点到目标节点成本最小的路径。启发式通常用于资讯充份的搜寻演算法,例如最好优先贪婪演算法与A*。最好优先贪婪演算法会为启发式函数选择最低代价的节点;A*则会为选择最低代价的节点,此是从起始节点到目前节点的路径的确实代价。如果是可接受的(admissible)意即未曾付出超过达到目标的代价,则A*一定会找出最佳解。
最能感受到启发式演算法好处的经典问题是n-puzzle。此问题在计算错误的拼图图形,与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时,使用了本演算法。注意,上述两条件都必须在可接受的范围内。
任何的搜寻问题中,每个节点都有个选择以及到达目标的深度,一个毫无技巧的演算法通常都要搜寻个节点才能找到答案。启发式演算法借由使用某种切割机制降低了分支因子(branching factor)以改进搜寻效率,由降到较低的。分叉率可以用来定义启发式演算法的偏序关系,例如:若在一个节点的搜寻树上,的分叉率较低,则。启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率,因此它们拥有较佳效率的计算能力。
如何找到一个分叉率较少又通用的合理启发式演算法,已被人工智慧社群[哪个/哪些?]深入探究过。他们使用几种常见技术:
一个在1993年由A.E. Prieditis写出的程式ABSOLVER就运用了这些技术,这程式可以自动为问题产生启发式演算法。ABSOLVER为8-puzzle产生的启发式演算法优于任何先前存在的!而且它也发现了第一个有用的解魔术方块的启发式程式。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.