案例库 · 研发与科研 · 技术决策 · 1968
A*算法利用可采纳的启发函数，无需全面探索即可找到最短路径
1968年，Hart、Nilsson和Raphael提出的A*搜索算法将已花费代价与可采纳的启发函数结合，在扩展较少节点的同时保证找到最短路径。
斯坦福研究所
那一手
在大型图中寻找最便宜路线是一个经典问题。广度优先搜索有保证但会探索所有节点；贪婪最佳优先搜索快速但可能找到非最便宜的路径。
1968年Hart、Nilsson和Raphael的论文定义了A*算法：扩展f = g + h最小的节点，其中g是当前已花费代价，h是对剩余代价的启发式估计。如果h是可采纳的（即从不高估），A*保证返回最优路径。
该论文证明，在给定启发函数下，A*扩展的节点数少于任何最优算法。这种权衡是精确的：好的h能加速搜索而不牺牲保证，因此A*成为路径规划和游戏规划的标准。
为什么管用
- 可采纳的启发函数聚焦搜索，但不会排除真正的最优解。
- f = g + h 的评分平衡了已走距离与剩余距离。
- A*被证明是最优的，且比无信息搜索扩展的节点少得多。
- 它是一个模板，领域只需提供合适的启发函数。
值了多少按已知代价加合理猜测进行搜索聪明
可以搬走什么
不要只扩展最便宜的已知路径或贪婪地追逐目标。将每个选项评分为已花费代价加上一个永不高估的估计值，这样既能保持最优性，又能提高速度。
后来呢
A*成为游戏、机器人、地图和路径规划中寻路的基础，也是启发式搜索算法大家族发展的起点。其最优性证明和可采纳启发函数的概念至今仍处于核心地位。
资料来源
发现哪里写错了？告诉我们。