深搜的剪枝策略
可行性剪枝
搜索过程中,一旦发现某些状态无论如何都不能找到最终解,就可以将其“剪枝”了
从1 ~ 30 选出8个数,使得和值为200
#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i, int cnt, int s) {//i: 数组索引位置; cnt: 以选数据个数; s: 和
if (cnt > k) { //可行性剪枝,选择数的个数不可能超过k
return;
}
if (s > sum) { //可行性剪枝,s大于sum的不用考虑
return;
}
if (i == n) {
if (cnt == k && s == sum) {
ans++;
}
return;
}
dfs(i + 1, cnt, s); //不选第i个数
dfs(i + 1, cnt + 1, s + a[i]); //选第i个数
}
int main() {
n = 30;
k = 8;
sum = 200;
for (int i = 0; i < 30; i++) {
a[i] = i + 1;
}
ans = 0;
dfs(0, 0, 0);
cout << ans << endl;
return 0;
}
最优性剪枝
最优解问题,通常可以用最优性剪枝,如在求解迷宫最短路的时候,若发现当前的步数已经超过了当前最优解,那从当前状态开始的搜索都是多余的
在搜索是否有可行解的过程中,一旦找到了一组可行解,后面的搜索都不必再进行了,(最优性剪枝的特例)
#include <iostream>
#include <string>
using namespace std;
int n, m;
string mp[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const int INF = 0x3f3f3f3f;
int ans = INF;
bool in(int x, int y)
{
return 0 <= x && x < n && 0 <= y && y < m;
}
void dfs(int x, int y, int step)
{
if (step > ans)
{ //不可能再是最优解,不用再算了
return;
}
if (mp[x][y] == 'T')
{
ans = step;
return;
}
vis[x][y] = true;
for (int i = 0; i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty) && mp[tx][ty] != '*' && !vis[tx][ty])
{
dfs(tx, ty, step + 1);
}
}
vis[x][y] = false;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> mp[i];
}
int x, y;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mp[i][j] == 'S')
{
x = i, y = j;
}
}
}
dfs(x, y, 0);
cout << ans << endl;
}
重复性剪枝
对于某一些特定的搜索方式,一个方案可能会被搜索很多次,这样是没必要的。
给定 n 个整数,要求选出 K 个数,使得选出来的 K 个数的和为 sum。
那么 1, 2, 3这个选取方法能被搜索到 6 次,这是没必要的,因为我们只关注选出来的数的和,而根本不会关注选出来的数的顺序,所以这里可以用重复性剪枝。
我们规定选出来的数的位置是递增的,在搜索的时候,用一个参数来记录上一次选取的数的位置,那么此次选择我们从这个数之后开始选取,这样最后选出来的方案就不会重复了。
当然,搜索的效率也要比直接二进制枚举更高。
void dfs(int s, int cnt, int pos) {
...
...
for (int i = pos; i <= n; i++) {
if (!xuan[i]) {
xuan[i] = true;
dfs(s + a[i], cnt + 1, i + 1); // i + 1 表示从上一次选取的位置后面开始选
xuan[i] = false;
}
}
}
奇偶性剪枝
有一个 n×m 大小的迷宫。其中字符
'S'
表示起点,字符'D'
表示出口,字符'X'
表示墙壁,字符'.'
表示平地。你需要从'S'
出发走到'D'
,每次只能向上下左右相邻的位置移动,并且不能走出地图,也不能走进墙壁。 每次移动消耗 1 时间,走过路都会塌陷,因此不能走回头路或者原地不动。现在已知出口的大门会在 T 时间打开,判断在 0 时间从起点出发能否逃离迷宫。数据范围 n*,m≤10,*T≤50。
我们只需要用
DFS
来搜索每条路线,并且只需搜到 T 时间就可以了(这是一个可行性剪枝)。但是仅仅这样也无法通过本题,还需考虑更多的剪枝。如上图所示,将 n×m 的网格染成黑白两色。我们记每个格子的行数和列数之和为 x,如果 x 为偶数,那么格子就是白色,反之奇数时为黑色。容易发现相邻的两个格子的颜色肯定不一样,也就是说每走一步颜色都会不一样。更普遍的结论是:走奇数步会改变颜色,走偶数步颜色不变。
那么如果起点和终点的颜色一样,而 T 是奇数的话,就不可能逃离迷宫。同理,如果起点和终点的颜色不一样,而 T 是偶数的话,也不能逃离迷宫。遇到这两种情况时,就不用进行
DFS
了,直接输出"NO"
。这样的剪枝就是奇偶性剪枝,本质上也属于可行性剪枝。
#include <iostream>
#include <string>
using namespace std;
const int N = 10;
int n, m, T;
string mp[N];
bool vis[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
bool ok;
//x, y 坐标; t 时间
void dfs(int x, int y, int t) {
if (ok) return; //最优性剪枝
if (t == T) {
if (mp[x][y] == 'D') ok = true;
return; //可行性剪枝
}
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (0 <= tx && tx < n && 0 <= ty && ty < m && mp[tx][ty] != 'X' && !vis[tx][ty]) {
dfs(tx, ty, t + 1);
}
}
vis[x][y] = false;
}
int main() {
cin >> n >> m >> T;
for (int i = 0; i < n; i++) {
cin >> mp[i];
}
int sx, sy, ex, ey;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == 'S')
sx = i, sy = j;
if (mp[i][j] == 'D')
ex = i, ey = j;
}
}
if ((sx + sy + ex + ey + T) % 2 != 0) { //奇偶性剪枝
cout << "NO" << endl;
} else {
ok = false;
dfs(sx, sy, 0);
if (ok) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
剪枝例题
引爆炸弹
在一个 n×m 的方格地图上,某些方格上放置着炸弹。手动引爆一个炸弹以后,炸弹会把炸弹所在的行和列上的所有炸弹引爆,被引爆的炸弹又能引爆其他炸弹,这样连锁下去。
现在为了引爆地图上的所有炸弹,需要手动引爆其中一些炸弹,为了把危险程度降到最低,请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。 数据范围:1≤n,m≤1000;
#include <iostream>
using namespace std;
int n, m;
char mp[1000][1000];
bool row[1010], col[1010]; //标记行和列是否被访问过
void dfs(int x, int y) {
mp[x][y] = '0';
if (!row[x]) {
row[x] = true; // 若该行没有被访问过,则这次引爆该行
for (int i = 0; i < m; i++) {
if (mp[x][i] == '1') {
dfs(x, i);
}
}
}
if (!col[y]) {
col[y] = true; // 若该列没有被访问过,则这次引爆该列
for (int i = 0; i < n; i++) {
if (mp[i][y] == '1') {
dfs(i, y);
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> mp[i];
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == '1') {
cnt++;
dfs(i, j);
}
}
}
cout << cnt << endl;
}
找数字 - (抽象dfs + 剪枝)
给一个数 n,让你找出一个只由 0,1 组成的十进制数 m*,要求这个正整数 m 可以被 n* 整除。 输入格式: 输入一个整数 n (1≤n<200)。 输出格式: 对于输入整数 n 的每一个值,输出 m 的相应值,保证有一个数字长度小于 19 位的数字。如果有一个给定值 n 有多个解,其中任何一个都是可以接受的。 本题答案不唯一,符合要求的答案均正确 样例输入复制:
2
样例输出复制:
10
- 2分支dfs,要么后面加0,要么后面加1
- 特别注意不是所有分支都有结果,所以要剪枝
- 注意条件保证有结果长度小于19,所以当长度大于等于19,return
#include <iostream>
using namespace std;
int n;
bool ok;
void dfs(long long s, int cnt) {
if (ok) return; //最优性剪枝,已经找到了可行解,没有必要继续搜索
if (cnt >= 19) { //递归出口1,字符串长度超过19
return;
}
if (s % n == 0) { //递归出口2,找到了可行性答案
ok = true;
cout << s << endl;
return;
}
dfs(s * 10, cnt + 1);
dfs(s * 10 + 1, cnt + 1);
}
int main() {
cin >> n;
dfs(1, 0); //因为是正整数,故不能为0
return 0;
}
全排列
从 n 个不同元素中任取 m (m≤n) 个元素,按照一定的顺序排列起来,叫做从 n 个不同元素中取出 m 个元素的一个排列。当m=n 时所有的排列情况叫全排列。 今天这道题目很简单就是给你一个整数n ,计算 [1,n] 所有数字的排列组合。 输入格式: 第一行输入一个整数 n(1≤n≤9). 输出格式: 第一行输出一个全排列的方案总数 m。 接下来按照字典序依次输出这 m 个排列。 排列的字典的比较方法和字符串一样,比如两个排列 a,b,从第一个数开始,找到第一个不同的数的位置为 ii,然后比较 a[i] 和 b[i] 的大小,如果 a[i] 小的,那么 a 的字典序就小,否则 b 的字典序更小。 样例输入1:
2
样例输出1
2 12 21
也可以用 next_permutation()
来做
#include <iostream>
#include <set>
#include <string>
using namespace std;
//--------
int n;
bool vis[10];
//n个位置,从1~n中选一个数塞进去,
void dfs(int num, int cnt) {
if (cnt == n) {
cout << num << endl;
return; //小心别少啦!
}
for (int i = 1; i <= n; i++) { //对于每一个位置,去枚举每一个可以用的数
if (!vis[i]) { //如果之前没有被用过
vis[i] = true; //标记使用该数
dfs(num * 10 + i, cnt + 1); //对于这种全是数字的用,当成数字拼接好了
vis[i] = false; //去试探别的数前,要取消对该数的标记
}
}
}
int main() {
cin >> n;
int ans = 1;
for (int i = 1; i <= n; i++) {
ans *= i;
}
cout << ans << endl;
dfs(0, 0);
return 0;
}
蒜头君的旅游计划
马上就要放寒假了,蒜头君已经辛勤的工作一年了,打算和家人一起出去旅游放松放松。有经验的人一定知道,出去旅游前一定要有详细的旅行规划。蒜头君打算旅游 n 个城市,但并不是每条路线的花费都是一样的。蒜头君是一个勤俭节俭的人,他就在想怎么把所有的城市旅游一遍花费最小呢?(蒜头君不喜欢重复旅游同一个城市,也就是说已到达过的城市蒜头君是不会再次光临的)
输入格式
第一行输入一个整数 n(1≤n≤15),表示有 n 个城市。
接下来有一个 n×n 的矩形,表示每两个城市之间的火车花费,每两个城市之间的花费不会超过 10000。
输出格式
输出一个整数,表示从 11 号城市把所有景点旅游一遍并且回到 11 号城市的最小花费。
样例输入
4 0 1 1 1 1 0 2 1 5 5 0 6 1 1 3 0
样例输出
8
#include <iostream>
#include <algorithm>
using namespace std;
int G[20][20];
bool vis[20];
int n, ans = 0x3f3f3f;
// u:当前所在点 cnt:所走步数 sum:总花费
void dfs(int u, int cnt, int sum) {
if (sum > ans) { //最优性剪枝
return;
}
if (cnt == n - 1) {
ans = min(ans, sum + G[u][0]);
}
vis[u] = true; //标记在循环外,包含源点,循环n-1次,到达目的
for (int i = 0; i < n; i++) {
if(!vis[i]) {
dfs(i, cnt + 1, sum + G[u][i]);
}
}
vis[u] = false;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> G[i][j];
}
}
dfs(0, 0, 0);
cout << ans;
return 0;
}
蒜头君手上有一些小木棍,它们长短不一,蒜头君想用这些木棍拼出一个正方形,并且每根木棍都要用到。 例如,蒜头君手上有长度为 1,2,3,3, 3 的 5 根木棍,他可以让长度为1,2 的木棍组成一条边,另外三根分别组成 3 条边,拼成一个边长为 3 的正方形。蒜头君希望你提前告诉他能不能拼出来,免得白费功夫。
输入格式
首先输入一个整数 n(4≤n≤20),表示木棍数量,接下来输入 n 根木棍的长度 pi(1≤pi≤10000)。
输出格式
如果蒜头君能拼出正方形,输出
"Yes"
,否则输出"No"
。样例输入1复
4 1 1 1 1
样例输出1复
Yes
样例输入2
5 10 20 30 40 50
样例输出2
No
#include <iostream>
#include <algorithm>
using namespace std;
int p[25];
bool vis[25];
int n;
int sum = 0;
bool ok;
void dfs(int s, int cnt, int pos) {
if (ok) { //最优性剪枝
return;
}
if (s > sum / 4) { //注意这里是sum / 4, 别写成 sum % 4
return;
}
if (s == sum / 4) {
dfs(0, cnt + 1, 0); //pos 重新从0开始搜素
return;
}
if (cnt == 4) {
ok = true;
return;
}
for (int i = pos; i < n; i++) { //重复性剪枝
if (!vis[i]) {
vis[i] = true; //虽然使用重复性剪枝,但是重新搜索时 pos 从0开始
dfs(s + p[i], cnt, i + 1);
vis[i] = false;
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p[i];
sum += p[i];
}
if (sum % 4 != 0) {
cout << "No" << endl;
} else {
dfs(0, 0, 0);
if (ok) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
}