算法基础 chap5学习资料

第五章 回溯法搜索技术的相关概念回溯法的算法框架用回溯法解决问题实例回溯法的效率分析2搜索技术问题描述假定问题的解能表示成一个n-元组(X1,…,Xn)，其中Xi取自某个有穷集Si。所有这些n-元组构成问题的解空间。假设集合Si的大小是mi，则可能的元组数为m=m1m2…mn。考虑两类问题：存在性问题：求满足某些条件的一个或全部元组，如果不存在这样的元组，算法应返回false；这些条件称为约束条件。满足约束条件的元组称为问题的可行解。优化问题：给定一组约束条件，在问题的可行解中求使某目标函数达到最大（小）值的元组，即最优解。解决这类问题的一般方法是搜索技术，即系统化的搜索解空间的技术，主要包括回溯法和分支限界法。3搜索技术实例1：8后问题在8×8的棋盘上放置8个皇后，使得这8个皇后不在同一行、同一列及同一斜角线上。QQQQQQQQ12345678123456784搜索技术8皇后问题可以表示成8-元组(x1,…,x8)，其中xi是放在第i行的皇后所在的列号。于是，解空间由88个8-元组组成。约束条件：xi≠xjforalli,j|xi-xj|≠|j-i|约束条件之一为没有两个xi相同(即任意两个皇后不在同一列上)。将其加入到元组的定义中，这时解空间的大小由88个元组减少到8!个元组。n-皇后问题只要可行解，不需要最优解。5搜索技术状态空间树解空间的树结构称为解空间树，它是尝试选择元组的各个分量时产生的树结构。树中的每个结点代表问题求解过程中的一个状态，根节点到它的路径代表对一些分量已作出的选择。根到一个节点的路径可以表示为(x(1),…,x(k))，也用这个元组标识该节点。状态空间树的所有节点构成问题求解的状态空间。如果由根到节点S的那条路径确定了解空间的一个元组,则称S对应的状态为一个解空间状态。如果一个解状态代表的元组满足约束条件称其为可行解。6搜索技术4-皇后问题的解空间树（4！），节点按深度优先检索编号12503418

X1=115121o75173133282623211383292419454035615651141196416303227252220234

X2=2341

3

41

241

23X3=31143423243443423243413x4=1…………7搜索技术搜索算法搜索算法通过展开解空间树来找所求的解。用以下术语描述展开状态空间树的各种方法：活结点：已展开一个以上子节点，但所有子结点尚未全部产生的结点。死结点：被限界或已展开了所有子结点的结点。E-结点(扩展结点)：当前正在展开子结点的结点（某刻唯一）。深度优先展开方法：一个E-结点C展开自己的一个子结点R后，就让结点R成为E-结点，当完成R的所有子树的搜索后，让C重新成为E-结点，继续展开C的子结点(如果存在)。这种方法相当于对解空间树做深度优先搜索，称为深度优先展开方法。广度优先展开方法：在当前E-结点处，先展开自己的所有子结点，然后再从当前的活结点表中选择下一个E-结点。8搜索技术剪枝使用启发式的剪枝技术能使搜索算法只展开解空间树的一部分，降低了搜索的开销。剪枝函数从分析约束条件或某种启发式得到。剪枝函数必须计算简单。9搜索技术搜索方式回溯法：加剪枝的深度优先展开方法称为回溯法。分枝限界法：以广度优先或最小耗费优先的方式搜索解空间树。10回溯法的算法框架回溯法回溯法是能避免不必要搜索的搜索法。适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点为根的子树是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法：为了避免生成那些不可能产生最优解的问题状态，要不断地利用剪枝函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。11回溯法的算法框架回溯法的基本步骤针对所给问题，定义问题的解空间；相当于找出进行穷举的搜索范围确定易于搜索的解空间结构；一般是形成解空间树以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树（一定不是可行解）；用限界函数剪去得不到最优解的子树（一定不是最优解）。12回溯法的算法框架递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。voidbacktrack(intt)//t：递归深度，如何调用函数完成整个递归？{

if(t>n)output(x);//n：递归深度阈值

elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}P118有详细说明13回溯法的算法框架迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。voiditerativeBacktrack(){intt=1;

while(t>0){

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--;}}P118的说明14回溯法的算法框架子集树与排列树所给的问题是从n个元素的S中找出满足某种性质的子集时，相应的解空间树称为子集树。通常有2n个叶子结点，结点总数为2n+1-1。遍历子集树需要Ω(2n)的计算时间。所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。通常有n!个叶子结点。遍历排列树需要Ω(n!)的计算时间。15回溯法的算法框架用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。16n后问题（5.5）算法设计解向量：(x1,x2,…,xn)，xi表示第i个皇后的列号。解空间：用完全n叉树表示（n的n次方解空间）。显约束：xi

xj，不同列。隐约束：设两个皇后(i,xi)，(j,xj)在同一斜线上，则有： i–j

=xi–xj(斜率为1)或者i-j=xj-xi(斜率为-1)

即：|i-j|

|xi-xj|。因此，约束条件不同斜线可以转化为：|i-j|

|xi-xj|。可行性约束place剪去不满足上述约束条件的子树。17n后问题递归回溯privatebooleanPlace(intk){for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}privatestaticvoidBacktrack(intt){if(t>n)sum++;//sum为当前可行方案数elsefor(inti=1;i<=n;i++){ //一行中的n个放置位置x[t]=i;if(Place(t))Backtrack(t+1);}}18n后问题迭代回溯privatestaticvoidbacktrack(){x[1]=0;intk=1; /*k：搜索深度,行号*/while(k>0){ x[k]=x[k]+1; /*在当前列加1的位置开始搜索*/while((x[k]<=n)&&(!place(x,k))) /*当前列位置是否满足条件*/x[k]=x[k]+1; /*不满足条件,继续搜索下一列位置*/if(x[k]<=n){ /*存在满足条件的列*/if(k==n)sum++; /*是最后一个皇后,完成搜索*/else{k=k+1;x[k]=0;}/*不是,则处理下一行的皇后*/}else{ /*x[k]>n,已判断完n列,均没有满足条件*/k=k–1; /*回溯到前一行*/}}}19n后问题算法分析运行时间取决于所访问结点个数c，每访问一个结点，就调用一次place函数计算约束方程。place函数循环体的执行次数，最多n-1次。因此，总次数为O(n)。结点个数是动态生成的，对不同实例，具有不确定性。一般可由n的多项式确定。在4叉完全树中，结点总数有40＋41＋42＋43＋44＝341个，回溯法处理时，c=27，约为前者的8%。实际模拟表明，当n=8时，被访问的结点数与结点总数之比约为1.5%。20n后问题4皇后问题包含显约束条件的解空间树21装载问题（5.2）问题描述有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且有：装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这两艘轮船。可能装不下？例：当n=3，c1=c2=50，w=[10,40,40]时，可将货箱1,2装到第一艘船上，货箱3装到第二艘船上。如果w=[20,40,35]，则无法将货箱全部装走。当集装箱总重量为c1+c2时，等价于子集和问题，当c1=c2且集装箱总重量为2c1时，等价于划分问题。22装载问题装载策略如果一个装载问题有解，则采用下面的策略可得到最优装载方案。首先将第一艘轮船尽可能装满；将剩余的集装箱装上第二艘轮船。证明设可行解在第一艘船装入W1（≤c1）重量，在第二艘船装入W2（≤c2）重量；设最大化第一艘船的装船量为M1，则W1≤M1；而剩下的集装箱重量之和＝总重量（W1+W2）－M1≤总重量－W1＝W2，剩下的集装箱一定能装入第二艘船。23装载问题将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题（wi=vi）。可以用动态规划求解，时间复杂度为O(min{nc,2n})。可以用回溯法求解，时间复杂度为O(2n)，在某些情况下优于动态规划算法。24装载问题回溯算法设计子集树：左子结点表示x(i)=1，右子结点表示x(i)=0。cw记录当前结点相应的装载重量，bestw记录当前已经获得的最大装载重量。剪枝函数约束函数：cw＋w(i)>c1，则杀死该左子结点。右子结点如何处理？右子结点的cw值与扩展结点的cw值相等，因此，展开右子结点时，不检查约束函数。限界函数：设r为未装的货箱的总重量，如cw+r<=bestw，则停止展开该结点，即剪去右子树。左子结点如何处理？左子结点和父结点有相同的cw+r值，所以，展开左子结点时，不检查限界函数。25装载问题搜索过程：设x=(x(1),…,x(k-1))为当前E结点；展开左子结点：如果cw+w(k)>c1，则停止展开该左子结点，r←r-w(k)，并展开右子结点；否则，x(k)←1，cw←cw+w(k)，r←r-w(k)，并令(x(1),…,x(k))为E结点；展开右子结点：如果cw+r≤bestw，则停止展开该右子结点，并回溯到最近的一个活结点；否则，令x(k)=0,(x(1),…,x(k))为E结点。回溯：从i=k-1开始，找x(i)=1的第一个i；修改cw和r的值：cw←cw-w(i)(最后的),r←r+w(i)(每次的i)。26装载问题k=n时，x=(x(1),…,x(n-1))，cw+w(n)>c1，则左子结点是不可行结点，考虑右子结点：如果cw+r=cw>bestw，bestw←cw，x(n)←0；否则cw+r=cw<=bestw，右子结点被限界，回溯。cw+w(n)≤c1，则左子结点是可行结点：cw←cw+w(n)，如果cw>bestw，bestw←cw，x(n)←1；否则cw<=bestw，左子结点不含最优解，同时右子结点也不可能有最优解，回溯。bestw初始值为-∞在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索；否则将右子树剪去。27装载问题例：假定n=4，w=[8,6,2,3]，c1=12。状态空间树：装载问题的解空间树，未显示叶结点28装载问题递归过程展开的状态空间树：在进入左、右子树，递归进入下一层之前，加入输出cw和r的语句，输出结果如下：ABKJE

110cw=0cw=8cw=8cw=10cw=801bestw=10bestw=110XYw=[8,6,2,3]，c1=12。290-1背包问题（5.6）算法描述与装载问题类似，是一个优化问题，因此不仅可以使用约束函数，而且可以使用限界函数做剪枝函数。子集树：左子结点表示x(i)=1，右子结点表示x(i)=0。剪枝函数：约束函数：cw+wk≥M限界函数：cp+r≤bestpcw：到当前节点时，已装入背包的重量cp：到当前节点时，已装入背包的价值WK：当前节点所要判断物品（K）的重量M：背包所能容忍的最大重量r：当前剩余物品（还未判断取舍的物品）的价值和bestp：当前已获得的最优价值（可行解，但不一定是最优解）0-1背包问题1.上界是界线，越接近理论界线越有意义。r是当前剩余物品（还未判断取舍）的价值和,cp+r是否还有比2方法更接近理论界线的求上界方法？确定右子树中解的上界将剩余物品按单位重量价值非递增排序，依次在剩余背包中装入物品，直到无法全部装入某物品时，装入该物品的一部分将背包填满，此时对应的价值是右子树中解的上界。cp+r’300-1背包问题对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3.5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。对于相同背包，相同物品，背包问题的最优解不小于0-1背包问题的最优解。310-1背包问题对某一节点来说，剩余背包容量装剩余物品，也可得到一个价值上界。cp+r’用这样一个小的价值上界代替2计算出的价值上界，有什么好处？对某一节点，根据2方法，cp+r>bestp对某一节点，根据3方法，cp+r’<=bestp减掉更多子树，提高搜索速度320-1背包问题2算法框架331)预处理：各物品按单位重量价值降序排序，重量放于数组w[]，价值放于数组p[]2)回溯算法Privatestaticvoidbacktrack(inti){ if(i>n){//reachtheleafnode bestp=cp; return;} //searchthesubtree if(cw+w[i]<=c){//entertheleftsubtree cw+=w[i];cp+=p[i]; backtrack(i+1); cw-=w[i];cp-=p[i];} if(bound(i+1)>bestp) backtrack(i+1); //entertherightsubtree}Privatestaticdoublebound(inti){Doublecleft=c-cw;doublebound=cp;//以单位重量价值递减顺序装入while(i<=n&&w[i]<=cleft){ cleft-=w[i];bound+=p[i];i++}//装满背包If(i<=n) bound+=p[i]*cleft/w[i];returnbound;}340-1背包问题3.实例：n=8,M=110,W=[1,11,21,23,33,43,45,55],P=[11,21,31,33,43,53,55,65]图中未用字母标识的末端结点表示被剪枝的结点，可以不画在图中。图中圈内数字表示结点的重量和价值，圈外的数字表示其上界值。35旅行售货员问题（5.9） 旅行商问题（Hamiltoniancircuit）某售货员要到若干个城市去推销商品。已知各个城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总的路程（或总旅费）最小。用一个带权图G＝(V,E)来表示，顶点代表城市，边表示城市之间的道路。图中各边所带的权即是城市间的路程（或旅费）。36旅行售货员问题用1，2，…，n代表n个顶点，一个周游i1,i2…,in,i1用数组(i1,i2…,in)表示，它是旅行商问题的一个可行解。如果可行解的前k-1个分量x1,x2…,xk-1已经确定,则判定x1,x2…,xk-1,xk能否形成一条路径，只需做k-1次比较： xk≠x1,xk≠x2…,xk≠xk-1 构成旅行商问题的显性约束条件，可直接用在减小解空间树。用w(i,j)记边(i,j)的权值，cl记当前路径x1,x2…,xk-1的长度，即旅行商问题求解使cl(k=n)取最小值的解。37旅行售货员问题算法描述解空间：排列树递归回溯算法中，i=n时，当前扩