Lesson 54: A*寻路算法

练习任务

难度：中

在 6 行 × 5 列的网格地图上实现 A* (A-Star) 寻路算法，从起点 (0,0) 找到终点 (5,4) 的最短路径，绕过四个障碍物 (2,2), (3,2), (1,3), (3,3)。你需要完成四个核心任务：

定义 Node 结构体 — 坐标 r/c、代价 g/h/f、parent 索引、closed 标记；声明全局 nodes[] 数组和 node_count
实现 heuristic() 函数 — Manhattan 距离：|r - gr| + |c - gc|
补全 A 主循环* — Open/Closed 数组管理 + 四方向邻居扩展（边界检查、障碍物跳过）
实现路径重建 — 从终点沿 parent 回溯到起点，逆序输出坐标和路径长度

main() 框架已提供：初始化起点、调用 find_or_create、打印格式信息。find_or_create 和 pick_best 的骨架在注释中给出。

验证方式：

make test

make test 编译程序后运行，通过管道 | diff 比对 expected_output.txt。

提示：A* 的核心是 f = g + h——每一步都选"已走距离 + 估计剩余距离"最小的节点扩展。Manhattan 距离满足可接受性（admissible），保证找到最优解。Open 表 = closed==false 的节点，Closed 表 = closed==true 的节点。路径回溯从终点沿 parent 走到起点（parent=-1），然后逆序输出。

核心知识点

盲目搜索 vs 启发式搜索 — BFS 按层、Dijkstra 按 g(n)、贪心按 h(n)、A* 按 f(n)=g(n)+h(n) 扩展，四者在评估函数、最优性保证、扩展效率上的逐维差异
f = g + h 的含义 — g 是"沉没成本"（已走步数），h 是"未来估计"（预测剩余步数），f 是"总账"。A* 永远优先探索总账最低的路径
Manhattan 距离的可接受性 — h(r,c) = |r-gr| + |c-gc|，对四方向网格从不高于实际剩余步数，因此保证最优。推导：每步最多减少一项绝对值，总步数 ≥ |Δr|+|Δc|
Open/Closed 表管理 — 同一数组 nodes[] 通过 closed 标志区分两表；find_or_create 在重访同一格子时保留 g 更小的路径（最优子结构）
6×5 网格追踪 — 障碍物 (2,2)/(3,2)/(1,3)/(3,3) 构成"墙"，迫使路径沿左下绕行；全程 f=9 恒为常数的现象解读（每远一步 g+1 就离终点近一步 h-1）
路径回溯重建 — parent 存 nodes[] 数组索引（非坐标），从终点逆链到起点后逆序输出，路径长度 = path_len - 1（步数，起点不算一步）
A vs Dijkstra vs BFS 对比* — 评估函数、数据结构、扩展方向、节点数、最优性保证的三维对比；h=0 时 A* 退化为 Dijkstra；h 高估时退化为贪心

代码框架

54_astar_pathfinding.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define ROWS 6
#define COLS 5
#define MAX_NODES (ROWS * COLS)

/* 地图：0=可通行，1=障碍物 */
static const int OBS[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
};

/* ─── TODO 1: Node 结构体 ─── */
// struct Node { int r,c,g,h,f,parent; bool closed; };
// Node nodes[MAX_NODES];
// int node_count = 0;

/* ─── TODO 2: heuristic — Manhattan 距离 ─── */
// static int heuristic(int r, int c, int gr, int gc) {
//     return abs(r - gr) + abs(c - gc);
// }

/* ─── 已有骨架: find_or_create ─── */
// static int find_or_create(int r, int c, int g, int parent,
//                           int gr, int gc) {
//     /* ① 遍历 nodes，若坐标已存在：
//      *     若新 g < 旧 g → 更新 g/f/parent（更优路径）
//      *     return 该索引
//      * ② 若不存在：创建 Node 加入 nodes
//      *    h = heuristic(r,c,gr,gc); f = g + h
//      *    node_count++; return 新索引
//      */
// }

/* ─── 已有骨架: pick_best ─── */
// static int pick_best(void) {
//     /* ① 遍历 nodes  跳过 closed==true
//      * ② 找 f 最小的索引
//      *    f 相同时选 h 更小的（打破平局）
//      * ③ 无可选节点返回 -1
//      */
// }

int main(void) {
    int sr = 0, sc = 0, gr = 5, gc = 4;
    printf("=== A* Pathfinding: 6x5 Grid ===\n");
    printf("Start: (%d,%d)  Goal: (%d,%d)\n", sr, sc, gr, gc);
    printf("Obstacles: (2,2) (3,2) (1,3) (3,3)\n\n");

    node_count = 0;
    find_or_create(sr, sc, 0, -1, gr, gc);
    int goal_idx = -1;

    /* ═══ TODO 3: A* 主循环 ═══
     * while (1):
     *   ① cur = pick_best() → 若 < 0 则 break
     *   ② nodes[cur].closed = true
     *   ③ 打印 "Expand: (r,c) g=X h=Y f=Z"
     *   ④ 若 (r,c) 是终点 → goal_idx = cur; break
     *   ⑤ 扩展四个方向邻居 (上/下/左/右):
     *      - 检查边界: 0 <= nr < ROWS, 0 <= nc < COLS
     *      - 检查障碍物: if (OBS[nr][nc]) continue
     *      - ng = nodes[cur].g + 1
     *      - find_or_create(nr, nc, ng, cur, gr, gc)
     */

    /* ═══ TODO 4: 路径重建 ═══
     * if (goal_idx < 0) → printf("No path found.\n");
     * else:
     *   ① path[] 从 goal_idx 沿 parent 回溯到 -1
     *   ② 打印 "Path found (length=X):" 其中 X = path_len - 1
     *   ③ 逆序打印 "(r,c) -> " （最后一个不带箭头）
     */
    return 0;
}

阅读骨架后，尝试自己填充 TODO 1-4。核心挑战在于：f = g + h 的"总账"概念如何在在 pick_best 中生效？find_or_create 在重访已有节点时如何保留更优路径？parent 存索引而非坐标——回溯时如何利用这一设计？

TIP

先不要往下翻看参考解答。用纸笔画出 6×5 网格，手工追踪 A* 的 10 步扩展过程。重点关注每一步扩展节点的 f 值——你会发现它们始终是 9，为什么？

深度讲解

1. 盲目搜索上的启发式搜索——两种根本不同的策略

1.1 图搜索的通用框架

寻路问题本质上是图搜索：每个可通行格子是一个节点，相邻格子之间有无权边（代价为 1）。给定起点和终点，目标是找到一条代价最小的路径。

所有图搜索算法共享一个通用框架：

通用搜索框架:
  Open ← {起点}
  while Open 非空:
    cur ← 从 Open 中选出一个节点
    if cur == 终点: 返回路径
    Closed ← Closed ∪ {cur}
    for 邻居  in cur.邻居:
      if 邻居 ∉ Closed:
        更新邻居的代价 / 将邻居加入 Open

不同算法的唯一区别在于"按什么标准从 Open 表中选节点"。

1.2 四种算法的逐维对比

evaluation_functions.c

/*
 * 四种算法的评估函数差异:
 *
 * BFS:        无评估函数——按 FIFO 顺序取，等价于按层扩展
 * Dijkstra:   f(n) = g(n)     ——"已走最少"优先
 * 贪心最佳优先: f(n) = h(n)   ——"离终点最近估计"优先
 * A*:         f(n) = g(n) + h(n) ——"总账最低"优先
 */

算	评估函数	数据结构	扩展方向	最优性	扩展节点数
BFS	无	队列	所有方向均匀	保证（均匀代价）	多
Dijkstra	f = g	优先队列	按 g 从小到大	保证	中
贪心最佳优先	f = h	优先队列	偏向终点方向	不保证	少（但可能绕远）
A*	f = g + h	优先队列	平衡方向	保证（h 可接受时）	少（且最优）

IMPORTANT

A* 是 Dijkstra 和贪心最佳优先的TODO 1：g(n) 保证最优性（来自 Dijkstra），h(n) 提供方向性（来自贪心）。单独使用任一项都有缺陷——只用 g 则"漫无目的"，只用 h 则"急功近利"下A* 在两者间取得平衡。

Dijkstra 的行为（h=0 → 只看已走距离）:

     S ──·──·──·──终点
     |   |   |   |
     · ──·──·───·
     |   |   |   |
     · ──·──·──·

  从起点向所有方向均匀扩展——像水波扩散。
  保证最优，但效率低：会探索大量与终点方向无关的节点。

贪心最佳优先的行为（只看 h, 忽略 g）:

     S ──·──·──·──终点
                 |
     · ──·──·─────·  ← 直奔终点方向，撞墙后才绕路
                 |
     · ──·──·──·

  直奔终点方向——可能走"死胡同"后绕远。
  效率高但不保证最优。

A* 的行为（看 g + h）:

     S ──·──·──·──终点
     |           |
     · ──·──墙──墙──·
     |           |
     · ──·──·──·──·

  沿左下绕路——既不走"回头路"（g 约束），
  也不盲目冲向墙（h 约束）。直奔目标方向，
  同时绕开障碍物。

2. A* 的核心思想：f = g + h

2.1 三个分量的含义

┌─────────────────────────────────────────────────┐
│                  f(n) = g(n) + h(n)              │
│                   ↑        ↑        ↑            │
│               总估计代价  实际代价  启发值       │
                 (总账)     (沉没成本) (未来预测)     │
└─ ┌───────────────────────────────────────────────┘

g(n): 从起点到节点 n 的已知实际代价
      → "我已经走了多远"（确定性事实）

h(n): 从节点 n 到终点的估计剩余代价
      → "我大概还要走多远"（启发猜测）

f(n): 经过节点 n 的完整路径估计总代价
      → "走这条路总共要花多少"（综合评估）

2.2 城市导航类比——最直观的理解

比喻: 你在陌生城市开车去机场。

  g = 里程表读数（已经开了多少公里）—— 确定的事实
  h = GPS 估算剩余距离              —— 合理的猜测
  f = 预计总里程                    —— 综合判断

    你不会只按"离机场直线最近"选路（可能走断头路），
  也不会只按"已经开得最少"选路（可能往反方向开）。
  A* 同时看两者: "我已经开了这么多 + 估计还要开那么多"。

2.3 f 值在无障碍直线路径上恒为常数

这是理解 A* 效率的关键现象。假设无障碍物、走直线路径：

起点 (0,0)  终点 (0,9)  网格 1×10（单行）

    g: 0  1  2  3  4  5  6  7  8  9
    h: 9  8  7  6  5  4  3  2  1  0
    f: 9  9  9  9  9  9  9  9  9  9  ← 始终为 9！

每远离起点一步 (g+1)，就离终点近一步 (h-1)。
g 和 h 的变化恰好抵消，f 保持恒定。

NOTE

这就是 A* 在无障碍直线上"不需选择"的原因——路径上所有节点的 f 值相同，任意扩展都沿着最优方向。如果 H(n) 恰好等于实际剩余距离（完美启发），A* 只扩展最优路径上的节点，零浪费。虽然完美启发通常不可得，但 f=g+h 的设计已经让 A* 在"接近直线"的场景中极为高效。

3. Manhattan 距离——网格世界的天然启发函数

3.1 公式与得名

对于四方向网格（只允许上下左右移动，不允许对角线），Manhattan 距离是最广泛使用的启发函数：

heuristic_formula.c

/*
 * Manhattan 距离启发函数
 *
 * h(r, c) = |r - goal_r| + |c - goal_c|
 *
 * 得名: 曼哈顿的街道呈棋盘状，你只能沿街道南北或东西走，
 *       不能"穿越大楼走对角线"——恰好对应四方向网格移动。
 */
static int heuristic(int r, int c, int gr, int gc) {
    return abs(r - gr) + abs(c - gc);
}

示例计算: 起点 (0,0), 终点 (5,4)

  h(0,0) = |0-5| + |0-4| = 5 + 4 = 9
  h(1,0) = |1-5| + |0-4| = 4 + 4 = 8
  h(3,2) = |3-5| + |2-4| = 2 + 2 = 4
  h(5,4) = |5-5| + |4-4| = 0 + 0 = 0  ← 终点 h=0

3.2 可接受性（Admissibility）——为什么 A* 保证最优

如果一个启发函数从不高估实际剩余代价（即对所有节点 n，h(n) ≤ h*(n)，其中 h* 是真实最短距离），则称该启发函数是可接受的（admissible）。

Manhattan 距离在四方向网格上是可接受的，严格证明如下：

证明: 对四方向网格上的任意节点 (r,c) 到终点 (gr,gc):

  1. 每步只能改变一行或一列的坐标，且每步变化量的绝对值恰好为 1
  2. 要从行坐标 r 变到 gr，至少需要 |r - gr| 步（每步最多改变行坐标 1）
  3. 要从列坐标 c 变到 gc，至少需要 |c - gc| 步（每步最多改变列坐标 1）
  4. 一个移动不能同时改变行和列（四方向约束）
  5. 因此总步数 ≥ |r - gr| + |c - gc| = h(r,c)

  ∴ h(r,c) ≤ h*(r,c) 对于所有 (r,c) 成立 ∎

IMPORTANT

如果启发函数高估了实际代价（h(n) > h*(n)），A* 可能错过更优路径——它会过早地把某个"看起来近但实际远"的节点其移入 Closed 表，而这个节点可能在另一条更优路径上。Manhattan 距离的可接受性正是 A* 最优性的数学保障。

3.3 四种启发函数的适用场景

heuristic_comparison.c

/*
 * 四种常见启发函数及其适用移动方式
 *
 * Manhattan:  |dr| + |dc|                    → 四方向（上下左右）
 * Euclidean:  sqrt(dr² + dc²)                → 任意角度
 * Chebyshev:  max(|dr|, |dc|)                → 八方向（含对角线）
 * Diagonal:   |dr|+|dc| + (√2-2)*min(|dr|,|dc|) → 八方向，代价为 1 和 √2
 */

扩展节点数	公式	移动方式	可接受性
Manhattan	\|Δr\| + \|Δc\|	四方向	可接受
Euclidean	√(Δr² + Δc²)	任意角度	可接受（可能低估）
Chebyshev	max(\|Δr\|, \|Δc\|)	八方向	可接受
Diagonal	\|Δr\|+\|Δc\|+(√2-2)×min(\|Δr\|,\|Δc\|)	八方向	可接受

CAUTION

本题只能四方向移动。如果误用 Chebyshev 距离（max(|dr|,|dc|)）作为启发函数，当对角移动不被允许时，它可能高估实际代际代价 → A* 不保证最优。例如从 (0,0) 到 (5,5)：Chebyshev h=5，但实际最短需要 10 步（不行对角线），h > h* → 不可接受。

4. Open/Closed 表的数组实现

4.1 一张数组，两套语义

本题不使用优先队列——因为 6×5=30 个节点，每次 O(n) 遍历完全足够。更重要的是，这让学生能直接看到表的部状态，不被优先队列的黑盒遮蔽。

┌────────────────────────────────────────────┐
│           nodes[MAX_NODES]                 │
├────┬────┬────┬────┬────┬────┬────┬────────┤
│ N0 │ N1 │ N2 │ N3 │ N4 │ N5 │ N6 │ ...    │
├────┴────┴────┴────┴────┴────┴────┴────────┤
│  ↑                          ↑             │
│  closed=false               closed=true    │
│  → 在 Open 表（候选）       → 在 Closed 表（已处理）│
└────────────────────────────────────────────┘

Open 表  = { i | nodes[i].closed == false }  ← 还需扩展的候选
Closed 表 = { i | nodes[i].closed == true  }  ← 已扩展，不再考虑

4.2 pick_best() — 从 Open 表选最优节点

pick_best.c

/*
 * 从 Open 表中选出 f 最小的节点
 * f 相同时选 h 更小的（更接近终点，打破平局）
 */
static int pick_best(void) {
    int best_idx = -1;
    int best_f = 999999;
    int best_h = 999999;

    for (int i = 0; i < node_count; i++) {
        if (nodes[i].closed) continue;  // 跳过 Closed 表

        // f 更小 → 直接替换
        if (nodes[i].f < best_f) {
            best_f = nodes[i].f;
            best_h = nodes[i].h;
            best_idx = i;
        }
        // f 相同且 h 更小 → 打破平局，选更接近终点的
        else if (nodes[i].f == best_f && nodes[i].h < best_h) {
            best_h = nodes[i].h;
            best_idx = i;
        }
    }
    return best_idx;  // 无可选节点时返回 -1
}

pick_best 的行为示意（假设当前状态）:

  nodes[]:
  [0] (0,0) g=0 h=9 f=9 closed=true   ← 跳过
  [1] (1,0) g=1 h=8 f=9 closed=false  ← 候选 f=9
  [2] (2,0) g=2 h=7 f=9 closed=false  ← 候选 f=9
  [3] (3,0) g=3 h=6 f=9 closed=false  ← 候选 f=9
  [4] (0,1) g=1 h=8 f=9 closed=false  ← 候选 f=9
  ...

  所有候选 f 都是 9 → 选 h 最小的 = (3,0) h=6
  → 打破平局，偏向更接近终点的节点

4.3 find_or_create() — 节点查找与创建

这是节点管理的核心——需要处理同一格子被不同路径发现的情况：

find_or_create.c

/*
 * 查找或创建节点
 *
 * 输入: 坐标 (r,c)、从 cur 出发的新代价 g、父索引 parent、终点 (gr,gc)
 *
 * 逻辑:
 *   1. 如果该坐标已在 nodes[] 中存在:
 *      - 若新 g < 旧 g → 更新 g/f/parent（找到了更短的到达路径）
 *      - 返回该节点索引
 *   2. 如果该坐标尚未在 nodes[] 中:
 *      - 创建 Node{h=heuristic(...), f=g+h, parent, closed=false}
 *      - node_count++
 *      - 返回新索引
 */
static int find_or_create(int r, int c, int g, int parent,
                          int gr, int gc) {
    // 查找是否已存在
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].r == r && nodes[i].c == c) {
            // 已存在: 如果新 g 更优则更新
            if (g < nodes[i].g) {
                nodes[i].g = g;
                nodes[i].f = g + nodes[i].h;  // h 不变，f 随之更新
                nodes[i].parent = parent;
            }
            return i;
        }
    }

    // 不存在: 创建新节点
    Node n;
    n.r = r; n.c = c;
    n.g = g;
    n.h = heuristic(r, c, gr, gc);
    n.f = n.g + n.h;
    n.parent = parent;
    n.closed = false;

    nodes[node_count] = n;
    return node_count++;
}

CAUTION

更新已有节点时，必须同时更新 f = g + h。许多初学者只更新 g 而忘记更新 f，导致 pick_best() 基于过时的 f 值做决策——A* 的核心机制被破坏，可能返回非最优路径。

4.4 数组 Open 表 vs 优先队列

维度	数组实现（本题）	二叉堆/优先队列
pick_best()	O(n) 遍历	O(log n)
插入节点	O(1)	O(log n)
更新节点 g	O(1) 原地修改	O(log n) 需调整堆
代码复杂度	低	中
适用规模	小网格 (n ≤ 30)	大网格 (n > 1000)

对于 6×5 = 30 个节点，数组 O(n) 遍历总开销 ≈ 30×30 = 900 次比较——毫秒级完成。优先队列的优势在 1000×1000 大型地图中才会体现。

5. 完整逐步追踪：6×5 障碍网格

5.1 地图可视化

         c0    c1    c2    c3    c4
      ┌─────┬─────┬─────┬─────┬─────┐
  r0  │  S  │  ·  │  ·  │  ·  │  ·  │     S = 起点 (0,0)
      ├─────┼─────┼─────┼─────┼─────┤
  r1  │  ·  │  ·  │  ·  │  X  │  ·  │     G = 终点 (5,4)
      ├─────┼─────┼─────┼─────┼─────┤
  r2  │  ·  │  ·  │  X  │  ·  │  ·  │     X = 障碍物
      ├─────┼─────┼─────┼─────┼─────┤
  r3  │  ·  │  ·  │  X  │  X  │  ·  │     · = 可通行
      ├─────┼─────┼─────┼─────┼─────┤
  r4  │  ·  │  ·  │  ·  │  ·  │  ·  │
       ┌─────┼─────┼─────┼─────┼─────┤
  r5  │  ·  │  ·  │  ·  │  ·  │  G  │
      └─────┴─────┴─────┴─────┴─────┘

障碍物 (2,2), (3,2), (1,3), (3,3) 形成一道"墙"，迫使路径沿左下侧或右上侧绕行。

5.2 逐步追踪表

步骤	扩展节点	g	h	f	说明
0	(0,0)	0	9	9	起点入 Open 表，向下扩展
1	(1,0)	1	8	9	继续向下（f 仍为 9）
2	(2,0)	2	7	9	右侧 (2,1) → (2,2) 被障碍物阻挡，向下
3	(3,0)	3	6	9	障碍物封锁右上角 (3,2),(3,3)，继续向下
4	(4,0)	4	5	9	到达底部边界附近
5	(5,0)	5	4	9	到达底部，向右拐弯
6	(5,1)	6	3	9	沿底部向右
7	(5,2)	7	2	9	继续向右（障碍物在上面一行）
8	(5,3)	8	1	9	接近终
9	(5,4)	9	0	9	到达终点！

路径: (0,0) → (1,0) → (2,0) → (3,0) → (4,0) → (5,0) → (5,1) → (5,2) → (5,3) → (5,4)

路径长度: 9 步

5.3 f 值始终为 9 的直观解释

沿最优路径前进时:
  g 每步 +1（远离起点一步）
  h 每步 -1（接近终点一步）
  f = g + h = 常数 9

这是 A* 在"无障碍直线"路径上的典型行为:
  只要沿着"正方向"移动，f 值恒为常数。
  如果往反方向走一步: g+1, h+1 → f+2（f 变大 → 不会被优先选）。
  如果横向绕路: g+1, h 不变 → f+1（f 变大 → 次优选）。

NOTE

路径上所有节点的 f 都是 9——这意味着只要沿着正确方向走，"总账"不变。A* 在众多 f=9 的节点中通过 h 打破平局（选 h 更小的 = 更接近终点的），因此一步步将 h 从 9 降到 0。

5.4 为什么不是上面的路径？

上面也有一条等长路径:
  (0,0)→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)→(2,4)→(3,4)→(4,4)→(5,4)
  同样是 9 步。

两条路径的 f 值在整个过程中都是 9。选择哪条取决于:
  1. 邻居扩展顺序（本题先扩展"下"方向。
  2. pick_best() 的平局策略（f 相同时选 h 更小）

  向下走: (1,0) h=8  →  向右走: (0,1) h=8
  h 相同 → 取决于谁先被加入 Open 表。
  本题先扩展"下"方向 → 走底部路线。

6. 路径回溯重建——从 parent 链提取路径

6.1 parent 存索引而非坐标

parent_index.c

/*
 * parent 字段存储 nodes[] 数组的索引，而不是坐标对。
 *
 * 为什么这样设计？
 *   存索引 → nodes[parent] 可立即获取父节点的所有信息
 *           （坐标、g/h/f、甚至父节点的父节点）
 *   存坐标 → 每次回溯需遍历 nodes 查找对应坐标 → O(n) 每次跳跃
 */

parent 链的可视化:

  nodes[0]: (0,0) parent=-1   ← 起点，无父节点（根）
  nodes[1]: (1,0) parent=0    ← 父节点是 nodes[0]
  nodes[2]: (2,0) parent=1    ← 父节点是 nodes[1]
  nodes[3]: (3,0) parent=2    ← ...
  nodes[4]: (4,0) parent=3
  nodes[5]: (5,0) parent=4
  nodes[6]: (5,1) parent=5
  nodes[7]: (5,2) parent=6
  nodes[8]: (5,3) parent=7
  nodes[9]: (5,4) parent=8    ← 终点

回溯: nodes[9] → nodes[8] → nodes[7] → ... → nodes[0]
      逆链: (5,4)→(5,3)→(5,2)→...→(0,0)

6.2 路径重建代码

path_reconstruct.c

/*
 * 路径重建：从终点沿 parent 回溯到起点并逆序输出
 */
int path[MAX_NODES];
int path_len = 0;

// ① 从终点沿 parent 链回溯
int cur = goal_idx;
while (cur != -1) {
    path[path_len++] = cur;   // 存入索引
    cur = nodes[cur].parent;  // 跳转到父节点
}
// 此时 path[] = [终点, ..., 起点]，path_len 包含起点

// ② 打印路径信息
printf("\nPath found (length=%d):\n", path_len - 1);  // 步数 = 节点数 - 1
printf("  ");

// ③ 逆序输出（从起点到终点）
for (int i = path_len - 1; i >= 0; i--) {
    printf("(%d,%d)", nodes[path[i]].r, nodes[path[i]].c);
    if (i > 0) printf(" ->  ");  // 最后一个不加箭头
}
printf("\n");

path[] 数组的内容和执行流程:

  回溯后 path[]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
                 终点                        起点

  path_len = 10 → 路径长度 = 10 - 1 = 9 步

  逆序输出: path[9]→path[8]→...→path[0]
  即: (0,0)→(1,0)→(2,0)→...→(5,4) ✓

TIP

路径长度 = path_len - 1（步数 = 节点数 - 1）。如果打印 path_len（10）而非 path_len - 1（9），路径长度就多算了一步。这就是 exercises.toml 中 length=9 而非 10 的原因。

7. A* vs Dijkstra vs BFS——三维对比与算法退化

7.1 对比总结

algorithm_comparison.c

/*
 * 三种算法的本质差异在于"按什么标准选下一个节点":
 *
 * BFS:      无评估 → 按层扩展 → 适合无权图
 * Dijkstra: f = g  → 按已走距离扩展 → 适合加权图
 * A*:        f = g + h → 按总账扩展 → 适合有启发信息的图
 *
 * 数据结构:
 *   BFS: 队列 (FIFO)
 *   Dijkstra: 优先队列 (按 g)
 *   A*: 优先队列 (按 f)
 */

维度	BFS	Dijkstra	A*
评估函数	无（FIFO）	f = g	f = g + h
扩展方向	所有方向均匀	按 g 从小到大	偏向终点方向
最优性	保证（均匀代价）	保证	保证（h 可接受时）
扩展节点数	多（O(b^d)）	中	少（取决于 h 精度）
适用场景	无权图	加权图	有启发信息的图

7.2 算法退化——h(n) = 0 和高估的两极

algorithm_degradation.c

/*
 * A* 的退化行为取决于启发函数:
 *
 * 1. h(n) = 0 → f(n) = g(n) → A* 退化为 Dijkstra
 *    → 仍然保证最优，但效率降低（向所有方向均匀扩展）
 *
 * 2. h(n) >> g(n) → f(n) ≈ h(n) → A* 退化为贪心最佳优先
 *    → 效率高但不保证最优（可能绕远路）
 */

h(n) = 0 时的行为（退化为 Dijkstra）:

     S ──·──·──·──终点
     |   |   |   |
     · ──·──·──·
     |   |   |   |
     · ──·──·──·

  像水波从起点均匀扩散——会扩展大量无关节点，
  直到"水波"碰到终点。保证最优但浪费。

h(n) = 100 × Manhattan 时的行为（退化为贪心）:

     S ──·──·──·──终点
                 |
     · ──·──·──墙──·  ← 直奔终点方向，撞墙后绕远
                 |
     · ──·──·──·

  只看到 h（未来预测），忽略 g（已走距离）。
  可能走更长的路——不保证最优。

IMPORTANT

A* 的最优性依赖于可接受启发（h ≤ h*）。只要满足这个条件，无论 h 多"弱"（如 h=0），A* 都保证最优。h 越接近真实 h*，效率越高——极端情况下（h = h*），A* 只扩展最优路径上的节点。

7.3 为什么本题不需要优先队列

网格大小: 6 × 5 = 30 个格子 (MAX_NODES = 30)

数组实现:
  pick_best(): 每次遍历 30 个节点 → 30 次比较
  总遍历次数: 约 10 次扩展 × 30 = 300 次比较
  总开销: 微秒级

二叉堆实现:
  pick_best(): O(log 30) ≈ 5 次比较
  每个邻居插入: O(log 30) 堆调整
  总开销: 纳秒级（无人察觉的差异）

结论:
  30 个节点量级下，O(n) 和 O(log n) 的差异是理论上的。
  本题的目的不是性能——而是让你直接看到表的内部状态，
  理解 Open/Closed 的语义，不被优先队列黑盒遮蔽。

参考解答

练习1: Node 结构体 + heuristic + find_or_create + pick_best

solution_54_astar_definitions.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define ROWS 6
#define COLS 5
#define MAX_NODES (ROWS * COLS)

static const int OBS[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
};

/* TODO 1: Node 结构体 */
typedef struct {
    int r, c;       // 坐标
    int g;          // 从起点到当前节点的实际代价
    int h;          // 启发函数值（到终点的估计代价）
    int f;          // f = g + h
    int parent;     // 父节点在 nodes[] 中的索引，起点为 -1
    bool closed;    // true = 已扩展（在 Closed 表中）
} Node;

Node nodes[MAX_NODES];
int node_count = 0;

/* TODO 2: Manhattan 启发函数 */
static int heuristic(int r, int c, int gr, int gc) {
    return abs(r - gr) + abs(c - gc);
}

/* 查找或创建节点 */
static int find_or_create(int r, int c, int g, int parent,
                          int gr, int gc) {
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].r == r && nodes[i].c == c) {
            if (g < nodes[i].g) {
                nodes[i].g = g;
                nodes[i].f = g + nodes[i].h;
                nodes[i].parent = parent;
            }
            return i;
        }
    }
    nodes[node_count].r = r;
    nodes[node_count].c = c;
    nodes[node_count].g = g;
    nodes[node_count].h = heuristic(r, c, gr, gc);
    nodes[node_count].f = nodes[node_count].g + nodes[node_count].h;
    nodes[node_count].parent = parent;
    nodes[node_count].closed = false;
    return node_count++;
}

/* pick_best: 从 Open 表中选 f 最小的节点 */
static int pick_best(void) {
    int best = -1;
    int best_f = 999999;
    int best_h = 999999;
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].closed) continue;
        if (nodes[i].f < best_f) {
            best_f = nodes[i].f;
            best_h = nodes[i].h;
            best = i;
        } else if (nodes[i].f == best_f && nodes[i].h < best_h) {
            best_h = nodes[i].h;
            best = i;
        }
    }
    return best;
}

要点：Node 结构体 6 个字段覆盖了 A* 的全部状态。find_or_create 处理"重访已有节点"场景——保留 g 更小的路径（体现最优子结构）。pick_best 的平局策略选 h 更小的（偏向终点方向）。

练习2: A* 主循环 + 路径重建（完整程序）

solution_54_astar_complete.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define ROWS 6
#define COLS 5
#define MAX_NODES (ROWS * COLS)

static const int OBS[ROWS][COLS] = {
    {0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
};

typedef struct {
    int r, c, g, h, f, parent;
    bool closed;
} Node;

Node nodes[MAX_NODES];
int node_count = 0;

static int heuristic(int r, int c, int gr, int gc) {
    return abs(r - gr) + abs(c - gc);
}

static int find_or_create(int r, int c, int g, int parent,
                          int gr, int gc) {
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].r == r && nodes[i].c == c) {
            if (g < nodes[i].g) {
                nodes[i].g = g;
                nodes[i].f = g + nodes[i].h;
                nodes[i].parent = parent;
            }
            return i;
        }
    }
    nodes[node_count].r = r;
    nodes[node_count].c = c;
    nodes[node_count].g = g;
    nodes[node_count].h = heuristic(r, c, gr, gc);
    nodes[node_count].f = nodes[node_count].g + nodes[node_count].h;
    nodes[node_count].parent = parent;
    nodes[node_count].closed = false;
    return node_count++;
}

static int pick_best(void) {
    int best = -1, best_f = 999999, best_h = 999999;
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].closed) continue;
        if (nodes[i].f < best_f) {
            best_f = nodes[i].f;
            best_h = nodes[i].h;
            best = i;
        } else if (nodes[i].f == best_f && nodes[i].h < best_h) {
            best_h = nodes[i].h;
            best = i;
        }
    }
    return best;
}

int main(void) {
    int sr = 0, sc = 0, gr = 5, gc = 4;
    printf("=== A* Pathfinding: 6x5 Grid ===\n");
    printf("Start: (%d,%d)  Goal: (%d,%d)\n", sr, sc, gr, gc);
    printf("Obstacles: (2,2) (3,2) (1,3) (3,3)\n\n");

    node_count = 0;
    find_or_create(sr, sc, 0, -1, gr, gc);
    int goal_idx = -1;

    /* ─── A* 主循环 ─── */
    while (1) {
        int cur = pick_best();
        if (cur < 0) break;  // Open 表空 → 无路可走

        nodes[cur].closed = true;
        printf("Expand: (%d,%d) g=%d h=%d f=%d\n",
               nodes[cur].r, nodes[cur].c,
               nodes[cur].g, nodes[cur].h, nodes[cur].f);

        if (nodes[cur].r == gr && nodes[cur].c == gc) {
            goal_idx = cur;
            break;
        }

        // 四方向邻居: 上/下/左/右
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        for (int d = 0; d < 4; d++) {
            int nr = nodes[cur].r + dr[d];
            int nc = nodes[cur].c + dc[d];
            if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS)
                continue;  // 边界检``
            if (OBS[nr][nc])
                continue;  // 障碍物跳过
            find_or_create(nr, nc,
                           nodes[cur].g + 1, cur,
                           gr, gc);
        }
    }

    /* ─── 路径重建 ─── */
    if (goal_idx < 0) {
        printf("No path found.\n");
    } else {
        int path[MAX_NODES], path_len = 0;
        int cur = goal_idx;
        while (cur != -1) {
            path[path_len++] = cur;
            cur = nodes[cur].parent;
        }

        printf("\nPath found (length=%d):\n  ", path_len - 1);
        for (int i = path_len - 1; i >= 0; i--) {
            printf("(%d,%d)", nodes[path[i]].r, nodes[path[i]].c);
            if (i > 0) printf(" ->  ");
        }
        printf("\n");
    }
    return 0;
}

核心逻辑解析：

A* 主循环：每次从 Open 表选 f 最小的节点（pick_best），标记 closed，打印扩展信息。若到达终点则退出循环。否则扩展四方向邻居——先检查边界和障碍物，再通过 find_or_create 管理节点。
邻居扩展：ng = nodes[cur].g + 1（每步代价为 1）。find_or_create 负责新节点的创建或已有节点的更新（保留 g 更小的候选路径。
路径长度：从 goal_idx 沿 parent 链回溯到 -1（起点），存入 path[]。逆序输出得到从起点到终点的顺序。路径长度 = path_len - 1（步数 = 节点数 - 1）。
时间复杂度：每次 pick_best O(n)，n ≤ 30，总扩展 ≤ 30 次 → 微秒级完成。
空间复杂度：nodes[30] + path[30] = 约几百字节。

对照检查：Node 结构体是否包含 parent 和 closed 字段？heuristic 用的是 abs(r-gr)+abs(c-gc)Manhattan 而非 Euclidean 吗？边界检查 0 <= nr < ROWS 和 0 <= nc < COLS 两端都检查了吗？障碍物跳过条件用的是 continue 吗？路径长度打印的是 path_len - 1 而非 path_len 吗？

课堂讨论

如果把启发函数改成 h(n) = 0，A* 变成什么算法？在本题的 6×5 网格上，会多扩展多少节点？
如果把启发函数改成 h(n) = 100 × Manhattan（严重高估），会发生什么？A* 还保证找到最优路径吗？为什么？
本题的障碍物形成一道"墙"。如果把这四个障碍物全部移除，A* 会扩展多少节点？路径是什么？
parent 字段为什么存索引而不是坐标？如果存坐标，路径回溯时会发生什么？效率差多少？
如果允许对角线移动（八方向，对角线代价为 √2 ≈ 1.414），需要改哪些部分？启发函数应该换成什么？
find_or_create 中比较新旧 g 并保留更小 g 的逻辑是干什么的？如果去掉这段逻辑（总是用新 g 覆盖），在什么情况下会出错？

讨论答案

Q1: h(n)=0 → 退化为 Dijkstra，多扩展多少节点？

h(n) = 0 时，f(n) = g(n) —— A* 按"已走距离"扩展，退化为 Dijkstra。

本题 6×5=30 个格子，无障碍时:
  A*:      扩展约 10 个节点（沿最优路径）
  Dijkstra: 扩展约 30 个节点（所有格子——像水波扩散到每个角落才碰到终点）

有障碍物时差异更明显:
  Dijkstra 会从起点向所有方向扩展——上方、左方——直到填满整个可达区域。
  A* 被 h 引导，沿左下绕路，只扩展路径上的节点。

如果网格是 6×5，A* 扩展 ~10 个节点，Dijkstra 可能扩展 ~20-25 个——多出 2~3 倍。在 100×100 的网格上，差异可达数十倍。

Q2: h 严重高估 → 退化为贪心，不保证最优

h(n) = 100 × Manhattan 时:
  f(n) = g(n) + 100 × h(n) ≈ 100 × h(n)

  g(n) 被淹没——A* 按"离终点估计最近"扩展，
  等同于贪心最佳优先搜索。

具体反例（假设障碍物布局不同）:
  
    S · · G
    · · X ·
    · · · ·
  
  贪心: S →右→右(G方向) →被墙挡住 →不得不绕路走下面
       路径可能不是最短的。

  A* (正常): 同时看 g 和 h →不会盲目冲向墙
             →可能直接走下路（更短）。

可接受性条件: h ≤ h* 对于所有 n。
若 h 高估: 某个节点被标记 closed 时，
          它的 f 可能大于真实最优路径经过它的 f → 被过早关闭
          → 真正的最优路径可能使用了这个"被关掉"的节点 → 丢失最优性。

Q3: 无障碍物时 A* 的行为

无障碍物时的追踪:

  step 0: (0,0) g=0 h=9 f=9
  step 1: (0,1) g=1 h=8 f=9  或 (1,0) g=1 h=8 f=9
          ─取决于扩展顺序和 pick_best 的平局策略
  ...
  step 9: (5,4) g=9 h=0 f=9  到达终点

  所有 f=9，路径长度仍为 9。

两条等优路径:
  上路径: (0,0)→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)→(2,4)→(3,4)→(4,4)→(5,4)
  下路径: (0,0)→(1,0)→(2,0)→(3,0)→(4,0)→(5,0)→(5,1)→(5,2)→(5,3)→(5,4)
  
  两者长度相同 (9 步)，都是最优路径。选择哪条取决于:
    1. 邻居扩展顺序（上/下/左/右哪个先）
    2. pick_best() 平局策略（f 相同时选 h 更小）

Q4: parent 存索引 vs 存坐标

parent_index_vs_coord.c

/*
 * 方案 A: parent 存索引（本题方案）
 */
typedef struct {
    int r, c;
    int parent;  // nodes[] 索引
} NodeA;

/* 路径回溯: O(path_len) */
int cur = goal;
while (cur != -1) {
    printf("(%d,%d)\n", nodes[cur].r, nodes[cur].c);
    cur = nodes[cur].parent;  // 直接 O(1) 跳转
}

/*
 * 方案 B: parent 存坐标
 */
typedef struct {
    int r, c;
    int pr, pc;  // 父节点坐标
} NodeB;

/* 路径回溯: O(path_len × node_count) */
int cr = goal_r, cc = goal_c;
while (!(cr == -1 && cc == -1)) {
    printf("(%d,%d)\n", cr, cc);
    // 需遍历 nodes 查找坐标匹配的节点
    for (int i = 0; i < node_count; i++)
        if (nodes[i].r == cr && nodes[i].c == cc) {
            cr = nodes[i].pr; cc = nodes[i].pc;
            break;
        }
    // 每次回溯 O(n) 查找
}

存索引优势：

直接 O(1) 跳转到父节点
nodes[parent] 一站获取父节点的所有信息
无需遍历数组查找

存坐标的问题：

每次回溯需遍历整个 nodes[] 查找坐标匹配节点
回溯总开销 O(path_len × n)

Q5: 对角线移动的改动方案

diagonal_extension.c

/*
 * 八方向移动需要改动三处:
 *
 * 1. 邻居方向: 4 → 8
 *    dr[] = {-1,-1,-1, 0, 0, 1, 1, 1}
 *    dc[] = {-1, 0, 1,-1, 1,-1, 0, 1}
 *
 * 2. 移动代价: 统一 1 → 分直角/对角
 *    直角移动: cost = 1
 *    对角移动: cost = 1.414 (√2)，或用整数近似 14/10
 *
 *    实现: ng = nodes[cur].g + (对角线 ? 14 : 10);
 *    最后输出时除以 10 恢复: printf("length=%.1f", len/10.0);
 *
 * 3. 启发函数: Manhattan → Chebyshev 或 Diagonal
 *    Chebyshev: h = max(|dr|, |dc|)
 *    Diagonal:  h = |dr| + |dc| + (√2 - 2) × min(|dr|, |dc|)
 */

改动项	四方向（本题）	八方向
邻居数量	4（上下左右）	8（+四个对角）
移动代价	1	直角 1，对角 √2
启发函数	Manhattan	Chebyshev 或 Diagonal
g 类型	int	double 或 int(放缩)

Q6: 去掉 g 比较逻辑的后果

find_or_create_bug.c

/*
 * 错误版本: 只查找不比较，用新 g 覆盖旧 g
 */
static int find_or_create_bug(int r, int c, int g, int parent,
                              int gr, int gc) {
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].r == r && nodes[i].c == c) {
            // BUG: 不检查 g 大小，总是覆盖！
            nodes[i].g = g;
            nodes[i].f = g + nodes[i].h;
            nodes[i].parent = parent;
            return i;
        }
    }
    // ... 创建新节点
}

/*
 * 出错的场景:
 *
 *   网格:
 *     S ── A ── B
 *     |         |
 *     └── C ────┘
 *
 *  路径 S→C→B 可能比 S→A→B 更短。
 *  如果 S→A→B 先到达 B，B 的 g = 2，parent = A。
 *  当 S→C→B 后到达时，若不去检查并保留更小的 g，
 *  B 被错误地更新为 g=2（而非更优的 g=1）→ 丢失更优路径。
 *
 *  正确逻辑: 只在新 g < 旧 g 时才更新——保留最优子结构。
 */

这就是 A* 中"最优子结构"的体现：到达同一个格子的不同路径有不同代价，必须保留最小的那个。如果随意覆盖，可能丢失最优路径，或使后续扩展基于错误的 g 值。

课后练习

实现 Dijkstra 变体。将 heuristic 改为始终返回 0（即 h(n) = 0），重新运行程序。观察在 6×5 网格上，Dijkstra 扩展了多少节点（vs A* 的 10 个）。记录每个被扩展节点的 g 值——它们如何变化？
知识点提示：将 heuristic 返回值从 abs(r-gr)+abs(c-gc) 改为 0。pick_best 此时退化为按 g 最小选择。重点观察扩展节点数量的差异。

修改启发函数为 Chebyshev（假设允许对角线移动，h = max(|dr|, |dc|)）。运行程序，观察路径是否发生变化。在仅四方向移动的前提下，Chebyshev 可能高估实际代价——找到一条不是最优的路径来验证。

知识点提示：将 heuristic 改为 return abs(r-gr) > abs(c-gc) ? abs(r-gr) : abs(c-gc)。Chebyshev 在四方向网格上可能高估 → 可接受性被破坏 → 可能得到非最优路径。

参考解答

ex2_chebyshev.c

/* Chebyshev 启发函数——八方向网格上可接受，四方向网格上可能高估 */
static int heuristic_chebyshev(int r, int c, int gr, int gc) {
    int dr = abs(r - gr);
    int dc = abs(c - gc);
    return dr > dc ? dr : dc;  // max(|dr|, |dc|)
}

/*
 * 验证: 从 (0,0) 到 (5,4)
 *   Manhattan: h = 5 + 4 = 9   ← 可接受 (≤ 9)
 *   Chebyshev: h = max(5,4) = 5 ← 在四方向网格上不可接受! (5 < 9)
 *   ← 虽然看起来低估，但 Chebyshev 对"四方向"总是低估还是高估？
 *
 * 实际上 Chebyshev 在四方向网格上总是**低估**实际代价
 * (因为 h ≤ Manhattan，而 Manhattan ≤ h*)。
 * 所以 Chebyshev 仍然是可接受的! 只是它更"弱"（更低的下界），
 * 导致 A* 更接近 Dijkstra 的行为——扩展更多节点。
 *
 * 真正"高估"的例子需要更极端: h(n) = 100 × Manhattan
 */

路径可视化输出。修改程序，在打印路径之前先以 ASCII 字符画的形式输出 6×5 网格：. 表示可通行，X 表示障碍物，S 表示起点，G 表示终点，* 表示路径经过的格子，o 表示被扩展（closed）但不在路径上的节点。

知识点提示：准备一个 char grid[ROWS][COLS] 数组，依次填充障碍物、closed 节点、路径节点、起点和终点。用 printf 逐行打印。这可以帮助直观理解 A* 的搜索与寻路

参考解答

ex3_visualize.c

void print_grid(int path[], int path_len) {
    char grid[ROWS][COLS];

    for (int r = 0; r < ROWS; r++)
        for (int c = 0; c < COLS; c++)
            grid[r][c] = OBS[r][c] ? 'X' : '.';

    // 标记 closed 节点（不在路径上）为 'o'
    for (int i = 0; i < node_count; i++) {
        if (nodes[i].closed) {
            int on_path = 0;
            for (int j = 0; j < path_len; j++)
                if (path[j] == i) { on_path = 1; break; }
            if (!on_path) grid[nodes[i].r][nodes[i].c] = 'o';
        }
    }

    // 标记路径为 '*'
    for (int j = 0; j < path_len; j++) {
        int idx = path[j];
        grid[nodes[idx].r][nodes[idx].c] = '*';
    }

    // 标时从起点和终点
    grid[0][0] = 'S';
    grid[5][4] = 'G';

    // 打印
    printf("\nSearch visualization:\n");
    for (int r = 0; r < ROWS; r++) {
        printf("  ");
        for (int c = 0; c < COLS; c++)
            printf("%c ", grid[r][c]);
        printf("\n");
    }
    printf("  S=Start G=Goal X=Obstacle *=Path o=Expanded\n");
}

实现双向 A*。同时从起点向终点和从终点向起点搜索。在某个节点首次出现在两个方向的搜索中时（即在两个方向的 Closed 表或其边界中相遇），合并路径。比较与单向 A* 的节点扩展数差异。
知识点提示：维护两组 nodes_from_start[] 和 nodes_from_goal[]，各自有独立的 node_count 和 closed。每轮交替扩展，或每次选两个方向中 f 更小的扩展。相遇条件：一个方向的节点坐标出现在另一个方向的 nodes[] 中。
动态障碍物模拟。预先在 grid 上设置障碍物，但允许通过 # 命令动态切换某个格子的障碍物状态。每次切换后重新运行 A*（复用已建好的节点结构，只需更新受影响的区域）。适合理解 D* Lite 等增量搜索算法的动机。
知识点提示：用 fgets 读取'#'命令和坐标。切换 OBS[r][c] 后可以简单地从起点重新搜索。更高级的做法是只使受影响的节点失效（标记为未访问）并重新搜索——这正是 D* Lite 的核心思想。

参考资料

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. — A* 算法的原始论文
Amit Patel's A* Pages — 经典交互式可视化教程，直观理解 A* 每一步的决策过程
Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach, 4th ed., Chapter 3 — 启发式搜索章节，涵盖 A* 的最优性证明和可接受性分析
《算法导论》(CLRS) 第 24 章 — Dijkstra 算法与单源最短路径
VisuAlgo - Pathfinding — Dijkstra 和 A* 的交互式动画对比
man 3 abs — C 标准库绝对值函数

"A* is like Dijkstra with a sense of direction." — 经典算法课表述

Lesson 54: A*寻路算法 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 盲目搜索上的启发式搜索——两种根本不同的策略 ​

1.1 图搜索的通用框架 ​

1.2 四种算法的逐维对比 ​

2. A* 的核心思想：f = g + h ​

2.1 三个分量的含义 ​

2.2 城市导航类比——最直观的理解 ​

2.3 f 值在无障碍直线路径上恒为常数 ​

3. Manhattan 距离——网格世界的天然启发函数 ​

3.1 公式与得名 ​

3.2 可接受性（Admissibility）——为什么 A* 保证最优 ​

3.3 四种启发函数的适用场景 ​

4. Open/Closed 表的数组实现 ​

4.1 一张数组，两套语义 ​

4.2 pick_best() — 从 Open 表选最优节点 ​

4.3 find_or_create() — 节点查找与创建 ​

4.4 数组 Open 表 vs 优先队列 ​

5. 完整逐步追踪：6×5 障碍网格 ​

5.1 地图可视化 ​

5.2 逐步追踪表 ​

5.3 f 值始终为 9 的直观解释 ​

5.4 为什么不是上面的路径？ ​

6. 路径回溯重建——从 parent 链提取路径 ​

6.1 parent 存索引而非坐标 ​

6.2 路径重建代码 ​

7. A* vs Dijkstra vs BFS——三维对比与算法退化 ​

7.1 对比总结 ​

7.2 算法退化——h(n) = 0 和高估的两极 ​

7.3 为什么本题不需要优先队列 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 54: A*寻路算法

练习任务

核心知识点

代码框架

深度讲解

1. 盲目搜索上的启发式搜索——两种根本不同的策略

1.1 图搜索的通用框架

1.2 四种算法的逐维对比

2. A* 的核心思想：f = g + h

2.1 三个分量的含义

2.2 城市导航类比——最直观的理解

2.3 f 值在无障碍直线路径上恒为常数

3. Manhattan 距离——网格世界的天然启发函数

3.1 公式与得名

3.2 可接受性（Admissibility）——为什么 A* 保证最优

3.3 四种启发函数的适用场景

4. Open/Closed 表的数组实现

4.1 一张数组，两套语义

4.2 pick_best() — 从 Open 表选最优节点

4.3 find_or_create() — 节点查找与创建

4.4 数组 Open 表 vs 优先队列

5. 完整逐步追踪：6×5 障碍网格

5.1 地图可视化

5.2 逐步追踪表

5.3 f 值始终为 9 的直观解释

5.4 为什么不是上面的路径？

6. 路径回溯重建——从 parent 链提取路径

6.1 parent 存索引而非坐标

6.2 路径重建代码

7. A* vs Dijkstra vs BFS——三维对比与算法退化

7.1 对比总结

7.2 算法退化——h(n) = 0 和高估的两极

7.3 为什么本题不需要优先队列

参考解答

课堂讨论

讨论答案

课后练习

参考资料