第五十三章 DFS进阶（一）——剪枝优化

一、什么是剪枝？

我们知道DFS在很多场景内都是一个指数级别的算法，其时间复杂度是相当巨大的。

而在我们枚举的时候，有很多种情况在枚举了一部分之后，就知道它不是正确答案了，那么在这种情况下，该种情况就没有继续向后枚举的必要了。那么将这些情况挑出来并舍弃掉的过程，就叫做剪枝。它能在一定程度上，对我们的代码进行优化。

二、剪枝优化的策略

1、优化搜索顺序

我们搜索的过程其实就是一个暴力枚举所有情况的过程，而之所以这么多情况，关键在于我们的选择太多。

那么为了减少搜索的时间，我们就要尽可能地减少一些选择。这就是我们优化搜索顺序的目的。

比如说，给定一串正整数，我们要找到几个数字的组合，不超过给定的最大值M。

假设我们这的数字是从小到大排列的，如果一开始就选一个最小的数字的话，那么我们后续的选择就会很多，这就导致我们的搜索树的子树很多，就导致节点变多，从而加长了时间。

但是我们从大到小开始枚举的话，由于这些数字很大，那么留给后续数字的可选择的空间就会变少，从而减少了选择，即优化了时间。

2、排除等效冗余

等效冗余即虽然方案和方案之间的选择不同，但是他们导致的结果是一致的，在这种情况下，我们只需要选择一种即可。比如刚刚的例题，我们只在乎选出一个组合，但是组合之间的顺序其实是无关紧要的，那么我们只需要枚举出一种顺序，其他的扔掉就行了。

3、可行性剪枝

依旧以刚刚的问题为例子，如果某种方案在枚举过程中已经超过了最大值M，那么后续就不需要枚举了，因为这种方案肯定不行。

4、最优性剪枝

如果当前方案通过某种判断已经确定不是最优解了，那么也可以直接扔掉。

5、记忆化搜索

三、例题

1、AcWing 165. 小猫爬山（DFS + 剪枝优化）

AcWing 165. 小猫爬山（DFS + 剪枝优化）

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
typedef long long ll;
int n, w;
int c[N];
int ans = N;
bool st[N];
ll sw[N];
bool cmp(int x, int y)
{return x >y;
}
void dfs(int u, int nums)
{if(u == n){ans = min(ans, nums);return;}if(nums >= ans)return;int cnt = 0;for(int i = 1; sw[i] != 0; i ++ ){if(sw[i] + c[u] <= w){sw[i] += c[u];dfs(u + 1, nums);sw[i] -= c[u];}cnt ++;}sw[cnt + 1] = c[u];dfs(u + 1, cnt + 1);sw[cnt + 1] -= c[u];
}void solve()
{cin >> n >> w;for(int i = 0; i < n; i ++ )cin >> c[i];sort(c, c + n, cmp);dfs(0, 0);cout << ans << endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}

2、AcWing 167. 木棒（DFS + 剪枝优化）

AcWing 167. 木棒（DFS + 剪枝优化）

#include<bits/stdc++.h>
using namespace std;
const int N = 70;int n;
int w[N];
int sum, length;
bool st[N];bool dfs(int u, int cur, int start)
{if (u * length == sum) return true;if (cur == length) return dfs(u + 1, 0, 0);for (int i = start; i < n; i ++ ){if (st[i] || cur + w[i] > length) continue;st[i] = true;if (dfs(u, cur + w[i], i + 1)) return true;st[i] = false;if (!cur || cur + w[i] == length) return false;int j = i;while (j < n && w[j] == w[i]) j ++ ;i = j - 1;}return false;
}int main()
{while (cin >> n, n){memset(st, 0, sizeof st);sum = 0;for (int i = 0; i < n; i ++ ){cin >> w[i];sum += w[i];}sort(w, w + n);reverse(w, w + n);length = 1;while (true){if (sum % length == 0 && dfs(0, 0, 0)){cout << length << endl;break;}length ++ ;}}return 0;
}

3、AcWing 166. 数独（DFS + 剪枝优化 + lowbit函数 + 状态压缩）

AcWing 166. 数独（DFS + 剪枝优化 + lowbit函数 + 状态压缩）

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 9;
int row[N], col[N], ones[1 << N], cell[3][3];
char str[100];
int ma[1 << N];
int lowbit(int x)
{return x & -x;
}int get(int x, int y)
{return row[x] & col[y] & cell[x / 3][y / 3];
}void init()
{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 nums, bool flag)
{if(flag)str[x * N + y] = '1' + nums;elsestr[x * N + y] = '.';int v = 1 << nums;if(!flag)v = -v;row[x] -= v;col[y] -= v;cell[x / 3][y / 3] -= v;
}bool dfs(int cnt)
{if(!cnt)return true;int minv = INF;int 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;}}	}}int state = get(x, y);for(int i = state; i ; i -= lowbit(i)){//枚举当前所有可以写的数字int t = ma[lowbit(i)];//在该位补上合适的数字，并更新行，列，九宫格的状态draw(x, y, t, true);if(dfs(cnt - 1))return true;//复原draw(x, y, t, false);} return false;
}void solve()
{for(int i = 0; i < N; i ++ )ma[1 << i] = i;//记录1 << i代表的是哪个数字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);}elsecnt ++;}dfs(cnt);cout << str << endl;	}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();	
}