1. 简介
我们之前研究过 Dijkstra 算法，它是一种用于寻找两点之间最短路径的经典方法。本文我们将介绍 A*（A-Star）算法，它是在 Dijkstra 算法基础上进行优化的一种更高效的路径搜索算法。
A* 算法的核心思想是引入“启发式”评估机制，使得搜索过程更倾向于朝向目标节点的方向进行。相比 Dijkstra 的盲目搜索，A* 更聪明，效率更高。
2. A* 算法原理
A* 是 Dijkstra 算法的一个改进版本，本质上是一种 Best-First Search（最佳优先搜索）算法。
它通过为每个节点维护两个评分机制来实现：
g(n)：从起点到当前节点 n 的实际代价，与 Dijkstra 一致；h(n)：从当前节点 n 到目标节点的启发式估计代价；- 最终节点的优先级由
f(n) = g(n) + h(n)决定。
这样做的好处是：在搜索过程中始终优先考虑离目标更近的节点，从而更高效地找到最优路径。
⚠️ 一个小细节：如果我们的启发函数 h(n) 始终返回 0，那么 A* 就完全退化为 Dijkstra 算法。这说明两者本质是同一类算法，区别仅在于启发函数的设计。
2.1 伪代码实现
A* 的核心逻辑与 Dijkstra 非常相似，只是多了启发函数的参与。
algorithm AStar(graph, startNode, targetNode):
// INPUT
// graph = the graph to search
// startNode = the starting node of the path
// targetNode = the target node of the path
// OUTPUT
// The shortest path from startNode to targetNode using the A* algorithm
for node in graph:
node.score <- infinity
node.heuristicScore <- infinity
node.visited <- false
startNode.score <- 0
startNode.heuristicScore <- 0
while true:
currentNode <- nodeWithLowestScore(graph)
currentNode.visited <- true
for nextNode in currentNode.neighbors:
if not nextNode.visited:
newScore <- calculateScore(currentNode, nextNode)
if newScore < nextNode.score:
nextNode.score <- newScore
nextNode.heuristicScore <- newScore +
calculateHeuristicScore(nextNode, targetNode)
nextNode.routeToNode <- currentNode
if currentNode = targetNode:
return buildPath(targetNode)
if nodeWithLowestScore(graph).score = infinity:
throw NoPathFound
algorithm nodeWithLowestScore(graph):
// INPUT
// graph = the graph from which to find the node with the lowest score
// OUTPUT
// result = the node with the lowest heuristic score that has not been visited
result <- null
for node in graph:
if not node.visited and (result is null
or node.heuristicScore < result.heuristicScore):
result <- node
return result
nodeWithLowestScore的逻辑与 Dijkstra 类似，只是它现在基于heuristicScore来选择下一个节点。而calculateScore和buildPath的实现与之前保持一致。
2.2 启发函数设计
启发函数 h(n) 是 A* 的核心部分，它的设计直接影响算法的效率和路径的最优性。
常见的启发函数包括：
- 曼哈顿距离（Manhattan Distance）：适用于只能在四个方向移动的网格地图；
- 欧几里得距离（Euclidean Distance）：适用于可以朝任意方向移动的地图；
- 切比雪夫距离（Chebyshev Distance）：适用于允许八方向移动的棋盘类地图。
✅ 启发函数设计要求：
- 一致性（Consistency）：任意两个相邻节点间，启发值的变化不能超过边的实际代价；
- 可接受性（Admissibility）：启发值不能高估实际代价，否则可能导致非最优路径；
⚠️ 如果启发函数不满足上述要求，A* 可能会跳过最优路径，导致找到的路径不是最短的。
3. A* 的特性
A* 是一种功能强大、应用广泛的路径搜索算法，具有以下关键特性：
3.1 终止性与完备性
- 终止性（Termination）：算法最终会停止，要么找到路径，要么确认路径不存在；
- 完备性（Completeness）：只要存在路径，算法就一定能找到；
在有限图中，只要边的权重非负，A* 就具有终止性和完备性。对于无限图，只有在启发函数满足一定条件时才能保证找到路径。
3.2 可接受性（Admissibility）
启发函数是可接受的，当且仅当它永远不会高估从当前节点到目标的最小代价。
✅ 如果启发函数是可接受的，则 A* 找到的路径一定是最优路径。
❌ 如果启发函数不可接受，A* 可能会找到次优路径，但仍然能找到一条路径。
在实际应用中，有时为了提升性能，我们会使用略高于实际代价的启发函数，以牺牲最优性换取速度。
4. 时间与空间复杂度
A* 的性能与启发函数的质量密切相关。
时间复杂度
- 最坏情况下为 **O(b^d)**，其中：
b是分支因子（每个节点平均有多少条边）；d是路径长度；
- 启发函数越准确，需要访问的节点越少，复杂度越低。
Dijkstra 的有效分支因子等于实际分支因子，而 A* 的理想情况下有效分支因子接近 1，意味着每一步只访问一个节点。
空间复杂度
- 标准 A* 的空间复杂度为 **O(b^d)**，因为需要保存所有已访问节点；
- 可以通过动态加载节点、遗忘不重要节点等方式优化空间使用，但可能会牺牲路径质量。
5. 总结
A* 是一种结合了 Dijkstra 和启发式搜索的高效路径查找算法。它在游戏开发、机器人导航、地图导航等领域有广泛应用。
✅ 优点：
- 搜索方向明确，效率高；
- 启发函数设计合理时能找到最优路径；
❌ 缺点：
- 启发函数设计不当可能导致非最优路径；
- 空间开销较大；
在实际项目中，根据具体场景选择合适的启发函数，是提升 A* 性能的关键。
如果你对 A* 的 Java 实现感兴趣，可以参考我之前写的一篇实战文章：A* 算法实战。