《搜索算法DFS再探究ppt课件.ppt》由会员分享，可在线阅读，更多相关《搜索算法DFS再探究ppt课件.ppt（46页珍藏版）》请在三一办公上搜索。
1、搜索算法之DFS再探究,深度优先搜索算法（DFS）,深度优先搜索是实现搜索的一种策略深度优先搜索的基本思想：为了求得问题的解，先选择一种可能情况不断向前探索，一旦发现选择错误，则退回一步重新选择，然后继续向前探索简单来说就是“一条路走到底，不通再掉头”深度优先搜索最基本的算法实现方式就是采用递归回溯,全排列问题,设有n个整数的集合1,2,n，从中任意取出r个数进行排列（rn），试列出所有的排列。,n=4，r=3时的搜索树,1,2,3,4,2,3,4,1,2,3,3,4,2,4,2,3,2,3,1,3,1,2,例题1 数字游戏,有这么一个游戏：写出一个1N的排列ai，然后每次将相邻两个数相加，构
2、成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：3 1 2 4 4 3 6 7 9 16最后得到16这样一个数字。现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列ai。若答案有多种可能，则输出字典序最小的那一个。,例题1 数字游戏,【输入文件】输入文件bds.in的第1行为两个正整数n，sum。【输出文件】输出文件bds.out包括1行，为字典序最小的那个答案。【样例输入】4 16【样例输出】3 1 2 4【数据规模与约定】对于40%的数据，n7；对于80%的数据，n10；对于10
3、0%的数据，n12，sum12345，且保证一定有解。,例题1 数字游戏,思路：,枚举初始排列，状态数：n!计算最后的数字，复杂度：O(n2)最终复杂度O(n!*n2)N=12时，复杂度6*1010，超时！,例题1 数字游戏,思路：,设排列为a1,a2,aN，经过一系列累加得到了最后的答案sum，既然是累加，设：sum=c1*a1+c2*a2+cn*an求ci，设ai=1，其他a均为0，模拟计算一次，就可以得到ai被累加了几次，即得到了ci。1 0 0 00 1 0 00 0 1 00 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 2 1 1 2 0 1 1 3 3 1,
4、例题1 数字游戏,可以发现，其实最后系数为杨辉三角第N层的系数 1 1 1 1 2 1 1 3 3 11 4 6 4 1例如N=5，最初的排列为A B C D Esum=A*1+B*4+C*6+D*4+E*1解题步骤：1、计算杨辉三角第N层的系数b1.n2、枚举初始排列a1.n，状态数：n!3、计算sum(ai*bi)i1.n，复杂度：O(n)最终复杂度O(n!*n)N=12时，复杂度109,关于搜索的关键词,对象状态转移边界剪枝方向,例题2 小木棍,有一些等长的木棍，被切成一些已知长度的小木棍（最长50），求最小可能原长。小木棍的个数不超过60。,例题2 小木棍,搜索方法：先假设一个长木棍的
5、长度，再试着用小木棍一根根地拼，看看能不能拼出来。搜索对象1：长木棍O(50*N)搜索对象2：小木棍O(N!)总复杂度：O(50*N*N!)2.5*1085,例题2 小木棍,搜索状态怎么表示，如何转移？对于搜索对象1：长木棍长度状态：直接定义一个变量orglen转移：枚举范围：最长小木棍长度小木棍总长,例题2 小木棍,对于搜索对象2：小木棍状态：dfs(curnum,rest,f)curnum：目前正在拼第几根长木棍rest：当前的长木棍还剩多长没拼f：从第几根小木棍开始尝试转移：1、rest=0dfs(curnum+1,orglen,1)2、第i根小木棍可用dfs(curnum,rest-a
6、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的两个木块之间要间隔i个其它木块。比如N=3时，下面就是一个可行的排列：3，1，2，1，3，2。编程实现，对给定的N(n=40)，求出一个可行排列给出的输入数据保证能找到可行的排列,例题3 间
8、隔排列,搜索策略：排列：O(2N)!)，没有很好的剪枝回溯：O(2N)!)，在回溯过程中进行剪枝广搜：空间需求大，另本题并非求最优解采用回溯（深搜）策略，在深搜过程中减少搜索分支,例题3 间隔排列,搜索思路1对象：自然数1N状态：dfs(K)，K为木块序号，表示尝试在第K木块上标上1N的自然数转移：K2N，找到解，搜索结束找到一个可标在第K个木块的数dfs(K+1)找不到可标在第K个木块的数回溯dfs(K-1)，查找下一个可标在第K-1个木块的数字,例题3 间隔排列,搜索思路1剪枝：因为两个相同数字i的间隔为i，所以若数字i第一次标在第K个木块中，则必定K+i+1个木块也应标上数字i。dfs(
9、K)中只搜索第一次标的的数字，dfs(K)实际只需嵌套N层若i+K+12*N，则i可以剪枝，因为i第二次标注已经超过木块数在dfs(K)中，数字从N到1进行尝试。因为大数字的选择余地比较小,例题3 间隔排列,搜索思路2对象：木块12N状态：dfs(Num)，Num为数字序号，表示尝试在12N的木块中查找可以标上数字Num的木块转移：NumN，找到解，搜索结束找到可标上Num的木块dfs(Num+1)找不到可标上Num的木块回溯dfs(Num-1)，为Num-1换一个位置,例题3 间隔排列,搜索思路2剪枝：若尝试将数字Num第一次标在第K个木块中，应该同时标在第K+Num+1个木块上，减少后续的
10、dfs(Num)中对木块的搜索搜索可标注木块时，范围从第12*N-Num-1块先尝试大数字dfs(Num)的状态改为从N开始Num=0，找到解，搜索结束找到可标上Num的木块：dfs(Num-1)找不到可标上Num的木块：回溯dfs(Num+1)，为Num+1换一个位置,例题3 间隔排列,运行效果对比,例题4 数独,数独是一款能开发智力的游戏，其规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。,例题4 数独,例题4 数独,明显，这是一道深搜的题目
11、搜索对象：空白格子、数字1-9状态：9*9矩阵转移：在某一空白格子，搜到可填数字，更新9*9矩阵边界：没有空白格子填充完成某一个空白格子搜索不到合适数字回溯,例题4 数独,剪枝：某一格没有可填的数字，剩下格子也不用搜索了方向按格子坐标顺序？模拟人的思维，先易后难！先填可选择数字少的,例题4 数独,搜索顺序数组sziji：081，待填的空白格子数j：0、1，空白格子坐标 2，格子可填数字的数量搜索顺序数组排序（一边排序一边更新）设待排序区间为szaszb查找最小的szi2，szisza 在sza+1szb中查找与sza在同一列或同一行或同一区域的格子szj，将szj2值减1,例题4 数独,在程序
12、需维护的几个状态colij：第i列中，数字j是否可用rowij：第i行中，数字j是否可用blockij：第i区域中，数字j是否可用,col,row,block,例题4扩充 靶形数独,每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。完成一个给定的数独，而且要争取更高的总分数。总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。,例题4扩充 靶形数独,与数独类似，难点在于需要找出所有的填充方案。剪枝？设已经找到最大分数为max当前已经填充的格子分数和为cur未填充的格子最大可能分数和为rest若cur+restmax则剪枝操作代价太大！,例题4扩充 靶形数独
13、,搜索顺序分值越大的越先搜索？按照分值大小来搜索，目的是为了依据分数来剪枝，但剪枝的操作代价太大反正都必须一搜到底，分值大小对减少搜索没有意义可选择的数字越少越先搜索可大大减少搜索树的分支,例题4扩充 靶形数独,搜索顺序数组sziji：081，待填的空白格子数j：0、1，空白格子坐标 2，格子可填数字的数量搜索顺序数组排序（一边排序一边更新k值）设待排序区间为szaszb查找最小的szi,2，szisza 在sza+1szb中查找与sza在同一列或同一行或同一区域的格子szj，将szj,2值减1,例题4扩充 靶形数独,其它优化采用位运算来减少判断操作：把每行、每列、每个区域可填的数用二进制集合
14、表示，求3者交集来快速确定可填数字预先存储各个分值的格子位置，在计算总分时相同分值的数字相加求和，再将和与分值相乘，最后将乘积相加，减少乘法运算,例题5 生日蛋糕,要制作一个体积为N*的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1Ri+1且HiHi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q=S*请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）。数据规模：N=10000；M=20,例题5 生日蛋糕,条件1：RiRi+1（iHi+1（im)条件3：V=(*Ri2*
15、Hi)=*(Ri2*Hi)=*nn=(Ri2*Hi)Q=*R12+(2*Ri*Hi)=*(R12+2(Ri*Hi)=*SS=R12+2(Ri*Hi)在满足条件1、2、3的情况下求最小S,例题5 生日蛋糕,基本思路尝试第一层蛋糕的大小为R1、H1根据第一层蛋糕的大小尝试第二层蛋糕的大小：R2R1，H2H1依此类推，逐层尝试在尝试中查看是否符合条件 是否做到了m层 是否最终体积为0 是否当前面积最小若不成立，则继续尝试做下一层蛋糕。若成立，检查，若成立则保留当前最优值，否则返回上一层，重做蛋糕,例题5 生日蛋糕,搜索对象：每一层的Ri、Hi状态：dfs(i,Ri,Hi,Vi,Si)i：第i层蛋糕R
16、i：第i层蛋糕的半径Hi：第i层蛋糕的高度Vi：做完第i层后剩余的蛋糕体积Si：做完第i层后蛋糕的表面积转移：dfs(i,Ri,Hi,Vi,Si)dfs(i+1,Ri+1,Hi+1,Vi+1,Si+1)Ri+1：Ri1MiHi+1：Hi1MiVi+1：ViRi+12*Hi+1Si+1：Si+2*Ri+1*Hi+1边界：i=M,例题5 生日蛋糕,dfs(i,Ri,Hi,Si,Vi)对每层蛋糕进行搜索if(im)then for Ri+1Ri1 downto Mi for Hi+1Hi1 downto Mi Si+1Si+2*Ri+1*Hi+1 Vi+1Vi-Ri+1*Ri+1*Hi+1 dfs(
17、i+1,Ri+1,Hi+1,Si+1,Vi+1)else if(Vi=0)then 更新最优值,例题5 生日蛋糕,主程序：枚举所有的初始状态（第一层蛋糕的大小）for R1m to sqrt(n)/假设 H1=1，只做1层 for H1n div(R1*R1)downto m S1=2*R1*H1+R1*R1 V1=nR1*R1*H1 dfs(1,R1,H1,S1,V1),例题5 生日蛋糕,剪枝1：因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们就可以加入如下剪枝条件:if 当前的表面积+余下的側面积当前最优值 then exit设已经做了i层蛋糕,则还需做m-i层，设：Si：第i
18、层蛋糕的侧面积；FSi：余下的侧面积 因为:2Vi=2Ri+12*Hi+1+.+2Rm2*Hm=Ri+1*Si+1+.+Rm*Sm Ri+1*(Si+1+.+Sm)=Ri+1*FSi 所以:FSi2Vi/Ri+1 因此剪枝条件为：if Si+FSi=2*Vi/Ri+1当前最优值 then exit,例题5 生日蛋糕,剪枝2：如果剩下的蛋糕材料太少，不能保证做到m层,那么没有必要继续往下做了，设：第m层半径和高都为1，Rm=Hm=1第m-1层半径和高都为2，Rm-1=Hm-1=2第i+1层半径和高都为i,Ri=Hi=mi 这样，余下的m-i层的最小体积为：MINi=k3(k=1.mi)剪枝条件为
19、：if ViMINi then exit,例题5 生日蛋糕,剪枝2：MINi=k3(k=1.mi)初始化剪枝MINi条件MINm=0for im-1 to 1 do MINi=MINi+1+(m-i)*(m-i)*(m-i),例题5 生日蛋糕,剪枝3：如果剩下的蛋糕材料太多，以最大的方式做完m层,仍有材料剩余,那么没有必要继续往下做了，设：第i+1层半径和高为：Ri+1=Ri1，Hi+1=Hi1第i+2层半径和高为：Ri+2=Ri2，Hi+2=Hi2第层半径和高为：Rm=Rim+i，Hm=Him+i这样，余下的mi层的最大体积为MAXi,R,H=(Rjj)2*(Hjj)(j=1.Mi)因此，剪
20、枝条件为：if(ViMAXi,R,H)then exit,例题5 生日蛋糕,剪枝3：MAXi,R,H=(Rjj)2*(Hjj)(j=1.Mi)初始化剪枝MAXi,R,H条件for R1 to sqrt(n)for H1 to n/(R*R)MAXm,R,H0 for im-1 downto 1 MAXi,R,HMAXi+1,R,H+(R-m+i)2*(H-m+i);,例题5 生日蛋糕,最优化剪枝 剪枝1：if Si+FSi=2*Vi/Ri+1 当前最优值 then exit可行性剪枝 剪枝2：if ViMAXi,R,H then exit,dfs(i,Ri,Hi,Si,Vi)if(im)then for Ri+1Ri 1 downto Mi for Hi+1Hi 1 downto Mi Si+1Si+2*Ri+1*Hi+1 Vi+1Vi-Ri+1*Ri+1*Hi+1 dfs(i+1,Ri+1,Hi+1,Si+1,Vi+1)else if(Vi=0)then 更新最优值,min(Vi/(Ri+1*Ri+1),Hi-1),
