A* 启发式搜索算法 - NOI提高级教程

📖 算法原理：估价函数与智能导引

宽度优先搜索 (BFS) 会盲目以起点为圆心铺满四周；Dijkstra 考虑了路程权重但依然漫无目的。A* 算法通过引入启发式估价函数 (Heuristic)，使寻路方向如同有雷达精确制导般直指终点。

📐 A* 核心数学估价公式

对于任意格子节点 $n$，其综合评估代价 $f(n)$ 计算公式为：

$$\color{cyan} f(n) = g(n) + h(n)$$

$g(n)$：从起点到当前节点 $n$ 的实际已知代价/步数。
$h(n)$：从当前节点 $n$ 到终点的估计未来代价/步数（通常使用曼哈顿距离或欧几里得距离）。
曼哈顿距离公式：$h(n) = |n.x - target.x| + |n.y - target.y|$。

定理（可采纳性 Admissibility）：只要我们的估计值 $h(n)$ 始终小于或等于实际最短距离，A* 算法就必然能找到全局最优最短路径！

寻路模式：

演示速度：

用鼠标点击或拖拽网格可以直接绘制/擦除墙壁，拖拽 S（起点）或 E（终点）可以更改其坐标。然后点击"开始寻路"。

已扫描节点数 (Visited) 0

队列中待处理数 (Open Set) 0

最终路径长度 (Path) 0

🕸️ 2D 迷宫拓扑网格 (点击绘制墙壁)

struct Node {
    int x, y, g, h, f;
    bool operator<(const Node& o) const {
        return f > o.f; // 估价 f 越小优先级越高 (小顶堆)
    }
};

void aStar() {
    priority_queue<Node> open_set;
    open_set.push({startX, startY, 0, getH(startX, startY), getH(startX, startY)});
    
    while (!open_set.empty()) {
        Node curr = open_set.top(); open_set.pop();
        if (curr.x == endX && curr.y == endY) {
            reconstructPath(); // 寻获终点，回溯路径
            return;
        }
        for (auto next : getNeighbors(curr)) {
            int next_g = curr.g + 1;
            int next_h = getH(next.x, next.y);
            int next_f = next_g + next_h; // 核心启发式估价
            
            if (next_f < dist[next.x][next.y]) {
                dist[next.x][next.y] = next_f;
                open_set.push({next.x, next.y, next_g, next_h, next_f});
            }
        }
    }
}

📋 A* 寻路状态流与估价历史