第 5.16 章：搜索专题（剪枝、迭代加深与 A*）

5.16.0 从一道题出发

🧩 题目：数一数 N 皇后 在 N×N 棋盘上放 N 个皇后，使得任意两个皇后不同行、不同列、不同对角线。问有多少种摆法。 数据规模： 1 ≤ N ≤ 13。

第 2.8 章的枚举思想立刻能用：每个皇后占一行，那么一个方案就是「第 i 行的皇后放在哪一列」的一个序列 (c₁, c₂, …, c_N)。最暴力的写法是枚举所有 13^13 种序列？不行，那约是 3×10¹⁴。聪明一点：同一行天然只放一个皇后，用 DFS 逐行放置，每行从 13 列里选一列——即使这样，最坏也有 13! ≈ 6.2×10⁹ 个完整排列：

第 1 行：13 种选法
第 2 行：12 种（排除同列）……
全排列数 13! ≈ 62 亿

按每秒 10⁸ 次运算，需要跑一分钟以上——超时。

但请你手动模拟前两行：第 1 行放列 0，第 2 行也放列 0？冲突，立刻失败。可朴素 DFS 还会继续往下放第 3、4、5……行，把整棵子树搜完才回头！问题的根源是：冲突在前 2 行就已注定，后面的 11 行全是白搜。

如果我们在每放一个皇后时就检查冲突、冲突立刻回溯，搜索树会在很浅的地方就被砍掉大片分支——这就是剪枝。加了剪枝的 N 皇后，N=13 只需约 0.04 秒（本章 5.16.2 有完整代码和实测数据）。

同一道题还藏着本章的其它主角：

这一章是把第 5.2 章 BFS/DFS 的「遍历」升级成一门手艺：搜索人人会写，会剪枝、会选框架的人才能在 1 秒时限内过题。

5.16.1 状态空间与搜索树：换一个视角看 DFS/BFS

5.2 章的图 vs 本章的「状态空间」

第 5.2 章的 BFS/DFS 走的是给定的图：输入邻接表，节点编号 1..N，遍历它。但 N 皇后没有输入任何图——棋盘上的部分摆放方案本身就是节点。这引出本章的核心视角：

搜索 = 在「状态空间」上做遍历。状态空间是一张隐式生成的图，它的节点是「局面」，边是「一步决策」。

三个术语，以 N 皇后为例：

迷宫其实也是状态空间搜索——只不过它的状态（格子）与输入的图一一对应。N 皇后更典型：13! 个排列的状态空间根本不可能显式存下来，它在 DFS 过程中被「随用随生成、用完即丢弃」。

搜索树

从初始状态出发，把每个状态的每种转移画成一棵树，就得到搜索树。N=4 皇后搜索树的开头：

                     空棋盘
        ┌───────────┬─────┴──────┬───────────┐
      放(1,1)     放(1,2)      放(1,3)     放(1,4)
       │             │            │            │
   ┌───┴───┐     ┌───┴───┐    ┌───┴───┐    ┌───┴───┐
 放(2,3) 放(2,4) 放(2,4)  ✗   ✗      放(2,1) 放(2,1) 放(2,2)
   ...     ...    ...   (2,2列冲突)  ...    ...    ...

（放(r,c) = 第 r 行第 c 列；✗ = 放下即冲突的死分支。）

注意两件事：

1. 搜索树 ≠ 状态空间图。 迷宫中格子 A → B → A 是图中的一条路，但搜索树里「回到 A」是不同的节点——搜索树按路径区分，状态图按局面区分。DFS 天然处理的是搜索树；如果同一局面会经多条路径到达且你想去重，就得像 BFS 那样记 visited（哈希表 / 编码）。
2. 搜索树的规模是指数级的。 分支因子 b、解在深度 d，最坏要访问约 bᵈ 个节点。b=13、d=13 时，这就是 5.16.0 里的 62 亿。本章所有技术，本质都是在缩小这棵树：

⚠️ 常见错误：忘了状态会重复

5.16.2 剪枝三招：可行性、上下界、搜索顺序

剪枝 = 在递归进入子树之前判断「这棵子树还有希望吗」，没希望就直接 return。三招按威力从小到大：

第一招：可行性剪枝（剪「必败」的分支）

当前局面已违反约束 → 立刻回溯。

N 皇后逐行放置时，每放一个就检查列和两条对角线是否冲突，冲突立即回溯——这就是可行性剪枝。它把 13! 砍成了「合法前缀」的树，节点数骤降几个数量级。

其它例子：组合枚举中「已选元素和 > 目标」即回溯；数独中尝试的数字与同行/列/宫冲突即跳过。

第二招：最优性剪枝 / 上下界剪枝（剪「必不优」的分支）

求最小代价时：当前代价 + 完成剩余部分的乐观估计 ≥ 已知最优解 → 回溯。

关键在「乐观估计」：必须是下界（永远不高于真实剩余代价），否则会把最优解剪掉。例：

• 数独/填数问题：剩余空格都填最小值也追不上当前最优 → 剪。
• 旅行商分支限界：当前路径长 + 剩余城市的 MST 长度 ≥ 最优 → 剪。
• 埃及分数（5.16.3 例题）：剩余 k 个分数每个最多 1/d，a/b > k/d 则这条分支无解 → 剪。

对求最大值的问题对称地用上界。注意：这种剪枝通常要求先有一个可行解（哪怕很烂）作为初始最优值——这就是第三招的用武之地。

第三招：搜索顺序剪枝（让好答案早点出现）

优先尝试更可能产生（更优）答案的分支。

搜索顺序不改变正确性（最坏情况不变），但改变好答案出现的时机，而好答案越早出现，第二招的剪枝越狠。例：

• 数钱币凑金额：从大到小试面额，先试「大子」分支；
• 分团/独立集问题：优先扩展度数大的节点；
• 求字典序最小方案：按字典序尝试分支，找到第一个解就停；
• 埃及分数：分母从小到大枚举——最优解（项数最少、字典序最小）就在浅处靠左。

例题：N 皇后（完整代码）

用三个 bitmask 记录「哪些列 / 左对角线 / 右对角线已被占用」。第 r 行放置列 c 时：

• 列 c 占用：bit c；
• 同一条 ↘ 对角线上 (r+k, c+k) 与 (r, c) —— 观察：往下一行走，这条对角线的列号 +1，所以把「左移一位的占用掩码」往下传；
• 同一条 ↙ 对角线同理右移一位。

#include <bits/stdc++.h>
using namespace std;

int n;
long long cnt = 0;

// cols: 已占用的列   d1: ↘ 对角线（本行视角）   d2: ↙ 对角线（本行视角）
void dfs(int row, int cols, int d1, int d2) {
    if (row == n) { cnt++; return; }
    // avail 的每个 1 位 = 本行可以放的列
    int avail = ((1 << n) - 1) & ~(cols | d1 | d2);
    while (avail) {
        int p = avail & (-avail);      // 取最低位的 1（尝试该列）
        avail -= p;
        dfs(row + 1,
            cols | p,                  // 列占用传递
            (d1 | p) << 1,             // ↘ 对角线：下一行列号 +1
            (d2 | p) >> 1);            // ↙ 对角线：下一行列号 -1
    }
}

int main() {
    cin >> n;
    dfs(0, 0, 0, 0);
    cout << cnt << "\n";
}

实测（Apple M 系列，单核）：

对比朴素的 13! ≈ 62 亿次排列枚举：可行性剪枝把它压到了千万级节点。

手算 N=4：看见被剪掉的子树

N=4 只有两个解：(2,4,1,3) 和 (3,1,4,2)（第 i 行皇后的列号）。沿搜索树走一遍（✗ = 放下即与前面某皇后冲突）：

第 1 行放列 1：
  第 2 行：列 1✗(列冲突)  列 2✗(↘对角)  列 3 可 → 第 3 行：1✗ 2✗ 3✗ 4✗ 全冲突 → 回溯
                            列 4✗(↙对角)              【整棵子树死】
第 1 行放列 2：
  第 2 行：列 1 可 → 第 3 行：3✗(列) 4✗(对角) → 死
            列 2✗  列 3✗(对角)  列 4 可 → 第 3 行：列 1 可 → 第 4 行：只剩列 3 ✓ 解 (2,4,1,3)！
第 1 行放列 3：                       ← 与「放列 2」左右镜像 → 解 (3,1,4,2)
第 1 行放列 4：                       ← 与「放列 1」左右镜像 → 全死

要点：

• 不带剪枝的枚举要试 4^4 = 256 种完整放置（或 4! = 24 个排列）；带可行性剪枝的 DFS 只走了上面十几步——每条根到叶的活路只有 2 条，其余 254 种组合都在浅处被剪掉。
• 第 1 行放列 1 的子树里，最深的死分支也只到第 3 行——剪枝把「注定失败」的判断提前到了失败被造成的那一刻，而不是方案完成时。这就是 13! 被砍到千万级节点的机制。
• 对角线判断最易手误（(2,4) 与 (3,1) 行差 1 列差 3，不冲突），这正是代码里把对角线交给 bitmask 滚动传递、而不是写一串 if 的原因。

5.16.3 迭代加深（IDDFS）：DFS 的空间，BFS 的深度保证

一个两难

设想解的深度未知（不知道答案离起点几步）：

埃及分数正是这种题：展开 a/b 为项数最少、字典序最小的单位分数之和，答案几项？不知道。

IDDFS：限定深度地做 DFS，深度不够就加一

迭代加深（Iterative Deepening DFS，IDDFS）：先做深度上限为 1 的 DFS，找不到解就把上限加到 2，再来……直到找到解。

• 每轮 DFS 是深度受限的：不会掉进比上限更深的死路；
• 找到解时，上限恰好是最浅解的深度（上一轮已证明更浅处无解）——拿到了 BFS 的性质；
• 每轮只用 O(深度) 的栈空间——拿到了 DFS 的性质。

重复搜索不亏吗？ 亏，但亏得很少。设分支因子 b，深度上限 d 的一轮 DFS 访问约 bᵈ 个节点，之前所有轮加起来约 bᵈ⁻¹ + bᵈ⁻² + … < bᵈ/(b−1)。总代价与单独跑最后一轮之比：

(b^d + b^(d-1) + ...) / b^d = 1/(1 - 1/b) = b/(b-1)

b=10 时只多花 11%，b=4 时多 33%——指数增长的最后一层占据几乎全部工作量，前面几层白搜也便宜。这与第 2.9 章倍增的思想一脉相承：宁可重做便宜的部分，换确定性的终止条件。

例题：埃及分数

🧩 题目：埃及分数 给定真分数 a/b（0 < a < b ≤ 10⁶），把它展开成互不相同的单位分数之和，要求：

1. 项数最少；
2. 项数相同时字典序最小（即第一个分母尽量小，其次第二个……）。 输出一种最优展开。

为什么 IDDFS？ 答案项数未知（可能 1 项，可能 5 项）。按「项数 = 深度上限」做迭代加深，从小到大尝试；同一深度内分母从小到大枚举（搜索顺序剪枝，保证字典序最小）。

剪枝：

1. 可行性：分母严格递增（保证互不相同 + 字典序结构）；
2. 下界（上界剪枝）：当前已枚举到分母 d、还剩 remain 项，每项 ≤ 1/d，故必须 a/b ≤ remain/d，即 a·d ≤ remain·b——不满足就 break（后面的 d 更大，只会更差）；
3. 整除特判：只剩 1 项时，a/b 必须恰好是 1/d（即 b % a == 0）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll path[100];      // 当前路径上的分母
int pathLen = 0;
ll a, b;           // 展开 a/b

// 用恰好 remain 个分母严格大于 start 的单位分数凑出 a/b
bool dfs(ll a, ll b, ll start, int remain) {
    if (remain == 0) return a == 0;
    if (remain == 1) {                        // 只剩一项：必须能整除
        if (b % a == 0 && b / a > start) {
            path[pathLen++] = b / a;
            return true;
        }
        return false;
    }
    // 分母下界：d > start，且 d >= ceil(b/a)（否则 1/d > a/b 超出目标）
    // 分母上界（下界剪枝）：remain 项每项 <= 1/d，必须 cover a/b => a*d <= remain*b
    for (ll d = max(start + 1, (a + b - 1) / a); a * d <= (ll)remain * b; d++) {
        ll na = a * d - b, nb = b * d;        // 剩余：a/b - 1/d = (ad-b)/(bd)
        if (na < 0) continue;
        ll g = gcd(na, nb); na /= g; nb /= g;
        path[pathLen++] = d;
        if (dfs(na, nb, d, remain - 1)) return true;
        pathLen--;
    }
    return false;
}

int main() {
    cin >> a >> b;
    ll g = gcd(a, b); a /= g; b /= g;
    for (int limit = 1; ; limit++) {          // 迭代加深：项数上限 1, 2, 3, ...
        pathLen = 0;
        if (dfs(a, b, 0, limit)) {
            cout << a << "/" << b << " = ";
            for (int i = 0; i < pathLen; i++)
                cout << "1/" << path[i] << (i + 1 < pathLen ? " + " : "\n");
            return 0;
        }
    }
}

实测（已与朴素枚举对拍验证一致）：

⚠️ a/b 可能不小于 1（如 4/3），所以第一项分母可以从 1 开始——代码用 start = 0 自然处理了这一点。

5.16.4 A* 与 IDA*：让启发函数带路

启发函数与可采纳性

BFS/Dijkstra 像「匀速扩散」，四面八方等速推进。如果每个状态到目标还剩多远有个估计，就能优先扩展「看起来离目标近」的状态。

启发函数 h(n)：状态 n 到目标剩余代价的估计。 可采纳性（admissible）：h(n) 从不高估真实剩余代价（h ≤ 真实值）。 一致性（更强）：h(u) ≤ w(u,v) + h(v)，即边上的估计跌幅不超过边权。

可采纳性是 A 正确性的命根子*：只有不高估，某状态被弹出时才敢断言它的 g 值已是真实最短。高估哪怕 1，都可能把最优解藏在一棵「估计悲观」的子树里。

A* = Dijkstra + h

回忆 5.4 章 Dijkstra：优先队列按 g(n)（已走代价）弹出。A* 只改一处——按 f(n) = g(n) + h(n) 弹出：

Dijkstra:  弹出 g 最小的
A*:        弹出 g + h 最小的

h ≡ 0 时 A* 退化为 Dijkstra（无权图上就是 BFS）。h 越接近真实值（仍不高估），越少扩展无用状态；h = 真实值时几乎直奔答案。

例题：八数码（A* 实现）

🧩 题目：八数码 3×3 棋盘上有 1–8 和一个空格（0）。每步把空格与相邻数字交换。给定初始局面，求还原到 123456780 的最少步数，无解输出 −1。

无解判定（先于搜索！）：把局面按行展开成序列（去掉 0），统计逆序对。每次移动是空格与相邻数字交换，在展开序列中相当于把一个数移动一格——逆序对奇偶性不变。目标 12345678 逆序对为 0（偶），所以初始逆序对为奇 ⇒ 无解。先判奇偶能省下整场无用搜索。

启发函数：曼哈顿距离。每个数字到其目标格子的 |Δ行|+|Δ列| 之和（不含 0）。一次交换至多让一个数字移动一格，故真实步数 ≥ 曼哈顿和——可采纳 ✓。

#include <bits/stdc++.h>
using namespace std;

const string GOAL = "123456780";

int manhattan(const string& s) {          // h(n)：各数字曼哈顿距离和
    int d = 0;
    for (int i = 0; i < 9; i++) {
        if (s[i] == '0') continue;
        int v = s[i] - '1';
        d += abs(i / 3 - v / 3) + abs(i % 3 - v % 3);
    }
    return d;
}

bool solvable(const string& s) {          // 逆序对奇偶性判定
    int inv = 0;
    for (int i = 0; i < 9; i++) if (s[i] != '0')
        for (int j = i + 1; j < 9; j++) if (s[j] != '0' && s[j] < s[i]) inv++;
    return inv % 2 == 0;
}

int astar(const string& start) {
    if (!solvable(start)) return -1;
    if (start == GOAL) return 0;
    // 优先队列按 f = g + h 弹出
    priority_queue<pair<int, string>,
                   vector<pair<int, string>>,
                   greater<pair<int, string>>> pq;
    unordered_map<string, int> dist;      // 已知最优 g 值
    dist[start] = 0;
    pq.push({manhattan(start), start});
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    while (!pq.empty()) {
        auto [f, s] = pq.top(); pq.pop();
        int g = dist[s];
        if (f > g + manhattan(s)) continue;   // 过期条目：已有更优 g
        if (s == GOAL) return g;
        int z = s.find('0');
        for (int k = 0; k < 4; k++) {
            int nr = z / 3 + dx[k], nc = z % 3 + dy[k];
            if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            string t = s;
            swap(t[z], t[nr * 3 + nc]);
            if (!dist.count(t) || g + 1 < dist[t]) {
                dist[t] = g + 1;
                pq.push({g + 1 + manhattan(t), t});
            }
        }
    }
    return -1;
}

int main() {
    string s;
    for (int i = 0; i < 9; i++) { char c; cin >> c; s += c; }
    cout << astar(s) << "\n";
}

实测（已与朴素 BFS 对拍，结果一致）：

IDA* = IDDFS + 「f 超上限就剪」

A* 要用优先队列 + 哈希表存所有状态，八数码状态多达 9!/2 = 181440 个——尚可，但状态空间更大（如 15 数码）就爆内存。IDA* 换个组合：

IDA*：以 f(n) = g(n) + h(n) 为对象做迭代加深——第 i 轮的「深度上限」是 f 上限 bound；DFS 中 g + h > bound 即剪枝回溯；一轮失败后 bound 设为「本轮遇到的最小超限 f 值」。

对比 A*：

八数码的 IDA* 实现（细节：禁止撤销上一步交换——上一位置 prevz 不回走，代替 visited 判重）：

#include <bits/stdc++.h>
using namespace std;

const string GOAL = "123456780";
int bound;

int manhattan(const string& s) {
    int d = 0;
    for (int i = 0; i < 9; i++) {
        if (s[i] == '0') continue;
        int v = s[i] - '1';
        d += abs(i / 3 - v / 3) + abs(i % 3 - v % 3);
    }
    return d;
}

bool solvable(const string& s) {
    int inv = 0;
    for (int i = 0; i < 9; i++) if (s[i] != '0')
        for (int j = i + 1; j < 9; j++) if (s[j] != '0' && s[j] < s[i]) inv++;
    return inv % 2 == 0;
}

bool dfs(string& s, int g, int prevz) {
    int h = manhattan(s);
    if (g + h > bound) return false;          // f 超上限：剪
    if (h == 0) return true;
    int z = s.find('0');
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    for (int k = 0; k < 4; k++) {
        int nr = z / 3 + dx[k], nc = z % 3 + dy[k];
        if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
        int nz = nr * 3 + nc;
        if (nz == prevz) continue;            // 不撤销上一步
        swap(s[z], s[nz]);
        if (dfs(s, g + 1, z)) return true;
        swap(s[z], s[nz]);                    // 回溯
    }
    return false;
}

int idastar(const string& start) {
    if (!solvable(start)) return -1;
    string s = start;
    bound = manhattan(s);
    if (bound == 0) return 0;
    while (true) {                            // 迭代放宽 f 上限
        if (dfs(s, 0, -1)) return bound;
        bound++;
    }
}

int main() {
    string s;
    for (int i = 0; i < 9; i++) { char c; cin >> c; s += c; }
    cout << idastar(s) << "\n";
}

（实现从简：bound++ 逐个加 1；更快的写法是把 bound 直接跳到「上一轮遇到的最小超限 f 值」，正确性相同。）实测 724506831 → 20、234150768 → 19、867254301 → 31，与 A* 和朴素 BFS 完全一致。

A 的正确性要点*：弹出时 f = g + h，若 h 可采纳则任何尚未弹出的状态的真实最短距离 ≥ 当前 f —— 所以第一个弹出即目标的 g 就是答案。「过期条目检查」（if (f > g + manhattan(s)) continue）不能省，原理同 5.4 章 Dijkstra 的惰性删除。

5.16.5 双向 BFS：从两头往中间搜

b^(d/2) + b^(d/2) 远小于 b^d

起点、终点都已知，答案是最短距离时（如迷宫最短路、隐式图上的最少步数），不必从起点单向搜到终点——同时从起点和终点扩展，两个扩散前沿在中间相遇。

单向 BFS 扩到深度 d 需访问约 bᵈ 个状态；双向各扩 d/2：

单向：  b^d
双向：  2 · b^(d/2)        （平方根！）
d = 30, b = 4：单向 4^30 ≈ 10^18（不可行）；双向 2 · 4^15 ≈ 2×10^9（勉强可行）

注意代价结构：答案必须是「距离」且边权一致（每步代价相同），这样两条半程路径拼起来才是最短路。加权图上的推广是双向 Dijkstra，正确性坑多，USACO 中极少需要。

实现要点（容易写错！）

1. 交替扩展较小的一侧前沿——保证两边均衡生长，这是复杂度成立的前提；
2. 相遇判定：新扩展的状态若已被另一侧访问，得到一个候选答案 ds + dt；
3. 不能一相遇就返回：同一层内可能有多处相遇、距离不同，必须把当前层扩完，取最小候选（这是最经典的写错点——早退可能拿到比最优长 1 的答案）。

代码模板（网格迷宫版）

#include <bits/stdc++.h>
using namespace std;

int R, C;
vector<string> grid;

int bibfs(int sr, int sc, int tr, int tc) {
    if (sr == tr && sc == tc) return 0;
    vector<vector<int>> ds(R, vector<int>(C, -1)), dt = ds;
    queue<pair<int,int>> qs, qt;
    qs.push({sr, sc}); ds[sr][sc] = 0;
    qt.push({tr, tc}); dt[tr][tc] = 0;
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    while (!qs.empty() && !qt.empty()) {
        bool expandS = qs.size() <= qt.size();   // ① 扩较小的一侧
        auto& q    = expandS ? qs : qt;
        auto& dcur = expandS ? ds : dt;
        auto& doth = expandS ? dt : ds;
        int ans = -1;
        int layer = q.size();
        while (layer--) {                        // ③ 整层扩完再返回
            auto [r, c] = q.front(); q.pop();
            for (int k = 0; k < 4; k++) {
                int nr = r + dx[k], nc = c + dy[k];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (grid[nr][nc] == '#' || dcur[nr][nc] != -1) continue;
                dcur[nr][nc] = dcur[r][c] + 1;
                if (doth[nr][nc] != -1) {        // ② 与另一侧相遇
                    int cand = dcur[nr][nc] + doth[nr][nc];
                    if (ans == -1 || cand < ans) ans = cand;
                }
                q.push({nr, nc});
            }
        }
        if (ans != -1) return ans;
    }
    return -1;
}

int main() {
    cin >> R >> C;
    grid.resize(R);
    int sr, sc, tr, tc;
    for (int i = 0; i < R; i++) {
        cin >> grid[i];
        for (int j = 0; j < C; j++) {
            if (grid[i][j] == 'S') sr = i, sc = j;
            if (grid[i][j] == 'T') tr = i, tc = j;
        }
    }
    cout << bibfs(sr, sc, tr, tc) << "\n";
}

正确性验证：在数千张随机图上，该模板与朴素 BFS 的最短距离逐一相等；在 7×11 迷宫样例上两者同为 16 步。

何时用？ 单向 BFS 状态数将爆炸而深度较深时。一句话呼应：状态空间是「指数级的一半可省」的场景还有第 6.4 章的折半搜索（meet in the middle）——那边拆的是「决策序列」，本节拆的是「图上的距离」，思想同源。

5.16.6 何时不该搜索：复杂度估算与与 DP 的分界

动手前先算：b^d 卡上限

搜索题 90% 的 WA/TLE 出在「没算规模就开写」。开搜前回答两问：

1. 分支因子 b 是多少？ 每个状态平均有几个后继；
2. 深度 d 到哪？ 解最深在几层。

然后拿 b^d 与机器上限（约 10⁸–10⁹ 次操作/秒 × 时限）对比：

例：埃及分数 limit=4 时分母上界由剪枝 ③ 压住，实际节点数远小于表面上界——剪枝的本质就是把「有效 b」和「有效 d」变小。

搜索还是 DP？看重叠子问题

搜索树里同一局面经不同路径反复出现（重叠子问题）→ 每个局面只算一次就是 DP：

没有重叠子问题 → 搜索；有重叠子问题 → DP 或记忆化搜索。

记忆化搜索是两者的桥梁：DFS 写法 + 每个状态第一次算完就缓存（第 6.2 章）。判断口诀：「能不能到同一个地方」——能，就别让搜索树替你重复劳动。

最后一条经验法则：先写朴素搜索，对拍验证，再加剪枝/换框架，逐步优化。一次到位的精妙剪枝往往掩盖正确性 bug；朴素版是最好的对拍基准（本章代码全部按此流程验证）。

⚠️ 常见错误

本章总结

📌 核心要点

❓ 常见问题

Q1：剪枝会不会把正确答案剪掉？

A：会，如果剪枝条件写错方向。铁律：可行性剪枝只剪确定非法的分支；上下界剪枝的界必须是保守估计（下界估计 ≤ 真实值）。写完先用朴素版对拍。

Q2：IDDFS 重复搜索这么多遍，真的不慢吗？

A：指数树中最后一层占绝对大头，前面各层加起来只有最后一层的 1/(b−1)。b≥4 时总开销增幅 <33%，换来 O(深度) 空间和「最浅解」保证。

Q3：A 的 h 用曼哈顿距离还是「错位数」？*

A：曼哈顿距离。错位数（不在位的数字个数）也可采纳但更弱（每步至多修正 1 个错位）；曼哈顿更接近真实值，扩展状态数少一个数量级以上。更强的还有线性冲突（linear conflict），仍可采纳，Gold 以上可选学。

Q4：什么时候 IDA 比 A 好？**

A：状态空间大到存不下哈希表（15 数码、深层博弈），或状态难以编码成哈希键时。IDA* 只需能算 h 和枚举转移。代价是每轮重搜，h 准确时这个代价很小。

Q5：双向 BFS 为什么要求边权一致？

A：相遇拼接的两段要能直接相加才是最短距离。若边权不一，两侧「半程最优」的拼接未必全局最优，需要更复杂的停止条件与加权双向 Dijkstra——USACO 范围内一般用不到。

🔗 与其他章节的联系

• 第 5.2 章（BFS 与 DFS）：本章是它们的「战斗力升级版」——同一对遍历骨架，加上剪枝、限深、启发、双向四类优化
• 第 5.4 章（最短路）：A* 是 Dijkstra 的启发式推广；h≡0 时两者等价
• 第 6.2 章（记忆化搜索）：5.16.6 的「重叠子问题」判断标准正是记忆化/DP 的启动开关
• 第 6.4 章（折半搜索）：把指数砍半的姊妹技术——那边砍决策序列、这边砍图距离
• 第 8 章（调试与对拍）：搜索题的剪枝必须靠朴素版本对拍验证，本章所有代码均如此验证

综合练习

🟢 简单

5.16-E1. 全排列皇后检查器 给定 N（1 ≤ N ≤ 10）和一个排列 c₁..c_N（第 i 行皇后在第 cᵢ 列），判断它是否为合法的 N 皇后方案；若不合法，输出第一个冲突的皇后对 (i, j)。 输入： 第一行 N，第二行 N 个整数。 （热身：练习增量化的冲突检查——正是剪枝的基础部件）

5.16-E2. 素数环 把 1..N（N ≤ 16）排成一个环，使相邻两数之和均为素数。输出方案数（1 固定在第一个位置以去重）。 数据规模： 2 ≤ N ≤ 16。 （经典回溯 + 可行性剪枝）

🟡 中等

5.16-E3. 木棒拼接（Sticks 风格） N 根木棍（N ≤ 64，每根长度 ≤ 50），把它们拼成若干根等长的原始木棒，求原始木棒的最小可能长度。 （搜索顺序 + 多重剪枝的经典综合题）

5.16-E4. 双向 BFS 走密码锁 密码锁有 4 个 0–9 的转盘，每步可把任意一个转盘 +1 或 −1（0 与 9 相邻），或交换两个相邻转盘的数字（代价同为 1 步）。给定初始状态和目标状态，求最少步数。状态总数仅 10⁴，但单向 BFS 基准版与双向版都要写，比较扩展的状态数。 数据规模： 多组查询（≤ 100 组）。

🔴 困难

5.16-E5. 加法链（Addition Chains） 加法链是整数序列 1 = a₀ < a₁ < … < a_m = n，其中每个 aᵢ（i ≥ 1）都是前面某两个 aⱼ + aₖ（j, k < i，允许 j = k）之和。给定 n（1 ≤ n ≤ 1000），求最短的 m。 （POJ 2248 风格；IDDFS 的标准练习）

5.16-E6. 15 数码判定 4×4 的 15 数码（数字 1–15 与空格 0），给定局面，判定是否可解，并输出还原所需最少步数的一个下界（不必真正求解）。 数据规模： 单组局面。

下一步

• 把 5.16.2 的 N 皇后改成输出第一个字典序最小的具体方案（练习：找到即停 + 搜索顺序）；
• 第 6.2 章记忆化搜索：看看「搜索 + 缓存」如何统一本章与 DP 的分界；
• 第 6.4 章折半搜索：另一条「指数减半」路线，与双向 BFS 对照学习。