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等组合问题中寻找最优解
- 网络路由:利用链路质量启发式确定高效的数据包路由
- 生物信息学:序列比对和蛋白质结构预测搜索
使用方式
使用方式
创建一个包含起始节点的开放集,将其g值(从起始点的代价)设置为零,并使用启发式函数计算其h值。
从开放集中选择f值最低的节点,计算其未访问邻居的f值,并将有希望的邻居添加到开放集中。
继续扩展节点,直到以最低f值到达目标;通过回溯父指针重建路径。
常见陷阱
- 使用不可采纳的启发式函数,高估代价,导致次优路径
- 选择过于简单或与问题无关的启发式函数,降低搜索效率
- 开放集实现效率低下(应使用优先队列),导致节点选择缓慢
常见问题
什么是可采纳的启发式函数,为什么它很重要?
可采纳的启发式函数从不高估到目标的真实代价。此属性保证A*找到最优路径。如果启发式函数高估,A*可能会错过较短的路径并返回次优解。
如何为问题设计一个好的启发式函数?
好的启发式函数基于领域知识和问题结构。对于基于网格的寻路,曼哈顿距离或欧几里得距离效果很好。对于更复杂的问题,可以考虑放宽约束或使用模式数据库来计算可采纳的启发式函数。
A*和Dijkstra算法有什么区别?
两者都能找到最优路径,但A*使用启发式函数优先探索目标方向,当有好的启发式函数时,它会快得多。Dijkstra算法均匀地向所有方向探索,当启发式函数不可靠时更安全。
A*能保证找到最短路径吗?
是的,当启发式函数是可采纳的(从不高估真实代价)时,A*保证找到最短路径。对于不可采纳的启发式函数,不保证最优性。
相关方法
参考文献
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 文献已复制。Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ISBN:978-0-13-604259-4已复制。