Skip to content
返回搜索结果

A*搜索算法

提出者
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
年份
1968
类型
algorithm
类别
Graph Algorithms

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

A*搜索算法由Peter E. Hart、Nils J. Nilsson和Bertram Raphael于1968年提出,是一种结合了Dijkstra算法优势和启发式引导的最优路径查找算法。它通过平衡从起点到当前节点的实际距离与到目标节点的估计距离,有效地找到最短路径。

方法背后的直觉

A*使用评估函数f(n) = g(n) + h(n),其中g(n)是从起点到节点n的实际代价,h(n)是到目标节点的剩余代价的启发式估计。通过探索f(n)值最低的节点,当启发式函数是可采纳的(从不高估)时,该算法能有效地将搜索空间缩小到目标,同时保持最优性。这使得A*比无信息搜索方法快得多,同时仍能保证找到最优路径。

历史学

Hart、Nilsson和Raphael于1968年发表了A*算法,证明将启发式信息添加到Dijkstra算法中可以显著提高搜索效率,同时保持最优性。该算法成为人工智能和运筹学的基础。随后的发展包括双向A*、IDA*(迭代加深)和各种启发式改进。A*仍然是现代游戏引擎和机器人系统中寻路的标准选择。

何时使用

当需要在一个有良好启发式函数的图中找到最优路径时,应用A*算法。它在游戏、机器人和路线规划中的寻路方面特别有效,因为有信息搜索可以显著减少计算量。当速度很重要但又要求最优性时,请使用它。对于没有可靠启发式函数的情况,请改用Dijkstra算法。

局限与注意事项

  • 最优性取决于启发式函数的可采纳性
  • 当启发式函数不佳或不可采纳时,性能显著下降
  • 在大型搜索空间中(维护开放集和关闭集)内存使用量可能很大
  • 需要明确的领域知识来设计良好的启发式函数

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 当启发式函数可采纳时,可实现最优路径查找
  • 当有良好启发式函数时,比Dijkstra或广度优先搜索快得多
  • 灵活:适用于任何可采纳的启发式函数
  • 非常适合单目标寻路问题
  • 在游戏、机器人和导航系统中经过广泛的实际验证

应用

  • 视频游戏寻路:动态游戏环境中NPC的实时导航
  • 机器人运动规划:避开障碍物的自主机器人的最优路径规划
  • GPS导航:考虑路网和交通情况计算高效路线
  • 谜题求解:在15-puzzle等组合问题中寻找最优解
  • 网络路由:利用链路质量启发式确定高效的数据包路由
  • 生物信息学:序列比对和蛋白质结构预测搜索

使用方式

使用方式

1

创建一个包含起始节点的开放集,将其g值(从起始点的代价)设置为零,并使用启发式函数计算其h值。

2

从开放集中选择f值最低的节点,计算其未访问邻居的f值,并将有希望的邻居添加到开放集中。

3

继续扩展节点,直到以最低f值到达目标;通过回溯父指针重建路径。

常见陷阱

  • 使用不可采纳的启发式函数,高估代价,导致次优路径
  • 选择过于简单或与问题无关的启发式函数,降低搜索效率
  • 开放集实现效率低下(应使用优先队列),导致节点选择缓慢

常见问题

什么是可采纳的启发式函数,为什么它很重要?

可采纳的启发式函数从不高估到目标的真实代价。此属性保证A*找到最优路径。如果启发式函数高估,A*可能会错过较短的路径并返回次优解。

如何为问题设计一个好的启发式函数?

好的启发式函数基于领域知识和问题结构。对于基于网格的寻路,曼哈顿距离或欧几里得距离效果很好。对于更复杂的问题,可以考虑放宽约束或使用模式数据库来计算可采纳的启发式函数。

A*和Dijkstra算法有什么区别?

两者都能找到最优路径,但A*使用启发式函数优先探索目标方向,当有好的启发式函数时,它会快得多。Dijkstra算法均匀地向所有方向探索,当启发式函数不可靠时更安全。

A*能保证找到最短路径吗?

是的,当启发式函数是可采纳的(从不高估真实代价)时,A*保证找到最短路径。对于不可采纳的启发式函数,不保证最优性。

相关方法

参考文献

  1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.

    打开 DOI 文献
    已复制。
  2. Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.

    ISBN:978-0-13-604259-4
    已复制。