【搜索】DFS剪枝与优化

算法提高课笔记

剪枝是什么意思呢？

我们知道，不管是内部搜索还是外部搜索，都可以形成一棵搜索树，如果将搜索树全部遍历一遍，效率会很低，但如果我们能在搜索的过程中，提前预知，判断某一些不可能是正确答案的情况，就可以不用遍历其下的子树，从而提高我们的算法效率

我们可以从以下几个角度考虑剪枝：

1. 优化搜索顺序
   优先选择分支较少的结点
2. 排除等效冗余
   尽量保证不搜索重复的状态（就是在不考虑顺序时，采用组合的方式搜索）
3. 可行性剪枝
   不合法提前退出
4. 最优性剪枝
   如果当前答案无论如何都比目前的最优解要差，那就可以不要往下搜了
5. 记忆化搜索（DP）

接下来将通过例题来讲解

小猫爬山

原题链接

翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。

当然，每辆缆车上的小猫的重量之和不能超过 W。

每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？

输入格式

第 1 行：包含两个用空格隔开的整数，N 和 W。

第 2…N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

1 ≤ N ≤ 18,
1 ≤ C_i ≤ W ≤ 108

输入样例

5 1996
1
2
1994
12
29

输出样例

2

题意

给出小猫重量、缆车承重，问最少要多少缆车能把所有小猫运走

思路

枚举每只小猫，有两种状态：

• 放到当前这辆车上
• 新开一辆车

优化：

1. 优化搜索顺序：比较一只比较轻的猫和另一只比较重的猫，显然是比较重的猫带来的分支数量较少，因为如果猫非常重可以直接把车占满，但是猫很轻的话我们就要考虑还要加什么别的猫，因此：将所有猫按从大到小排序，优先放重猫
2. 可行性剪枝：当发现目前小猫的重量已经超过缆车承重，就不要再往下搜了
3. 最优性剪枝：当发现目前缆车数量已经大于等于当前计算出的缆车最少数量，就不要再搜索了

代码

#include <bits/stdc++.h>using namespace std;const int N = 20;int n, m;
int w[N];
int sum[N];
int ans = N; // 最坏的情况:每只小猫占一辆车void dfs(int u, int k) // u:当前在搜第几只猫 k:当前在搜第几辆车
{// 最优性剪枝if (k >= ans) return;if (u == n){ans = k;return;}for (int i = 0; i < k; i ++ ) // 遍历每一辆车// 可行性剪枝if (sum[i] + w[u] <= m) // 称重符合条件{sum[i] += w[u];dfs(u + 1, k);sum[i] -= w[u]; // 恢复现场}// 新开一辆车sum[k] = w[u];dfs(u + 1, k + 1);sum[k] = 0; // 恢复现场
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 0; i < n; i ++ ) cin >> w[i];// 优化搜索顺序sort(w, w + n);reverse(w, w + n);dfs(0, 0);cout << ans << '\n';
}

数独

原题链接

数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

题意

填好数独，保证每行每列、每个3x3方块都包含1-9

思路

先做一个小优化，看比如说一个3x3小方格中有哪些数字没被用过，随意选择一个格子，然后对这些数字依次枚举搜索即可

优化：

1. 优化搜索顺序：选择格子时，尽量选择分支数量较少的格子，比如说一个格子有2种填法，另一个格子有5种，那肯定优先选择2种的
2. 可行性剪枝：一旦与行列九宫格重复时就不要继续搜了
3. 位运算优化： 特殊优化，可以用一个九位的二进制数表示每一行数使用的状态
   比如：0 1 0 0 1 1 1 0 0 可以用来表示2 5 6 7还没用其他数字用过了
   我们考虑这一位上能不能填这个数时，应该考虑二进制数的交集，即在行、列、九宫格的二进制数列上，这个数字都为1，表示在行、列、九宫格内这个数字都没有被使用，我们才能用这个数（直接按位与&）
   这里有个比循环九次更好的办法——lowbit
   lowbit运算可以帮助我们在O(1)的时间复杂度内，返回当前数里的最后一个1，因此用lowbit循环就可以抠出来所有的1

好难啊好难啊qaq看代码注释吧还是

代码

#include <bits/stdc++.h>using namespace std;const int N = 9, M = 1 << N;int ones[M]; // 每个二进制数里1的个数
int mapp[M]; // 把二进制数换成第几位是1
int row[N], col[N], cell[3][3];
char str[100];void init() // 初始化，将所有位置都标记成没用过(也就是标记成1)
{for (int i = 0; i < N; i ++ ) row[i] = col[i] = (1 << N) - 1;for (int i = 0; i < 3; i ++ )for (int j = 0; j < 3; j ++ )cell[i][j] = (1 << N) - 1;
}void draw(int x, int y, int t, bool is_set) // 在(x,y)这个位置填上/删去t 填上的话is_set为true 删去为false
{if (is_set) str[x * N + y] = '1' + t; // t属于0-8 要把它换算成1-9else str[x * N + y] = '.';int v = 1 << t; // t换算到在每一行的位置if (!is_set) v = -v; // 若为清空操作则取反row[x] -= v;col[y] -= v;cell[x / 3][y / 3] -= v;
}int lowbit(int x) // 返回二进制数的最后一个1以及这个1之后的所有0
{return x & -x;
}int get(int x, int y) // 返回(x,y)能填的数字(二进制序列)
{return row[x] & col[y] & cell[x / 3][y / 3];
}bool dfs(int cnt)
{if (!cnt) return true; // 全部填完int minv = 10; // 首先找分支数最少的空格，将最少的分支数赋给maxxint x, y;for (int i = 0; i < N; i ++ )for (int j = 0; j < N; j ++ )if (str[i * N + j] == '.') // 格子为空可以填数字{int state = get(i, j); // 该格子能填的数字的交集if (ones[state] < minv){minv = ones[state]; // 更新最少分支数x = i, y = j; // xy存的就是分支数量最少的格子的坐标}}int state = get(x, y);for (int i = state; i; i -= lowbit(i)){int t = mapp[lowbit(i)]; // 得到最后一个1所在的位置draw(x, y, t, true); // 把t填进去if (dfs(cnt - 1)) return true; // 成功直接返回truedraw(x, y, t, false); // 失败就把填进去的值再删掉}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);// 打表得到ones和mappfor (int i = 0; i < N; i ++ ) mapp[1 << i] = i; // 将所有2^k转化成k(也就是返回二进制数里唯一一个1的位置)for (int i = 0; i < 1 << N; i ++ )for (int j = 0; j < N; j ++ )ones[i] += i >> j & 1; // 记下每个二进制数里1的个数while (cin >> str, str[0] != 'e'){init();int cnt = 0; // 有多少位置没填for (int i = 0, k = 0; i < N; i ++ )for (int j = 0; j < N; j ++, k ++ )if (str[k] != '.') // 位置不空就把值填进去{int t = str[k] - '1';draw(i, j, t, true);}else cnt ++ ; // 位置空就累加空位的数量dfs(cnt);puts(str);}
}

木棒

原题链接

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 50。

输入样例

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例

6
5

题意

给出一些数，将其分成若干组，使每一组总和相等，问最小的总和是多少

思路

木棒：每一组的总和
木棍：题目中输入的数据

先从小到大枚举木棒的长度length，看木棍能不能组成该长度的木棒

优化：

1. 所有木棍的总长度sum必须能整除木棒的长度length，才可能有解，不能整除的情况直接回溯不要搜了
2. 优化搜索顺序：先枚举比较长的木棍，使之后的分支较少
3. 排除等效冗余：
   (1) 如果一根木棒里有第一根第二根两根木棍，那么先用第一根和先用第二根达成的效果都是一样的，因此按照组合数方式枚举
   (2) 如果当前木棍加到当前木棒中失败，那直接略过后面所有等长木棍
   (3) 如果是木棒的第一根木棍失败（说明这根木棍没地方放），则当前状态一定失败，直接回溯不要往下搜了
   (4) 如果是木棒的最后一根木棍失败（这里的意思是往下dfs找不到解），则当前状态一定失败（因为放入比这根木棍小的木棍拼接起来的也一定找不到解），直接回溯不要往下搜了

代码

#include <bits/stdc++.h>using namespace std;const int N = 70;int n;
int w[N], sum, length; // w[i]:每根小棍长度 sum:所有小棍总长度 length:每组总和
bool st[N]; // 小棍有没有用过bool dfs(int u, int s, int start) // u:当前枚举到哪根大棍 s:当前大棍长度 start:开始位置
{if (u * length == sum) return true; // 符合条件if (s == length) return dfs(u + 1, 0, 0); // 这根木棍长度已达要求，开下一根木棍// 优化3(1):从start开始枚举for (int i = start; i < n; i ++ ) // 从start开始遍历木棍{if (st[i]) continue; // 已遍历if (s + w[i] > length) continue; // 可行性剪枝st[i] = true; // 更改状态if (dfs(u, s + w[i], i + 1)) return true; // 下一层遍历st[i] = false; // 恢复现场// 优化3(3):开头不行就一定不行if (!s) return false;// 优化3(4):结尾不行就一定不行if (s + w[i] == length) return false;// 优化3(2):等长直接略过int j = i;while (j < n && w[j] == w[i]) j ++ ;i = j - 1;}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);while (cin >> n, n){memset(st, false, sizeof st);sum = 0;for (int i = 0; i < n; i ++ ){cin >> w[i];sum += w[i];}// 优化2：搜索顺序sort (w, w + n);reverse(w, w + n);length = 1;while (1){// 优化1:必须是整数倍if (sum % length == 0 && dfs(0, 0, 0)){cout << length << '\n';break;}length ++ ;}}
}

生日蛋糕

原题链接

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 Nπ 的 M 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 i 层蛋糕是半径为 Ri，高度为 Hi 的圆柱。

当 $i<M$ 时，要求 $Ri>Ri+1$ 且 H_i > H_i+1。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 Q 最小。

令 $Q=S\pi$ ，请编程对给出的 N 和 M，找出蛋糕的制作方案（适当的 Ri 和 Hi 的值），使 S 最小。

除 Q 外，以上所有数据皆为正整数。

输入格式

输入包含两行，第一行为整数 N，表示待制作的蛋糕的体积为 Nπ。

第二行为整数 M，表示蛋糕的层数为 M。

输出格式

输出仅一行，是一个正整数 S（若无解则 S=0）。

数据范围

1 ≤ N ≤ 10000,
1 ≤ M ≤ 20

输入样例

100
2

输出样例

68

题意

多层蛋糕，给出总体积总层数，可以自定义每一层半径和高度，使得从上往下看的总面积和总侧面积之和最小，求最小值

思路

首先明确我们的目的是让 2 * R_m * h_m + 2 * R_m-1 * h_m-1 + … + 2 * R₁ * h₁ + R_m² 最小（省去了所有的$\pi$）

优化：

1. 优化搜索顺序：分支少的先搜，从大到小枚举
   (1) 要先搜面积大的，因此自底向上搜
   (2) 半径是平方级别，高是一次方，半径对体积影响更大，因此先枚举半径
2. 可行性剪枝：
   (1) 设从上往下为1-m层，第 u 层的半径记为 R_u，一定比 u 大，且比 R_u+1 - 1 小，同时，我们设第 u 层下方的所有体积为 V，那么前 u 层的体积就是 $n-V$，即有 $n-V>=R_u^2{h}_u$，放缩后有 $R_u<=\sqrt{n-V}$
   据此得到： u < = R u < = m i n { R u + 1 − 1 , n − V } u <= R_u <= min\{R_{u+1}-1, \sqrt{n-V}\} u<=Ru​<=min{Ru+1​−1,n−V ​}
   (2) 同时，H_u也>=u，且比 H_u+1小， $n-V>=R_u^2{h}_u$，放缩后有 $h_u<=\frac{n-V}{R^2}$
   据此得到： u < = h u < = m i n { h u + 1 − 1 , n − V R 2 } u <= h_u <= min\{h_{u+1}-1, \frac{n-V}{R^2}\} u<=hu​<=min{hu+1​−1,R2n−V​}
3. 最小体积是半径和高都取1时，因此可以预处理一下前 u 层的体积最小值$minv(u)$和表面积最小值$mins(u)$，需要满足以下两个条件才有往下搜的必要，否则直接回溯：
   $V+minv(u)<=n$
   $s+mins(u)<ans$
4. 已知：$n-V={\sum }_{k=1}^u{R}_k^2{h}_k$
   并且：$S_{1\to u}={\sum }_{k=1}^{u}2R_k{h}_k=\frac{2}{R_{u+1}}{\sum }_{k=1}^u{R}_{u}h{R}_{u+1}>\frac{2}{R_{u+1}}{\sum }_{k=1}^u{R}_u^{2}h$
   因此：$S_{1\to u}>\frac{2(n-V)}{R_{u+1}}$
   所以当$s+\frac{2(n-V)}{R_{u+1}}>=ans$时，已经不可能是最优解了，直接回溯

(好难…疯掉TAT

代码

#include <bits/stdc++.h>using namespace std;const int N = 25, inf = 1e9;int n, m;
int minv[N], mins[N]; // 分别表示每一层及该层上方的最小体积和最小表面积
int R[N], H[N]; // 表示每一层的半径和高
int ans = inf;void dfs(int u, int v, int s) // u:当前层数 v:当前体积 s:当前表面积
{if (v + minv[u] > n) return; // 优化3if (s + mins[u] >= ans) return; // 优化3if (s + 2 * (n - v) / R[u + 1] >= ans) return; // 优化4if (!u) //已全部搜完{if (v == n) ans = s;return;}// 优化1:从大到小枚举for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- ) // 优化2for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h -- ) // 优化2{int t = 0;if (u == m) t = r * r; // 如果是最底层，要加上底面积R[u] = r, H[u] = h; // 更新RHdfs(u - 1, v + r * r * h, s + 2 * h * r + t);}
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;// 打表做出minv minsfor (int i = 1; i <= m; i ++ ){minv[i] = minv[i - 1] + i * i * i;mins[i] = mins[i - 1] + 2 * i * i;}R[m + 1] = H[m + 1] = inf; // 设置哨兵dfs(m, 0, 0);if (ans == inf) ans = 0; // 无满足要求的情况cout << ans << '\n';
}