深度优先搜索 的每个状态都对应搜索树上的一个节点,继续决策就会进入它的子树。若能证明某棵子树不必搜索,就可以提前停止,这称为剪枝。
判断依据通常有三类:
| 方法 | 可以停止的原因 |
|---|---|
| 可行性剪枝 | 当前状态已经无法产生合法解 |
| 最优性剪枝 | 当前分支无法改进已有的最优解 |
| 排除等效冗余 | 其他分支已经代表了相同的后续可能 |
优化搜索顺序则是优先尝试限制更强或更有希望的选择。它本身不删除候选,但可能让冲突更早暴露,或更早找到较好的可行解,从而加强其他剪枝。它不保证每组数据都更快。
每加一条剪枝,都应回答:为什么这整棵子树可以跳过?这个理由是否适用于当前要求的“找一个解、求最优值或统计方案数”?
1 八皇后
题目:luogu P1219: [USACO1.5] 八皇后 Checker Challenge。
在
以
同列由列号判断;同一条主对角线的
以下为计数核心。col、diag1、diag2 是初值为 false 的全局数组,ways 初值为 search_queens(1) 开始。主对角线下标加
void search_queens(int row) {
if (row > n) {
++ways;
return;
}
for (int c = 1; c <= n; ++c) {
int x = row - c + n, y = row + c;
if (col[c] || diag1[x] || diag2[y]) continue;
col[c] = diag1[x] = diag2[y] = true;
search_queens(row + 1);
col[c] = diag1[x] = diag2[y] = false;
}
}
这属于可行性剪枝:删掉的分支都不能产生合法解,所以统计全部方案时也可以使用。标记只描述当前路径,递归返回后必须恢复,否则会错误地限制下一条分支。
最坏搜索仍为阶乘量级,辅助空间为
完整题解:pcs2:八皇后。
2 小猫爬山
题目:roj 3060: 小猫爬山。
有
依次安排小猫。状态 dfs(u, used) 表示接下来安排第 used 辆车,load[i] 记录每辆车的载重。当前猫可以进入某辆已有车,也可以新开一辆。
2.1 容量与界限
可行性剪枝。 若 load[i] + w[u] > W,就不能把当前猫放入这辆车。所有重量为正,后续也不会将已经超载的车变合法。
最优性剪枝。 用 best 保存已经得到的最少车数,初值取 used >= best,继续安排只能保持或增加车数,不可能得到更优值,直接返回。
best 必须来自可行方案。随意给一个过小的初值,可能将所有正确答案都剪掉。本题只求最优值,所以与 best 相等也可以剪;若要统计全部最优分组,剪枝条件和去重方式都需要重新分析。
2.2 等价分支
如果两辆车的当前载重相同,将当前猫放入其中任意一辆,得到的载重多重集相同。交换车辆编号后,后续装法一一对应,所以同一层只需尝试其中一辆。
这条规则比较的是当前这一次决策中的车辆载重,不能把某个载重全局标记为“已经尝试过”。不同猫、不同剩余物品对应的后续问题可能不同。
空车之间也完全等价。代码只保存已经使用的车辆,额外提供一次“开新车”选择,无须枚举所有未使用的车号。
2.3 搜索顺序
按重量降序安排,较重的猫往往能放入的车辆更少,容量冲突也更容易提前显现。这是搜索顺序优化,所有仍然可能改进答案的装法都要继续尝试。
不能据此直接贪心。容量为
两辆都恰好装满。一个较好的贪心方案可以提供初始上界,但“先试某个选择”不意味着“只试这个选择”。
2.4 代码实现
同载重去重通过检查编号更小的车实现。每次递归返回后恢复载重;新车分支结束后也要将对应位置清零。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20; // n <= 18
int n, capacity, w[maxn], load[maxn], best;
// 安排第 u 只猫,已有 used 辆车;load[i] 是第 i 辆车的当前载重。
void dfs(int u, int used) {
if (used >= best) return; // 车数不会减少,已经无法改进最优值
if (u > n) {
best = min(best, used);
return;
}
for (int i = 1; i <= used; ++i) {
if (load[i] + w[u] > capacity) continue; // 超载分支不可行
bool same_load = false;
for (int j = 1; j < i; ++j) {
if (load[j] == load[i]) {
same_load = true;
break;
}
}
if (same_load) continue; // 同一层,相同载重的车只尝试一辆
load[i] += w[u];
dfs(u + 1, used);
load[i] -= w[u]; // 恢复现场,再尝试其他车
}
// 未使用的空车没有区别,只开一辆编号为 used+1 的新车。
load[used + 1] = w[u];
dfs(u + 1, used + 1);
load[used + 1] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> capacity)) return 0;
for (int i = 1; i <= n; ++i) cin >> w[i];
sort(w + 1, w + n + 1, greater<int>()); // 优先安排较重的猫
best = n; // 每只猫单独一车,是题目保证可行的初始上界
dfs(1, 0);
cout << best << '\n';
return 0;
}
每一层至多有
2.5 搜索量对比
固定容量
| 已启用的优化 | DFS 调用次数 | 最少车数 |
|---|---|---|
| 只在叶子检查容量 | 142418 | 4 |
| 提前检查容量 | 16263 | 4 |
再加入 used >= best |
539 | 4 |
| 再按重量降序 | 21 | 4 |
| 再跳过同载重车辆 | 17 | 4 |
各版本均只开一辆新车,初始 best=n;前三个版本保留原输入顺序,最后两个版本降序排列。这组数据的总重量为
表中每一行都保留了上一行的优化,数值只描述这组固定数据,不代表任意输入都能按同样比例减少。
完整题解:pcs2:小猫爬山。
3 小木棍
题目:luogu P1120: [CERC 1995] 小木棍。
将若干短木段全部拼成长度相等的原木,求最小原木长度。设木段总长为
按
木段降序排列,一根原木内部按下标递增选择,避免重复枚举同一批木段的排列;同层尝试某段失败后,跳过其他未使用的等长木段,因为它们在后续拼接中可以互换。
除此之外,还有两条需要证明的失败剪枝。
3.1 新原木的第一段失败
开始拼一根新原木时,可以强制放入第一段尚未使用的木段。若这样无法完成剩余全部拼接,就直接返回失败。
理由是:所有木段最终都必须使用。在任意合法划分中,这段木段必然属于某根原木;原木没有编号区别,可以把那根原木调整为当前先拼的这一根。因此,不必改用另一段作为起点再搜一次。
3.2 恰好拼满后失败
当前原木还缺长度
假设反而存在另一种合法方案:当前缺口用若干段
| 原木 | 假设存在的方案 | 交换后 |
|---|---|---|
| 当前这一根 | 已拼部分 |
已拼部分 |
| 包含 |
因为
两条剪枝都依赖:木段全部使用、原木等长、没有额外的分组限制。它们不能只凭代码形式照搬到其他分组题中。
完整题解:pcs2:小木棍。
4 数独
题目:luogu P1074: [NOIP 2009 提高组] 靶形数独。
填满
固定按行扫描空格,可能先在一个有多个候选的格子上展开很多分支,过很久才发现另一个格子已经没有候选。
每次搜索时,先根据行、列、宫的已用数字,计算各空格的候选集合:
- 某个空格候选数为
:当前状态无法完成,立即回退,这是可行性剪枝。 - 否则选择候选数最少的空格,尝试其中每个数字,这是搜索顺序优化。
候选最少的格子往往约束更强,可以更早暴露矛盾。换顺序没有取消任何候选数字,因此仍能覆盖全部合法填法。回溯时要恢复行、列、宫的标记;若通过交换空格列表调整次序,也要恢复这个交换。
本题求最高分,找到第一个合法填法时只更新最优值,还需继续搜索可能得分更高的填法。
最高分上界
设当前得分为
任意合法完成方案在每个空格填入的数字都不超过当前候选最大值,且权重为正,因此最终得分不会超过
完整题解:pcs2:靶形数独。
5 相关题解
暂无相关题解