企业网站数据库表设计,企业官方网站建设教程,wordpress vr插件,360海南地方网站递归型枚举与回溯剪枝初识 1.枚举子集2.组合型枚举3.枚举排列4.全排列问题 什么是搜索#xff1f;搜索#xff0c;是一种枚举#xff0c;通过穷举所有的情况来找到最优解#xff0c;或者统计合法解的个数。因此#xff0c;搜索有时候也叫作暴搜。搜索一般分为深度优先搜索… 递归型枚举与回溯剪枝初识 1.枚举子集2.组合型枚举3.枚举排列4.全排列问题 什么是搜索搜索是一种枚举通过穷举所有的情况来找到最优解或者统计合法解的个数。因此搜索有时候也叫作暴搜。搜索一般分为深度优先搜索(DFS)与宽度优先搜索(BFS)。深度优先遍历 vs 深度优先搜索宽度优先遍历 vs 宽度优先搜索。遍历是形式搜索是目的。不过在一般情况下我们不会去纠结概念的差异两者可以等同。回溯与剪枝
回溯当在搜索的过程中遇到走不通或者走到底的情况时就回头。剪枝在搜索过程中剪掉重复出现或者不是最优解的分。
递归型枚举与回溯剪枝初识
画决策树。根据决策树写递归。
搜索的本质对决策树进行一次遍历直到将所有的情况搜集到为止。
1.枚举子集
B3622 枚举子集递归实现指数型枚举 解法深搜
设一共有 3 人分别是 123。「从前往后」考虑每一个人针对当前这个人「选」或者「不选」我们可以画出如下「决策树」 设计递归函数
重复子问题针对某一位「选」或者「不选」。因为最终结果要按照「字典序」输出我们可以「先考虑不选」然后「再考虑选」。实现方式参考代码和注释结合「决策树」一起看会很清晰。
#includeiostream
#includestring
using namespace std;const int N 11;int n;
string path; //记录递归过程中每⼀步的决策void dfs()
{if(path.size() n){cout path endl; //path存着前n个⼈的决策 return;}//不选path N;dfs();path.pop_back(); //回溯恢复现场//选path Y;dfs(); path.pop_back(); //回溯恢复现场
}int main()
{cin n;dfs();return 0;
}2.组合型枚举
P10448 组合型枚举 解法深搜
设 n 4, m 3「从前往后」考虑 3 个位置应该选哪个数我们可以画出如下决策树 设计递归函数
重复子问题当前这一位应该放哪个数上去。因为这是一个「组合」问题不涉及排列所以我们当前位置开始放的数应该是「上次决策的数的下一位」。实现方式参考代码和注释结合「决策树」一起看会很清晰。
#includeiostream
#includevector
using namespace std;int n, m;
vectorint path; //记录递归过程中每⼀步的决策void dfs(int pos)
{if(path.size() m){for(auto e : path) cout e ;cout endl;return;}for(int i pos; i n; i){path.push_back(i);dfs(i 1);path.pop_back(); //回溯恢复现场}
}int main()
{cin n m;dfs(1);return 0;
}3.枚举排列
B3623 枚举排列递归实现排列型枚举 解法深搜
设 n 3, k 2一共要选出两个数可以依次「考虑要选出来的数」是谁画出如下决策树 设计递归函数
重复子问题考虑这一位要放上什么数。因为是「排列」问题所以我们直接从 1 开始枚举要放的数。剪枝在这一条路径中我们「不能选择之前已经选择过的数」需要用到辅助数组。实现方式参考代码和注释结合「决策树」一起看会很清晰。
#includeiostream
#includevector
using namespace std;const int N 15;int n, k;
vectorint path; //记录递归过程中每⼀步的决策
bool vis[N]; //辅助数组标记哪些数已经选过 void dfs()
{if(path.size() k){for(auto e : path) cout e ;cout endl;return;}for(int i 1; i n; i){if(vis[i] false){vis[i] true;path.push_back(i);dfs();//回溯恢复现场path.pop_back();vis[i] false;}}
}int main()
{cin n k;dfs();return 0;
}4.全排列问题
P1706 全排列问题 解法深搜
跟上一道题的决策一样我们可以枚举每一位应该放上什么数只不过少了 k 的限制。剪枝的策略还是一样的那就是在路径中「不能选择之前已经选过的数」。 #includeiostream
#includevector
using namespace std;const int N 15;int n;
vectorint path; //记录递归过程中每⼀步的决策
bool vis[N]; //辅助数组标记哪些数已经选过void dfs()
{if(path.size() n){for(auto e : path) printf(%5d, e);cout endl;return;}for(int i 1; i n; i){if(vis[i] false){vis[i] true;path.push_back(i);dfs();//回溯恢复现场path.pop_back();vis[i] false;}}
}int main()
{cin n;dfs();return 0;
}
