搜索算法-DFS再探究课件.ppt

《搜索算法-DFS再探究课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索算法之DFS再探究深度优先搜索算法（DFS）深度优先搜索是实现搜索的一种策略深度优先搜索的基本思想：为了求得问题的解，先选择一种可能情况不断向前探索，一旦发现选择错误，则退回一步重新选择，然后继续向前探索简单来说就是“一条路走到底，不通再掉头”深度优先搜索最基本的算法实现方式就是采用递归回溯全排列问题设有n个整数的集合{1,2,…,n}，从中任意取出r个数进行排列（r

2、一个游戏：写出一个1～N的排列a[i]，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：31244367916最后得到16这样一个数字。现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列a[i]。若答案有多种可能，则输出字典序最小的那一个。例题1数字游戏【输入文件】输入文件bds.in的第1行为两个正整数n，sum。【输出文件】输出文件bds.out包括1行，为字典序最小的那个答案。【样例输入】416【样例输出】3124【数据规模与约定】对于40%的数据，

3、n≤7；对于80%的数据，n≤10；对于100%的数据，n≤12，sum≤12345，且保证一定有解。例题1数字游戏思路：枚举初始排列，状态数：n!计算最后的数字，复杂度：O(n^2)最终复杂度O(n!*n^2)N=12时，复杂度≈6*10^10，超时！例题1数字游戏思路：设排列为a[1],a[2],…,a[N]，经过一系列累加得到了最后的答案sum，既然是累加，设：sum=c[1]*a[1]+c[2]*a[2]+……+c[n]*a[n]求c[i]，设a[i]=1，其他a均为0，模拟计算一次，就可以得到a[i]被累加了几次，即得到了c[i]。10000100001000011001100110

4、01102112011331例题1数字游戏可以发现，其实最后系数为杨辉三角第N层的系数111121133114641例如N=5，最初的排列为ABCDEsum=A*1+B*4+C*6+D*4+E*1解题步骤：1、计算杨辉三角第N层的系数b[1..n]2、枚举初始排列a[1..n]，状态数：n!3、计算sum(a[i]*b[i]){i∈1..n}，复杂度：O(n)最终复杂度O(n!*n)N=12时，复杂度≈10^9关于搜索的关键词对象状态转移边界剪枝方向例题2小木棍有一些等长的木棍，被切成一些已知长度的小木棍（最长50），求最小可能原长。小木棍的个数不超过60。例题2小木棍搜索方法：先假设一个长木

5、棍的长度，再试着用小木棍一根根地拼，看看能不能拼出来。搜索对象1：长木棍O(50*N)搜索对象2：小木棍O(N!)总复杂度：O(50*N*N!)≈2.5*10^85例题2小木棍搜索状态怎么表示，如何转移？对于搜索对象1：长木棍长度状态：直接定义一个变量orglen转移：枚举范围：最长小木棍长度小木棍总长例题2小木棍对于搜索对象2：小木棍状态：dfs(curnum,rest,f)curnum：目前正在拼第几根长木棍rest：当前的长木棍还剩多长没拼f：从第几根小木棍开始尝试转移：1、rest=0dfs(curnum+1,orglen,1)2、第i根小木棍可用dfs(curnum,rest-

6、a[i],i+1)边界：1、curnum=长木棍数量并且rest=0，返回true2、找不到任何一根小木棍<=rest，返回false例题2小木棍剪枝1：长木棍应满足什么条件？为所有小木棍总长度的因数。剪枝2：长木棍有最小值吗？显然最小值为小木棍的最大长度。例题2小木棍剪枝3：如何定一个搜索顺序能加快搜索？将小木棍从长到短排序，短的木棍使用更灵活，所以先放长的小木棍较好，否则一开始就用完短的小木棍再放长的小木棍就不好放了。剪枝4：在还原长木棍时，第1根放什么，能确定吗？显然，最长的那根小木棍肯定要放进去，那么作为第1根，如果这都搜不出来那么肯定就无解了。例题2小木棍剪枝5：长度相同的木棍可以做

7、什么优化？如果有多根长度为x的小木棍，现在放x搜不出结果，那么这些再把另一个x放进去肯定也搜不出结果来。剪枝6：如果当前放的是最长的那一根小木棍，他正好与前面放置的小木棍拼出了一根长木棍，但是搜下去却找不到一种可行方案，那么？不继续进行搜索！放弃尝试更短的小木棍。例题3间隔排列有2N个木块，每个木块标上1到N的自然数中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木