A星搜索算法

A 星搜索算法通常写作 A*（A-star），在带非负费用的图中寻找从起点到目标的最低费用路径。它为每个待处理顶点记录两项数值：已经走出的费用 $g(v)$，以及对剩余费用的估计 $h(v)$；每次优先取 $f(v)=g(v)+h(v)$ 最小者。估计值要满足条件，才不会为了“看起来离终点近”而丢掉真正便宜的路线。

一张四点图

在有向图中，边及费用为 $S\to A:3,S\to B:1,B\to A:1,A\to T:2,B\to T:7$。目标是从 S 到 T。路径 S→A→T 的费用为 5，S→B→T 为 8，而 S→B→A→T 为 $1+1+2=4$，是本例最优路线。

边旁数字是真实费用；节点旁的 h 是到终点剩余费用的估计，路径费用仍需把经过的边相加。

先取 $h(S)=4,h(A)=2,h(B)=3,h(T)=0$。这些值在此例恰等于各点到 T 的真实最低剩余费用，但运行 A* 时并不需要预先知道真实答案；这里只用小图方便逐项检查条件。

取出的顶点	当前 $g$	当前 $f=g+h$	扩展后产生或改善的候选
S	0	4	B：$g=1,f=4$；A：$g=3,f=5$
B	1	4	A 改为 $g=2,f=4$；T：$g=8,f=8$
A	2	4	T 改为 $g=4,f=4$
T	4	4	到达目标，回溯前驱得到 S→B→A→T

表里 A 最初有一条费用 3 的候选，后来被 B→A 的费用 2 候选替换；T 也由 8 改善到 4。旧候选即使还留在优先队列中，也不能当作当前最优记录继续扩展。

启发值的两个条件

可采纳是指 $h(v)$ 不高估从 $v$ 到目标的真实最低剩余费用，并约定 $h(T)=0$。一致进一步要求每条费用为 $w(u,v)$ 的边都满足 $$h(u)\le w(u,v)+h(v).$$ 本例可逐边核对：S→B 上有 $4\le 1+3$，B→A 上有 $3\le 1+2$，A→T 上有 $2\le 2+0$；其他两条边也成立。一致性沿整条路线相加便推出不高估，所以它比可采纳更强。

一致性使沿路径的估计总费用不下降：若从 $u$ 走费用 $w(u,v)$ 到 $v$，则 $$g(u)+h(u)\le g(u)+w(u,v)+h(v)=g(v)+h(v).$$ 当优先队列取出目标时，$h(T)=0$，其 $f$ 就是已找到路径的真实费用。若还有更便宜的路线，那条路线尚未处理完的前沿至少有一个候选，其 $f$ 不超过整条便宜路线的费用，应该先于当前目标取出，矛盾。这说明在上述条件下，按最小 $f$ 取目标可得到最低费用。

过早关闭顶点的反例

只把 $h(A)$ 从 2 改为 0，其余不变。它仍可采纳，因为 0 没有高估 A 到 T 的真实费用 2；但 B→A 不再一致：$h(B)=3>1+h(A)=1$。从 S 扩展后，A 的 $f=3$ 会先于 B 的 $f=4$ 被取出，得到暂时的 S→A→T，费用 5。随后 B 找到费用 2 的更好 A 路线。若把“曾取出过 A”当作永久关闭、拒绝再次处理 A，就会错误地返回 5；允许 A 在 $g$ 改善后重新进入优先队列，便能找到费用 4 的路线。

下方实现保存每个顶点当前最好的 $g$，并允许改善后的顶点重新入队。它跳过仍在堆里的旧记录，不会因为“已经见过”就忽略更便宜的路线。图有限、边权非负、$h$ 可采纳且目标的启发值为 0 时，这种重开策略能够保持目标出队时的最优性；若启发值高估真实费用，保证便不存在。

A 星搜索的候选更新

比较 g、h、f，查看更便宜的路线怎样替换旧候选。

打开交互演示

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

邻接表中每项是 (相邻顶点, 费用)；启发值由字典提供。函数返回 (最低费用, 路径)，目标不可达时返回 None，不修改输入。代码检查顶点和非负边权，却无法从数值表本身证明启发值可采纳；这一条件要由建模者根据问题检查。

Python 3

from heapq import heappop, heappush
from itertools import count


def astar(graph, start, goal, heuristic):
    if start not in graph or goal not in graph:
        raise KeyError("start and goal must be vertices")
    if heuristic[goal] != 0:
        raise ValueError("heuristic at goal must be zero")
    for u, neighbors in graph.items():
        if u not in heuristic:
            raise KeyError(u)
        for v, weight in neighbors:
            if v not in graph:
                raise KeyError(v)
            if weight < 0:
                raise ValueError("edge weights must be nonnegative")

    serial = count()
    queue = [(heuristic[start], next(serial), 0, start)]
    best = {start: 0}
    parent = {start: None}
    while queue:
        _, _, g, u = heappop(queue)
        if g != best[u]:
            continue
        if u == goal:
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return g, list(reversed(path))
        for v, weight in graph[u]:
            candidate = g + weight
            if candidate < best.get(v, float("inf")):
                best[v] = candidate
                parent[v] = u
                heappush(queue, (
                    candidate + heuristic[v], next(serial), candidate, v
                ))
    return None


if __name__ == "__main__":
    graph = {
        "S": [("A", 3), ("B", 1)],
        "A": [("T", 2)],
        "B": [("A", 1), ("T", 7)],
        "T": [],
    }
    consistent = {"S": 4, "A": 2, "B": 3, "T": 0}
    inconsistent = {"S": 4, "A": 0, "B": 3, "T": 0}
    assert astar(graph, "S", "T", consistent) == (
        4, ["S", "B", "A", "T"]
    )
    assert astar(graph, "S", "T", inconsistent) == (
        4, ["S", "B", "A", "T"]
    )
    assert astar(graph, "T", "S", {v: 0 for v in graph}) is None

成本与适用范围

令 $V,E$ 分别为顶点、边数。把 $h$ 全设为 0 时，队列按已走费用 $g$ 排序，本算法退化为一致费用搜索，即此处的Dijkstra 方法；只按 $h$ 排序则是另一种贪心最佳优先搜索，不能和 A* 混称。广度优先搜索按边数扩展，只在每条边代价相同等条件下才与费用最短相符。

每次扩展会检查邻边并操作堆，但实际扩展次数取决于启发值、平手规则和是否重开。不能给任意启发值下的这份实现无条件套用一次访问每点的 $O((V+E)\log V)$ 界。在一致启发值下，顶点的最优记录出队后不再改善；每条边至多引发一次改善入堆，故此处允许旧记录留堆的实现耗时 $O((V+E)\log (V+E+1))$，堆、费用表和前驱合计占 $O(V+E)$ 额外空间。启发值越贴近真实剩余费用，常可能减少无关区域的扩展，但“接近”不是比正确性条件更高的优先级。

参考资料

• TheAlgorithms/Python：a_star.py：格网搜索的选题参考；本文用独立加权图和可重开堆实现讲解。
• Poole、Mackworth，Artificial Intelligence 3e §3.7：启发值条件与多路径搜索。
• 先修：图论、最短路径；对照：广度优先搜索。