查看“︁A星搜索算法”︁的源代码

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

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

[[File:Gezhi-astar-four-vertex.svg|frame|center|alt=有向图S到A费用三、S到B费用一、B到A费用一、A到T费用二、B到T费用七；节点旁分别标注启发值四二三零|边旁数字是真实费用；节点旁的 h 是到终点剩余费用的估计，路径费用仍需把经过的边相加。]]

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

{| class="wikitable"
! 取出的顶点 !! 当前 <math>g</math> !! 当前 <math>f=g+h</math> !! 扩展后产生或改善的候选
|-
| S || 0 || 4 || B：<math>g=1,f=4</math>；A：<math>g=3,f=5</math>
|-
| B || 1 || 4 || A 改为 <math>g=2,f=4</math>；T：<math>g=8,f=8</math>
|-
| A || 2 || 4 || T 改为 <math>g=4,f=4</math>
|-
| T || 4 || 4 || 到达目标，回溯前驱得到 S→B→A→T
|}

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

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

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

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

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

<math-experiment type="algorithm" demo="astar" />

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

<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
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]&#32;!= 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&#32;!= 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
</pre>
</div>

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

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/graphs/a_star.py TheAlgorithms/Python：a_star.py]：格网搜索的选题参考；本文用独立加权图和可重开堆实现讲解。
* [https://artint.info/3e/html/ArtInt3e.Ch3.S7.html Poole、Mackworth，Artificial Intelligence 3e §3.7]：启发值条件与多路径搜索。
* 先修：[[图论]]、[[最短路径]]；对照：[[广度优先搜索]]。
[[分类:算法]]