ch1-5 回溯法

算法分析与设计,单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,单击此处编辑母版标题样式,算法分析与设计,清华大学出版社,王晓东等,编著,任课教师：向金海,联系电话：,62193562,，,87282492,（,O,）,Email:,jimmy_xiang,jimmy_xiang,第四章 回溯法,华中农业大学理学院,2007,，,9,7,主要内容,:,1,）装载问题；,2,）批处理作业调度；,3,）符号三角形问题,4,）,n,后问题；,5,）,0-1,背包问题；,6,）最大团问题；,7,）图的,m,着色问题,8,）旅行售货员问题,9,）圆排列问题,10,）电路板排列问题,11,）连续邮资问题,学习要点,理解回溯法的深度优先搜索策略,掌握用回溯法解题的算法框架,1,）递归回溯最优子结构性质,2,）迭代回溯贪心选择性质,3,）子集树算法框架,4,）排列树算法框架,引言,回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。,回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,5.1,回溯法的算法框架,本节介绍回溯法算法框架的有关问题：,一、问题的解空间,二、回溯法的基本思想,三、递归回溯,四、迭代回溯,五、子集树与排列树,一、问题的解空间,应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个,(,最优,),解。,问题的解向量：回溯法希望一个问题的解能够表示成一个,n,元式,(x1,x2,xn,),的形式。,显约束：对分量,xi,的取值限定。,隐约束：为满足问题的解而对不同分量之间施加的约束。,解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。,例如，对于有,n,种可选物品的,0-1,背包问题，其解空间由长度为,n,的,0-1,向量组成。,n=3,时的,0-1,背包问题用完全二叉树表示的解空间,二、回溯法的基本思想,回溯法的基本步骤：,(1),针对所给问题，定义问题的解空间；,(2),确定易于搜索的解空间结构；,(3),以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,常用剪枝函数：,用约束函数在扩展结点处剪去不满足约束的子树；,用限界函数剪去得不到最优解的子树。,二、回溯法的基本思想,关于复杂性：,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为,h(n,),，则回溯法所需的计算空间通常为,O(h(n,),。而显式地存储整个解空间则需要,O(2h(n),或,O(h(n,)!),内存空间。,生成问题状态的基本方法,扩展结点,：一个正在产生儿子的结点称为扩展结点,活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点,死结点,：一个所有儿子已经产生的结点称做死结点,深度优先的问题状态生成法：如果对一个扩展结点,R,，一旦产生了它的一个儿子,C,，就把,C,当做新的扩展结点。在完成对子树,C,（以,C,为根的子树）的穷尽搜索之后，将,R,重新变成扩展结点，继续生成,R,的下一个儿子（如果存在）,宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点,生成问题状态的基本方法,回溯法,：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数,(bounding function),来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。,示例,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,示例,1 0-1,背包问题,再扩展,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,示例,1 0-1,背包问题,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,，,V=25,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=0;i n) /,到达叶结点,更新最优解,bestx,bestw;return,;,r -= wi;,if (,cw,+ wi ,bestw,) ,xi = 0; /,搜索右子树,backtrack(i + 1); ,r += wi;,批处理作业调度,给定,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,。,批处理作业调度,解空间：排列树,private static void,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,),。,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,解向量：,(x,1, x,2, ,x,n,),显约束：,x,i,=1,2, ,n,隐约束：,1),不同列：,x,i,x,j,2),不处于同一正、反对角线：,|,i-j|,|x,i,-x,j,|,n,后问题,private static,boolean,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);,0-1背包问题,解空间：子集树,可行性约束函数：,上界函数：,private static double,bound,(int,i),/,计算上界,double cleft = c -,cw,; /,剩余容量,double bound = cp;,/,以物品单位重量价值递减序装入物品,while,(i = n & wi = cleft),cleft -= wi;,bound += pi;,i+;,/,装满背包,if (i n) /,到达叶结点,for (,int,j = 1; j = n; j+),bestxj, = xj;,bestn,=,cn,; return; ,/,检查顶点,i,与当前团的连接,boolean,ok = true;,for (,int,j = 1; j ,bestn,) /,进入右子树,xi = 0;,backtrack(i + 1); ,复杂度分析,最大团问题的回溯算法,backtrack,所需的计算时间显然为,O(n2,n,),。,1,2,4,5,3,进一步改进算法的建议,选择合适的搜索顺序,，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。,定义,Si=v,i,v,i+1,.,v,n,，依次求出,S,n,S,n-1,.,S,1,的解。从而得到一个,更精确的上界函数,，若,cn+S,i,n) sum+;,else,for,(,int,i=1;i=m;i+) ,xt=i;,if,(,ok,(t),backtrack,(t+1);,private static,boolean,ok,(int,k),/,检查颜色可用性,for,(,int,j=1;j=n;j+),if,(akj & (xj=xk),return,false;,return,true;,复杂度分析,图,m,可着色问题的解空间树中内结点个数是,对于每一个内结点，在最坏情况下，用,ok,检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时,O(mn,),。因此，回溯法总的时间耗费是,思考：图的,m,着色问题与图的最大团问题有何关系，你能否利用这个关系改进最大团问题的上界？,旅行售货员问题,解空间：排列树,private static void,backtrack,(int,i),if,(i = n) ,if,(axn - 1xn Float.MAX_VALUE & axn1 Float.MAX_VALUE &,(,bestc,= Float.MAX_VALUE | cc+axn - 1xn+axn1,bestc,) ,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 Float.MAX_VALUE &,(,bestc,= Float.MAX_VALUE | cc+axi - 1xj,bestc,) /,搜索子树,MyMath.,swap,(x, i, j);,cc+=axi - 1xi;,backtrack,(i + 1);,cc-=axi - 1xi;,MyMath.,swap,(x, i, j);,复杂度分析,算法,backtrack,在最坏情况下可能需要更新当前最优解,O(n-1)!),次，每次更新,bestx,需计算时间,O(n),，从而整个算法的计算时间复杂性为,O(n!),。,圆排列问题,给定,n,个大小不等的圆,c1,c2,cn,，现要将这,n,个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从,n,个圆的所有排列中找出有最小长度的圆排列。例如，当,n=3,，且所给的,3,个圆的半径分别为,1,，,1,，,2,时，这,3,个圆的最小长度的圆排列如图所示。其最小长度为,圆排列问题,private static float,center(int,t),/,计算当前所选择圆的圆心横坐标,float temp=0;,for (,int,j=1;jtemp) temp=,valuex,;,return temp;,private static void compute(),/,计算当前圆排列的长度,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+) ,MyMath.swap(r, t, j);,float,centerx,=center(t);,if (centerx+rt+r1min) ,/,下界约束,xt=,centerx,;,backtrack(t+1);,MyMath.swap(r, t, j);,复杂度分析,由于算法,backtrack,在最坏情况下可能需要计算,O(n!),次当前圆排列长度，每次计算需,O(n),计算时间，从而整个算法的计算时间复杂性为,O(n+1)!),上述算法尚有许多改进的余地。例如，象,1,2,n-1,n,和,n,n-1, ,2,1,这种互为镜像的排列具有相同的圆排列长度，只计算一个就够了，可减少约一半的计算量。另一方面，如果所给的,n,个圆中有,k,个圆有相同的半径，则这,k,个圆产生的,k!,个完全相同的圆排列，只计算一个就够了。,连续邮资问题,假设国家发行了,n,种不同面值的邮票，并且规定每张信封上最多只允许贴,m,张邮票。连续邮资问题要求对于给定的,n,和,m,的值，给出邮票面值的最佳设计，在,1,张信封上可贴出从邮资,1,开始，增量为,1,的最大连续邮资区间。,例如，当,n=5,和,m=4,时，面值为,(1,3,11,15,32),的,5,种邮票可以贴出邮资的最大连续邮资区间是,1,到,70,。,连续邮资问题,解向量：用,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,(yr,maxint,) r+;,5.12,连续邮资问题,本节要点,回顾回溯法的基本思想,连续邮资问题描述,问题分析,算法设计,一、回溯法的基本思想,1,、确定问题的解空间,子集树问题：装载问题、符号三角形问题、,0-1,背包问题、最大团问题,排列树问题：批处理作业调度、,n,后问题、旅行售货员问题、圆排列问题、电路板排列问题,其他：图的,m,着色问题,2,、找出适当的剪枝函数,约束函数,限界函数,3,、以深度优先的方式搜索解空间,递归回溯,迭代回溯,二、问题描述,假设国家发行了,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,。,三、问题分析,基本思路：搜索所有可行解，找出最大连续邮资区间的方案,解向量：用,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+;,四、算法设计,P155-156,5.13,回溯法的效率分析,本节要点：,一、影响回溯算法效率的因素,通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：,(1),产生,xk,的时间；,(2),满足显约束的,xk,值的个数；,(3),计算约束函数,constraint,的时间；,(4),计算上界函数,bound,的时间；,(5),满足约束函数和上界函数约束的所有,xk,的个数。,好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。,二、重排原理,对于许多问题而言，在搜索试探时选取,xi,的值顺序是任意的。在其它条件相当的前提下，让可取值最少的,xi,优先。从右图中关于同一问题的,2,棵不同解空间树，可以体会到这种策略的潜力。,图,(a),中，从第,1,层剪去,1,棵子树，则从所有应当考虑的分支中一次消去,12,个分支。对于图,(b),，虽然同样从第,1,层剪去,1,棵子树，却只从应当考虑的分支中消去,8,个分支。前者的效果明显比后者好。,(a),(b),三、回溯法的效率,解空间的结构已经选定，影响回溯法效率的前三个因素就可以确定，只剩下生成结点的数目是可变的，它将随问题的具体内容及结点的不同生成方式而变动。即使对同一问题的不同实例，回溯法所产生的结点数也会有很大变化。对于一个实例，回溯法可能只产生,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),四、概率方法,对于一个具体的问题来说，回溯法的有效性往往就体现在当问题实例的规模,n,较大时，它能够用很少的时间就求出问题的解。而对于一个问题的具体实例我们又很难预测回溯法的算法行为。特别是我们很难估计出回溯法在解这一具体事例时所产生的结点数，这是分析回溯法效率的主要困难。,下面我们介绍一个概率算法，用于克服这一困难：,1,、基本思想,2,、估算,m,3,、一个实例：,8,后问题,1,、基本思想,当应用回溯法解某一具体问题的具体实例,I,时，可用蒙特卡罗方法来估算回溯法将要产生的结点数目。,该方法的基本思想是：在解空间树上产生一条随机的路径，然后沿此路径估算满足约束条件的结点总数,m,：,设,x,是所产生的随机路径上的一个结点，且位于解空间树的第,i,层上；,对于,x,的所有儿子结点用约束函数检测出满足条件的结点数目,m,i,；,路径上下一个结点是从,x,的这,m,i,个孩子中随机选取的；,这条路径一直延伸到一个叶结点或没有满足条件的子结点为止；,通过这些,m,i,的值，就可以估算出解空间树中满足约束条件的结点总数,m,。,1,、基本思想,在回溯法求解问题的所有解时，这个数特别有用，因为在这种情况下，解空间中所有满足条件的结点都必须生成；若只要求用回溯法找出问题的一个解，则所生成的结点数一般只是这,m,个结点中的一小部分，此时用,m,来估计回溯法生成的结点数就过于保守。,2,、估算,m,估算,m,的公式：,Thank you!,