算法设计与分析回溯法

1、第七章回溯法§ 1.回溯法的基本思想回溯法有“通用的解题法”之称应用回溯法解问题时，首先应该明确问题的解空间一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以 看作是由若干个小的决策组成很多时候它们构成一个决策序列解决一个问题 的所有可能的决策序列构成该问题的解空间.解空间中满足约束条件的决策序列 称为可行解.一般说来，解任何问题都有一个目标，在约束条件下使目标达优的 可行解称为该问题的最优解.在解空间中，前k项决策已经确定的所有决策序列 之集称为k定子解空间.0定子解空间即是该问题的解空间.例1 旅行商问题：某售货员要到若干个城市去推销商品.已知各个城市之 间的路程（或旅

2、费）.他要选定一条从驻地出发，经过每个城市一遍，最后回到 驻地的路线，使得总的路程（或总旅费）最小.我们用一个带权图G（V, E）来表示，顶点代表城市，边表示城市之间的道路 图中各边所带的权即是城市间的路程（或城市间的旅费）10求赋权图G的具有最小权的Hamilton 圈则旅行商问题即是：在带权图G中找到一条路程最短的周游路线，即权值之和最小的Hamilton圈.如果假定城市A是驻地.则推销员从A地出发，第一站有3种选择：城市B、 C或城市D;第一站选定后，第二站有两种选择：如第一站选定B，则第二站只能选C、D两者之一.当第一、第二两站都选定时，第三站只有一种选择：比如， 当第一、第二两站先后

3、选择了 B和C时，第三站只能选择D.最后推销员由城市D 返回驻地A.推销员所有可能的周游路线可由 下面的图反映出来.例2.定和子集问题：已知一个正实数的集合 A=ww2,wn和正实数M.试求A的所有子集S,使得S中的数之和等于M.这个问题的解可以表示成0/1数组（XX2,，Xn），依据W1是否属于S，洛分别取值1或0.故解空间中共有2n个元素.它的树结构是一棵完全二叉树.例3. 4皇后问题：在4X 4棋盘上放置4个皇后，要使得每两个之间都不能互相攻击，即任意两个皇后都不能放在同一行、同一列及同一对角线上将4个皇后分别给以1到4的编号，这个问题的解决就是要安排4个皇后的 位置.因而，每个决策序列

4、由4个决策组成：Pi，P2, P3，R，这里Pk代表安排第 k个皇后的位置，因而有16种可能.该问题的解空间有164个决策序列.这时的约 束条件是：任意两个皇后均不能位于同一行、同一列及同一个对角线上.注意到 这个解空间比较大，从中搜索可行解较为困难 .现在把约束条件中的“任意两个 皇后均不在同一行” 也放在问题中考虑，即:将4个皇后放在4X 4棋盘的不同 行上，使得每两个皇后均不能位于同一列、同一对角线上.则解空间中共有 44个决策序列，因为此时可以假定第 k个皇后处于第k行上.此时的约束条件为：任 意两个皇后均不能位于同一列及同一个对角线上 .事实上，我们还可以用另一种 方法描述，使得解空

5、间进一步缩小.将问题陈述为：将4个皇后放在4X 4棋盘的 不同行、不同列上，使得任意两个皇后均不能处在同一对角线上.这时的解空间应当由4!个决策序列构成.因为此时每个决策序列实际上对应于1,2, 3, 4 的一个排列.我们可以用树来描述解空间.从例3来看，解空间的确定与我们对问题的描述有关.如何组织解空间的结构 会直接影响对问题的求解效率.这是因为回溯方法的基本思想是通过搜索解空间 来找到问题的可行解以至最优解.当所给的问题是从n个元素的集合S中找出满足 某种性质的子集时，相应的解空间树称为子集合树 .此时，解空间有2n个元素， 遍历子集树的任何算法均需'j（2n）的计算时间.如例2.

6、当所给的问题是确定n个 元素的满足某种性质的排列时，相应的解空间树称为排列树，此时，解空间有n!个元素.遍历排列树的任何算法均需（n!）计算时间，如例1和例3.本章只讨论具 有上两类解空间树的求解问题.确定了解空间的组织结构后，回溯法就从开始顶点（解空间树的根顶点）出 发，以深度优先的方式搜索整个解空间.这个开始顶点就成为一个活顶点，同时 也成为当前的扩展顶点.在当前的扩展顶点处，搜索向纵深方向移至一个新顶点. 这个新顶点就成为一个新的活顶点，并且成为当前的扩展顶点.如果在当前的扩 展顶点处不能再向纵深方向移动，则当前的扩展顶点就成为死顶点.此时应往回移动（回溯）至最近一个活顶点处，并使这个活

7、顶点成为当前扩展顶点.回溯法即以这种工作方式递归地在解空间中搜索，直至找到要求的解或解空间中已无活 结点时为止.事实上，当我们将问题的有关数据以一定的方式存储好以后（例如， 旅行商问题存储赋权图的邻接矩阵、定和子集问题是存储已知的n+1个数、4皇后问题用整数对（i,j）表示棋盘上各个位置），不必先建立一个解空间树，然后再 搜索该树寻找所需要的解.回溯法实际上在搜索的同时逐步生成解空间树（实际只需要一部分)也就是说，对于实际问题我们不必要搜索整个解空间为了使搜 索更加有效，我们常常在搜索过程中加一些判断以决定搜索是否该终止或改变路 线.通常采用两种策略来避免无效的搜索，提高回溯法的搜索效率其一是

8、使用约 束函数在扩展顶点处剪去不满足约束的子树；其二是用限界函数(后面将阐述) 剪去不能得到最优解的子树这两种函数统称为剪枝函数运用回溯法解题通常包括以下三个步骤：1) .针对所给问题，定义问题的解空间；2) .确定易于搜索的解空间结构；3) .以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效 的搜索.§ 2.定和子集问题和0/1背包问题定和子集问题可以描述成下列的数学问题：确定所有向量x =(X,X2 , xn)满足：(7.2.1)则0/1背包问题可以(7.2.2)Xi 01, i 72, ,nwixi 二 M如果让wi表示第i件物品的重量，M代表背包的容量，描述为：

9、确定一个向量乂=(治”2, ,xn)满足Xi 0,1, i =1,2, ,n二 Wi Xi 三 M1岂宜s.t. max ' Pi Xj1丄勺这是一个优化问题，与定和子集问题比较，它多出优化函数，但只要求确定一个 最优解，定和子集问题要求确定所有可行解.1 .定和子集问题用回溯法求解定和子集问题的过程也即是生成解空间树的一棵子树的过程， 因为,在搜索期间将剪掉不能产生可行解的子树(即不再对这样的子树进行搜索) 按照前面关于回溯算法的基本思想的说明，搜索是采用深度优先的路线，算法只 记录当前路径.假设当前扩展顶点是当前路径的k级，也就是说当前路径上，心 仁心k已经确定，算法要决定下一步搜

10、索目标.此时，有两种情况：' Wj 片=M 与 ' WjXj ： Mriik1迪迄前一种情况说明当前路径已经建立一个可行解，当前扩展顶点即是一个答案顶点 此时，应该记录已经获得的解(后面的变量取 0),停止对该路径的继续搜索， 返回到前面最近活结点后一种情况出现，算法需要判断是否需要继续向前搜索 显然，只有当v wi7Wj_M时才有必要继续向前搜索.如果集合1-2 <kk 1dmA二WW2,，Wn中的元素是按不降的次序排列的，则上述继续搜索的条件还可以加强为' WjXj' Wj _ M and ' wixi wkM (7.2.3)1 ”k 1 &l

11、t;_ni ii_k上述不等式记做B.程序7-2-1定和子集问题的回溯算法伪代码SumSubset(s,k,r)/ 寻找 W1:n中元素和为M的所有子集.W1:n中元素按不 降次序排列，进入此过程时，X1, . . ., Xk-1的值已经确定.记s= WjXj，r=»Wj,假定 W1 < M, ' Wj_M1 :j <k _1k ：j1:：j :：n1 global in tegerM, n; global real W1: n;2 global boolea n X1: n;3 real r, s; integer k, j;/ 由于 3-1=true，因此 s

12、 + Wk < M4 Xk=1; / 生成左儿子.5 if s + Wk= M thenprint (Xj,j from 1 to k);6 else7 if s + Wk + Wk+1< M then8 SumSubset(s+Wk, k+1, r-Wk);9 en dif10 en dif11 if s + r - Wk - M and s + Wk+1< M then12 Xk=0; / 生成右儿子13 SumSubset(s,k+1,r-Wk);14 en dif15 end SumSubset因为假定W1 <M 送Wj兰M，所以程序开始执行时，B0=true.

13、同样, 1当应程序在递归执行过程中，总是以前提条件B-i=true开始处理第k级顶点的儿子们的生成过程，由第310语句完成，并在此过程中决定是否转到生成下一级顶 点的儿子的生成过程，由1114语句完成.语句11是一个判断条件，如果这个 条件不能满足，则没有必要生成k级顶点的右儿子.而在左儿子被生成后，语句4和语句7决定是否沿着这个左儿子继续搜索.所以该算法所生成的子树的叶顶 点或是某个左儿子，此时找到一个可行解；或者是某个右儿子，此时由根顶点到 该顶点的路径不能延伸为可行解例子：n=6,M=30; W1:6=(5,10,12,13,15,18). 由算法 SumSubset所生成 的解空间树的

14、子树参看 文档SumSubset树.2. 0/1背包问题0/1背包问题是一个优化问题，因此不仅可以使用约束函数，而且可以使用 限界函数做剪枝函数.如果当前背包中的物品总重量是cw,前面k-1件物品都已经决定好是否放入包中，那么第k件物品是否放入包中取决于不等式cw + wk < M是否满足这即是搜索的约束函数另外，我们可以如下确定限界函数回忆背包 问题的贪心算法，当物品按照Pi / Wi _ Pi 4 / Wi 4的规则排序时，最优解是(%,X|，X|,X| q，,Xn)二,1,t,0, ,0)的形式,其中,0乞t乞1.设当前背包中物品的总效益值cp，如下方式确定限界函数：程序7-2-2

15、构造限界函数Bou ndF(cp,cw,k,M) /返回效益值的当前限界gloal n, p1:n,w1:n;integer k,i; real b,c,cp,cw,M;b=cp;c=cw;for i from k+1 to n doc=c+wi;if c < M then b=b+pi;else return b+(1-(c-M)/wi)*pi;en difen dforreturn (b);end BoundF这样确定的限界函数表明，从当前确定的k-1定子解空间中寻求到的可行解 所能达到的效益值以当前限界函数的值为上界.所以，如果搜索最优解的算法在 此之前已经知道大于这个限界值的效益

16、，则没有必要在当前确定的k-1定子解空 间中搜索据此我们给出0/1背包问题的回溯算法程序7-2-3 0/1背包问题的回溯算法BackKnap(M,n,W,P,fw, fp,X)/M 是背包容量.n 件物品,数 W1:n和 P1:n 分/别表示重量和价值，并按单位价值的不增顺序排列下标.fw是背包的最后/重量,fp是背包的最大效益.X1:n中每个元素取0或1值.若物品k未放/入背包，则Xk=0;否则,Xk=1.1 integer n,k,Y1:n,I,X1:n;2 real M,W1:n,P1:n,fw,fp,cw,cp;3 cw=0; cp=0; k=1; fp=-1;4 loop5 whil

17、e k m&& cw+Wk乞 M do / 使用约束函数6 cw=cw+Wk; cp=cp+Pk; Yk=1; k=k+1;7 en dwhile8 if k>n then9 fp=cp; fw=cw;k=n;X=Y;/修改解10 else Yk=0;11 en dif12 while BoundF(cp,cw,k,M)_fpdo13 while k -0 && Yk -1 do14 k=k-1;15 en dwhile16 if k=0 then return endif17 Yk=O;cw=cw-Wk;cp=cp-Pk;18 en dwhile19 k

18、=k+1;20 en dloop21 end BackKnap例子算法采用一个大的循环搜索各条可能的路径.当一条路径的搜索到某一步不 能继续往下搜索时，此时或是因为约束函数不满足，或是因为限界函数不满足.它 们分别在语句57的子循环和语句1218的子循环中达到.这是程序的两个主要 部分，其余主要是处理边界条件，如k > n的验证等.第一种情况出现时，语句811 给出部分处理，剩下的事情交给语句1219来处理.这里给出了搜索退回的方案.下面的也许能够帮助理解本算法.§ 3. n-皇后问题和旅行商问题在第一节已经给出了这两个问题的解空间如果用（Xi%,，XJ表示解,则它是自然数1,

19、2,n的一个排列.对于旅行商问题,我们可以假定 = 1,表示售 货员的驻地是城市1.采用回溯法，对于旅行商问题主要是给出限界函数，而对 于n皇后问题,主要任务是给出约束函数.此时我们可以假定带权图是完全图，这 只要将实际不相邻的两个顶点间用带有权的边连接即可.1.n-皇后问题这里的约束条件是：任何两个皇后都不能位于同一对角线上.如果我们用（i, j）表示棋盘上第i行与第j列交叉的位置.则在同一条平行于主对角线的对角 线上的两点（i,j）和（k,l）满足关系式ij=k-l；而处于同一条平行于副对角线 的对角线上的两点（i, j）和（k,l）则满足关系式r j =k l .将这两个关系式略作 变形

20、即得两种情况的统一表示：|i -k|=|j -丨 |（7.3.1）反之，如果棋盘上的两点（i,j）和（k,l）满足关系式（7.3.1）,则它们一定位于 同一条对角线上.所以，如果（X1,X2，Xn）是n皇后问题的一个可行解，则对任何 i = k ,等式|i -k 冃人-兀 |（7.3.2）均不得成立.这即是约束条件.如果假定前面的k-1个皇后位置已经排好，现在要 安排第k个皇后的位置，必须使得xj Xk ,而且等式（7.3.2）不成立,i =1,2/ , k -1.算法可以这样设计：对于xk所有可能的取值，验证上述条件.对 于每个取值xk,验证它是否满足上述两个条件，用一个boolean函数P

21、lace来完 成.程序7-3-1皇后冋题放置函数Place（k）/ 如果第k个皇后能放在第Xk列，则返回true,否则返/回false. X 是一个全程数组，进入此过程时已经设置了 k个值global X1:k; integer i,k;i=1;while i<k doif Xi=Xk or |Xi-Xk|= |i-k|thenreturn (false);en difi=i+1;en dwhilereturn (true);end Place使用函数Place能使求n-皇后问题的回溯算法具有简单的形式程序7-3-2求n-皇后问题可行解的回溯算法n Quee ns(n)in teger

22、k,n ,X1: n;X1=0; k=1; /k是当前行,Xk是当前列while k>0 doXk=Xk+1; 转到下一列while Xk - n &&Place(k)=false doXk=Xk+1;en dwhileif Xk - n thenif k=n thenPrin t(X);else k=k+1; Xk=0; / 转到下一行en difelse k=k-1; 回溯en difen dwhileend n Quee ns程序nQueens处理4-皇后问题的执行过程参看文档” 4-皇后结构树”2.旅行商问题用1,2,n代表n个顶点，一个周游讣2叮1用数组(ii2

23、,，in)表示，它是旅行商问题的一个可行解如果可行解的前k-1个分量Xi,X2,，Xk已经确定,则判(733)定X1X2XkMk能否形成一条路径,只需做k-1次比较：Xk = X1 , Xk = X2, Xk = Xk J ,此即构成旅行商问题的约束条件用w(i,j)记边(i,j)的权值.cl记当前路径X1X2Xk丄的长度,即Cl = W(Xi,Xi 1).如果当前知道的最短周游的线路长度1空工为fl,则当cl w(k1, k) . fl(7.3.4)时,%X2XkHk不会是最短周游路线的一部分,在解空间树中,相应的一枝被剪 掉,(7.3.4)即是旅行商问题的限界条件.此外，当k二n时，若cl

24、 w(k -1, k) w(k,1) ： fl(7.3.5)则算法需要更新fl ,令fl 二 cl w(k -1,k)w(k,1)(7.3.6)程序7-3-3旅行商冋题的约束条件函数NextValue(k) /从顶点1出发的路径，如果第k个顶点是顶点Xk，则返回 /true,否则返回false. X是一个全程数组，进入此过程时已经设置了k/个值，其中X1=1, Xk是当前扩展顶点.global X1:k;integer i,k;i=1;while i<k doif Xi=Xk thenreturn (false);en dif i=i+1;en dwhile return (true);

25、 end NeXtValue使用函数NextValue能使求旅行商问题的回溯算法具有简单的形式程序7-3-4求旅行商问题的回溯算法BackTSP(n,W) 求图G的从顶点1出发的最短周游(Hamilton圈)路线.W /是G的邻接矩阵.Xk是当前路径的第k个顶点,c是当前路径的长度，fl /是当前所知道的最短的周游(Hamilton圈)的长度in tegerk,n ,X1: n;real W1: n,1: n,cl,fl;X2=1; k=2; cl=0; fl=+ :;while k>1 doXk=(Xk+1) modn; 给 Xk预分配一个值for j from 1 to n doif

26、 NextValue(k)=truethen exit; endifXk=(Xk+1)mod n;en dforif fl < cl+Wk-1,k or k=n and fl<cl+Wk-1,k+WX n,1the n k=k-1; / 回溯elif k=n && fl _cl+Wk-1,k+WXk,1the nfl = cl+Wk-1,k+WXk,1; k=k-1; /回溯else cl= cl+Wk-1,k; k=k+1;/继续纵深搜索en difen dwhileend BackTSP旅行商问题的例子§4图的着色问题已知一个无向图G和m种颜色，在只准

27、使用这m种颜色对图G的顶点进行着 色的情况下，是否有一种着色方法，使图中任何两个相邻的顶点都具有不同的颜 色？如果存在这样的着色方法，则说图 G是m-可着色的，这样的着色称为图G的一种m-着色.使得G是m-可着色的最小数m称为图G的色数.这一节所讨论的 图的着色问题是：给定无向图G和m种颜色，求出G的所有m-着色.用G的邻接矩阵W表示图G, Wi,j=1表示顶点i与j相邻（有边相连），否 则Wi,j=0. m 种颜色分别用1, 2,m表示.图G的每一种m-着色都可以用 一个n-维数组X1:n表示.Xi=k 表示顶点i被着上颜色k.简单分析可知，解 空间是一个完全的m-叉树，共有n+1级.X是可

28、行解，当且仅当Wi,j=1二 Xi =Xj,(741)此即是约束条件假如已经给前j-1个顶点着好颜色，即X1,Xj-1已经确 定，则确定第j个顶点所着的颜色Xj时,根据约束条件，应该验证条件Wi,j=1= Xi =Xj, 1<i<j(7.4.2)是否满足.这可以由下面程序完成程序7-4-1下一步选颜色算法NextColor ( j ) /进入此过程前，X1,Xj-1已经确定且满足约束条件. /本过程给Xj确定一个整数k，0_km如果还有一种颜色k可以分配 /给顶点j (满足约束条件)，则令Xj = k；否则，令Xj = 0.globa l integer m, n, X1:n, W

29、1:n, 1:n;integer j, k;loopXj=(Xj+1) mod (m+1);if Xj=0 then returnendiffor i from 1 to j-1 do /验证约束条件if Wi, j=1 && Xi=Xjthen exitendifen dforif i=j then returnendif / 找到一种颜色en dloopend NextColor在程序NextColor开始执行之前，诸Xk均已经有值.这可在着色问题的回溯算 法初次调用该函数时赋予初值：Xi=0,i=1,2,n.程序7-4-2 图的着色问题回溯算法GraphColor (k)

30、 /采用递归.W1:n, 1:n 是图G的邻接矩阵，1,2, /,m代表m种颜色.k是下一个要着色的顶点.global integer m, n, X1:n, W1:n, 1:n;loopNextColor ( k ); / 确定 Xk的取值if Xk=0 then exitendif /说明没有颜色可以分配给第 k个点if k=n then /已经找到一种着色方法print (X);else GraphColor ( k+1 ) ; / 递归 en difen dloopend GraphColor正好用3种颜色的解只有12个.§ 5.回溯法的效率分析回溯法是以深度优先的方式系统地

31、搜索问题的解空间.解空间是由所有可能 的决策序列（为公2,，人）构成.在搜索过程中，采用剪枝函数尽量避免无意义的 搜索.通过前面的具体实例的讨论容易看出，一个回溯算法的效率在很大程度上 依赖于以下几个因素：1) .产生Xk的时间；2) . Xk的取值范围；3) .计算约束函数的时间和计算限界函数的时间；4) .满足约条件及限界条件的Xk的个数.一般来说，一个好的约束函数能够显著地减少所生成的顶点的数目.但是，这样的约束函数往往计算量较大.因此在选择约束函数时通常存在着顶点数与约 束函数计算量之间的折中.我们希望总的计算时间较少.为了提高效率，通常采用 所谓的“重排原理”.对于许多问题而言，在进

32、行搜索试探时，选取 Xk值的顺序 是任意的.这提示我们，在其它条件相同的前提下，如果让取值最少的Xk优先.则将会使算法更有效.如文档“解空间树比较”中的图，是同一个问题的不同的 解空间树，从中可以体会到这种策略的效力.在第一个图中，若从第1级剪去一棵子树，则从所有应当考虑三元组中一次 消去12个三元组；在第二个图中，虽然同样从第 1级剪去一棵子树，却只从应 当考虑的三元组中一次消去8个三元组.前者的效果显然比后者好.解空间的结构一经选定，影响回溯法效率的前三个因素就可以确定，只剩下生成顶点的数目是可变的，它将随问题的具体内容以及拟定的不同生成方式而变 动.即使是对于同一问题的不同实例，回溯法所

33、产生的顶点的数目也会有很大变 化.对于一个实例，回溯法可能只产生 O(n)个顶点.而对于另一个相近的实例，回溯法可能产生解空间中的所有顶点.如果解空间的顶点数是2n或n!，则在最坏情况下，回溯法的时间耗费一般为 0(p(n)2n)或0(q(n)n!).其中，p(n)和q(n)均 为n的多项式.对于一个具体问题来说，回溯法的有效性往往就体现在当问题实 例的规模n较大时，它能够用很少的时间求出问题的解 .而对于一个问题的具体 实例，我们又很难预测回溯法的算法行为.特别地，很难估计在解这一具体实例 时所产生的顶点数.这是在分析回溯法效率时遇到的主要困难 .下面所介绍的概 率方法也许对解决这个问题有所

34、帮助.当用回溯法解某一个具体问题实例时，可用蒙特卡罗方法估算回溯法将要产 生的顶点数目.该方法基本思想是在解空间树上产生一条随机路径，然后沿此路 径来估算结空间中满足约束条件的顶点数m.设x是所产生的随机路径上的一个顶点，且位于解空间树的第i级上.对于x的所有儿子顶点，用约束函数检测出 满足约束条件的顶点数 m.路径上的下一个顶点是从x的m个满足约束条件的儿 子顶点中随机选取的.这条路径一直延伸到一个叶顶点或一个所有儿子顶点都不满足约束条件的顶点为止.通过这些m的值，就可估计出解空间树中满足约束条 件的顶点的总数m.在用回溯法求问题的所有可行解时，这个数特别有用.因为在这种情况下，解空间所有满

35、足约束条件的顶点都必须生成.若只要求用回溯法找出问题的一个解，则所生成的顶点一般只是 m个满足约束条件的顶点中的一部分 此时用m来估计回溯法生成的顶点数就过于保守了 .为了从m的值求出m的值，还需要对约束函数做一些假定.在估计m时，假 定所有约束函数是静态的，即在回溯法执行过程中，约束函数并不随随算法所获 得信息的多少而动态地改变.进一步还假定对解空间树中同一级的顶点所用的约 束函数是相同的.对于大多数回溯法，这些假定都太强了 .实际上，在大多数回溯 法中，约束函数是随着搜索过程的深入而逐渐加强的.在这种情形下，按照前面所做假定来估计m就显得保守.如果将约束函数变化的因素也加进来考虑，所得 出的满足约束条件的顶点总数将会少于 m，而且会更精确些.在静态约束函数假设下，第一级共有 m个满足约束条件的顶点.若解空间的同 一级的顶点具有相同的出度，则在第一级上的每个顶点将会有m儿子满足约束条件.因此，第二级将会有mm个满足约束条件的顶点.同理，第三级上满足