算法设计与分析耿国华第五章

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,第五章 回溯法,算法设计与分析,算法,设计与分析,主编 耿国华,本章内容,5,.,1,回溯法基础,5.1.1,回溯法的基本思想,5.1.2,回溯法的解空间,5.1.3,回溯算法实现,5.1.4,回溯法的基本步骤,5.1.5,回溯法实例,运动员最佳配对问题,5.2,子集和问题,5.3 n,皇后问题,5.4,连续邮资问题,5.5,哈密顿回路,5.6,本章小结,Chapter,5,引言,在程序设计中，有很多问题是无法运用某种公式推导或采用循环的方法来求解的。假如完成某一件事需要经过若干步骤，而每一步又都有若干种可能的方案供选择，完成这件事就有许多方法。当需要在其中找出满足条件的最优解时，无法根据某些确定的计算法则，而是利用试探和回溯的搜索策略。具有限界函数的深度优先生成法称为回溯法，用该方法求解问题时会按选优条件向前搜索，即系统搜索一个问题的所有解或任一解，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，既带有系统性又带有跳跃性。,Chapter,5,因此，它也是一种选优搜索法，采用走不通就退回再走的搜索技术。回溯法的本质是先序遍历一棵状态树过程，不是遍历前预先建立，而是隐含在遍历过程中，使用它可以避免穷举式搜索，适用于解一些组合数相当大的问题。回溯算法比前面介绍的其它方法复杂， 但它是程序设计中最重要的基础算法之一。,5.1,回溯法基础,Chapter,5,5.1.1,回溯法的基本思想,5.1.2,回溯法的解空间,5.1.3,回溯算法实现,5.1.4,回溯法的基本步骤,5.1.5,回溯法实例,运动员最佳配对问题,5.1.1,回溯法的基本思想,先定义问题的解空间，然后在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先的策略进行搜索。这种以深度优先的方式系统地搜索问题解的算法为回溯法，它适用于求解解空间较大的问题。整个试探搜索的过程是由计算机完成的，所以对于搜索试探要避免重复循环，即要对搜索过的结点做标记。,可见，回溯法就是,“,试探着走,”,。如果尝试不成,功则退回一步，再换一个办法试试。反复进行,这种试探性选择与返回纠错过程，直到求出问,题的解为止。,Chapter,5,5.1.2,回溯法解空间,1.,问题的解空间,（,1,）解空间概念,问题的解向量,问题的解空间,问题的可行解,问题的最优解,显约束,隐约束,Chapter,5,5.1.2,回溯法解空间,算法,5.1,用回溯法搜索子集树的一般算法框架,void backtrack (,int,t),if (tn),output(x,);,else,for (,int,i=0;in),output(x,);,else,for (,int,i=,t;i,n),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,时，则说明已经找到了一个运动员配对方案， 此时只需判断其是否是最优解，设用变量,cc,存放各组男女运动员双方竞赛优势乘积的总和,用变量,bestc,最优值,即存放竞赛优势乘积总和的最大值，在搜索过程中，,cc,和,bestc,中存放相应的当前值与当前最优值，此时若,cc,bestc,，则说明当前的最优方案已不再最优， 此时就用找到的方案来更新当前的最优方案,;,否则仍然保持以前的最优值,。,Chapter,5,若,i n,且,cc n), if (cc,bestc,) ,for (j=0;j=,n;j,+),bestxj,=,xj,;,bestc,=cc;,else,for(j,=,i;j,n,时，算法搜索至叶节点，其相应的子集和为,cs,。当,cs,=c,，则找到了符合条件的解。,当,i n,时，当前扩展结点,Z,是子集树的内部结点。该结点有,xi,=1,和,xi,=0,两个儿子结点。其左儿子结点表示,xi,=1,的情形。,剪枝函数,（,1,）,约束函数,（,2,）,限界函数,Chapter,5,5.2,子集和问题,算法的设计与实现,void,Subsum:backtrack(int,i),if (in),if (,cs,=c),for(int,j=1;j=,len;j,+),if(xj, =1),cout, w j“,”,;/,输出结果,cout,endl,;,return ;,r -=,wi,;,Chapter,5,4.,算法的设计与实现,算法,5.6,解运动员最佳配对问题的递归回溯法,5.2,子集和问题,算法的设计与实现,if (,cs+wi,=c) /,检测右子树,xi, = 0;,backtrack(i+1); /,深度优先遍历 ，递归处理右子树,r+=,wi,;/,递归退层时：将该段加入剩余路径,r,中,return ;,Chapter,5,5.3 n,皇后问题,本节内容,1.,定义问题的解空间,2.,确定解空间树的结构,3.,搜索解空间树,4.,算法的设计与实现,Chapter,5,5.3 n,皇后问题,问题描述,N,皇后问题，是一个古老而著名的问题，是回溯算法的典型例题，可以简单的描述为 ：在,N*N,格的棋盘上摆放,N,个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？,Chapter,5,5.3 n,皇后问题,定义问题的解空间,1,定义问题的解空间,以,8,皇后为例，可以用一棵树表示,8,皇后问题的解空间。假设皇后,i,放在第,i,行上，,8,皇后问题可以表示成,8,元组,(X1,，,X2,，,，,X8),，其中,Xi(i,=1,，,2,，,，,8),表示皇后,i,所放位置的列号，此时该问题的解空间为,8,个,8,元组。加上隐式约束条件：没有两个,Xi,相同，且不存在两个皇后在同一条对角线上，因此问题的解空间进一步减小为,8,！。由于,8,皇后问题的解空间为,8,！种排列，因此我们将要构造一棵排列树。,Chapter,5,5.3 n,皇后问题,5.3 n,皇后问题,确定解空间树的结构,2.,确定解空间树的结构,n,=4,时问题的一种,空间树,结构。,Chapter,5,5.3 n,皇后问题,确定解空间树的结构,确定解空间树的结构,具有限界函数的,4,皇后问题的状态空间树,Chapter,5,5.3 n,皇后问题,确定解空间树的结构,皇后问题的解示例,Chapter,5,4,皇后问题的解图示,5.3 n,皇后问题,搜索解空间树,3,搜索解空间树,解,n,后问题的回溯算法可描述如下：求解过程从空配置开始。在第,1,列,的,m,列为合理配置的基础上，再配置第,m+1,列，直至第,n,列也是合理时，就找到了一个解。在每列上，顺次从第一行到第,n,行配置，当第,n,行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。,用元组,x1:n,表示皇后问题的解，,xi,表示皇后,i,放在第,i,行的第,xi,列上，用完全叉树表示解空间。,Chapter,5,剪枝函数设计：对于两个皇后,A(i,j,),、,B(k,i,),两个皇后不同行：,i,不等于,k;,两个皇后不同列：,j,不等于,i;,两个皇后不同一条斜线,|,i-k|j-i,|,，即两个皇后不处于同一条,y=,x+a,或,y=-,x+a,的直线上,5.3 n,皇后问题,算法设计和实现,算法,5.7,解,N,后问题的递归回溯算法,int,Queen:queen(int,t),if(t,n & n0),/,当放置的皇后超过,n,时，可行解个数加,1,，此时,n,必须大于,0,sum+;,else,for(int,i=1;i0),xt, += 1;,while(xt,=,n)&!(Place(t,),xt, += 1;,if(xt,n,时，表示已搜索至一个叶结点，得到一个新的邮票面值设计方案,stampsValue,1:n,。如果该方案能贴出的最大连续邮资区间大于当前已找到的最大连续邮资区间,maxValue,，则更新当前最优值,maxValue,和相应的最优解,bestValue,。,Chapter,5,当,i=n,时，当前扩展结点,Z,是解空间中的一个内部结点。在该结点处,stampsValue,1:i-1,能贴出的最大连续邮资区间为,r-1,。因此，在结点,Z,处，,stampsValuei,的可取值范围是,stampsValue,i-1+1:r,，从而，结点,Z,有,r-stampsValue,i-1,个儿子结点。算法对当前扩展结点,Z,的每一个儿子结点，以深度优先方式递归的对相应的子树进行搜索。,5.4,连续邮资问题,算法设计和实现,算法,5.9,最大连续邮资区间的回溯算法,void Stamp:,conStamps,(,int,i,，,int,r),for(int,j=0;j=,stampsValue,i-2*(m-1);j+),if(stampsNum,jm),for(int,k=1;k=,m-stampsNum,j;k,+),if(stampsNumj+k,stampNumj+stampsValue,i-1*k),stampsNum,j+stampsValuei-1*k=,stampNum,j+k,;,while(stampsNum,rn),if(r-1,maxValue,),maxValue,=r-1;,for(int,j=1;j=,n;j,+),bestValue,j=,stampsValuej,;,return;,Chapter,5,4.,算法设计和实现,5.4,连续邮资问题,算法设计和实现,int,*z=new,int,maxl+1;,for(int,k=1;k=,maxl;k,+),zk,=,stampsNum,k;,for(int,h=stampsValuei-1+1;h=,r;h,+),if(stampsNum,r-h,m),stampsValuei,=h;,conStamps,(i+1,，,r+1);,/*,递归回溯第,i+1,层结点*,/,for(int,k=1;k=,maxl;k,+),stampsNum,k=,zk,;,delete z,;,Chapter,5,5.5,哈密顿回路,本节内容,1.,定义问题的解空间,2.,确定解空间树的结构,3.,搜索解空间树,4.,算法的设计与实现,Chapter,5,5.5,哈密顿回路,问题描述,设,G=,（,V,，,E,）是一个有,n,个节点的有向图或无向图，一条哈密顿回路是通过图中每个节点仅且一次的回路,问,:,给定一个图，求其是否存在一条哈密顿回路。如果是，输出每一条回路；否则给出提示。,Chapter,5,5.5,哈密顿回路,例如图：,Chapter,5,1,2,3,4,5,8,7,6,1,2,3,4,5,第一个图中存在回路：,1,，,2,，,8,，,7,，,6,，,5,，,4,，,3,，,1,第二个图中不存在,5.5,哈密顿回路,定义问题的解空间,1.,定义问题的解空间,所给问题是从,n,个元素的集合中找出满足某种性质的排列，因此，解空间可以组成一颗排列树，节点总数为,n!,，,遍历它至多需要,O(n,!),的计算时间。,Chapter,5,5.5,哈密顿回路,确定解空间树的结构,2.,确定解空间树的结构,用数组,xn,表示该问题的一组解，,xi,表示在一个可能回路上第,i,此访问的节点号。规定,x1=1,假定已经选完了,x1,到,xk-1,1kn.,那么,xk,可以取不同于,xi(i,可取从,1,到,k-1),且有一条边与,xk-1,相连的任意节点之一，而,xn,必须是与,xn-1,和,x1,都相连的节点，若这样的,xk,找不到则回溯到,xk-2,重找下一个节点,xk-1.,Chapter,5,5.5,哈密顿回路,搜索解空间树,3.,搜索解空间树,在遍历解空间树时，当,i=n,当前扩展节点是排列树的叶节点的父节点。此时需要检测无向图,G,是否存在一条从顶点,xn-1,到顶点,xn,的边和一条从顶点,xn,到顶点,1,的边，如果存在，则找到一条哈密顿回路。,当,in&gxk-11=1),output(x,);,else,for(int,i=,k;i,=,n;i,+),swap(xk,xi,);,if(gxk-1xk=1),hamilton(k+1,g);,swap(xi,xk,);,Chapter,5,4.,算法设计与实现,5.5,哈密顿回路,算法设计与实现,（,2,）迭代回溯法,void,backtrack(int,i),if(i,=n+1), /,当前扩展结点是排列树叶结点的父结点，图,G,存在一条从顶点,xn-1,到顶点,xn,的边和一条从顶点,xn,到顶点,1,的边，即找到一条旅行售货员回路,if(axn-1xn!=NoEdge&axn1!=,NoEdge,&(,bestc,=NoEdge|(cc+axn-1xn+axn1),bestc,),for(int,j=1;j=,n;j,+),bestxj,=,xj,;/,最优解,bestc,=cc+axn-1xn+axn1;/,当前最优值（最小费用）,Chapter,5,5.5,哈密顿回路,算法设计与实现,else,for(int,j=,i;j,=,n;j,+),/,是否可进入,xj,子树,if(axi-1xj ,！,=,NoEdge,&(,bestc,=,NoEdge,|(cc+axi-1xj),bestc,),/,搜索子树,swap(xi, ,xj,);,/,交换使得可以从当前结点选择其他的子节点,cc+=axi-1xi;,backtrack(i+1);,/,递归回溯,cc-=axi-1xi;,swap(xi,xj,);,Chapter,5,5.6,本章小结,回溯法类似于枚举的思想，适用于查问问题的解集或符合某种限制条件的最佳解集，通常采用剪枝策略进行范围控制，这样一般其最坏时间复杂度仍然很高，但对于,NP,完全问题来说，回溯法被认为是目前较为有效的方法。,Chapter,5,回溯算法的基本步骤,（,1,）定义给定问题的解空间：子集树问题、排列树问题和其他因素。,（,2,）确定状态空间树的结构。,（,3,）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。其中深度优先方式可以选为递归回溯或者迭代回溯。,