网站维护客户,小制作大全,网上商城功能模块图,哪个网站做网站好第五十四章 DFS进阶#xff08;一#xff09;——剪枝优化一、什么是剪枝#xff1f;二、剪枝优化的策略1、优化搜索顺序2、排除等效冗余3、可行性剪枝4、最优性剪枝5、记忆化搜索三、例题1、AcWing 165. 小猫爬山#xff08;DFS 剪枝优化#xff09;2、AcWing 167. 木棒…
第五十四章 DFS进阶一——剪枝优化一、什么是剪枝二、剪枝优化的策略1、优化搜索顺序2、排除等效冗余3、可行性剪枝4、最优性剪枝5、记忆化搜索三、例题1、AcWing 165. 小猫爬山DFS 剪枝优化2、AcWing 167. 木棒DFS 剪枝优化3、AcWing 166. 数独DFS 剪枝优化 lowbit函数 状态压缩一、什么是剪枝
我们知道DFS在很多场景内都是一个指数级别的算法其时间复杂度是相当巨大的。
而在我们枚举的时候有很多种情况在枚举了一部分之后就知道它不是正确答案了那么在这种情况下该种情况就没有继续向后枚举的必要了。那么将这些情况挑出来并舍弃掉的过程就叫做剪枝。它能在一定程度上对我们的代码进行优化。
二、剪枝优化的策略
1、优化搜索顺序
我们搜索的过程其实就是一个暴力枚举所有情况的过程而之所以这么多情况关键在于我们的选择太多。
那么为了减少搜索的时间我们就要尽可能地减少一些选择。这就是我们优化搜索顺序的目的。
比如说给定一串正整数我们要找到几个数字的组合不超过给定的最大值M。
假设我们这的数字是从小到大排列的如果一开始就选一个最小的数字的话那么我们后续的选择就会很多这就导致我们的搜索树的子树很多就导致节点变多从而加长了时间。
但是我们从大到小开始枚举的话由于这些数字很大那么留给后续数字的可选择的空间就会变少从而减少了选择即优化了时间。
2、排除等效冗余
等效冗余即虽然方案和方案之间的选择不同但是他们导致的结果是一致的在这种情况下我们只需要选择一种即可。比如刚刚的例题我们只在乎选出一个组合但是组合之间的顺序其实是无关紧要的那么我们只需要枚举出一种顺序其他的扔掉就行了。
3、可行性剪枝
依旧以刚刚的问题为例子如果某种方案在枚举过程中已经超过了最大值M那么后续就不需要枚举了因为这种方案肯定不行。
4、最优性剪枝
如果当前方案通过某种判断已经确定不是最优解了那么也可以直接扔掉。
5、记忆化搜索
三、例题
1、AcWing 165. 小猫爬山DFS 剪枝优化
AcWing 165. 小猫爬山DFS 剪枝优化
#includebits/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 剪枝优化
#includebits/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函数 状态压缩
#includebits/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();
}
