第75课：A* 搜索算法
学习目标
完成本课学习后，你将能够：
- 理解 A* 算法的核心思想及其在路径规划问题中的优势。
- 掌握启发式函数（Heuristic Function）的设计原则及其对算法性能的影响。
- 使用优先级队列（Priority Queue）正确实现 A* 算法。
- 能够将 A* 算法应用于二维网格等具体的寻路问题中。
核心概念
在寻找从起点到终点的最短路径时，我们已学习过广度优先搜索（BFS）和 Dijkstra 算法。BFS 适合无权重图，Dijkstra 适合带非负权重的图，但它们都是“盲目”的，即没有利用任何关于终点位置的先验知识。
A（A-Star）算法* 是一种在图或网格中寻找最短路径的启发式搜索算法。它在 Dijkstra 算法的基础上引入了“启发”，从而能更智能、更快速地向目标靠近。你可以将其想象为一个知道目的地大致方向的寻路人，他不仅计算已经走过的路，还会估算剩余的距离，优先探索看起来最有希望的路径。
A* 的核心思想是评估每个位置（或节点）的“潜力”，这个潜力用 f(n) 值来表示：
f(n) = g(n) + h(n)
g(n)：从起点到当前节点n的实际已知成本（例如，已走过的路径长度）。h(n)：从当前节点n到目标节点的估算成本（启发式值）。这是我们根据问题设计的一个“预估函数”。f(n)：经过节点n的路径的总估算成本。算法始终优先扩展f(n)值最小的节点。
启发式函数 h(n) 是 A 的灵魂*，它的质量直接影响算法的效率和最优性：
- 可采纳性（Admissible）：如果
h(n)永远不会高估从n到目标的实际最低成本，那么我们称这个启发式是“可采纳的”。这是保证 A* 找到最优解的关键。 - 一致性（Consistent）/ 单调性：在网格或图中，要求对于任意相邻节点
n和m，满足h(n) ≤ cost(n, m) + h(m)。一致性保证了找到的路径是最优的，且每个节点只被处理一次。
常用的启发式函数（以网格为例）：
- 曼哈顿距离：
|dx| + |dy|。适用于只能上下左右移动的网格。 - 欧几里得距离：
sqrt(dx^2 + dy^2)。适用于可以沿任意方向移动的场景。 - 切比雪夫距离：
max(|dx|, |dy|)。适用于可以对角线移动的网格。
代码示例
下面是一个在二维网格中使用 A* 算法寻找最短路径的完整 Python 实现。网格中 0 表示可通行，1 表示障碍物。
import heapq # 用于实现优先级队列
def heuristic(a, b):
"""计算曼哈顿距离作为启发式函数 h(n)。"""
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def astar(grid, start, end):
"""
A* 寻路算法。
:param grid: 二维网格，0为通路，1为障碍
:param start: 起点坐标 (row, col)
:param end: 终点坐标 (row, col)
:return: 从起点到终点的路径列表，如果无路径则返回空列表
"""
rows, cols = len(grid), len(grid[0])
# 检查起点或终点是否有效
if grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1:
return []
# 定义四个移动方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 优先级队列，存放 (f_cost, g_cost, 当前节点, 父节点)。f_cost 用于排序。
open_set = []
heapq.heappush(open_set, (0, 0, start, None))
# 记录每个节点的最佳 g_cost，用于判断是否需要更新路径
g_costs = {start: 0}
# 记录每个节点的父节点，用于最后回溯路径
came_from = {}
while open_set:
# 弹出 f_cost 最小的节点
f_current, g_current, current, parent = heapq.heappop(open_set)
# 如果当前节点是终点，回溯构建路径
if current == end:
path = []
while current:
path.append(current)
current = came_from.get(current)
return path[::-1] # 反转得到从起点到终点的顺序
# 记录父节点关系（用于回溯）
came_from[current] = parent
# 探索相邻节点
for dx, dy in directions:
neighbor = (current[0] + dx, current[1] + dy)
# 检查邻居节点是否有效：在网格内且不是障碍
if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols and grid[neighbor[0]][neighbor[1]] == 0:
# 计算从起点经过 current 到达 neighbor 的新 g_cost
new_g = g_current + 1 # 假设每移动一步代价为 1
# 如果这个节点未被访问过，或者我们找到了一条更优的路径
if neighbor not in g_costs or new_g < g_costs[neighbor]:
g_costs[neighbor] = new_g
f_cost = new_g + heuristic(neighbor, end) # f = g + h
# 将新节点信息加入优先级队列
heapq.heappush(open_set, (f_cost, new_g, neighbor, current))
# 优先级队列为空仍未找到终点，说明无路径
return []
# 测试代码
if __name__ == "__main__":
# 定义网格：0-可走， 1-障碍
grid = [
[0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[1, 1, 0, 0, 0, 0]
]
start = (0, 0) # 左上角
end = (4, 5) # 右下角
path = astar(grid, start, end)
if path:
print("找到最短路径，长度为:", len(path) - 1) # 路径节点数减1为步数
print("路径坐标:")
for point in path:
print(point)
else:
print("未找到从起点到终点的路径。")
实践练习
练习 1：修改启发式函数 将上述代码中的启发式函数从“曼哈顿距离”改为“欧几里得距离”。重新运行代码，观察找到的路径长度和访问的节点数量是否发生变化？并思考在什么情况下，这两种启发式函数会给出不同的结果？
练习 2：处理对角线移动
假设现在允许在网格中向对角线移动（共8个方向，每步代价为 sqrt(2) ≈ 1.414）。请修改代码以支持这种情况。你需要：
- 添加新的移动方向。
- 修改
new_g的计算逻辑，区分直线移动和对角线移动。 - 调整启发式函数，使其更适应对角线移动（例如使用切比雪夫距离或欧几里得距离）。
- 测试新代码能否在带有障碍的网格中找到对角线路径。
练习 3：实现另一个经典问题 使用 A* 算法的思想，尝试解决“八数码问题”（或简化为“3x3 数字华容道”）。你需要将每个数字盘面状态看作一个节点，将数字的移动（空格与相邻数字交换）看作移动操作。启发式函数可以选择“错位数字的个数”或“每个数字到其目标位置的曼哈顿距离之和”。
常见错误
- 优先级队列实现错误：没有正确使用堆（heapq）。注意，Python 的
heapq是最小堆，直接存放元组时，会按元组的第一个元素（即f_cost）进行比较。如果f_cost相同，可能会比较元组的后续元素（如节点坐标），这可能导致非预期的顺序。对于明确要求的顺序，可以存储一个计数器来打破平局。 - 忽略“已访问”状态：在代码中，我们使用
g_costs字典来记录到达每个节点的最佳路径长度。这是一个关键优化。如果每次都将邻居节点无条件加入优先级队列，会导致同一个节点被多次处理，大幅降低效率。正确做法是只当新路径更优时，才更新或添加节点。 - 启发式函数设计不当：设计了一个高估未来成本的启发式函数（如使用曼哈顿距离却允许对角线移动，这会导致高估），这可能导致 A* 失去最优性，找到的路径可能不是最短的。
- 边界条件处理：没有检查起点或终点本身是否是障碍物，或者移动后是否越界。
小结
本课我们学习了强大的 A* 搜索算法：
- 核心公式：
f(n) = g(n) + h(n)，综合了已知成本和预估成本。 - 关键优势：通过启发式函数
h(n)引导搜索方向，比 Dijkstra 算法更高效，特别适合目标明确的路径规划问题。 - 实现基石：依赖优先级队列来始终扩展最有希望的节点 (
f_cost最小)。 - 启发式设计：必须保证其可采纳性（不高估）以确保找到最优解。启发式函数的质量直接决定了算法的速度。
A* 算法是路径规划、游戏 AI、机器人导航等领域的基础算法。理解其原理并掌握实现，将为你解决更复杂的搜索问题打下坚实基础。在下一课，我们将学习另一种高效的动态数据结构——跳表。