启发式搜索

✍ dations ◷ 2025-06-08 01:43:12 #算法

计算机科学中所谓的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产生的启发式算法优于任何先前存在的!而且它也发现了第一个有用的解魔术方块的启发式程序。

相关

  • 杜勒阿尔布雷希特·丢勒(德语:Albrecht Dürer,1471年5月21日-1528年4月6日)德国中世纪末期、文艺复兴时期著名的油画家、版画家、雕塑家及艺术理论家。他在二十多岁时高水准的木刻版
  • 直译直译(英语:literal translation,direct translation,word-for-word translation)即逐词翻译,是一种与意译(翻译句子或词组意义上的)相对的翻译方式。Literal translation的另一个术
  • 工商业工商业包括工业和商业两大部分。
  • 段玉裁段玉裁(1735年-1815年10月10日),字若膺,号茂堂,晚年又号砚北居士,长塘湖居士,侨吴老人。江苏金坛人。清朝语言学家,训诂家、经学家。雍正十三年乙卯(1735年),出生于江苏省金坛县西门外大
  • 谴责李顿报告(Lytton Report)是由国际联盟的李顿调查团在1932年发表的报告,用以协助调查及解决1931年的日本及中国之间发生的九一八事变。李顿调查团由英国的维克多·布尔沃-李顿,第
  • 广东人民抗日游击队东江纵队路东干部训练班广东人民抗日游击队东江纵队路东干部训练班,位于中国广东省东莞市东莞市清溪镇铁场村,为东莞市的一个市、县级文物保护单位,类型为近现代重要史迹及代表性建筑,公布时间为1982年
  • 半棒术半棒术,日本传统武术之一,为棒术或杖术的一种。棒术使用的棍棒长六尺,而半棒术使用长三尺(约90公分)的棍棒,因此得名。在明治年间之后,又被称为杖术,或半杖术。日本棒术一般使用六尺
  • 卡尔·西吉斯蒙德·孔茨卡尔·西吉斯蒙德·孔茨(Carl Sigismund Kunth,1788年6月18日-1850年3月22日)为德国植物学家。
  • 秦昌遇秦昌遇,字景明,号广埜山道人。中国明朝云间(今上海市松江区)人,医家。 生卒年不详。幼时聪明,因身体多病,遂学医。秦氏医技高超,其或病至沉笃时,张口瞑目,投剂能立起。,精小儿科与内科,
  • 全储备银行业务经济政策 财政政策 · 货币政策 贸易政策 · 投资政策 农业政策 · 产业政策 能源政策 · 社会政策 政策组合税收政策 · 预算政策 政府收入 · 政府支出 政府预算 · 赤