1.2 A* 与启发式：估计必须和代价模型说同一种语言

一致代价搜索能找到最低代价路线，却会向所有方向扩散。若能估计“从这里到终点至少还要付出多少”，搜索就可以优先处理更有希望的状态。方向感可以省计算，但不能顺手把最优性也省了。

A* 不会凭空剪掉所有坏路线。它用 $f(n)=g(n)+h(n)$ 改变扩展顺序；最优性取决于启发式、终止规则和重复状态处理。

本课目标

• 区分累计代价 $g$、启发式 $h$ 与优先级 $f$；
• 判断启发式是否 admissible、consistent；
• 实现能处理旧队列项与 reopen 的 A*；
• 衡量启发式收益和 Weighted A* 的最优性权衡。

1. A* 的三个量

• $g(n)$：起点到 $n$ 的已知最低路径代价；
• $h(n)$：从 $n$ 到目标的估计剩余代价；
• $f(n)=g(n)+h(n)$：经由 $n$ 的解成本估计。

当 $h(n)=0$，A* 退化为 UCS。若 $h$ 完全等于真实剩余成本，搜索会非常直接；真实成本未知才需要启发式。

启发式单位必须与边代价一致。若 $g$ 是时间，$h$ 不能直接用公里数相加，除非用速度界转换为时间下界。

2. Admissible 与 consistent

可采纳（admissible）：

$$0\le h(n)\le h^{\ast }(n),$$

即不高估真实最低剩余代价。

一致（consistent/monotone）：对每条 $n\to n^{\prime }$：

$$h(n)\le c(n,n^{\prime })+h(n^{\prime }).$$

一致性类似三角不等式，并蕴含沿路径 $f$ 不下降。对 graph A*，一致启发式让节点从优先队列以最佳 $g$ 弹出后可安全关闭。可采纳但不一致的启发式仍可能找到最优解，但实现要允许更优路径重新打开已扩展状态。

3. 一个稳妥的 A* 实现

这是 Python 3 片段（partial），复用上一课的 reconstruct；调用者提供后继、目标和启发式函数。状态应可哈希且不能为 None，代价为有限非负数。下文的终止保证还要求目标启发式为 0，并满足有限图或相应的完整性条件。

import heapq
from itertools import count

def a_star(edges, start, is_goal, heuristic):
    tie = count()
    best_g = {start: 0.0}
    parent = {start: None}
    frontier = [(heuristic(start), 0.0, next(tie), start)]

    while frontier:
        _, g, _, state = heapq.heappop(frontier)
        if g != best_g.get(state):
            continue                    # 更优路径已入队，旧项作废
        if is_goal(state):
            return reconstruct(parent, state), g

        for next_state, step_cost in edges(state):
            if step_cost < 0:
                raise ValueError("A* requires non-negative edge costs")
            new_g = g + step_cost
            if new_g < best_g.get(next_state, float("inf")):
                best_g[next_state] = new_g
                parent[next_state] = state
                new_f = new_g + heuristic(next_state)
                heapq.heappush(
                    frontier,
                    (new_f, new_g, next(tie), next_state),
                )

    return None

队列同时保存入队时的 g，弹出时与 best_g 比较，跳过 stale entry。没有永久 closed set，因此发现更低代价时会重新处理状态，适用于不一致启发式。

目标在弹出（当前最小 f）时终止，而不是第一次生成时终止。后者可能在更便宜路径尚未扩展时提前返回。

一个可手算的重开例子是：S→A=3、S→B=1、B→A=1、A→G=3，取 h(S)=0、h(A)=0、h(B)=4、h(G)=0。这些估计都不高估真实剩余代价，但 B→A 不满足一致性。A 会先以 g=3 扩展，再经 B 以 g=2 重开，最终得到成本 5；永久关闭 A 则会留下成本 6 的路线。可采纳性和重开要求可对照 Berkeley CS 188 的 A* 说明。

4. 网格启发式要匹配动作

四方向移动、每步单位代价且无传送时，Manhattan distance：

$$h=|x-x_g|+|y-y_g|$$

是自然下界。允许对角单位移动时，Manhattan 会高估；可考虑 Chebyshev distance。对角代价为 $\sqrt{2}$ 时可用 octile distance。

障碍通常让真实路径更长，不破坏这些下界；但传送、不同地形成本和负代价会改变条件。启发式不是因为名字叫“距离”就自动可采纳。

5. 从松弛问题构造启发式

删除原问题的一些约束，得到更容易求解的 relaxed problem；其最优成本通常是原问题的下界。

例子：

• 忽略墙，得到网格几何距离；
• 滑块谜题允许方块穿过彼此，得到错位数或 Manhattan 总和；
• 路线规划忽略拥堵，使用理论最快时间。

也可预计算 pattern database。启发式计算本身有成本：每个节点都运行一个昂贵优化器，可能比多扩展一些节点更慢。

6. 比较启发式的支配关系

若两个启发式都可采纳，且对所有节点 $h_2(n)\ge h_1(n)$，则 $h_2$ 信息更强（dominates）。在一致启发式等适用条件下，更强的下界可减少必须扩展的节点；最优成本处的平局顺序和不一致启发式导致的重开会影响实际次数，不能只凭支配关系断言运行更快。

评估同时报告：

• 最终路径成本；
• expanded/generated/reopened 节点数；
• frontier 峰值；
• 启发式计算时间；
• 总运行时间与内存。

只比较找到路径的速度，可能把返回次优结果的启发式误判为“更好”。

7. 不可采纳启发式与 Weighted A*

Weighted A* 使用：

$$f(n)=g(n)+wh(n),w>1.$$

它更偏向目标方向，常减少搜索，却通常放弃严格最优。特定条件下可给出 bounded-suboptimal 保证，但要明确算法版本和前提，不能简单说“不可采纳会更快”。

在实时系统中，可使用 anytime 算法：先返回可行解，再逐步收紧界。选择依据是允许的次优比例、响应时限和失败代价。

8. Tie-breaking 会影响实际成本

许多节点可能有相同 f。按较大 g、较小 h 或插入顺序打破平局，不改变满足条件下的最优成本，却会明显改变扩展数和结果路径。必须保证状态对象不可比较时 heap 仍有稳定 tie counter。

常见误区

• A 会剪掉所有不好的方向*：它主要改变扩展优先级。
• 直线/Manhattan 永远可采纳：要看动作和代价模型。
• 首次看到目标即可返回：生成时还不能保证其 g 最小。
• 有 visited 就更高效：永久关闭会让不一致启发式错过更优路径。

练习

1. 为四方向、八方向和传送网格分别判断 Manhattan 是否可采纳。
2. 构造可采纳但不一致启发式，观察 reopen。
3. 比较 $h=0$、Manhattan 和更强下界的扩展数与启发式耗时。
4. 用不同 $w$ 运行 Weighted A*，画时间与次优率曲线。

小结

A* 的保证来自下界性质和正确的 graph-search 实现，不来自“看起来更接近目标”。启发式必须匹配状态、动作和代价，并用总成本与扩展代价共同评估。

下一课把搜索空间换成对手的决策树：当环境会针对你的动作选择回应，目标不再是一条固定路径。