第5章-回溯法-复习.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,*,*,*,第,5,章 回溯法,通过应用范例学习回溯法的设计策略,（,1,）,装载问题,；,（,2,）,批处理作业调度；,（,3,）,符号三角形问题,（,4,）,n,后问题；,（,5,）,0-1,背包问题；,（,6,）,最大团问题；,（,7,）,图的,m,着色问题,；,（,8,）,旅行售货员问题；,（,9,）,圆排列问题；,（,10,）,电路板排列问题；,（,11,）,连续邮资问题。,2,问题的解空间,n=3,时的,0-1,背包问题用,完全二叉树,表示的解空间,W,=16,15,15,P,=45,25,25,3,问题的解空间,n=3,时的,0-1,背包问题用,完全二叉树,表示的解空间,C=30,W,=16,15,15,P,=45,25,25,4,回溯法在问题的解空间树中，按,深度优先策略,，从根结点出发搜索解空间树。,算法搜索至解空间树的任意一点,(,称为活结点,),时，先判断该结点是否包含问题的解。,如果肯定不包含，则跳过对该结点,(,称为死结点,),为根的子树的搜索，逐层向其祖先结点回溯；,否则，进入该子树,(,递归,),，继续按深度优先策略搜索。,回溯法,5,问题的解空间,问题的解向量：,回溯法希望一个问题的解能够表示成一个,n,元式,(x,1,x,2,x,n,),的形式。,显约束：,对,分量,x,i,的取值限定。,隐约束：,为满足问题的解而对不同,分量之间,施加的约束。,解空间：,对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。,6,旅行售货员问题,某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费），要求我们为他选定一条从驻地出发，经过每个城市仅有 一次，最后回到驻地的路线，使总路程（或总旅费）最小。,1,4,3,2,30,5,10,20,6,4,4,7,递归回溯,回溯法对解空间作深度优先搜索，在一般情况下用递归方法实现回溯算法。,void backtrack(int t),if(tn)output(x);,/tn,时，算法已经搜索到叶节点,n,控制递归深度,else,for(int i=,f(n,t),;i n),output(x,);,else,for(int i=0;in),output(x,);,else,for(int i=,t;i,n),/,到达叶结点,更新最优解值,bestw,(,当前最优载重量,),;,return;,if(,cw,+,wi,n),/,到达叶结点,更新最优值,bestw,bestw,=,cw,;,return;,r,-=,wi,;,/r-,剩余集装箱的重量,if(,cw,+,wi,bestw,),/,xi,=0,搜索右子树,backtrack(i,+1);,r+=,wi,;,由于,wi,没有装入,15,装载问题,构造最优解,void backtrack(int i),/,搜索第,i,层结点,if(i n),/,到达叶结点,更新最优值,bestx,bestw,;return;,r-=,wi,;,if(,cw,+,wi,bestw,),xi,=0;,/,搜索右子树,backtrack(i,+1);,r+=,wi,;,16,装载问题,装载类的设计：,template,class Loading,friend Type,MaxLoading(Type,，,Type,int,);,private:,void,Backtrack(int,i);,int n;/,集装箱数,Type*w,，,/,集装箱数组,c,/,第一艘轮船的载重量,cw,/,当前载重量,bestw,;/,当前最优载重量,；,17,装载问题,调用函数设计：,template,Type,MaxLoading(Typew,Type c,int n),/,返回最优载重量,Loading X;,/,初始化,X,X.w,=w;,X.c,=c;,X.n,=n;,X.bestw,=0;,X.cw,=0;,/,计算最有载重量,X.Backtrack(,1,);,return,X.bestw,;,输入：,5,100,70 10 40 70 80,输出：,90,18,给定,n,个作业的集合,J,1,J,2,J,n,。每个作业必须先由机器,1,处理，然后由机器,2,处理。,作业,J,i,需要机器,j,的处理时间为,t,ji,。对于一个确定的作业调度，设,F,ji,是作业,i,在机器,j,上完成处理的时间。,所有作业在机器,2,上完成处理的时间和称为该作业调度的完成时间和。,批处理作业调度问题要求对于给定的,n,个作业，制定最佳作业调度方案，使其完成时间和达到最小。,批处理作业调度,19,可以证明：存在最佳作业调度，使得在机器,1,和机器,2,上作业以相同次序完成。,这,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,。,t,ji,机器,1,机器,2,作业,1,2,1,作业,2,3,1,作业,3,2,3,批处理作业调度,20,批处理作业调度,解空间：排列树,class,Flowshop,friend int,Flow(int,M2,int,int );,private:,void,Backtrack(int,i);,int m 3,/,各作业所需处理时间，下标,0,没有使用,*,x,/,当前作业调度,*,bestx,/,当前最优作业调度,*,f2,/,机器,2,完成处理时间,f1,/,机器,1,完成处理时间,f,/,完成时间和,bestf,/,当前最优值,n;,/,作业数,;,4,21,批处理作业调度,解空间：排列树,void,Flowshop:Backtrack(int,i,),/,当前结点位于排列树的第,i-1,层,if(in),/,构造最优解,bestf,=f;,/,最优值,for(int j=1;j=n;j+),bestxj,=,xj,;,/,最优作业调度,return;,(next page),4,22,批处理作业调度,解空间：排列树,for(int j=i;jf1)?f2i-1:f1)+mxj2;,/,机器,2,的时间,f+=f2i+1;,/,当前的总时间,if(f,bestf,),/,不超过当前的最优值时,swap(xi,xj,);,/,xj,作为解空间的结点,Backtrack(i+1);,swap(xi,xj,);,/,恢复,xj,f1-=mxj1;,/,因为没有递归，恢复,f1,f,f-=f2i;,4,23,批处理作业调度,int,Flow(int,M 3,int n,int,bestx,),Flowshop,X;,X.x,=new int n+1;,X.f2=new int n+1;,X.bestx,=,bestx,;,X.bestf,=,Int_Max,;,X.n,=n;,X.f1=0;,X.f,=0;,for(int i=0;i=n;i+),X.mi1=Mi1;,X.mi2=Mi2;,X.xi,=i;,X.f2i=0;,X.Backtrack(,1,);,delete ,X.x,;,delete X.f2;,return,X.bestf,;,24,n,后问题,在,nn,格的棋盘上放置彼此不受攻击的,n,个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。,n,后问题等价于在,nn,格的棋盘上放置,n,个皇后，任何,2,个皇后不放在同一行或同一列或同一斜线上。,1,2,3,4,5,6,7,8,1,Q,2,Q,3,Q,4,Q,5,Q,6,Q,7,Q,8,Q,X,6,4,7,1,8,2,5,3,解向量：,(x,1,x,2,x,n,),显约束：,x,i,=1,2,n,隐约束：,1),不同列：,x,i,x,j,2),不处于同一正、反对角线：,|,i-j|,|x,i,-x,j,|,每列的值不一样,25,n,后问题,class,Queen,friend int,nQueen(int,);,private:,bool,Place(int,k);,void,Backtrack(int,t);,int n,/,皇后个数,*x;,/,当前解,long sum;,/,当前已经找到的,可行方案数,;,26,解向量：,(x,1,x,2,x,n,),显约束：,x,i,=1,2,n,隐约束：,1),不同列：,x,i,x,j,2),不处于同一正、反对角线：,|,i-j|,|x,i,-x,j,|,n,后问题,bool,Queen:Place(int,k),for(int j=1;jn)sum+;,/,有几种不同的方案,else,for(int i=1;i=,n;i,+),xt,=i;,if(,Place(t,)Backtrack(t+1);,27,n,后问题,int,nQueen(int,n),Queen X;,X.n,=n;,/n-Queen,X.sum,=0;,/,可行方案数,int*p=new intn+1;,/,动态数组,for(int i=0;i 0),xk,+=1;,/,从,1,开始试探,while(,xk,=n,)&!(,Place(k,),/,不合法,xk,+=1;,/,下一个数,if(,xk,=n),if(k=n),sum+;,/,得到一个解,else,k+;,xk,=0;,/,下一列,else,k-;/,回溯,29,0-1背包问题,解空间：子集树,可行性约束函数：,template,/,Typew,为重量,w,的数据类型，,Typep,为价值,p,的数据类型,class,Knap,friend,Typep,Knapsack(Typep,*,Typew,*,Typew,int);,/,为,Knap:Backtrack,(),初始化,private:,Typep,Bound(int,t);,/,计算上界,void,Backtrack(int,t);,/,回朔算法,Typew,c;,/,背包容量,int n;,/,物品数,Typew,*w;,/,物品重量数组,Typep,*p;,/,物品价值数组,Typew,cw,;,/,当前重量,Typep,cp;,/,当前价值,Typep,bestp,;,/,当前最优价值,;,30,0-1背包问题,回朔算法,template,void Knap:,Backtrack,(int i),if(i,n),/,到达叶节点,bestp,=cp;,return;,if(cw,+,wi,bestp,),/,进入右子树,Backtrack(i,+1);,31,0-1背包问题,上界函数：,template,Typep,Knap:,Bound,(int i),/,计算上界,Typew,cleft=c-,cw,;,/,剩余容量,Typep,b=cp;,/,当前价值,/,以物品单位重量价值递减序装入物品,while(i=n&,wi,=cleft),cleft-=,wi,;,b+=,pi,;,i+;,/,装满背包,(,部分装入,),if(i=n)b+=,pi/wi,*cleft;,return b;,32,0-1背包问题,class Object,friend int,Knapsack,(int*,int*,int,int);,public:,int operator=,a.d,);,private:,int ID;,/,物品编号,float d;,/,单位物品价值,;,33,0-1背包问题,template,Typep,Knapsack(Typep,p,Typew,w,Typew,c,int n),/,为,Knap:Backtrack,(),初始化,Typew,W=0;,/,物品总重量,Typep,P=0;,/,物品总价值,Object,*Q=new,Objectn,;,for(int,i=1;i=n;i+),/,建立,Q,数组,Qi,-1.ID=i;,/,建立序号,Qi,-1.d=1.0*,pi,/,wi,;,/,计算单位价值,P+=,pi,;,/,计算总价值,W+=,wi,;,/,计算总重量,34,0-1背包问题,if(W,=,c)return,P;,/,装入所有物品,Sort(Q,n);,/,按单位价值,排序,Knap,K,;,/Knap,的实例,K.p,=new,Typepn,+1;,K.w,=new,Typewn,+1;,for(int,i=1;i=n;i+),/,重新建立数组,p,和,q,K.pi,=pQi-1.ID;,/,排序之后的价值,K.wi,=wQi-1.ID;,/,排序之后的重量,35,0-1背包问题,K.cp,=0;,/,各个变量初值,K.cw,=0;,K.c,=c;,K.n,=n;,K.bestp,=0;,K.Backtrack(1);,delete Q;,/,垃圾回收,delete,K.w,;,delete,K.p,;,return,K.bestp,;,36,图的m着色问题,给定无向连通图,G,和,m,种不同的颜色。用这些颜色为图,G,的各顶点着色，每个顶点着一种颜色。是否有一种着色法使,G,中每条边的,2,个顶点着不同颜色。,这个问题是图的,m,可着色判定问题。,若一个图,最少需要,m,种颜色才能使图中每条边连接的,2,个顶点着不同颜色，则称这个数,m,为该图的色数。,求一个图的色数,m,的问题称为图的,m,可着色优化问题。,37,图的m着色问题,解向量：,(x1,x2,xn,),表示顶点,i,所着颜色,xi,可行性约束函数：顶点,i,与已着色的相邻顶点颜色不重复。,一棵高度为,n+1,的完全,m,叉树。,n,图的顶点数，,m,可用颜色数,n,m,38,图的m着色问题,class Color,friend int,mColoring,(int,int,int*);,private:,bool,OK,(int k);,/,检查颜色的可用性,void,BackTrack,(int i);,int n;,/,图的顶点数,int m;,/,可用颜色数,int*a;,/,图的邻接矩阵,int*x;,/,当前解,long sum;,/,着色的方案数,;,39,图的m着色问题,检查颜色可用性,bool,Color:Ok(int,k),for(int j=1;jn),/,搜索完毕,sum+;,for(int i=1;i=n;i+),cout,xi,;,cout,endl,;,else,for(int i=1;i=,m;i,+),xt,=i;,if(,Ok(t,)Backtrack(t+1);,41,图的m着色问题,int,mColoring(int,n,int m,int*a),Color X;,X.n,=n;,X.m,=m;,X.a,=a;,X.sum,=0;,int*p=new intn+1;,int i;,for(i=0;i=n;i+),pi,=0;,X.x,=p;,X.BackTrack(1);,delete p;,return,X.sum,;,42,图的m着色问题,复杂度分析,图,m,可着色问题的解空间树中内结点个数是,对于每一个内结点，在最坏情况下，用,ok,检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时,O(mn,),。因此，回溯法总的时间耗费是,O(nm,n,),43,旅行售货员问题,旅行商问题的解空间是一棵排列树,.,对于排列树的回溯搜索与生成,1,2,n,的所有排列的递归算法,P,ermutation,类似。设开始时,x=1,2,n,则相应的排列树由,x 1:n,的所有排列构成。,4,1,4,3,2,30,5,10,20,6,4,44,旅行售货员问题,class Traveling,friend Type,TSP(int,*,int,Type);,private:,void,Backtrack(int,i);,int n,/,图,G,的顶点数,*,x,/,当前解,*,bestx,;,/,当前最优解,Type*a,/,图,G,的邻接矩阵,cc,/,当前费用,bestc,/,当前最优值,NoEdge,;,/,无边标记,;,45,旅行售货员问题,解空间：排列树,template,void Traveling:,Backtrack,(int i),if(,i=n,),if(axn-1xn!=,NoEdge,&axn1!=,NoEdge,&,(cc+axn-1xn+axn1,bestc,|,bestc,=,NoEdge,),for(int j=1;j=n;j+),bestxj,=,xj,;,bestc,=cc+axn-1xn+axn1;,else,46,旅行售货员问题,else,for(int j=i;j=n;j+),/,是否可进入,xj,子树,?,if(axi-1xj,!=,NoEdge,&,(cc+axi-1xi,bestc,|,bestc,=,NoEdge,),/,搜索子树,Swap(xi,xj,);,cc+=axi-1xi;,/,此边可走,Backtrack(i+1);,cc-=axi-1xi;,/,恢复,Swap(xi,xj,);,47,旅行售货员问题,Type,TSP(Type,*,a,int,v,int,n,Type,NoEdge,),Traveling Y;,/,初始化,Y,Y.x,=new intn+1;,for(int,i=1;in),/,计算完毕,for(int j=1;j=n;j+),bestxj,=,xj,;,/,记录最优解,bestw,=,cw,;,if(,bestw,=c,)return true;,/,满足条件,(,找到了,),else return false;,54,子集和问题算法,r-=,wi,;,/,剩余大小,if(,cw+wi,bestw,),/,上界函数,xi,=0;,/,右子树,if(backtrack(i+1)return true;,r+=,wi,;,/,右子树无最优解,return false;,55,5-4,运动员最佳匹配问题,问题描述：,羽毛球队有男女运动员各,n,人。,给定,2,个,nn,矩阵,P,和,Q,。,Pij,是男运动员,i,和女运动员,j,配对组成混合双打的男运动员竞赛优势；,Qij,是女运动员,i,和男运动员,j,配合的女运动员竞赛优势。,由于技术配合和心理状态等各种因素影响，,Pij,不一定等于,Qji,。,男运动员,i,和女运动员,j,配对组成混合双打的男女双方竞赛优势为,Pij,*,Qji,。,设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。,56,运动员最佳匹配问题,编程任务：,设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。,数据输入：,第一行有,1,个正整数,n(1n20),。接下来的,2n,行，每行,n,个数。前,n,行是,p,，后,n,行是,q,。,结果输出,:,男女双方竞赛优势的总和的最大值。,输入示例：,3,10 2 3,2 3 4,3 4 5,2 2 2,3 5 3,4 5 1,输出示例：,52,p,q,57,运动员最佳匹配问题,结果输出,:,男女双方竞赛优势的总和的最大值。,样例分析,输入示例：,3,10 2 3,2 3 4,3 4 5,2 2 2,3 5 3,4 5 1,输出示例：,52,p,q,1,2,3,1,3,2,r,10*2+4*5+4*3=52,for(int i=1,temp=0;in)Compute();,/,构成,1,次全排列,else,for(int j=t;j=n;j+),/,从结点,t,到叶结点,swap(rt,rj,);,/,将结点,j,作为当前结点,Backtrack(t+1);,swap(rt,rj,);,/,将结点还回去,59,运动员最佳匹配问题算法,void,pref:Compute(void,),/,计算当前排列的竞赛优势,for(int i=1,temp=0;ibest),/,是更好的值？,best=temp;,for(int i=1;i=n;i+),/,构造最优解,bestri,=,ri,;,60,运动员最佳匹配问题算法,61,运动员最佳匹配问题算法,main,(),中的前半部分：,62,5-17,最佳调度问题,假设有,n,个任务由,k,个可并行工作的机器完成。完成任务,i,需要的时间为,t,i,。试设计一个算法找出完成这,n,个任务的最佳调度，使得完成全部任务的时间最早。,编程任务：,对任意给定的整数,n,和,k,，以及完成任务,i,需要的时间为,t,i,，,i=1n,。编程计算完成这,n,个任务的最佳调度。,63,最佳调度问题,数据输入：,第一行有,2,个正整数,n,和,k,。第,2,行的,n,个正整数是完成,n,个任务需要的时间。,结果输出,:,完成全部任务的最早时间。,输入示例,7 3,2 14 4 16 6 5 3,输出示例,17,64,4.7,多机调度问题,按算法,greedy,产生的作业调度如下图所示，所需的加工时间为,17,。,最长处理时间作业优先,机器空闲时间最长优先安排,65,最佳调度问题算法,void,search(int,dep,),/,初值为,1,if(,dep,=n),/,形成一种调度方案,int temp=comp();,/,计算完成任务的时间,if(,tmp,best)best=,tmp,;,/,更新最优解,return;,for(int i=0;ik;i+),/,对每台机器回溯,leni,+=,tdep,;,/,安排任务,dep,(,左子树,),if(,leni,best)search(dep+1);,leni,-=,tdep,;,/,右子树,66,最佳调度问题算法,计算完成任务的时间,int comp(),int,tmp,=0;,/,在,k,台机器中查找最大值,for(int i=0;i,tmp,),tmp,=,leni,;,return,tmp,;,67,5-30,离散,01,串问题,(n,k)01,串定义为：长度为,n,的,01,串，其中不含,k,个连续的相同子串。对于给定的正整数,n,和,k,，计算,(n,k)01,串的个数。,编程任务：,对于给定的正整数,n,和,k,，计算,(n,k)01,串的个数。,数据输入：,第一行有,2,个正整数,n,和,k,，,1,k,，,n,40,。,结果输出,:,(n,k)01,串的个数。,输入示例,2 3,输出示例,4,336,310,316,68,5-30,离散,01,串问题,具有对称性，只要考察首字符为,0,的情况，将找到的符合条件的,0-1,串的个数加倍。,void,backtrack(int,lev,),/,lev,从,2,开始,if(,lev,n),/,一种情况构造完毕,tot+=2;,/,个数加倍,return;,for(int i=0;i2;i+),bstrlev,=i;,/0,，,1,/,满足条件就回溯,if(,bstrok(lev,),)backtrack(,lev+1,);,69,5-30,离散,01,串问题,bool,bstrok(int,lev,),/,第,lev,位,for(int i=0;i0,),/,下标必须大于,0,if(,same(),)return false;,/,是相同的,for(int i=0;ik;i+),xi,-=i+1;,/,每隔,i,个位置,return true;,70,5-30,离散,01,串问题,/,判断是否相同,bool,same(),int,len,=x0-x1;,/,计算位置差,for(int i=0;i,len,;i+),/,搜索每一位,for(int j=1;jk;j+),/,每次搜索,k,位,if(,bstrxj+i,!=bstrxj-1+i),/,相邻位,return false;,/,只要有一个不相同即可,return true;,/,相同,71,5-30,离散,01,串问题,文件头：,#include,using namespace std;,int n,k;,int tot;,short*,bstr,;,int*x;,bool,bstrok(int,lev,);,bool,same();,72,