通用的解题法市公开课获奖课件省名师优质课赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,“通用解题法”,第5章 回溯法,1/35,回溯法,有许多问题，当需要找出它解集或者要求回答什么解是满足一些约束条件最正确解时，往往能够使用回溯法。,回溯法基本做法就是搜索。有时能够被认为是一个组织得,井井有条,，能防止无须要搜索,穷举式搜索,。,回溯法适合用于求解一些,组合数相当大,问题。,2/35,回溯法在问题解空间树中，按深度优先策略，从根结点出发搜索解空间树。,算法搜索至解空间树任意一点时，先判断该结点是否包含问题解。假如必定不包含，则跳过对该结点为根子树搜索，逐层向其祖先结点回溯；,不然，进入该子树，继续按深度优先策略搜索。,回溯法,3/35,了解回溯法深度优先搜索策略。,掌握用回溯法解题算法框架,（,1,）递归回溯最优子结构性质,（,2,）迭代回溯贪心选择性质,（,3,）子集树算法框架,（,4,）排列树算法框架,学习关键点,4/35,（,1,）装载问题；,（,2,）批处理作业调度；,（,3,）符号三角形问题,（,4,）,n,后问题；,（,5,）,0-1,背包问题；,（,6,）最大团问题；,应用范例,（,7,）图,m,着色问题,（,8,）旅行售货员问题,（,9,）圆排列问题,（,10,）电路板排列问题,（,11,）连续邮资问题,5/35,问题解空间,问题解向量：回溯法希望一个问题解能够表示成一个,n,元式,(,x,1,x,2,x,n),形式。,显约束：对分量,xi,取值限定。,隐约束：为满足问题解而对不一样分量之间施加约束。,解空间：对于问题一个实例，解向量满足显式约束条件全部多元组，组成了该实例一个解空间。,注意：同一个问题能够有各种表示，有些表示方法更简单，所需表示状态空间更小（存放量少，搜索方法简单）,n=3,时,0-1,背包问题用完全二叉树表示解空间,6/35,生成问题状态基本方法,扩展结点,:,一个正在产生儿子结点称为扩展结点,活结点,:,一个本身已生成但其儿子还没有全部生成节点称做活结点,死结点,:,一个全部儿子已经产生结点称做死结点,深度优先问题状态生成法：假如对一个扩展结点,R,，一旦产生了它一个儿子,C,，就把,C,当做新扩展结点。在完成对子树,C,（以,C,为根子树）穷尽搜索之后，将,R,重新变成扩展结点，继续生成,R,下一个儿子（假如存在）,宽度优先问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点,回溯法：为了防止生成那些不可能产生最正确解问题状态，要不停地利用限界函数,(bounding function),来处死那些实际上不可能产生所需解活结点，以降低问题计算量。,含有限界函数深度优先生成法称为回溯法,7/35,回溯法基本思想,(1),针对所给问题，定义问题解空间；,(2),确定易于搜索解空间结构；,(3),以深度优先方式搜索解空间，并在搜索过程中用剪枝函数防止无效搜索。,惯用剪枝函数：,用约束函数在扩展结点处剪去不满足约束子树；,用限界函数剪去得不到最优解子树。,用回溯法解题一个显著特征是在搜索过程中动态产生问题解空间。在任何时刻，算法只保留从根结点到当前扩展结点路径。假如解空间树中从根结点到叶结点最长路径长度为,h(n),，则回溯法所需计算空间通常为,O(h(n),。而显式地存放整个解空间则需要,O(2,h(n),),或,O(h(n)!),内存空间。,8/35,举例一,在选择装入背包物品时，对每种物品,i,只有,2,种选择，即装入背包或不装入背包。不能将物品,i,装入背包屡次，也不能只装入部分物品,i,。,给定,3,种物品和一个背包。物品,i,重量分别是,W,16,15,15,，其价值分别为,P,45,25,25,，背包容量为,C,30,。应怎样选择装入背包物品，使得装入背包中物品总价值最大,?,0-1,背包问题：,9/35,举例一,n=3,时,0-1,背包问题用完全二叉树表示解空间,10/35,举例二,在选择路线时，不能走回头路。,某售货员要到,3,个城市去推销商品，已知各城市之间旅程（或者旅费）。他要选定一条从驻地出发，经过每一个城市一遍，最终回到驻地路线，使总旅程（或者总旅费）最小。数据如图,5-2,。,旅行售货员问题：,11/35,举例二,旅行售货员问题解空间树,12/35,递归回溯,回溯法对解空间作深度优先搜索，所以，在普通情况下用递归方法实现回溯法。,void,backtrack,(int t),if,(tn),output,(x);,else,for,(int i=,f,(n,t);i0),if,(,f,(n,t)=,g,(n,t),for(int i=,f,(n,t);in)output(x);,else,for(int i=0;in)output(x);,else,for(int i=t;i n)/,抵达叶结点,更新最优解,bestx,bestw;return;,r-=wi;,if,(cw+wi bestw),xi=0;/,搜索右子树,backtrack,(i+1);,r+=wi;,17/35,批处理作业调度,给定,n,个作业集合,J,1,J,2,J,n,。每个作业必须先由机器,1,处理，然后由机器,2,处理。作业,J,i,需要机器,j,处理时间为,t,ji,。对于一个确定作业调度，设,F,ji,是作业,i,在机器,j,上完成处理时间。全部作业在机器,2,上完成处理时间和称为该作业调度完成时间和。,批处理作业调度问题要求对于给定,n,个作业，制订最正确作业调度方案，使其完成时间和到达最小。,t,ji,机器,1,机器,2,作业,1,2,1,作业,2,3,1,作业,3,2,3,这,3,个作业,6,种可能调度方案是,1,2,3,；,1,3,2,；,2,1,3,；,2,3,1,；,3,1,2,；,3,2,1,；它们所对应完成时间和分别是,19,，,18,，,20,，,21,，,19,，,19,。易见，最正确调度方案是,1,3,2,，其完成时间和为,18,。,18/35,批处理作业调度,解空间：排列树,void Flowshop:,Backtrack,(int i),if(i n),for(int j=1;j=n;j+),bestxj=xj;,bestf=f;,else,for(int j=i;j f1)?f2i-1:f1)+Mxj2;,f+=f2i;,if(f half)|(t*(t-1)/2-counthalf)return;,if(tn)sum+;,else,for(int i=0;i2;i+),p1t=i;,count+=i;,for(int j=2;j=t;j+),pjt-j+1=pj-1t-j+1pj-1t-j+2;,count+=pjt-j+1;,Backtrack(t+1);,for(int j=2;j=t;j+),count-=pjt-j+1;,count-=i;,+-+-+,+-+,-+-,-+-,-+-,-,+,复杂度分析,计算可行性约束需要O(n)时间，在最坏情况下有 O(2,n,)个结点需要计算可行性约束，故解符号三角形问题回溯算法所需计算时间为 O(n2,n,)。,符号三角形问题,21/35,n,后问题,在,nn,格棋盘上放置彼此不受攻击,n,个皇后。按照国际象棋规则，皇后能够攻击与之处于同一行或同一列或同一斜线上棋子。,n,后问题等价于在,nn,格棋盘上放置,n,个皇后，任何,2,个皇后不放在同一行或同一列或同一斜线上。,1 2 3 4 5 6 7 8,1,2,3,4,5,6,7,8,Q,Q,Q,Q,Q,Q,Q,Q,22/35,解向量：,(x,1,x,2,x,n,),显约束：,x,i,=1,2,n,隐约束：,1),不一样列：,x,i,x,j,2),不处于同一正、反对角线：,|i-j|,|x,i,-x,j,|,bool Queen:,Place,(int k),for(int j=1;jn)sum+;,else,for(int i=1;i=n;i+),xt=i;,if(Place(t)Backtrack(t+1);,n,后问题,23/35,0-1背包问题,解空间：子集树,可行性约束函数：,上界函数：,template,Typep Knap:,Bound,(int i),/,计算上界,Typew cleft=c-cw;/,剩下容量,Typep b=cp;,/,以物品单位重量价值递减序装入物品,while(i=n&wi=cleft),cleft-=wi;,b+=pi;,i+;,/,装满背包,if(i n)/,抵达叶结点,for(int j=1;j=n;j+)bestxj=xj;,bestn=cn;return;,/,检验顶点,i,与当前团连接,int OK=1;,for(int j=1;j bestn)/,进入右子树,xi=0;,Backtrack(i+1);,复杂度分析,最大团问题回溯算法,backtrack,所需计算时间显然为,O(n2,n,),。,1,2,4,5,3,26/35,图m着色问题,给定无向连通图,G,和,m,种不一样颜色。用这些颜色为图,G,各顶点着色，每个顶点着一个颜色。是否有一个着色法使,G,中每条边,2,个顶点着不一样颜色。这个问题是图,m,可着色判定问题。若一个图最少需要,m,种颜色才能使图中每条边连接,2,个顶点着不一样颜色，则称这个数,m,为该图色数。求一个图色数,m,问题称为图,m,可着色优化问题,。,27/35,解向量：,(x,1,x,2,x,n,),表示顶点,i,所着颜色,xi,可行性约束函数：顶点,i,与已着色相邻顶点颜色不重复,。,图m着色问题,void Color:,Backtrack,(int t),if(tn),sum+;,for(int i=1;i=n;i+),cout xi ;,cout endl;,else,for(int i=1;i=m;i+),xt=i;,if(Ok(t)Backtrack(t+1);,bool Color:,Ok,(int k),/,检验颜色可用性,for(int j=1;j=n;j+),if(akj=1),return true;,复杂度分析,图,m,可着色问题解空间树中内结点个数是,对于每一个内结点，在最坏情况下，用,ok,检验当前扩展结点每一个儿子所对应颜色可用性需耗时,O(mn),。所以，回溯法总时间花费是,28/35,旅行售货员问题,解空间：排列树,template,void Traveling:,Backtrack,(int i),if(i=n),if(axn-1xn!=NoEdge&axn1!=NoEdge&,(cc+axn-1xn+axn1 bestc|bestc=NoEdge),for(int j=1;j=n;j+)bestxj=xj;,bestc=cc+axn-1xn+axn1;,else,for(int j=i;j=n;j+),/,是否可进入,xj,子树,?,if(axi-1xj!=NoEdge&,(cc+axi-1xi bestc|bestc=NoEdge),/,搜索子树,Swap(xi,xj);,cc+=axi-1xi;,Backtrack(i+1);,cc-=axi-1xi;,Swap(xi,xj);,复杂度分析,算法,backtrack,在最坏情况下可能需要更新当前最优解,O(n-1)!),次，每次更新,bestx,需计算时间,O(n),，从而整个算法计算时间复杂性为,O(n!),。,29/35,圆排列问题,给定,n,个大小不等圆,c1,c2,cn,，现要将这,n,个圆排进一个矩形框中，且要求各圆与矩形框底边相切。圆排列问题要求从,n,个圆全部排列中找出有最小长度圆排列。比如，当,n=3,，且所给,3,个圆半径分别为,1,，,1,，,2,时，这,3,个圆最小长度圆排列如图所表示。其最小长度为,30/35,圆排列问题,float Circle:,Center,(int t),/,计算当前所选择圆圆心横坐标,float temp=0;,for(int j=1;jtemp)temp=valuex;,return temp;,void Circle:,Compute,(void),/,计算当前圆排列长度,float low=0,high=0;,for(int i=1;i=n;i+),if(xi-rihigh)high=xi+ri;,if(high-lown)Compute();,else,for(int j=t;j=n;j+),Swap(rt,rj);,float centerx=Center(t);,if(centerx+rt+r1min)/,下界约束,xt=centerx;,Backtrack(t+1);,Swap(rt,rj);,复杂度分析,因为算法,backtrack,在最坏情况下可能需要计算,O(n!),次当前圆排列长度，每次计算需,O(n),计算时间，从而整个算法计算时间复杂性为,O(n+1)!),上述算法还有许多改进余地。例如，象1,2,n-1,n和n,n-1,2,1这种互为镜像排列具有相同圆排列长度，只计算一个就够了，可降低约一半计算量。其次，如果所给n个圆中有k个圆有相同半径，则这k个圆产生k!个完全相同圆排列，只计算一个就够了。,31/35,连续邮资问题,假设国家发行了,n,种不一样面值邮票，而且要求每张信封上最多只允许贴,m,张邮票。连续邮资问题要求对于给定,n,和,m,值，给出邮票面值最正确设计，在,1,张信封上可贴出从邮资,1,开始，增量为,1,最大连续邮资区间,比如，当,n=5,和,m=4,时，面值为,(1,3,11,15,32)5,种邮票能够贴出邮资最大连续邮资区间是,1,到,70,。,32/35,连续邮资问题,解向量：用,n,元组,x1:n,表示,n,种不一样邮票面值，并约定它们从小到大排列。,x1=1,是唯一选择。,可行性约束函数：已选定,x1:i-1,，最大连续邮资区间是,1:r,，接下来,xi,可取值范围是,xi-1+1:r+1,。,怎样确定,r,值？,计算,X1:i,最大连续邮资区间在本算法中被频繁使用到，所以势必要找到一个高效方法。考虑到直接递归求解复杂度太高，我们不妨尝试计算用不超出,m,张面值为,x1:i,邮票贴出邮资,k,所需最少邮票数,yk,。经过,yk,能够很快推出,r,值。实际上，,yk,能够经过递推在,O(n),时间内处理：,for,(int j=0;j=xi-2*(m-1);j+),if,(yjm),for,(int k=1;k=m-yj;k+),if,(yj+kyj+xi-1*k)yj+xi-1*k=yj+k;,while,(yrmaxint)r+;,33/35,回溯法效率分析,经过前面详细实例讨论轻易看出，回溯算法效率在很大程度上依赖于以下原因：,(1),产生,xk,时间；,(2),满足显约束,xk,值个数；,(3),计算约束函数,constraint,时间；,(4),计算上界函数,bound,时间；,(5),满足约束函数和上界函数约束全部,xk,个数。,好约束函数能显著地降低所生成结点数。但这么约束函数往往计算量较大。所以，,在选择约束函数时通常存在生成结点数与约束函数计算量之间折衷,34/35,重排原理,对于许多问题而言，在搜索试探时选取,xi,值次序是任意。,在其它条件相当前提下，让可取值最少,xi,优先,。从图中关于同一问题,2,棵不一样解空间树，能够体会到这种策略潜力。,(a),(b),图,(a),中，从第,1,层剪去,1,棵子树，则从全部应该考虑,3,元组中一次消去,12,个,3,元组。,对于图,(b),，即使一样从第,1,层剪去,1,棵子树，却只从应该考虑,3,元组中消去,8,个,3,元组。前者效果显著比后者好。,35/35,