困难C++4 分钟1,402 字

搜索剪枝优化

朴素 DFS 会穷举所有分支,指数级复杂度往往无法接受。​剪枝​就是在搜索过程中提前判断"这条路走下去不可能更优",直接砍掉整个子树。它是提高级(CSP-S)搜索题从"能过小数据"到"能拿满分"的分水岭。

剪枝的本质

搜索树的每个节点代表一个"部分方案"。剪枝的依据是:​如果从当前状态出发,无论怎么走都不可能得到比已知最优解更好的结果,就没必要继续​​。

常见五类:

类型 依据 典型场景
可行性剪枝 当前状态已违反约束 八皇后、数独
最优性剪枝 上界 ≤ 当前最优解 0/1 背包搜索
搜索顺序优化 先试更可能成功的分支 最短路、搜索题
记忆化 / 去重 相同状态不重复计算 网格路径、状态 DP
极端情况 特判边界 已有答案等于理论下界

可行性剪枝

题目​​:n 皇后问题,在 n×n 棋盘放 n 个皇后,任意两个不在同一行、列、对角线。

cpp
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,求最大价值。

cpp
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,从而剪掉更多分支。

cpp
// 按单位价值降序排列物品
sort(items, items + n, [](Item a, Item b) {
    return (double)a.v / a.w > (double)b.v / b.w;
});

先试高价值物品,best 会很快变得接近最优,后续大量分支被剪掉。

记忆化搜索

当同一个状态会被多次访问​时,把结果存起来,下次直接查表。这是记忆化搜索的本质,也是"搜索"通向"动态规划"的桥梁。

cpp
// 记忆化:求斐波那契第 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*

当搜索深度不确定、又不想爆内存时,可以限制最大深度逐层加深​​:

cpp
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 就剪。写反会漏解。
  • 回溯不彻底​​:标记了却没撤销,结果偏小。

小结

剪枝 = 可行性 + 最优性 + 搜索顺序 + 记忆化​四件套。其中最优性剪枝必须先有一个合理的初始解,记忆化搜索则要求状态可唯一标识。掌握它们,指数级搜索才能在可接受时间内跑出正确答案。

同类知识点