启发式搜索

✍ dations ◷ 2025-06-28 19:17:58 #算法

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

相关

  • EET欧洲东部时间(Eastern European Time,缩写EET)是比世界标准时间(UTC)早二个小时的时区名称之一。它被部分欧洲国家、北非国家和中东国家采用。其中大部分国家夏季采用欧洲东部夏
  • 王世芳王世芳(?-?),字济美,直隶苏州府太仓州人,军籍,明朝政治人物。应天府乡试第二十二名,正德十六年(1521年),登第二甲第四十五名进士。官按察司提学副使。曾祖王辂;祖父王侨;父王悌,母陆氏。
  • 三王群岛三王群岛 (英语:Three Kings Islands,毛利语:Manawa-tawhi 或 Ngā Motu Karaka),是新西兰的一个群岛,由13个岛屿组成,位于北岛西北端雷恩加角西北方,滨临南太平洋与塔斯曼海。三王
  • NBA明星队赛NBA全明星赛(All-Star Game),是美国国家篮球协会举办的年度球星表演赛,由观众和教练选出全联盟的明星球员分别代表东部和西部出战,是NBA全明星周末的压轴比赛。第一届全明星赛是1
  • 日本动漫动漫是动画或漫画的合称与缩写,原意也是动画和漫画,但现代一般词意(被误解成)单纯的指是动画或是漫画,并且为了区别对“动画等于幼稚”这种刻板印象而才有了动漫现代大部分误解的
  • 路易·奥古斯特·布朗基路易·奥古斯特·布朗基(法语:Louis Auguste Blanqui;1805年2月1日-1881年1月1日)是一位法国社会主义者和政治活动家,曾以领导人的身份参与过1871年在法国爆发的巴黎公社。布朗基
  • ChinaChina可能是指:
  • 心灵独奏《心灵独奏》(英语:The Soloist),是2009年由乔·莱特执导的一部美国剧情片。主演是杰米·福克斯和小罗伯特·唐尼。该影片于2009年4月24日在电影院上演,影片DVD和蓝光DVD于同年8
  • 小立陶宛小立陶宛(立陶宛语:Mažoji Lietuva;德语:Kleinlitauen;波兰语:Litwa Mniejsza;俄语:Máлая Литвá),又称普鲁士立陶宛(立陶宛语:Prūsų Lietuva;德语:Preußisch-Litauen;波兰语:Li
  • 阪神间现代主义阪神间现代主义(日语:阪神間モダニズム/はんしんかんもだにずむ )是指在公元1900年代至1930年代的日本近畿地方,以受六甲山系与海洋围绕的阪神间(现今的兵库县神户市中央区、滩区