Lecture04

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,2011-2012-2:SCUEC,回溯算法-,Backtracking,理解回溯法的深度优先搜索策略,掌握用回溯法解题的算法框架,解决问题示例,通用解题法：,回溯,法,适用问题,:,有,很多可行解，但只有有限多, 不容易找到穷举之外的算法,。如哈密顿回路问题、,TSP,问题等,回溯,法是穷举查找方法的一个改进，通过有效的组织穷举，避免搜索所有的可能性。,系统地搜索一个问题的所有解或任一解，既有系统性又有跳跃性,每次,只构造候选解的一个分量，然后评估这个部分解，考虑其是否会导致一个解来决定是否产生下一个分量。,解的正确性是明显的。,问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个,n,元组,(x1,x2,xn),的形式。,显性约束,：对分量,xi,的取值限定。,隐性约束,：为满足问题的解而对不同分量之间施加的约束。,解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,解空间的组织方法：图或树,n=3,时的,0-1,背包问题用完全二叉树表示的解空间,扩展,结点：一,个正在产生儿子的,结点,活结,点：一,个自身已生成但其儿子还没有全部生成的,节点,死结,点：一,个所有儿子已经产生的结点称做死结点,深度优先模式的问题,状态生成法,：,对,一个扩展结点,R,，一旦产生了它的一个儿子,C,，就把,C,当做新的扩展,结点,在,完成对子树,C,（以,C,为根的子树）的穷尽搜索之后，将,R,重新变成扩展结点,，,继续,生成,R,的下一个,儿子，如果存在的话,否则，,R,变成死节点,生成问题解空间树的基本方法,生成问题解空间树的基本方法,回溯法：为了避免生成那些不可能产生最优解的问题状态，要不断地利用约束函数,(constraint function),或限界函数,(bounding function),来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。,具有约束函数或限界函数的深度优先生成法称为回溯法,扩展节点、活结点、死结点,考虑,n=3,时的,0-1,背包问题实例：,w=16, 15, 15, p=45, 25, 25, c=30,。,(1),针对所给问题，定义问题的解空间；,(2),确定易于搜索的解空间结构；,(3),以深度优先方式搜索解空间，并在搜索过程中用,剪枝函数,避免无效搜索。,常用,剪枝函数,：,用,约束函数,在扩展结点处剪去不满足约束的子树；,用,限界函数,剪去得不到最优解的子树。,回溯法的基本思想,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。,在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为,h(n),，则回溯法所需的计算空间通常为,O(h(n),。而显式地存储整个解空间则需要,O(2,h(n),),或,O(h(n)!),内存空间。,回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。,void,backtrack,(int t),if,(tn),output,(x);,else,for,(int i=,f,(n,t);i0) ,if,(,f,(n,t)=,g,(n,t),for (int i=,f,(n,t);in),output,(x);,else,for,(int i=0;in),output,(x);,else,for,(int i=t;i n) /,到达叶结点,更新最优解,bestw; return;,r -= wi;,if,(cw + wi bestw) ,xi = 0; /,搜索右子树,backtrack,(i + 1); ,r += wi;,图的m着色问题,给定无向连通图,G,和,m,种不同的颜色。用这些颜色为图,G,的各顶点着色，每个顶点着一种颜色。是否有一种着色法使,G,中每条边的,2,个顶点着不同颜色。这个问题是图的,m,可着色判定问题。,若一个图最少需要,m,种颜色才能使图中每条边连接的,2,个顶点着不同颜色，则称这个数,m,为该图的色数。求一个图的色数,m,的问题称为图的,m,可着色优化问题。,解向量：,(x,1, x,2, , x,n,),，,xi,表示,顶点,i,所着,颜色,可行性约束函数：顶点,i,与已着色的相邻顶点颜色不重复。,void Color:,Backtrack,(int t),if (tn) ,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);,bool Color:,Ok,(int k),/,检查颜色可用性,for (int j=1;j=n;j+),if (akj=1),return true;,若存在，找出图的,m,着色的所有可能方案,复杂度分析,图,m,可着色问题的解空间树中内结点个数是,对于每一个内结点，在最坏情况下，用,ok,检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时,O(mn),。因此，回溯法总的时间耗费是,3-,色问题,(3-coloring problem),Input:,一个无向图,G=(V, E),， 要求给每个点着色,1,或,2,， 或,3,，使得任意两个相邻的点着不同的颜色。,合法（,legal,）的着色：任意两个相邻的点着不同的颜色。,不合法（,illegal,）的着色：存在两个相邻的点着相同的颜色。,局部着色,(partial):,一个图的部分点的着色，而且相邻点着不同颜色。,一个合法的着色,(1,2,1,2,1,3,1):,一个不合法的着色,(1,2,1,2,1,2,1),：,a,e,f,b,g,c,b,a,d,c,e,d,g,f,3-,着色的表示,:,n-tuple(c,1, c,2, c,n,),其中每个,c,i,1,，,2,，,3,表示顶点,i,着的颜色。,可能的着色方案,(,合法的,+,不合法的,),：,3,n,种,-,每个顶点有,3,种可能的着色方案，,n,个顶点的总着色方案有,3*3*3,*3= 3,n,n,个,用,3,重搜索树表示所有可能的着色方案，从根到树叶的每一条路径表示一种着色方案,开始,b,c,a,共有,3,n,个叶子，即,3,n,种不同的着色方案,共有,3,n,+3,n-1,+1 = (3,n+1,-1)/2,个节点,回溯算法,-,增长,+,回溯,每次产生一个节点,检查它与从根到它的路上的节点的着色是否冲突。,如果从根到这个节点的路对应一个合法着色，结束。,如果这条路的长度,n,并且对应一个局部着色，则生成一个此节点的儿子（增长）,如果这条路的长度,n,并且对应的不是局部着色,（即有,相邻点着同色），把这个点标记为死节点，生成同一层的新的节点并着另一种颜色。,如果没有未曾使用过的颜色（,3,种颜色已用完），则回到父节点一层，生成新的节点并着另一种颜色。,a,b,d,c,e,a=1,b=1,&,b=2,&,c=1,&,c=2,c=3,d=1,e=1,&,e=2,&,e=3,&,d=2,&,d=3,e=1,共产生了,14,个节点，而一棵完整的三重树有,(3,5+1,-1)/2=364,个节点。,节点是以深度优先的方式生成的,只需要存储从根到当前活点的路径,(,实际上只需要记住到目前的局部着色,),&,An instance of 3-coloring:,3-,着色问题的递归式算法,Input: n,个节点的无向图(邻接矩阵,),Output:3-coloring c1,2,n or vertices, each ci is 1, or 2, or 3.,for,k,1 to,n,c,k,=0,end for,flag,false,graphcolor(1),if,flag,then output,c,else output,“,no solution,”,Procedure graphcolor(,k,),for color =1 to 3,c,k,color,if,c,is a legal coloring then set,flag,true and exit,else if,c,is partial then graphcolor(,k,+1),end for,graphcolor,的运行过程,k=1; color=1;c1=1;,call graphcolor(2),k=2,color=1,c2=1,判断当前的着色是否合理,是,;call graphcolor(3),；增长,否,;color=2; c2=2;,判断当前着色是否合理,是,call graphcolor(3);,增长,否,color=3;c2=3;,判断当前着色是否合理,是,call graphcolor(3);,增长,否,; k=1; color=2; c1=2;,call graphcolor(2),局部判断,注意：当考察当前路径对应的着色是否是局部着色时， 只需要判断,当前,的活点与此路径上前面的点是否有冲突：即是否与路上的点相邻且同色（通过邻接矩阵判断）。因为此路径上的其他点在之前已经验证过是互不冲突的了。,所以：每增加一个节点，所需时间是,O(n),最坏情况有,O(3,n,),个节点，故时间复杂性是,O(n3,n,).,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,解向量：,(x,1, x,2, , x,n,),显约束：,x,i,=1,2, ,n,隐约束：,1),不同列：,x,i,x,j,2),不处于同一正、反对角线：,|i-j|,|x,i,-x,j,|,bool Queen:,Place,(int k),for (int j=1;jn) sum+;,else,for (int i=1;i=1,while,x,k,4,x,k,x,k,+1,if,x,is legal then set,flag,true and exit from two while loops,else if,x,is partial then,k,k,+1,end while,x,k,=0,k,k,-1,end while,if flag then output,x,else output,“,no solution,”,x1=1,x2=1,&,2,&,3,x3=1,&,&,&,&,4,&,1,2,&,x4=1,&,2,3,&,&,4,&,3,&,4,x1=2,&,x2=1,2,&,&,3,4,x3=1,&,x4=1,&,2,3,legal,共有,27,个节点，比整个,4-,重搜索树,的节点个数,341,少很多,n-queens,的时间复杂性,最坏的情况下时间复杂性是,O(n,n+1,),k=1(,第一层,); n,个节点；每个节点,0,次比较；,n*0,k=2(,第二层,); n,2,个节点；每个节点,1,次比较；,n,2,*1,k=3(,第三层,); n,3,节点；每个节点,2,次比较；,n,3,*2,总时间：,n,2,*1+n,3,*2+,+n,n,*(n-1) =O(n,n+1,),分支限界法的基本思想,分支限界法与回溯法,求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,常见的两种分支限界法,队列式(,FIFO),分支限界法,按照队列先进先出（,FIFO）,原则选取下一个节点为扩展节点。,优先队列式分支限界法,按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,