2011算法第十二十三讲回朔法

ECNUYinpingLiu回溯法柳银萍ECNUYinpingLiu1.回溯法的基本思想回溯法有“通用的解题法”之称。应用回溯法解问题时，首先应该明确问题的解空间。一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标达优的可行解称为该问题的最优解。在解空间中，前k项决策已经确定的所有决策序列之集称为k定子解空间。0定子解空间即是该问题的解空间。ECNUYinpingLiu例1．旅行商问题:某售货员要到若干个城市去推销商品。已知各个城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使得总的路程（或总旅费）最短。ECNUYinpingLiu我们用一个带权图G(V,E)来表示，顶点代表城市，边表示城市之间的道路。图中各边所带的权即是城市间的距离（或城市间的旅费）。则旅行商问题即是：在带权图G中找到一条路程最短的周游路线，即权值之和最小的Hamilton圈。ECNUYinpingLiu如果假定城市A是驻地。则推销员从A地出发，第一站有3种选择：城市B、C或城市D；第一站选定后，第二站有两种选择：如第一站选定B，则第二站只能选C、D两者之一。当第一、第二两站都选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了B和C时，第三站只能选择D。最后推销员由城市D返回驻地A。推销员所有可能的周游路线.ECNUYinpingLiu例2．定和子集问题：已知一个正实数的集合A={w1,w2,…wn}和正实数M．试求A的所有子集S，使得S中的数之和等于M。这个问题的解可以表示成0/1数组(x1,x2,...,xn)，依据wi是否属于S，xi分别取值1或0。故解空间中共有2n个元素。它的树结构是一棵完全二叉树。ECNUYinpingLiu例3．4皇后问题:在4×4棋盘上放置4个皇后，且使得每两个之间都不能互相攻击，即任意两个皇后都不能放在同一行、同一列及同一对角线上。将4个皇后分别给以1到4的编号，这个问题的解决就是要安排4个皇后的位置。因而，每个决策序列由4个决策组成：P1，P2，P3，P4，这里Pk代表安排第k个皇后的位置，因而有16种可能。该问题的解空间有164个决策序列。这时的约束条件是:任意两个皇后均不能位于同一行、同一列及同一个对角线上。注意到这个解空间比较大，从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不在同一行”也放在问题中考虑，即：将4个皇后放在4×4棋盘的不同行上，ECNUYinpingLiu使得每两个皇后均不能位于同一列、同一对角线上。则解空间中共有44个决策序列，因为此时可以假定第k个皇后处于第k行上。此时的约束条件为：任意两个皇后均不能位于同一列及同一个对角线上。事实上，我们还可以用另一种方法描述，使得解空间进一步缩小。将问题陈述为：将4个皇后放在4×4棋盘的不同行、不同列上，使得任意两个皇后均不能处在同一对角线上。这时的解空间应当由4！个决策序列构成。因为此时每个决策序列实际上对应于{1,2,3,4}的一个排列。我们可以用树来描述解空间。ECNUYinpingLiu从例3来看，解空间的确定与我们对问题的描述有关。如何组织解空间的结构会直接影响对问题的求解效率。这是因为回溯方法的基本思想是通过搜索解空间来找到问题的可行解以至最优解。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集合树。此时，解空间有2n个元素，遍历子集树的任何算法均需(2n)的计算时间,如例2。当所给的问题是确定n个元素的满足某种性质的排列时，相应的解空间树称为排列树，此时，解空间有n!个元素。遍历排列树的任何算法均需(n!)计算时间，如例1和例3。本章只讨论具有上两类解空间树的求解问题。ECNUYinpingLiu子集树与排列树遍历子集树需O(2n)计算时间遍历排列树需要O(n!)计算时间voidbacktrack(intt){if(tn)output(x);elsefor(inti=0;i=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(tn)output(x);elsefor(inti=t;i=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}ECNUYinpingLiu扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点确定了解空间的组织结构后，回溯法就从开始顶点（解空间树的根顶点）出发，以深度优先的方式搜索整个解空间。这个开始顶点就成为一个活顶点，同时也成为当前的扩展顶点。在当前的扩展顶点处，搜索向纵深方向移至一个新顶点。这个新顶点就成为一个新的活顶点，并且成为当前的扩展顶点。ECNUYinpingLiu如果在当前的扩展顶点处不能再向纵深方向移动，则当前的扩展顶点就成为死顶点。此时应往回移动（回溯）至最近一个活顶点处，并使这个活顶点成为当前扩展顶点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到要求的解或解空间中已无活结点时为止。事实上，当我们将问题的有关数据以一定的方式存储好以后（例如，旅行商问题存储赋权图的邻接矩阵、定和子集问题是存储已知的n+1个数、4皇后问题用整数对(i,j)表示棋盘上各个位置），不必先建立一个解空间树，然后再搜索该树寻找所需要的解。ECNUYinpingLiu回溯法实际上在搜索的同时逐步生成解空间树（实际只需要一部分）。也就是说，对于实际问题我们不必要搜索整个解空间。为了使搜索更加有效，我们常常在搜索过程中加一些判断以决定搜索是否该终止或改变路线。通常采用两种策略来避免无效的搜索，提高回溯法的搜索效率。其一是使用约束函数在扩展顶点处剪去不满足约束的子树；其二是用限界函数（见下页例）剪去不能得到最优解的子树。这两种函数统称为剪枝函数。ECNUYinpingLiu运用回溯法解题通常包括以下三个步骤：1).针对所给问题，定义问题的解空间；2).确定易于搜索的解空间结构；3).以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效的搜索。用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。ECNUYinpingLiu构造限界函数(背包问题)BoundF(cp,cw,k,M)//返回效益值的当前限界gloaln,p[1:n],w[1:n];integerk,i;realb,c,cp,cw,M;b=cp;c=cw;forifromk+1tondoc=c+w[i];ifcMthenb=b+p[i];elsereturnb+((c-M)/w[i])*p[i];endifendforreturn(b);endBoundFECNUYinpingLiu递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归实现回溯法voidbacktrack(intt){if(tn)output(x);elsefor(inti=f(n,t);i=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}ECNUYinpingLiu迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。voiditerativeBacktrack(){intt=1;while(t0){if(f(n,t)=g(n,t))for(inti=f(n,t);i=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t)){if(solution(t))output(x);elset++;}}elset--;}}ECNUYinpingLiu装载问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且211ccwnii装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。ECNUYinpingLiu将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题。nixcxwxwiniiiniii1},1,0{s.t.max111用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。ECNUYinpingLiu•解空间：子集树•可行性约束函数(选择当前元素)：•上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r当前最优载重量bestwpublicclassLoading{//类数据成员staticintn;//集装箱数staticintw[];//集装箱重量数组staticintc;//第一艘轮船的载重量staticintcw;//当前载重量staticintbestw;//当前最优载重量staticintr;//剩余集装箱重量staticintx[];//当前解staticintbestx[];//当前最优解ECNUYinpingLiuintmaxloading(intww[],intcc,intx[]){n=ww.length-1;w=ww;c=cc;bestw=0;x=newint[n+1];bestx=x;//初始化rfor(inti=1;i=n;i++)r+=w[i];//计算最优载重量backtrack(1);returnbestw;}ECNUYinpingLiuvoidbacktrack(inti){//搜索第i层结点if(in)//到达叶结点for(intj=1;j=n;j++)bestx[j]=x[j];bestw=cw;//更新最优解bestx,bestw;return;}//搜索子树ECNUYinpingLiur-=w[i];if(cw+w[i]=c){//搜索左子树x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+rbestw){x[i]=0;//搜索右子树backtrack(i+1);}r+=w[i];}ECNUYinpingLiuintmaxloading(intw[],intc,intbestx[]){//迭代回溯法//返回最优载重量及其相应解//初始化根结点inti=1;//当前层intn=w.length–1;intx[]=newint[n+1];intbestw=0;intcw=0;intr=0;ECNUYinpingLiufor(intj=1;j=n;j++)r+=w[j];//搜索子树while(true)while(i=n&&cw+w[i]=c){//进入左子树r-=w[i];cw+=w[i];x[i]=1;i++;}if(in){//到达叶结点ECNUYinpingLiufor(intj=1;j=n;j++)bestx[j]=x[j];bestw=cw;}else{//进入右子树r-=w[i];x[i]=0;i++;}while(cw+r=bestw){//剪枝回溯i--;while(i0&&x[i]==0){//从右子树返回ECNUYinpingLiur+=w[i];i--;}if(i==0)returnbestw;//进入右子树x[i]=0;cw-=w[i];i++;}}}ECNUYinpingLiu批