第5章 回溯法1

第5章回溯法学习要点理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架（1）递归回溯最优子结构性质（2）迭代回溯贪心选择性质（3）子集树算法框架（4）排列树算法框架•有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。•回溯法属于穷举法，是一种逐步试探以求出问题解的方法。•回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。•回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。例：卒子穿阵问题问题描述：要求一卒子从顶部通过右图所示的阵列达到底部。要求：卒子行进中不可进入到代表敌兵驻守的区域内（标注1），并且不准后退。假定深度限制值为5。1000001001001000S0S1（1，1）S2（1，2）S8（1，3）S18（1，4）死……S3（2，2）S4（2，1）S7（2，3）S5（3，1）S6（4，1）S9（1，2）S14（1，4）S10（2，2）S11（2，1）S12（3，1）S13（2，3）S15（2，4）S16（3，4）S17（4，4）死死深度限制死解0001001001000001回溯法的基本思想是：假设能够用n元组（x1,x2,x3,……，xn）表示一个给定问题的解，xi取值于集合Si；n元组的子组（x1,x2,x3,……，xi）（in）称为部分解应满足一定的约束条件。如果已有满足约束条件的部分解，则添加xi+1∈Si+1到子组（x1,x2,x3,……，xi,xi+1）中形成新的子组并检查（x1,x2,x3,……，xi,xi+1）是否满足约束条件，若满足则继续添加xi+2∈Si+2，依次类推。如果所有的xi+1∈Si+1都不能得到部分解，那么去掉xi回溯到（x1,x2,x3,……，xi-1）中，然后添加那些未考察过的xi∈Si，判断其是否满足约束条件。如此反复进行下去，直到得到问题的解或者证明无解为止。•在解空间中，问题的求解就是搜索。•搜索的基本问题是：（1）搜索过程是否一定能找到一个解；（2）搜索过程是否能终止运行或是会陷入一个死循环；（3）当搜索过程找到解时，找到的是否是最佳解；（4）搜索过程的时间与空间复杂性如何。•搜索过程的要点是：（1）从初始或目标状态出发，并将它作为当前状态。（2）扫描操作算子集，将适用于当前状态的一些操作算子作用在其上面得到新的状态，并建立指向其父结点的指针。（3）检查所生成的新状态是否满足结束状态，如果满足，则得解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答途径；否则，将这新状态作为当前状态，返回到第（2）步再进行搜索。•搜索可按两个方向进行（1）从初始状态出发的正向搜索，也称为数据驱动；（2）从目的状态出发的逆向搜索，也称为目的驱动。•正向搜索是从问题给出的条件——一个用于状态转换的操作算子集合出发的。搜索的过程即为产生新条件的过程，这个过程一直持续到有一条满足目的要求的路径产生为止。•逆向搜索则是先从想要达到的目标入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件，这些新条件就成为我们要达到的新目的，即子目的。逆向搜索就通过反向的、连续的子目的不断地进行，一直找到问题给定的条件为止。•两种方向的搜索各有优缺点，具体应选择哪种应该根据实际问题来决定。比如，开始状态集合与目的状态集合中状态的个数、分支因素等。通常从小的状态集出发朝大的状态集搜索的求解过程要容易一些。1.问题的解空间5.1回溯法的算法框架•问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。•显约束：对分量xi的取值限定。•隐约束：为满足问题的解而对不同分量之间施加的约束。•解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的0-1背包问题用完全二叉树表示的解空间生成问题状态的基本方法•扩展结点:一个正在产生儿子的结点称为扩展结点•活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点•死结点:一个所有儿子已经产生的结点称做死结点•深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）•宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点•回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法对于n=3时的0-1背包问题，考虑下面例子：w=[16,15,15],p=[45,25,25],c=30。r=14,p=45不可解r=14,p=45不可解r=14,p=45r=30,p=0r=15,p=25r=0,p=50回溯法解旅行售货员问题：旅行售货员问题的提法是：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。设G=（V，E）是一个带权图。图中各边的费用（权）为一正数。图中的一条周游路线是包括V中的每个顶点在内的一条回路。一条周游路线的费用是这条路线上所有边的费用之和。所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线。14323010204561，2，4，3，11，3，2，4，11，4，3，2，1ABCDEFGHIJKLMNOPQ12343444433322221432301020456旅行售货员问题的解空间树回溯法的求解思路(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。递归回溯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);}}迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。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--;}}子集树与排列树当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。voidbacktrack(intt){if(tn)output(x);elsefor(inti=0;i=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}遍历子集树需O(2n)计算时间当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。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]);}}遍历排列树需要O(n!)计算时间装载问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且211ccwnii装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。例如：当n=3,c1=c2=50,且w=[10,40,40]时，则可以将集装箱1和2装到第一艘轮船上，而将集装箱3装到第二艘轮船上；如果W=[20,40,40],则无法将这3个集装箱都装上船。容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题。nixcxwxwiniiiniii1},1,0{s.t.max111用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。•解空间：子集树•可行性约束函数(选择当前元素)：11cxwniiivoidbacktrack(inti){//搜索第i层结点if(in)//到达叶结点更新最优解bestx,bestw;return;r-=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];}批处理作业调度给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。tji机器1机器2作业121作业231作业323作业1作业2作业33+6+7+3=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。作业1作业3作业23+4+3+7+1=18