启发式搜索

✍ dations ◷ 2025-04-05 00:36:32 #算法

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

相关

  • 行为行为是指有机体(包括人类与其他动物)的动作、行动方式,以及对所处环境与其他生物体或物体的一种反应。词性为中性。在生物适应环境上,行为有很重要的意义,有助于避免受到负面的环
  • Ma年,或称地球年、太阳年,是与地球在轨道上绕太阳公转有关事件再现之间的时间单位。将之扩展,可以适用于任何一颗行星:例如,一“火星年”是火星自己完整的运行绕太阳轨道一圈的时间
  • 金矿金矿开采是指从富含金的地层中开采黄金的过程。目前有多种技术可以从地层中开采出黄金,最原始的方法是淘金。目前工业上多用氰化法提纯金,但氰化物有毒,因此正在开发新的提金试
  • 纳波莱奥内·费拉拉纳波莱奥内·费拉拉(意大利语:Napoleone Ferrara,1956年7月26日-),出生于意大利卡塔尼亚,意大利血管生成研究人员,任职于加利福尼亚州的生物技术公司基因泰克。他于1981年毕业于卡塔
  • 保罗·杨森保罗·杨森(德语:Paul Adriaan Jan, Baron Janssen,1926年9月12日-2003年11月11日),比利时药学家,化学家,氟哌啶醇的发现者,杨森制药的创始人。1926年9月12日出生于比利时蒂伦豪特,195
  • 欧林市欧林(Irving, Texas)是美国德克萨斯州东北部的一个城市,属达拉斯县。面积175.3平方公里,2006年人口为196,084人。1903年开埠,1914年4月14日设市。石油巨头艾克森美孚总部位于该地
  • 虎钳虎钳,又称万力、台钳,是一个将工作物夹住方便加工的工具,工作物本身在加工时还可以改变施加的压力和固定。虎钳应用的是螺旋机制。水平式虎钳,固定在工作桌上,无法随时取下,用螺栓
  • 巴吉人巴吉人(1863年-1920年),清末民初中国象棋名手,满族人,生于江苏镇江,绰号巴不斗,曾经著有《象棋梅花心法谱》一书 (现今多称为《反梅花谱》)。巴吉人祖辈世居东北,满清入关后,到江苏镇
  • 凯伦·阿兰凯伦·珍·阿兰(英语:Karen Jane Allen,1951年10月5日-),是一名美国女演员,以出演《印第安纳·琼斯》系列电影《法柜奇兵》(1981年)和《水晶骷髅王国》(2008年)的角色“玛莉恩”而知名
  • 24/724/7 是一天24小时,一星期7天的缩写,即全天候营业、提供服务且全年无休。在商业和工业领域里,通常是指所提供的不间断的服务,即不管任何时候、白天或黑夜,都有营业。这样的服务一