迭代加深与双向 BFS

做法：只往下搜到第 limit 层，到了就掉头。 limit 从 0 开始一层层往上加，第一次搜到目标时，limit 就是最短步数。

for (limit = 0; limit <= 上限; limit++)
    if (dfs(0)) { 答案就是 limit; break; }

bool dfs(int depth) {
    if (到目标) return true;
    if (depth >= limit) return false;    // ← 就这一句，DFS 变成迭代加深
    for (每个选择) { 进入; if (dfs(depth+1)) return true; 撤销; }
    return false;
}

它同时拿到了两边的好处：

• 像 DFS 一样省内存 —— 只有一个递归栈，几十个字节，没有任何判重表
• 像 BFS 一样保证最短 —— 因为深度是一层层放开的，浅的解一定先被找到

每加一层，前面所有层都要重搜 —— 听着浪费得离谱。算一笔账：

设每个状态平均能扩展出 b 个新状态（八数码大约 2~3）。

深度 d 那一层：            b^d 个节点
前面所有层加起来：  1 + b + b² + … + b^(d-1) ≈ b^d / (b-1)

b = 3 时，前面全部重搜的总量还不到最后一层的一半。

指数增长下，最后一层就占了绝大多数 —— 前面重来几遍根本无所谓。 这条性质对所有指数级搜索都成立，值得记死。

迭代加深还有个明显的浪费：明明离目标还差十万八千里，它还在傻乎乎往下搜， 非要撞上深度上限才掉头。

如果能估计「从现在这个局面出发，至少还要走多少步」（记作 h），就能提前掐掉：

if (g + h() > limit) return false;      // 已经走了 g 步，至少还要 h 步 —— 本轮不可能走通

这就是第 16 章第 9 步提到的估价函数，也是 A* 家族的核心。

这道题用的估价：曼哈顿距离。 每个数字块「离它该在的位置」还差几格（横向差 + 纵向差），全部加起来。

为什么它是「至少还要走的步数」？因为每走一步只有一个块动一格， 它的曼哈顿距离最多减 1。要把总距离降到 0，至少需要那么多步。

单向 BFS 要铺开一棵深度 d 的树，节点数约 b^d。

如果从起点和终点同时往中间搜，两边各铺 d/2 层就会撞上：

单向：  b^d
双向：  2 · b^(d/2)

b = 3、d = 20 时：

单向：3²⁰ ≈ 35 亿
双向：2 × 3¹⁰ ≈ 12 万

**快了三万倍。**这不是常数优化 —— 它把指数砍了一半。

三个实现要点：

1. 每次扩展节点少的那一边，让两棵树长得均衡。
2. 相遇判定：新扩展出的状态如果在对面那张表里，答案 = 这边步数 + 对面步数。
3. 必须整层整层地扩，否则可能先撞上一条不是最短的路径。

1. 「记住的状态数」那一列就是内存。 迭代加深和 IDA* 是 0 —— 它们只有一个递归栈。 这是它们存在的全部理由：能解决那些 BFS 内存爆掉的题。

2. 迭代加深展开了 19 万个节点，却比只展开 1.9 万个的 BFS 还快。 因为它的每个节点极其便宜（就是几次交换）， 而 BFS 每个节点都要往哈希表里插一个字符串。 节点数不等于时间 —— 还要看每个节点有多贵。

3. IDA* 只用 149 个节点。 一个好的估价函数，比任何常数优化都值钱。

把「IDA*」那一栏换成你自己写的（迭代加深或双向 BFS 都行），再点开始。

标准答案用的是第 15 章那份单向 BFS —— 和你要验的东西机制完全不同， 这才是有意义的交叉验证。

这七行就是阶段 3 的全部。 剩下的都是往里面填「什么是状态」「什么是一步」。