启发式搜索

✍ dations ◷ 2025-04-26 16:35:45 #算法

计算机科学中所谓的heuristic,除了有经验法则的意思外(见启发式),它还有另外两个技术上的意义。

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

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

有一类的通用启发式策略称为元启发算法(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} ,一个毫无技巧的算法通常都要搜索 b d {\displaystyle b^{d}} 个节点才能找到答案。启发式算法借由使用某种切割机制降低了分支因子(branching factor)以改进搜索效率,由 b d {\displaystyle b^{d}} 降到较低的 b {\displaystyle b'} 。分叉率可以用来定义启发式算法的偏序关系,例如:若在一个 n {\displaystyle n} 节点的搜索树上, h 1 ( n ) {\displaystyle h_{1}(n)} 的分叉率较 h 2 ( n ) {\displaystyle h_{2}(n)} 低,则 h 1 ( n ) < h 2 ( n ) {\displaystyle h_{1}(n)<h_{2}(n)} 。启发式为每个要解决特定问题的搜索树的每个节点提供了较低的分叉率,因此它们拥有较佳效率的计算能力。

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

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

相关

  • 植物生态学植物生态学是生态学的一个分支学科,它研究植物的分布和数量,环境因素对植物的丰度的影响,植物和其他生物之间的相互作用。它们的实例是在北美温带落叶林的分布,沙漠植物对水的竞
  • 雷克雅未克雷克雅未克(冰岛语:Reykjavík,冰岛语音标: .mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000"
  • 白糖糕伦教糕(亦作伦滘糕),又称白糖糕,是中国广东珠江三角洲使用白米及白糖制成的传统小吃。始创于明朝时顺德伦教(古称伦滘)的一梁姓小贩。据说该小贩蒸松糕时失手,令粉质下坠,但蒸出来的
  • 禽鸟鸟或者鸟类是鸟纲(学名:Aves)动物的通称,是唯一存活至今的恐龙,现代所有鸟类在生物学上也被分类为鸟形恐龙(即鸟翼类)的一部分;鸟纲的全体成员均为两足、恒温、卵生、身披羽毛且色彩
  • 鳕角鳕鱼角(英语:Cape Cod),是美国东北部马萨诸塞州伸入大西洋的一个半岛,面积1033平方公里。1914年,美国在该半岛与大陆连接处开掘鳕鱼角运河,使鳕鱼角实际上成为了一个岛屿。
  • 名讳名讳是对本名的另一称呼。不少文化中都有本名与灵魂相连的宗教思想,因此对本名用字有一定的要求和禁忌,日常使用中也有特别注意之处,在英语中称为“True name”。在中国、日本
  • 陈颙 (地球物理学家)陈颙(1942年12月31日-),生于重庆,籍贯江苏宿迁,中国地球物理学家,中国地震局研究员。曾任国家地震局副局长、地球物理研究所所长,国际地震学和地球内部物理学会(IAPEI)的地震预报和地
  • 超高速超高速(英语:Hypervelocity)是指一个非常高的速度,一般超过3,000m/s(6,700mph,11,000km/h,10,000ft/s,或8.8马赫)。在超高速的速度下发生碰撞时,材料的强度与惯性应力相比会变得非常小
  • 2-乙基丁酸2-乙基丁酸,结构式CH3CH2CH(C2H5)COOH。无色透明液体。溶于醇、醚。1、由2-乙基丁醇氧化而得。2、由3-戊醇在硫酸作用下于15~20°C与无水甲酸反应而得。用于生产增塑剂、防腐
  • 勒内·马格里特勒内·弗朗索瓦·吉兰·马格里特(法语:René François Ghislain Magritte,1898年11月21日-1967年8月15日)是比利时超现实主义画家,并且因为其超现实主义作品中带有些许诙谐以及许