人工智能里有一类问题特别典型：给你一个起点和终点，要求你在一堆约束里找到一条代价最低的路径。A* 搜索算法就是为这类问题准备的。它既不像'盲搜'那样横冲直撞，也不会只凭经验瞎猜，而是把已走过的代价和到终点的预估代价结合起来，一步步逼近最优解。
A* 最早出现在 Shakey 项目中，后来被广泛用于游戏寻路、机器人规划、地图路径搜索等场景。只要问题能抽象成图上的节点和边，它就有机会派上用场。
什么是 A* 搜索算法？
可以把它理解成一种'带方向感'的图搜索。面对迷宫、路线规划这类问题，普通搜索往往会走很多冤枉路；A* 则会优先考虑那些看起来更接近目标、同时历史成本也更低的节点。
如果把迷宫映射成图：
- 节点表示位置或状态
- 边表示可移动的路径
- 边权表示移动代价
那么 A* 要做的事就很明确了：在所有可选路径里，找出从起点到终点最划算的一条。
它之所以'聪明'，关键不在于运气，而在于它总是围绕一个评分函数来决策：
f(n) = g(n) + h(n)
其中：
g(n)：从起点到当前节点n的真实代价h(n)：从n到终点的启发式估计代价
A* 每次都会优先扩展 f(n) 最小的节点。直观一点说，就是它既看'已经花了多少'，也看'未来大概要花多少'。
A* 的基本流程
A* 的实现思路并不复杂，真正需要理清的是它维护的两个集合：
- 开放列表（open set）：已经发现、但还没完全展开的节点
- 关闭列表（closed set）：已经检查过的节点
实际执行时，大致是这样一条链路：
- 把起点放入开放列表。
- 每轮从开放列表里取出
f值最小的节点，作为当前节点。 - 检查它的邻居：
- 如果邻居已经在关闭列表里，通常跳过。
- 如果邻居还没见过，就加入开放列表，并记录它的父节点。
- 如果邻居已经在开放列表里，但通过当前路径能得到更小的
g值，就更新它的父节点和代价。
- 当前节点处理完后，把它移到关闭列表。
- 如果当前节点就是终点，沿着父节点反向回溯，路径就找出来了。
- 如果开放列表空了还没找到终点，说明不存在可行路径。
这套流程的核心不是'走得快'，而是'每一步都尽量走在更值得走的方向上'。
为什么 A* 常被优先使用？
寻路问题看似简单，真正落到工程里往往不轻松。比如游戏角色移动，或者机器人避障，你不能只盯着眼前一步，否则很容易走进死胡同，或者绕出一条很长的弯路。
A* 的优势就在这里：它会提前评估前方区域，尽量避免明显不划算的选择。和单纯的局部移动策略相比，它更适合处理'全局最优路径'这类问题。
当然，它也不是没有代价。A* 需要维护更多状态，计算量通常比一些简单算法更高。可一旦启发式函数选得好，它的效率和结果质量往往都很有竞争力。
A* 的核心概念：启发式函数
A* 能不能跑得漂亮，很大程度上取决于 h(n) 这个启发式函数。
启发式函数本质上是对'离目标还有多远'的估计。它不要求绝对准确，但必须足够有参考价值。估计得太离谱，算法就会偏；估计得太保守，又会失去效率。
一个好的启发式函数通常要满足两个重要性质：
可接受性
如果启发式函数从不高估真实代价，就称它是可接受的。换句话说，它给出的估计值不会比实际最短路径更大。
一致性
如果从一个节点移动到相邻节点时，启发式估计满足单调关系，且不会出现前后矛盾的跳变，通常就认为它是一致的。对于 A* 来说，这能让搜索过程更稳定，也更容易保证最优性。
Python 实现示例
下面这个例子演示了如何用 A* 在一个加权图里寻找从 A 到 G 的最短路径。这里边上的数字表示实际移动代价，节点上的启发式值则用于估算到终点的距离。
先看思路：从 A 出发后，算法会比较几个候选方向的 f(n) 值。它并不会'看谁顺眼'，而是始终选择当前最有希望的那条路。这个例子里，最终找到的路径是 A -> E -> D -> G。
def aStarAlgo(start_node, stop_node):
open_set = set([start_node])
closed_set = set()
g = {}
parents = {}
g[start_node] = 0
parents[start_node] = start_node
while len(open_set) > 0:
n = None
for v in open_set:
if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
n = v
if n is None:
print('Path does not exist!')
return None
if n == stop_node:
path = []
while parents[n] != n:
path.append(n)
n = parents[n]
path.append(start_node)
path.reverse()
print('Path found: {}'.format(path))
return path
for (m, weight) in get_neighbors(n):
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
open_set.remove(n)
closed_set.add(n)
print('Path does not exist!')
return None
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
return None
def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0,
}
return H_dist[n]
Graph_nodes = {
'A': [('B', 2), ('E', 3)],
'B': [('C', 1), ('G', 9)],
'C': None,
'E': [('D', 6)],
'D': [('G', 1)],
}
aStarAlgo('A', 'G')
运行结果：
Path found: ['A', 'E', 'D', 'G']
这个例子里，A* 的行为很清晰：它不会只看眼前那条边的代价，也会把'走到终点还要花多少'算进去。正因为如此，它往往能避开一些表面上便宜、实际却更绕的路线。
A* 和 Dijkstra 的区别
很多人会把 A* 和 Dijkstra 放在一起比较。两者都能做最短路径搜索，但思路不一样。
- Dijkstra：更像是均匀地向外扩展，适合没有明确目标引导的最短路问题。
- A*：在 Dijkstra 的基础上引入启发式估计，因此能更有针对性地朝目标前进。
如果启发式函数设计得合理，A* 通常会比 Dijkstra 更省搜索范围；但如果启发式函数质量差，A* 的优势就会缩水。
小结
A* 搜索算法是图搜索里非常经典的一种方法。它把真实路径代价 g(n) 和启发式估计 h(n) 结合起来，在保证较强实用性的同时，也尽量兼顾最优性。对于游戏寻路、机器人导航、地图路径规划这类任务，它几乎是绕不开的基础算法之一。
真正决定 A* 表现的，不只是算法本身，还有启发式函数的质量。把这部分设计好，A* 才能真正发挥出'既聪明又稳妥'的优势。