算法刷题系列（三十五）：启发式搜索——用估价信息引导探索

算法刷题系列（三十五）：启发式搜索——用估价信息引导探索

广度优先搜索适合无权图，Dijkstra 适合非负权图。若搜索目标已知，而且能估计“离目标还要付出多少代价”，A* 可以用这个信息优先探索更有希望的状态。

本文在带非负边权的图上求起点到目标的最短距离。启发式函数 h(v) 估计从 v 到目标的剩余代价，队列按 f(v)=g(v)+h(v) 排序；g(v) 是目前已知的起点到 v 的实际代价。

启发式需要满足什么？

• 可采纳（admissible）：h(v) 不超过 v 到目标的真实最短距离，因此不会高估剩余代价。
• 目标值为零：h(goal)=0。
• 一致（consistent）：对每条边 u→v，有 h(u) ≤ cost(u,v)+h(v)。

一致性蕴含可采纳性，并使节点从优先队列取出时其最短距离已确定，可将每个节点视作最多扩展一次。若只有可采纳性而不一致，必须允许节点在找到更短路径时重新入队；下面的代码用距离表和过期状态检查实现重开，不使用永久关闭集合。非负边权是 Dijkstra/A* 这类代价搜索的重要前提。

Java 实现：邻接表与优先队列

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class AStarSearch {
    public static final class Edge {
        public final int to;
        public final long cost;

        public Edge(int to, long cost) {
            if (cost < 0) {
                throw new IllegalArgumentException("edge costs must be non-negative");
            }
            this.to = to;
            this.cost = cost;
        }
    }

    private static final class State {
        final int node;
        final long g;
        final long f;

        State(int node, long g, long f) {
            this.node = node;
            this.g = g;
            this.f = f;
        }
    }

    public static long shortestDistance(
        List<List<Edge>> graph, int start, int goal, long[] heuristic
    ) {
        int n = graph.size();
        if (heuristic.length != n || start < 0 || start >= n
            || goal < 0 || goal >= n) {
            throw new IllegalArgumentException("invalid graph or endpoints");
        }
        if (heuristic[goal] != 0) {
            throw new IllegalArgumentException("heuristic(goal) must be zero");
        }

        long[] distance = new long[n];
        Arrays.fill(distance, Long.MAX_VALUE);
        distance[start] = 0;
        PriorityQueue<State> queue = new PriorityQueue<>(
            (a, b) -> Long.compare(a.f, b.f)
        );
        queue.add(new State(start, 0, heuristic[start]));

        while (!queue.isEmpty()) {
            State state = queue.remove();
            if (state.g != distance[state.node]) {
                continue;
            }
            if (state.node == goal) {
                return state.g;
            }
            for (Edge edge : graph.get(state.node)) {
                long next = state.g + edge.cost;
                if (next < distance[edge.to]) {
                    distance[edge.to] = next;
                    queue.add(new State(
                        edge.to, next, next + heuristic[edge.to]
                    ));
                }
            }
        }
        return -1;
    }
}

Python 实现

from __future__ import annotations

import heapq

def astar(
    graph: list[list[tuple[int, int]]],
    start: int,
    goal: int,
    heuristic: list[int],
) -> int | None:
    n = len(graph)
    if len(heuristic) != n or not (0 <= start < n and 0 <= goal < n):
        raise ValueError("invalid graph or endpoints")
    if heuristic[goal] != 0:
        raise ValueError("heuristic(goal) must be zero")

    distance: list[int | None] = [None] * n
    distance[start] = 0
    queue = [(heuristic[start], 0, start)]
    while queue:
        _, cost_so_far, node = heapq.heappop(queue)
        if cost_so_far != distance[node]:
            continue
        if node == goal:
            return cost_so_far
        for neighbor, edge_cost in graph[node]:
            if edge_cost < 0:
                raise ValueError("edge costs must be non-negative")
            candidate = cost_so_far + edge_cost
            if distance[neighbor] is None or candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heapq.heappush(
                    queue, (candidate + heuristic[neighbor], candidate, neighbor)
                )
    return None

graph = [[(1, 2), (2, 5)], [(2, 1)], []]
assert astar(graph, 0, 2, [1, 0, 0]) == 3
assert astar(graph, 2, 0, [0, 0, 0]) is None

正确性与复杂度

对于可采纳启发式，任一尚未完成的最优路径前缀 v 都有 g(v)+h(v) 不大于最优完整路径代价。优先队列因此不会在仍有更优候选路径时，先把代价更大的目标状态确认为答案。代码只在弹出队列且条目仍对应当前最短 g 值时返回目标。若启发式不一致，较短的 g 值会重新入队，避免错误地永久锁定旧路径。

一致启发式下，每个顶点至多扩展一次，使用二叉堆的图搜索时间为 O((V+E) log V)，空间 O(V+E)（邻接表计入图存储）。启发式较弱时 A* 会接近 Dijkstra；可采纳但不一致时节点可能反复扩展，不能直接套用“一次扩展”的复杂度界。状态空间搜索中，启发式仍可能面对指数级搜索规模。

边界与易错点

• 启发式高估真实剩余成本时，可采纳性失效，返回结果不再保证最优。
• 一致性不是写代码时默认成立的性质；要根据估价定义和每条边的代价证明。
• 无效或过期的队列项要跳过，否则可能重复扩展旧状态。
• 图无解时返回哨兵值（Java -1，Python None），调用方要区分它与合法距离。
• 实际实现还应根据输入上界检查加法溢出；示例用 long，但极大权重仍需限制。

A* 的关键并非“加一个启发式就更快”，而是启发式影响探索顺序、正确性假设约束可否早停。启发信息越贴近真实剩余成本，通常越少扩展状态，但它的构造和证明同样是算法的一部分。