您当前位置：首页 > php开源 > 综合技术 > DFS + 剪枝策略

DFS + 剪枝策略

来源：程序员人生发布时间：2015-03-11 08:06:33 阅读次数：6144次

1：简介

（1）相信做过ACM的人，都很熟习图和树的深度优先搜索；算法里面有蛮力法 ―― 就是暴力搜索（不加任何剪枝的搜索）；

（2）蛮力搜搜需要优化时，就是需要不停的剪枝，提早减少没必要要的搜索路径，提早发现判断的过滤条件；

（3）剪枝的核心问题就是设计剪枝判断方法，哪些搜索路径应当舍弃，哪些搜索路径不能舍弃（保存）；

（4）高效的剪枝过滤条件需要从局部和全局来斟酌问题，发现内在的规律。

（5）详细的剪枝算法，请见剪枝算法(算法优化)

2：示例验证

（1）题目来源于 poj 1011 Sticks DFS + 剪枝

题目大意：给出1些长度不大于 50 的木棍，要求你把这些小木棍拼成,长度相同木棍，固然长度越小越好。

（2）解题思路

1. 首先 Sum1定要能被 L 整除。
2. L 1定大于等于题目给出的最长的木棍的长度 Max。由上述两点，我们想到，可以从 Max 开始递增地枚举 L, 直到成功地拼出 Sum/L 支长度为 L 的木棍。
搜索种的剪枝技能：
3. 将输入的输入从大到小排序，这么做是由于1支长度为 K 的完全木棍，总比几支短的小木棍拼成的要好。形象1些：如果我要拼 2 支长为8的木棍，第1支木棍我拼成 5 + 3 然后拼第2支木棍但是失败了，而我手中还有长为 2 和 1 的木棍，我可以用 5 + 2 + 1 拼好第1支，再尝试拼第2
支，仔细想想，就会发现这样做没意义，注定要失败的。我们应当留下 2+1 由于 2+1 比 3 更灵活。
4. 相同长度的木棍不要搜索屡次，比如：我手中有1些木棍, 其中有 2 根长为 4 的木棍，当前搜索状态是 5+4+....(即表示长度为 5,4,2 的3支拼在1起,
...表示深层的行将搜索的部份), 进行深搜后不成功，故我没必要用另外一个 4 在进行 5+4+... （题目中相邻的前后比较）
5. 将开始搜索1支长为 L 的木棍时，我们总是以当前最长的未被使用的木棍开始，如果搜索不成功，那末以比它短的开始，那末也1定不能获得全局的成功。由于每支题目给出的木棍都要被用到。如果，有
4
5 4 4 3 2 想拼成长为 6 的木棍，那末从 5 开始，但是明显没有能与 5 1起拼成 6 的，那末我就没必要去尝试从 4 开始的，由于终究 5 1定会被抛弃。在拼第 2 3 ... 支木棍时，1样。（小的更加灵活）

6. 最后的最简单的1个就是，
for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)
{}
与
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
{}
的区分，这个不多说了。
7. 我用过的另外一个剪枝，但是对 poj 的数据效果1般，用1个数组， Sum[i] 保存第 i 个木棍以后，即比第 i 枝木棍短或与之相等所有的木棍的长度和。试想，如果剩余的所有木棍加在1起都不能和我当前的状态拼出1根长为 L 的木棍(从长度来看)，还有必要搜下去么？

（3）详细代码

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int Max = 65; int n, len, stick[Max]; bool flag, vis[Max]; bool cmp(int a, int b) { return a > b; } void dfs(int dep, int now_len, int u) { // dep为当前已被用过的小棒数，u为当前要处理的小棒。 if(flag) return;//完成的递归返回条件 if(now_len == 0){ // 当前长度为0，寻觅下1个当前最长小棒。 int k = 0; while(vis[k]) k ++; // 寻觅第1个当前最长小棒。 vis[k] = true; dfs(dep + 1, stick[k], k + 1); vis[k] = false; return; } if(now_len == len) { // 当前长度为len，即又拼凑成了1根原棒。 if(dep == n) flag = true; // 完成的标志：所有的n根小棒都有拼到了。 else dfs(dep, 0, 0); return;//未完成的递归返回条件 } for(int i = u; i < n; i ++) if(!vis[i] && now_len + stick[i] <= len)// 过滤条件 { if(!vis[i⑴] && stick[i] == stick[i⑴]) continue; // 不重复搜索：最重要的剪枝。 vis[i] = true; dfs(dep + 1, now_len + stick[i], i + 1); vis[i] = false; } } int main() { while(scanf("%d", &n) && n != 0) { int sum = 0; flag = false; for(int i = 0; i < n; i ++) { scanf("%d", &stick[i]); sum += stick[i]; } sort(stick, stick + n, cmp); // 从大到小排序。 for(len = stick[0]; len < sum; len ++) if(sum % len == 0)// 这里也相当因而剪枝（过滤条件） { // 枚举能被sum整除的长度。 memset(vis, 0, sizeof(vis)); dfs(0, 0, 0); if(flag) break; } printf("%d ", len); } return 0; }

（4）对照比较 poj 1011(本博客) 和 poj 3900 (剪枝算法(算法优化))

对前者 ―― 是依照性价比排序；性价比高的未必最后会要（有选择的要）；构成两条剪枝条件：

剪枝1. 以后所有的钻石价值+目前已得到的价值<=ans 则剪枝。

剪枝2. 剩下的重量全部装目前最高性价比的钻石+目前已得到的价值<=ans 则剪枝（非常重要的剪枝）。

对后者 ―― 依照长度排序（都是提早从大到小的排序）；必须把全部小木棒用上，因此需要有visit数组在dfs前后的true 和 false 的变化；

剪枝1、由于所有原始棒子等长，那末必有sumlen%Initlen==0；

剪枝2、若能在[maxlen,sumlen-InitLen]找到最短的InitLen，该InitLen必也是[maxlen,sumlen]的最短；若不能在[maxlen,sumlen-InitLen]找到最短的InitLen，则必有InitLen=sumlen；

剪枝3、由于所有棒子已降序排序，在DFS时，若某根棒子不适合，则跳过其后面所有与它等长的棒子；

剪枝4、最重要的剪枝：对某个目标InitLen，在每次构建新的长度为InitLen的原始棒时，检查新棒的第1根stick[i]，若在搜索完所有stick[]后都没法组合，则说明stick[i]没法在当前组合方式下组合，不用往下搜索(往下搜索会令stick[i]被舍弃)，直接返回上1层

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生