什么是剪枝
搜索的过程中,避免不必要的搜索的过程,称为剪枝
搜索类似于从树的根出发,遍历整颗搜索树,某些地方是不必要的搜索区域,类似于减去某些枝条,故称为 剪枝
剪枝的原则
- 正确性:剪枝过程中不能丢失正确的解
- 准确性:尽可能多的减去不能通向正解的枝条
- 高效性:提高判断操作本身的时间效率,剪枝的同事不能让时间复杂度变得更高
深度优先搜索的优化技巧
- 优化搜索顺序:如生日蛋糕问题,改变搜索的顺序,不同的搜索形成的搜索树的形态大不相同,其规模大小也相差甚远
- 排序等效冗余:如果从当前节点通往正确答案的多条路径是等效的,那么我们只对其中一条进行搜索
- 可行性剪枝:在搜索过程中,对当前状态进行检查,如果发现分支已经无法到达递归边界,就执行回溯,即相当于我们能远远的看到是死胡同了,应该尽早掉头,而不是搜到死胡同尽头再选择调头
- 最优性剪枝:在最优化问题中,如果当前花费的代价已经超过当前搜到的最优解,那么无论采取多么优秀的策略到达递归边界,也不可能更新答案,此时应该尽早回溯
- 记忆化搜索:记录每一个搜索状态的结果,避免重复搜索和遍历,如倒水问题
例题1: 数的划分
题目大意:将整数 $n$ 分成 $k$ 份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:$n=7$,$k=3$,下面三种分法被认为是相同的
1, 1, 5;
1, 5, 1;
5, 1, 1
问有多少种不同的分法?
分析:
冗余性剪枝:$x_1 \leqslant x_2 \leqslant \cdots \leqslant x_k$
可行性剪枝:搜索上限变成 $\lfloor \frac{n}{k} \rfloor$
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
int ans;
void dfs(int n, int k, int last) {
if (n == 0 and k == 0) {
ans++;
return;
}
if (n == 0 or k == 0) return;
// 总和 n,拆分成 k 份,当前一份为 i,
// 那么总和剩余 n-i,并且还要拆分 k-1 份
for (int i = last; i <= n/k; ++i) {
dfs(n-i, k-1, i);
}
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, k;
cin >> n >> k;
dfs(n, k, 1);
cout << ans << '\n';
return 0;
}
例题2:子集和问题
题目大意:子集和问题的一个实例 <S, t>
。其中,$S = \{x_1, x_2, \cdots, x_n\}$ 是一个正整数的集合,$c$ 是一个正整数。子集和问题判定是否存在 $S$ 的一个子集 $S_1$,使得子集 $S_1$ 和等于 $c$。
分析:
可行性剪枝:
- $sum > c$
- $sum + \text{后面全取} < c$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::function;
int main() {
int n, c;
cin >> n >> c;
vector<int> x(n);
rep(i, n) cin >> x[i];
// w[i] 表示 x[i]+x[i+1]+...+x[n]
vector<int> w(n);
w[n-1] = x[n-1];
for (int i = n-2; i >= 0; --i) {
w[i] = w[i+1] + x[i];
}
bool ok = false;
vector<int> ans(n);
function<void(int, int, int)> dfs = [&](int sum, int p, int cnt) {
if (sum > c) return;
if (sum + w[p] < c) return;
if (ok) return;
if (sum == c) {
ok = true;
rep(i, cnt) cout << ans[i] << ' ';
return;
}
for (int i = p; i < n; ++i) {
ans[cnt] = x[i];
dfs(sum+x[i], i+1, cnt+1);
}
};
dfs(0, 0, 0);
if (!ok) puts("No Solution!");
return 0;
}
例题3: 倒水问题
题目大意:有两个无刻度标志的水壶,分别可装 $x$ 升和 $y$ 升 ( $x,y$ 为整数)的水。设另有一水缸,可用来向水壶灌水或接从水壶中倒出的水,两水壶间,水也可以相互倾倒。已知 $x$ 升壶为空壶,$y$ 升壶为空壶。问如何通过倒水或灌水操作,用最少步数能在 $x$ 或 $y$ 升的壶中量出 $z$ 升的水来。