从一张地图开始：理解 A* 寻路

这是一篇示例文章，用于展示代码、公式与图片排版。

先定义问题

在寻路问题中，我们通常在一个离散的网格地图上，从起点出发到达终点。地图由可通行的格子和不可通行的障碍物组成，每次可以向上下左右四个方向移动，移动到相邻格子的代价为 1。

我们的目标是找到一条总代价最低的路径。

同一张地图，不同路径有不同的代价。

估计一条路径的代价

A* 用两个量对节点进行评分：从起点到当前节点的已知代价 $g(n)$，以及从当前节点到终点的启发式估计 $h(n)$。两者相加得到：

$$f(n) = g(n) + h(n)$$

在允许上下左右移动、每步代价相同的网格中，可以用曼哈顿距离估计剩余步数：

$$h(n)=|x_n-x_{\mathrm{goal}}|+|y_n-y_{\mathrm{goal}}|$$

下面只展示评分函数。完整算法还需要优先队列、邻居遍历、代价更新和路径重建。

def heuristic(node, goal):
    return abs(node.x - goal.x) + abs(node.y - goal.y)


def score(node, goal, cost):
    return cost[node] + heuristic(node, goal)

实现与边界

启发式不是随意添加的“偏好”。在常见的最优路径保证下，需要合理限制估计值；在图搜索中，还需要正确处理已发现节点的代价更新。¹

地图规则	可考虑的启发式
四方向、单位代价	曼哈顿距离
无障碍平面、直线距离计费	欧几里得距离
无法可靠估计剩余代价	取零，退化为 Dijkstra 搜索

加入对角移动、传送门或不同地形代价后，需要重新检查启发式是否仍然合适。

让失败清楚地出现

如果起点或终点不在地图中，应在输入处指出问题。如果目标不可达，应明确返回“没有路径”，而不是显示一条穿过障碍物的路线。

延伸阅读

• Red Blob Games：Introduction to the A* Algorithm
• 让内容成为可以积累的档案

注释

1. 这篇示例只介绍问题与评分方式。实现完整图搜索时，还需考虑启发式的一致性，以及是否重新打开已经访问的节点。 ↩