搜索剪枝优化
朴素 DFS 会穷举所有分支,指数级复杂度往往无法接受。剪枝就是在搜索过程中提前判断"这条路走下去不可能更优",直接砍掉整个子树。它是提高级(CSP-S)搜索题从"能过小数据"到"能拿满分"的分水岭。
剪枝的本质
搜索树的每个节点代表一个"部分方案"。剪枝的依据是:如果从当前状态出发,无论怎么走都不可能得到比已知最优解更好的结果,就没必要继续。
常见五类:
| 类型 | 依据 | 典型场景 |
|---|---|---|
| 可行性剪枝 | 当前状态已违反约束 | 八皇后、数独 |
| 最优性剪枝 | 上界 ≤ 当前最优解 | 0/1 背包搜索 |
| 搜索顺序优化 | 先试更可能成功的分支 | 最短路、搜索题 |
| 记忆化 / 去重 | 相同状态不重复计算 | 网格路径、状态 DP |
| 极端情况 | 特判边界 | 已有答案等于理论下界 |
可行性剪枝
题目:n 皇后问题,在 n×n 棋盘放 n 个皇后,任意两个不在同一行、列、对角线。
int n, ans = 0;
bool col[20], diag1[40], diag2[40]; // 列、主对角、副对角
void dfs(int row) {
if (row == n) { ans++; return; }
for (int c = 0; c < n; c++) {
// 可行性剪枝:冲突就跳过
if (col[c] || diag1[row + c] || diag2[row - c + n]) continue;
col[c] = diag1[row + c] = diag2[row - c + n] = true;
dfs(row + 1);
col[c] = diag1[row + c] = diag2[row - c + n] = false; // 回溯
}
}
这里用三个布尔数组把"冲突判断"从 O(n) 降到 O(1),本身就是剪枝的一种——减少每次判断的成本。
最优性剪枝
题目:0/1 背包的搜索解法。n 个物品,容量 W,求最大价值。
int n, W, best = 0;
int w[50], v[50];
// 预处理:剩余物品中每单位重量价值最高的那一件,用于估算上界
double maxRatio[50];
void dfs(int i, int curW, int curV) {
// 最优性剪枝:即使把剩余所有物品都装下,也不如当前最优
if (curV + (W - curW) * maxRatio[i] <= best) return;
if (i == n) { best = max(best, curV); return; }
// 不选第 i 件
dfs(i + 1, curW, curV);
// 选第 i 件(可行性剪枝:容量够才选)
if (curW + w[i] <= W)
dfs(i + 1, curW + w[i], curV + v[i]);
}
(W - curW) * maxRatio[i] 是松弛上界:假设剩余容量全用来装单位价值最高的物品。这个上界可能不准确,但只要它 ≤ best 就一定能剪——因为我们只要求"上界不比最优解大",不需要精确。
搜索顺序优化
顺序选得好,剪枝效果天差地别。把"更可能产生好结果"的分支放在前面,能更早拿到较好的 best,从而剪掉更多分支。
// 按单位价值降序排列物品
sort(items, items + n, [](Item a, Item b) {
return (double)a.v / a.w > (double)b.v / b.w;
});
先试高价值物品,best 会很快变得接近最优,后续大量分支被剪掉。
记忆化搜索
当同一个状态会被多次访问时,把结果存起来,下次直接查表。这是记忆化搜索的本质,也是"搜索"通向"动态规划"的桥梁。
// 记忆化:求斐波那契第 n 项
long long memo[100];
long long fib(int n) {
if (n <= 1) return 1;
if (memo[n] != 0) return memo[n]; // 已算过,直接返回
return memo[n] = fib(n - 1) + fib(n - 2);
}
不加记忆化是 O(2^n),加了之后每个状态只算一次,变成 O(n)。
关键前提:状态必须能用一个下标(或一维编码)唯一标识,且结果只依赖状态本身。如果状态依赖"路径"(比如已经访问过哪些点),就无法简单记忆化。
迭代加深与 IDA*
当搜索深度不确定、又不想爆内存时,可以限制最大深度逐层加深:
for (int limit = 1; limit <= MAXD; limit++) {
if (dfs(0, limit)) break; // 找到解就停
}
配合 A* 的思路就是 IDA*:每层用估价函数判断"剩余步数是否已经超限",从而剪枝。这是深搜题拿高分的重要技巧。
实践技巧
1. 先求一个可行解
拿到一个合理的 best 初值(贪心解),最优性剪枝才能生效。best = 0 时几乎剪不掉任何东西。
2. 剪枝条件从强到弱排 先判断最可能成立、最省时的条件。
3. 避免重复计算 把能在函数开头一次性算完的量提到参数里传递,而不是每层重算。
4. 注意回溯的对称性 既然进入时标记,返回时必须原样恢复,否则后续分支会看到脏状态。
常见错误
- 记忆化忘记记录:
memo[n] = ...; return memo[n];必须真的写入。 - 状态标识不唯一:用了不完整的下标,导致不同状态命中同一个缓存。
- **剪枝用
>=还是>**:求最大值时,上界<= best就剪;求最小值时,下界>= best就剪。写反会漏解。 - 回溯不彻底:标记了却没撤销,结果偏小。
小结
剪枝 = 可行性 + 最优性 + 搜索顺序 + 记忆化四件套。其中最优性剪枝必须先有一个合理的初始解,记忆化搜索则要求状态可唯一标识。掌握它们,指数级搜索才能在可接受时间内跑出正确答案。