回溯法 - 山东师范大学.ppt

单击此处编辑标题,单击此处编辑文本,第二级,第三级,第四级,第五级,*,算法设计与分析,山东师范大学信息科学与工程学院软件工程研究所,徐连诚,E-Mail,：,lchxu,2006,年,11,月,20,日,第五章 回溯法,学习要点,理解回溯法的深度优先搜索策略,掌握用回溯法解题的算法框架,1,）递归回溯最优子结构性质,2,）迭代回溯贪心选择性质,3,）子集树算法框架,4,）排列树算法框架,通过应用范例学习回溯法的设计策略,1,）装载问题；,2,）批处理作业调度；,3,）符号三角形问题,4,）,n,后问题；,5,）,0-1,背包问题；,6,）最大团问题；,7,）图的,m,着色问题,8,）旅行售货员问题,9,）圆排列问题,10,）电路板排列问题,11,）连续邮资问题,2,引言,有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。,回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。,回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,3,5.1,回溯法的算法框架,本节介绍回溯法算法框架的有关问题：,一、问题的解空间,二、回溯法的基本思想,三、递归回溯,四、迭代回溯,五、子集树与排列树,4,一、问题的解空间,应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个,(,最优,),解。,问题的解向量：回溯法希望一个问题的解能够表示成一个,n,元式,(x1,x2,xn,),的形式。,显约束：对分量,xi,的取值限定。,隐约束：为满足问题的解而对不同分量之间施加的约束。,解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单例如，对于有,n,种可选物品的,0-1,背包问题，其解空间由长度为,n,的,0-1,向量组成。,n=3,时的,0-1,背包问题用完全二叉树表示的解空间,5,二、回溯法的基本思想,回溯法的基本步骤：,(1),针对所给问题，定义问题的解空间；,(2),确定易于搜索的解空间结构；,(3),以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,常用剪枝函数：,用约束函数在扩展结点处剪去不满足约束的子树；,用限界函数剪去得不到最优解的子树。,关于复杂性：,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为,h(n,),，则回溯法所需的计算空间通常为,O(h(n,),。而显式地存储整个解空间则需要,O(2h(n),或,O(h(n,)!),内存空间。,6,生成问题状态的基本方法,扩展结点：一个正在产生儿子的结点称为扩展结点,活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点,死结点：一个所有儿子已经产生的结点称做死结点,深度优先的问题状态生成法：如果对一个扩展结点,R,，一旦产生了它的一个儿子,C,，就把,C,当做新的扩展结点。在完成对子树,C,（以,C,为根的子树）的穷尽搜索之后，将,R,重新变成扩展结点，继续生成,R,的下一个儿子（如果存在）,宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点,回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数,(bounding function),来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。,7,示例,1 0-1,背包问题,n=3,C=30,w=16,15,15,v=45,25,25,开,始时，,C,r,=C=30,，,V=0,，,A,为唯一活结点，也是当前扩展结点,扩展,A,，先到达,B,结点,C,r,=C,r,-w,1,=14,，,V=V+v,1,=45,此时,A,、,B,为活结点，,B,成为当前扩展结点,扩展,B,，先到达,D,C,r,w,2,，,D,导致一个不可行解，回溯到,B,再扩展,B,到达,E,E,可行，此时,A,、,B,、,E,是活结点，,E,成为新的扩展结点,扩展,E,，先到达,J,C,r,45,，皆得到一个可行解,x=(0,1,1),，,V=50,L,不可扩展，成为死结点，返回到,F,再扩展,F,到达,M,M,是叶结点，且,2550,，不是最优解,M,不可扩展，成为死结点，返回到,F,F,没有可扩展结点，成为死结点，返回到,C,再扩展,C,到达,G,C,r,=30,，,V=0,，活结点为,A,、,C,、,G,，,G,为当前扩展结点,扩展,G,，先到达,N,，,N,是叶结点，且,2550,，不是最优解，又,N,不可扩展，返回到,G,再扩展,G,到达,O,，,O,是叶结点，且,050,，不是最优解，又,O,不可扩展，返回到,G,G,没有可扩展结点，成为死结点，返回到,C,C,没有可扩展结点，成为死结点，返回到,A,A,没有可扩展结点，成为死结点，算法结束，最优解,X=(0,1,1),，最优值,V=50,A,C,r,=C=30,，,V=0,B,w,1,=16,，,v,1,=45,C,r,=14,，,V=45,C,C,r,=30,，,V=0,D,C,r,w,2,不可行解,J,C,r,45,x=(0,1,1),F,w,2,=15,，,v,2,=25,C,r,=15,，,V25,M,25n),output(x,);,else,for(,int,i=,f(n,t);i,0),if(,f(n,t,)=,g(n,t,),for(,int,i=,f(n,t);i,n),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,5.3,批处理作业调度,一、问题描述,二、实例分析,三算法描述,18,一、问题描述,给定,n,个作业的集合,J1,J2,Jn,。每个作业必须先由机器,1,处理，然后由机器,2,处理。作业,Ji,需要机器,j,的处理时间为,tji,。对于一个确定的作业调度，设,Fji,是作业,i,在机器,j,上完成处理的时间。所有作业在机器,2,上完成处理的时间和称为该作业调度的完成时间和。,批处理作业调度问题要求对于给定的,n,个作业，制定最佳作业调度方案，使其完成时间和达到最小。,19,二、实例分析,这,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,。,t,ji,机器,1,机器,2,作业,1,2,1,作业,2,3,1,作业,3,2,3,20,三、算法描述,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;,25,5.5 n,后问题,一、问题描述,二、问题分析,三、算法描述,26,一、问题描述,在,nn,格的棋盘上放置彼此不受攻击的,n,个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。,n,后问题等价于在,nn,格的棋盘上放置,n,个皇后，任何,2,个皇后不放在同一行或同一列或同一斜线上。,1,Q,2,Q,3,Q,4,Q,5,Q,6,Q,7,Q,8,Q,1,2,3,4,5,6,7,8,27,二、问题分析,解向量：,(,x,1,x,2,x,n,),显约束：,x,i,=1,2,n,隐约束：,1),不同列：,x,i,x,j,2),不处于同一正、反对角线：,|,i,-,j,|,|,x,i,-,x,j,|,28,三、算法描述,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);,29,5.6 0-1,背包问题,解空间：子集树,可行性约束函数：,w,i,x,i,C,上界函数：,Bound(),算法：略,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;,int,OK=1;/,检查顶点,i,与当前团的连接,for(,int,j=1;j,bestn,)/,进入右子树,xi,=0;,Backtrack(i+1);,34,四、进一步改进,选择合适的搜索顺序，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。,定义,S,i,=,v,i,v,i,+1,.,v,n,，依次求出,S,n,S,n,-1,.,S,1,的解。从而得到一个更精确的上界函数，若,cn,+,S,i,n),sum+;,for(,int,i=1;i=n;i+),cout,xi,;,cout,endl,;,else,for(,int,i1;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)&(xj=,xk,)return false;,return true;,39,四、复杂性分析,图,m,可着色问题的解空间树中内结点个数是,m,i,(0,i,n,-1),。,对于每一个内结点，在最坏情况下，用,ok,检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时,O,(,mn,),。因此，回溯法总的时间耗费是,m,i,(,mn,)=,nm,(,m,n,-1)/(,m,-1)=,O,(,nm,n,),(0,i,n,-1),40,5.9,旅行售货员问题,void,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/,是否可进入,xj,子树,?,for(,int,j=i;j=n;j+)/,搜索子树,if(axi-1xj!=,NoEdge,&(cc+axi-1xi n)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,);,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-ri,high)high=,xi+ri,;,if(high-lowmin)min=high-low;,44,三、算法改进,上述算法尚有许多改进的余地。例如，象,1,2,n-1,n,和,n,n-1,2,1,这种互为镜像的排列具有相同的圆排列长度，只计算一个就够了，可减少约一半的计算量。,另一方面，如果所给的,n,个圆中有,k,个圆有相同的半径，则这,k,个圆产生的,k!,个完全相同的圆排列，只计算一个就够了。,45,5.11,电路板排列问题,一、问题描述,二、算法设计,三、算法描述,四、复杂性分析,46,一、问题描述,设,B1,2,n,是,n,块电路板的集合。集合,L=N1,N2,Nm,是这,n,块电路板的,m,个连接块。其中每个连接块,Ni,是,B,的一个子集，且,Ni,中的电路板用一根导线连接在一起。不同的连接快可能包含相同的电路板。,设,x,是,n,块电路板的一个排列，则电路板的排列密度,Density(x,),定义为跨越相邻电路板插槽的最大连线数。,电路板排列问题要求度与给定的电路板连接条件,(,连接块,),，确定电路板的最佳排列，使其具有最小密度。,47,二、算法设计,问题空间：排列树,48,三、算法描述,P,152-154,49,四、复杂性分析,每个结点处,Backtrack,函数的计算时间：,O,m,),结点数：,O,(,n,!),总的计算时间：,O,(,mn,!),50,5.12,连续邮资问题,本节要点,回顾回溯法的基本思想,连续邮资问题描述,问题分析,算法设计,51,一、回溯法的基本思想,1,、确定问题的解空间,子集树问题：装载问题、符号三角形问题、,0-1,背包问题、最大团问题,排列树问题：批处理作业调度、,n,后问题、旅行售货员问题、圆排列问题、电路板排列问题,其他：图的,m,着色问题,2,、找出适当的剪枝函数,约束函数,限界函数,3,、以深度优先的方式搜索解空间,递归回溯,迭代回溯,52,二、问题描述,假设国家发行了,n,种不同面值的邮票，并且规定每张信封上最多只允许贴,m,张邮票。连续邮资问题要求对于给定的,n,和,m,的值，给出邮票面值的最佳设计，在,1,张信封上可贴出从邮资,1,开始，增量为,1,的最大连续邮资区间。,(NOIP99),例如，当,n=2,、,m=3,时，如果面值分别为,1,、,4,，则在,l-6,之间的每一个邮资值都能得到,(,当然还有,8,、,9,和,12),；如果面值分别为,1,、,3,，则在,1-7,之间的每一个邮资值都能得到。可以验证当,n=2,、,m=3,时，,7,就是可以得到连续的邮资最大值，面值为,l,、,3,。,又如，当,n=5,和,m=4,时，面值为,(1,3,11,15,32),的,5,种邮票可以贴出邮资的最大连续邮资区间是,1,到,70,。,53,三、问题分析,基本思路：搜索所有可行解，找出最大连续邮资区间的方案,解向量：用,n,元组,x1:n,表示,n,种不同的邮票面值，并约定它们从小到大排列。,x1=1,是唯一的选择。,可行性约束函数：已选定,x1:i-1,，最大连续邮资区间是,1r,，接下来,xi,的可取值范围是,xi-1+1r+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(,yj,m),for(,int,k=1;k=,m-yj;k,+),if(,yj+k,yj+xi-1*k)yj+xi-1*k=,yj+k,;,while(,yr,maxint,)r+;,54,四、算法设计,P,155-156,55,5.13,回溯法的效率分析,本节要点：,一、影响回溯算法效率的因素,二、重排原理,三、回溯法的效率,四、概率方法,56,一、影响回溯算法效率的因素,通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：,(1),产生,xk,的时间；,(2),满足显约束的,xk,值的个数；,(3),计算约束函数,constraint,的时间；,(4),计算上界函数,bound,的时间；,(5),满足约束函数和上界函数约束的所有,xk,的个数。,好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。,57,二、重排原理,对于许多问题而言，在搜索试探时选取,xi,的值顺序是任意的。在其它条件相当的前提下，让可取值最少的,xi,优先。从右图中关于同一问题的,2,棵不同解空间树，可以体会到这种策略的潜力。,图,(a),中，从第,1,层剪去,1,棵子树则从所有应当考虑的分支中一次消去,12,个分支。对于图,(b),，虽然同样从第,1,层剪去,1,棵子树，却只从应当考虑的分支中消去,8,个分支。前者的效果明显比后者好。,(a),(b),58,三、回溯法的效率,解空间的结构已经选定，影响回溯法效率的前三个因素就可以确定，只剩下生成结点的数目是可变的，它将随问题的具体内容及结点的不同生成方式而变动。即使对同一问题的不同实例，回溯法所产生的结点数也会有很大变化。对于一个实例，回溯法可能只产生,O(n,),个结点，而对另一个非常相近的实例，回溯法可能就会产生解空间中的所有结点。,如果解空间的结点数是,2,n,或,n!,，则在最坏情况下，回溯法的时间耗费一般为,O(p(n)2,n,),或,O(q(n)n,!),。其中,p(n,),和,q(n,),均为,n,的多项式。,n=3,，,c=30,p=(100,1,1),，,v=(30,20,20),p=(1,1,100),，,v=(20,20,30),59,四、概率方法,对于一个具体的问题来说，回溯法的有效性往往就体现在当问题实例的规模,n,较大时，它能够用很少的时间就求出问题的解。而对于一个问题的具体实例我们又很难预测回溯法的算法行为。特别是我们很难估计出回溯法在解这一具体事例时所产生的结点数，这是分析回溯法效率的主要困难。,下面我们介绍一个概率算法，用于克服这一困难：,1,、基本思想,2,、估算,m,3,、一个实例：,8,后问题,60,1,、基本思想,当应用回溯法解某一具体问题的具体实例,I,时，可用蒙特卡罗方法来估算回溯法将要产生的结点数目。,该方法的基本思想是：在解空间树上产生一条随机的路径，然后沿此路径估算满足约束条件的结点总数,m,：,设,x,是所产生的随机路径上的一个结点，且位于解空间树的第,i,层上；,对于,x,的所有儿子结点用约束函数检测出满足条件的结点数目,m,i,；,路径上下一个结点是从,x,的这,m,i,个孩子中随机选取的；,这条路径一直延伸到一个叶结点或没有满足条件的子结点为止；,通过这些,m,i,的值，就可以估算出解空间树中满足约束条件的结点总数,m,。,在回溯法求解问题的所有解时，这个数特别有用，因为在这种情况下，解空间中所有满足条件的结点都必须生成；若只要求用回溯法找出问题的一个解，则所生成的结点数一般只是这,m,个结点中的一小部分，此时用,m,来估计回溯法生成的结点数就过于保守。,61,2,、估算,m,估算,m,的公式：,62,3,、实例：,8,后问题,P159,63,课后习题,习题,5-14,，,5-16,，,5-18,，,5-27,，,5-29,64,