旅游商城网站模板免费下载,wordpress忘记用户名,多个网站 备案,南京门户网站深度优先搜索#xff08;dfs#xff09;题目合集 全排列问题 dfs原理和模版深度优先搜索原理#xff08;纯个人理解#xff09;参考程序dfs通用模版 素数环组合的输出 剪枝新dfs模版参考程序新的dfs模版 自然数的拆分 利用形参进行回溯 全排列问题 dfs原理和模版
P1706 全… 深度优先搜索dfs题目合集 全排列问题 dfs原理和模版深度优先搜索原理纯个人理解参考程序dfs通用模版 素数环组合的输出 剪枝新dfs模版参考程序新的dfs模版 自然数的拆分 利用形参进行回溯 全排列问题 dfs原理和模版
P1706 全排列问题 - 洛谷 | 计算机科学教育新生态
深度优先搜索原理纯个人理解
和循环做对比
两层循环嵌套的情况下假设内层循环运行到一半时我不想运行了我想把外层循环的状态往回拨例如for循环一般用一个进度标记变量i表示循环进度修改i的值用以控制循环重新开始。
但是直接终止内层循环的话即使修改外层循环的循环进度也无法回到外层循环之前的状态或者说需要付出巨大的条件。
我们知道递归是函数调用自己本身。底层有专门的寄存器记录当前函数的进度当函数递归时在函数所在的栈空间会生成一个和自己一样的函数先执行新生成的函数执行完了会回到原来的函数原来的进度继续进行。
利用这个特性我们用递归代替外层的循环内部再用一个循环这样内层循环运行到一半不想运行了直接退出当前函数回到上一层函数发生递归的语句后继续运行。这样做的最大好处是可以以非常低的成本回到之前的状态。
这种利用递归和栈的特性实现的枚举方式被称作**深度优先搜索depth first search简称dfs**算法。
例如这题枚举全排列假设枚举到1,2,3时输出123然后3的空位让出来3后面没有数字了回到2,2的后面还有一个3于是有了1,3再到第三个空位此时有1,2可以用1之前用过了就把2放上去于是就有了132。
利用这个思路即可完成全排列的枚举。而这个思路也是dfs的通用思路。
用这个算法时一定要想清楚状态以及回来书上和资料上叫回溯的时候哪些状态要还原哪些不还原。例如这里1之前用过了后面就不能用了等之前的用完了才能用。
参考程序
#includestdio.hint flag[10];
int ans[10],p;//深度优先搜索
void dfs(int n,int depth){if(depthn){int i0;for(i1;in;i){printf(%5d,ans[i]);}printf(\n);return;}int i1;for(i1;in;i){if(flag[i]1)continue;flag[i]1;//标记状态下层枚举时跳过这层 ans[p]i;//记录答案 dfs(n,depth1);//前往下一层 --p;//回溯 flag[i]0;//回到之前的状态}
}int main() {int n;scanf(%d,n);dfs(n,1);return 0;
}但这个算法的时间复杂度一般都是平方甚至是指数级若递归太深还会导致栈溢出。所以dfs也有很大的局限性。为了降低复杂度和减少栈溢出有很多技巧有的大佬称之为剪枝可以进行后面有刷到相关的题就提一下。
dfs通用模版
模拟两层循环的dfs模版
void dfs(int depth, 其他参数){//depth用于标记递归深度可以没有if(depth太深不给往下走了或其他情况){整理状态;return;}if(其他情况如果有的话虽然可以放在一个if里处理){整理状态;return;}//...for(初始情况;是否枚举完了所有情况;){if(情况1不符合条件)continue;if(情况2不符合条件)continue;//...标记状态;处理当前情况;dfs(depth1其他参数);将标记的状态回溯到原来的样子;}
}个人更喜欢用这个因为在比赛的环境下自己并不能一下子想到所有不符合条件的情况或状态所以用这个模版的话想到一个添加一个也不用修改之前的判断。
当然模版并不唯一只要能理解整个思路以及整理好实际问题的所有状态就能用dfs解决问题。
素数环
2110【例5.1】素数环
参考程序
#define _CRT_SECURE_NO_WARNINGS 1/*
http://ybt.ssoier.cn:8088/problem_show.php?pid2110
*/#includeiostream
#includecmath
#define endl \n
using namespace std;bool flag[31] { 0 };
int n 0;
int ans[31] { 0 };//数据范围不超过30所以数组开31个空间bool prime(int x) {//判断素数if (x 2)return true;if (x 2)return false;int i 2;while (i sqrt(x) x % i ! 0)i;if (x % i 0)return false;return true;
}inline int judg(int x) {//防止数据越界if (x n)return 1;if (x 1)return n;return x;
}void dfs(int depth) {if (depth n1) {//所有空位都填满了flag[0] true;return;}for (int i 1; i n; i) {if (flag[i])//这个数字用过continue;//上一个空填有数字并且i和那个数字的和不是素数if (ans[judg(depth - 1)] ! 0 !prime(i ans[judg(depth - 1)]))continue;if (ans[judg(depth 1)] ! 0 !prime(i ans[judg(depth 1)]))continue;ans[depth] i;flag[i] true;dfs(depth 1);if (!flag[0]) {//如果凑齐了一个环就不回溯等所有递归解除回到main函数flag[i] false;ans[depth] 0;}}
}int main()
{cin n;dfs(1);for (int i 1; i n; i)cout ans[i] ;return 0;
}组合的输出 剪枝新dfs模版
1317【例5.2】组合的输出
剪枝的一个例子。
举1为根结点的树的例子画红圈的都是不要的结点应该剪去。 参考程序
剪去结点的方法很多比如在内层循环中作判断
#includeiostream
#includecstdio
using namespace std;int n, r, num[101];
bool vis1[101] { 0 };
void dfs1(int dep)
{if (dep r 1){for (int i 1; i dep; i)printf(%3d, num[i]);printf(\n);return;}for (int i 1; i n; i){if (!vis1[i]inum[dep-1])//这层递归填进去的答案比上一层大{vis1[i] 1;num[dep] i;dfs1(dep 1);vis1[i] 0;}}
}int main()
{cin n r;dfs1(1);return 0;
}或者对内部的循环的枚举范围进行限制
#includeiostream
#includecstdio
using namespace std;int n, r, num[101];
bool vis1[101] { 0 };
void dfs1(int dep) {if (dep r 1) {for (int i 1; i dep; i)printf(%3d, num[i]);printf(\n);return;}//从上一层的最大数开始枚举很不错的剪枝 for (int i num[dep - 1] 1; i n; i) {if (!vis1[i]) {vis1[i] 1;num[dep] i;dfs1(dep 1);vis1[i] 0;}}
}int main() {cin n r;dfs1(1);return 0;
}可以的话尽量用第2种思路第2种思路直接规避掉了很多不必要的判断。
新的dfs模版
void dfs(int depth, 其他参数){//depth用于标记递归深度可以没有if(depth太深不给往下走了或其他情况){整理状态;return;}if(其他情况如果有的话虽然可以放在一个if里处理){整理状态;return;}//...for(初始情况;是否枚举完了所有情况;){if(符合条件){标记状态;处理当前情况;dfs(depth1其他参数);将标记的状态回溯到原来的样子;}}
}自然数的拆分 利用形参进行回溯
1318【例5.3】自然数的拆分
例如这个样例
71111111
7111112
711113
711122
71114
71123
7115
71222
7124
7133
716
7223
725
734后面输出的数都不比前面的小又都能保证全部加起来等于7。
所以用到上题的剪枝。
参考程序
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif
#includeiostream
using namespace std;
int ans[101] { 0 };
int total 0;void dfs(int depth, int n, int sum, int ls) {if (sum 0) {total;cout n ;for (int i 1; i ans[0]; i)cout ans[i] ;cout ans[ans[0]] endl;return;}if (depth n || sum 0)return;for (int i ls; i n; i) {ans[ans[0]] i;//没有明显的条件限制dfs(depth 1, n, sum - i, i);--ans[0];//回溯}
}int main() {int n 0;cin n;dfs(1, n, n, 1);return 0;
}发现参考程序可以进一步被优化。例如n作为全局变量sum记录枚举的数的和当递归到下一层时sumi作为实参传递给下一层回来之后sum还是sum。
因为sum是形参可以理解为局部变量局部变量出了自己的作用域就用不了了而每层递归的形参和上层递归的关系只有上层递归传值给这层递归。利用这个原理可以实现自动回溯。
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif
#includeiostream
using namespace std;
int ans[101] { 0 };
int total 0;
int n 0;void dfs(int depth, int sum) {if (sum n)return;if (sum n) {cout n ;for (int i 1; i depth - 1; i)cout ans[i] ;cout ans[depth - 1] endl;return;}for (int i ans[depth - 1]; i n; i) {ans[depth] i;dfs(depth 1, sum i);}
}int main() {cin n;ans[0] 1;dfs(1, 0);return 0;
}
