回溯算法(高见元)概要课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,湖 北 经 济 学 院,计 科 系,第五章 回溯法,5.1 回溯算法基本思想,回溯法是一种通用的解决问题的办法，本质上就是一种穷举，并且是一种避免重复的穷举。,所有回溯算法与走迷宫具有相同的本质。,1,迷宫问题,回溯：往回退，追根溯源。,求解的目标:确定每一个十字路口的选择，最后走出迷宫。,2,问题的解空间树,问题的解向量：回溯算法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。,解空间树：由解元素x1,x2xn取不同值所构成组合(或排列)序列，迷宫中xi表示第i个十字路口做出的选择。,Eg.n=3时的0-1背包问题解空间树为左图所示二叉树,显式约束：对分量xi的取值限定。,隐式约束：为满足问题的解对不同分量之间施加的约束。,x1,x2,x3,3,回溯算法的本质：确定问题的解空间树后，深度优先遍历此空间树。,但是往往问题的解空间树是无法完全存储的（eg），所以遍历有它的特点。,通常情况下的处理策略是：一边生成解空间树，一边遍历。,4,解空间树的生成方法,深度优先的解空间树生成法：,从根结点R开始（R是第一个扩展结点），生成它的一个儿子结点C(即确定了x1)；然后以C作为新的扩展结点，在完成了以C为根的子树的穷尽搜索之后(即递归，是在x1保持不变的情况下，分别求解x2xn的所有可能组合)，将R重新变成扩展结点（即回溯到R结点处），继续生成R的下一个儿子（即让x1取另外一个值，直至没有值可取即会回退到R的父结点，此时以R为根的树遍历结束）。,扩展结点：一个准备生成其儿子的结点,5,回溯算法正是按深度优先解空间树生成法，结点生成到哪里，就遍历到哪里。,此过程可以表达成如下递归形式和非递归形式。,递归形式的表达：,BackTrack(k)/当前已经具备k-1个解元素，准备求X,k,if(x1,x2,x,k-1,)是问题的解 输出；,else ,计算第k个解元素的候选集合S,k,;,/S,k,相当于第k个十字路口的选择,while(S,k,!=,空),x,k,=S,k,中的一个元素；/X,k,已求出,S,k,=S,k,-x,k,；,BackTrack(k+1);/递归进一步求X,k+1,/while结束，即表示第k个路口已穷举完,6,非递归形式的表达：,BackTrack(X),计算解向量X的第一个元素x1的候选集合S1；,k=1;/S1即第一个十字路口处没有走过的支路,While(k0),while Sk!=空,Xk=Sk中的一个元素；/第k个路口已确定,Sk=Sk-Xk;/已走过的支路不会重复走,if(X=(x1,x2,xk)是问题的解)输出；,k+;计算候选集合Sk;,k-;/回溯，即回退到第k-1个十字路口,7,例如：输出1n的全排列，递归表达如下（pailie0.c）,void f(int k)/已经具备X1Xk-1,函数目的：求解Xk,int i;,if(k-1=n)/找到问题的一个解,coutendlThe+count:;,for(i=1;in+1;i+)coutXi“”;/输出解向量,else for(i=1;i0),for(;in+1;i+)if(!usedi&kn)output(x);,else for(int i=0;in)output(x);,else for(int i=t;i=n;i+),if(xianjie(t,i),xt=i;,backtrack(t+1);,排列树：即将一批元素进行排列的问题，例如N皇后、骑士、迷宫等问题,时间复杂度：,(n!),n为要排列元素个数,12,5.3 集装箱装载问题,有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。,容易想到下面的一种贪心策略：,(1)优先装重的箱子，将第一艘轮船尽可能装满；,(2)将剩余的集装箱装上第二艘轮船。,这种策略不能保证能得到问题的解。,经过分析：此问题等价于将全体集装箱分成2个子集，分别对应2艘船。与0-1背包问题一样，也是分成两个子集。,解向量：X=x1,x2,xn,xi=1表示第i个集装箱装入第1艘船，xi=2表示装入第2艘船，xi,1,2，,所以程序如下：,13,void,backtrack,(int k),/求解Xk，即确定集装箱k装哪艘船,if,(k-1=n)输出可行解;/箱子全部装完,for(i=1;i=2;i+)/Xk的候选集1,2,if(xianjie(k,i)/检查Xk能否取i，即第k个箱子,Xk=I;/能否装上第i艘船,backtrack(k+1);/继续装第k+1个箱子,/限界函数的设计是关键，根据问题约束条件来定义,时间复杂度,(2,n,),思考：如果m艘船来装，只需改变什么？,14,思考：n个礼物尽可能平均分配给2个人，其本质可以看成子集划分问题，思考其回溯算法程序。(liwufenpei.c),如果礼物尽可能平均分配给k个人，那么对应的回溯算法只需要修改什么地方即可。,附加介绍的案例：,子集和数问题(zijiheshu.c),子集和数问题：,即在一个集合A1n中找出所有元素之和等于S的子集。,首先分析确定解向量：X1n,Xi=1表示Ai被选中进入子集，Xi=0表示弃选，本质即对该集合划分成2个子集。,15,1)子集和数问题,递归算法：,void backtrack(int t),if(CurS=S)输出；,/CurS:前t-1个元素中选中元素之和,else for(I=0;I CurBest)记录此时结果;,/CurS:当前装入的价值,else for(I=0;I2 I+),if(xianjie(t,I),Xt=I;,if(I=1)CurS+=AI;CurW-=WI;,backtrack(t+1);,if(I=1)CurS-=AI;,CurW+=WI;,/限界函数设计的好的话，可以减少很多计算量。,/递归函数：T(n)=2T(n-1)+O(1)=,(2,n,),17,5.4,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,18,解向量：(x,1,x,2,x,n,),xi=j表示第i行的皇后放在第j列,显约束：x,i,=1,2,n,隐约束：1)不同列：,x,i,x,j,2)不处于同一正、反对角线：,|i-j|,|x,i,-x,j,|,，即斜率绝对值为1的两条直线,(NQueen.c),int,xianjie,(int k,int xk)/判断第k行皇后能否摆第Xk列,for,(int j=1;jn)output();sum+;,else for,(int i=1;i0),for(;in)success=1;exit(0);/,success为全局变量,else for(I=1;I=k;I+),if(xianjie(t,I)/,限界函数根据图（可采用邻接矩阵存储）,Xt=I;/,判断顶点t能否染第I种颜色,Digui(t+1);/继续染第t+1个顶点,非递归同样可以采用前面的思路结构很快可以写出来。（,自己转化,）,3）与求,最大团,（最大完全子图）问题等价,22,回溯还可以解决很多问题,Eg.1)13张卡片问题 2）求不定方程（不等式）的解问题 3）迷宫问题 4）最佳巡游路线问题（旅行商问题）,.,23,