学做家常菜的网站有哪些,网站为什么被挂马,个人做网站,学校校园网站本思路来自acwing算法提高课
题目描述 看本文需要准备的知识
1.dfs算法基本思想
2.对剪枝这个词有个简单的认识
迭代加深思想和此题分析
首先#xff0c;什么是迭代加深呢#xff1f;当一个问题的解有很大概率出现在递归树很浅的层#xff0c;但是这个问题的解本身存在…本思路来自acwing算法提高课
题目描述 看本文需要准备的知识
1.dfs算法基本思想
2.对剪枝这个词有个简单的认识
迭代加深思想和此题分析
首先什么是迭代加深呢当一个问题的解有很大概率出现在递归树很浅的层但是这个问题的解本身存在着很深的层当这个很浅的层的对应分支在搜索顺序比较靠后的位置时我们就会先搜索前几个很深的层导致浪费大量时间迭代加深就是为了解决这个问题如下图所示而存在的 迭代加深具体思想非常简单设置一个max_depth每次搜索超过这个值直接return如果搜完没搜到就逐步扩大max_depth
比如上面那个图刚开始max_depth1,对于左边那一堆往下搜一个没搜到直接return轮到第二个分支往下搜一个直接就找到答案了如果答案在第二个分支的第二层就会从最左边开始先往下搜两个没找到就开始搜第二个分支往下看两个就又找到了。
有人可能会问这样反复搜之前搜过的部分不会导致效率低吗
举一个满二叉树的例子吧
假设答案在第8层在max_depth从1到8的过程中会先搜索
2^12^2......2^72^8
所以相对第8层而言这个重复搜索不值一提
而对于这个题目举一个例子n127时可以是1,2,4,8,16,32,64,仅仅第7层就可以搜到而如果按照正常搜索顺序去搜举一个极端例子可以这样
1,2,填第三个时可以填123
1,2,3填第四个时可以填134,
依次类推甚至可以搜一百多层相对于第7层而言这做出了极大的优化
最后我们可以发现这有一种bfs的味道感觉就像是迭代加深把dfs的优势和bfs做了融合一样
剪枝
本题可以做几个剪枝
1.优化搜索顺序每层的搜索大的开始这样分支数会减少
2.可行性剪枝当某层上可能填入的数小于等于当前确定序列的最后一个数或者大于n那么就不选这个数
3.去掉冗余比如1,2,3,4,该搜第五个数时2314所以如果14已经搜过就不用弄23了故设立st数组标记已经搜过的下次再见时直接continue本次循环
本题感想
这道题目对于st数组到底是每层初始化一次还是每棵递归树整体初始化一次这个问题我思考了很长时间虽然知道结果是前者但始终找不到其中的原因现在我想通了找这个原因其实是没有必要的而且是很难的因为dfs层与层之间的调用会导致各种数组变量结果变化我们寻找这种具体变化和影响是极其艰难的所以我们需要做的事弄清st数组应该作用于什么地方就行了本题st数组的目的就是仅仅为了排除二重循环的X[i]X[j]相同的冗余问题既然仅仅作用于二重循环我们也仅仅需要在二重循环前面开一个st数组即可
代码
#includeiostream
#includecstring
using namespace std;
const int N110;
int path[N];
int n;
bool dfs(int u,int k)
{if(uk)return path[u-1]n;bool st[N];memset(st,0,sizeof st);for(int iu-1;i0;i--){for(int ji;j0;j--){int spath[i]path[j];if(sn||spath[u-1]||st[s])continue;path[u]s;st[s]true;if(dfs(u1,k))return true;}}return false;
}
int main()
{path[0]1;while(cinn,n){int k1;while(!dfs(1,k))k;for(int i0;ik;i)coutpath[i] ;coutendl;}return 0;
}
