第六章 回 溯 法 § 1. 回溯法的基本思想 回溯法有“通用的解题法”之称。应用回溯法解问题时，首先应 该明确问题的解空间。一个复杂问题的解决往往由多部分构成，即， 一个大的解决方案可以看作是由若干个小的决策组成。 很多时候它们 构成一个决策序列。 解决一个问题的所有可能的决策序列构成该问题 的解空间。 解空间中满足约束条件的决策序列称为可行解。 一般说来， 解任何问题都有一个目标， 在约束条件下使目标达优的可行解称为该 问题的最优解。在解空间中，前 k 项决策已经确定的所有决策序列之 集称为 k 定子解空间。 0 定子解空间即是该问题的解空间。 例 1．旅行商问题 : 某售货员要到若干个城市去推销商品。已知各 个城市之间的路程（或旅费） 。他要选定一条从驻地出发，经过每个 城市一次，最后回到驻地的路线，使得总的路程（或总旅费）最短。 我们用一个带权图 G(V, E)来表示，顶点代表城市，边表示城市之 间的道路。图中各边所带的权即是城市间的距离（或城市间的旅费） 。 30 5 4 6 10 20 具有四个顶点的带权图 则旅行商问题即是： 在带权图G 中找到一条路程最短的周游路线，即 A C D B 权值之和最小的Hamilton圈 。 如果假定城市 A是驻地。则推销员从A地出发，第一站有3 种选 择：城市B、C 或城市D；第一站选定后，第二站有两种选择：如第 一站选定B，则第二站只能选C、D 两者之一。当第一、第二两站都 选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了 B 和C 时，第三站只能选择D。最后推销员由城市D 返回驻地A。推 销员所有可能的周游路线可由下面的图反映出来 。 例 2． 定和子集问题： 已知一个正实数的集合 },,,{ 2 1 n wwwAL= 和正实数 M．试求 A 的所有子集 S，使得 S 中的数之和等于 M。 这个问题的解可以表示成 0/1 数组 (x 1 , x 2 , . . . , x n )，依据 w i 是否 属于 S， x i 分别取值 1 或 0。故解空间中共有 2 n 个元素。它的树结构 是一棵完全二叉树 。 例 3． 4 皇后问题 : 在 4× 4 棋盘上放置 4 个皇后，且使得每两个之 间都不能互相攻击，即任意两个皇后都不能放在同一行、同一列及同 一对角线上。 将 4 个皇后分别给以 1 到 4 的编号， 这个问题的解决就是要安排 4 个皇后的位置。因而，每个决策序列由 4 个决策组成： P 1 ， P 2 ， P 3 ， P 4 ，这里 P k 代表安排第 k 个皇后的位置，因而有 16 种可能。该问题 的解空间有 16 4 个决策序列。这时的约束条件是 : 任意两个皇后均不 能位于同一行、 同一列及同一个对角线上 。 注意到这个解空间比较大， 从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不 在同一行 ” 也放在问题中考虑，即：将 4 个皇后放在 4× 4 棋盘的不 同行上，使得每两个皇后均不能位于同一列、同一对角线上 。则解 空间中共有 4 4 个决策序列，因为此时可以假定第 k 个皇后处于第 k 行上。此时的约束条件为： 任意两个皇后均不能位于同一列及同一个 对角线上。 事实上，我们还可以用另一种方法描述，使得解空间进一 步缩小。将问题陈述为：将 4 个皇后放在 4× 4 棋盘的不同行、不同 列上，使得 任意两个皇后均不能处在同一对角线上 。这时的解空间应 当由 4！个决策序列构成。因为此时每个决策序列实际上对应于 {1, 2, 3, 4}的一个排列。我们可以用树来描述解空间。 从例3来看，解空间的确定与我们对问题的描述有关。如何组织 解空间的结构会直接影响对问题的求解效率。 这是因为回溯方法的基 本思想是通过搜索解空间来找到问题的可行解以至最优解。 当所给的 问题是从 n 个元素的集合S 中找出满足某种性质的子集时， 相应的解 空间树称为子集合树。此时，解空间有 n 2 个元素，遍历子集树的任 何算法均需 )2( n ? 的计算时间。如例2。当所给的问题是确定 n个元 素的满足某种性质的排列时，相应的 解空间树称为排列树，此时，解 空间有 !n 个元素。遍历排列树的任何算法均需 )!(n? 计算时间，如例 1 和例3。本章只讨论具有上两类解空间树的求解问题。 确定了解空间的组织结构后，回溯法 就从开始顶点（解空间树的 根顶点）出发，以深度优先的方式搜索整个解空间。这个开始顶点就 成为一个活顶点， 同时也成为当前的扩展顶点。 在当前的扩展顶点处， 搜索向纵深方向移至一个新顶点。这个 新顶点就成为一个新的活顶 点，并且成为当前的扩展顶点。如果在当前的扩展顶点处不能再向纵 深方向移动，则当前的扩展顶点就成为死顶点。此时应往回移动（回 溯）至最近一个活顶点处，并使这个活顶点成为当前扩展顶点。回溯 法即以这种工作方式递归地在解空间中搜索， 直至找到要求的解或解 空间中已无活结点时为止。事实上，当我们将问题的有关数据以一定 的方式存储好以后（例如，旅行商问题存储赋权图的邻接矩阵、定和 子集问题是存储已知的 n+1 个数、4 皇后问题用整数对(i,j)表示棋 盘上各个位置） ，不必先建立一个解空间树，然后再搜索该树寻找所 需要的解。回溯法实际上在搜索的同时逐步生成解空间树（实际只需 要一部分） 。也就是说，对于实际问题我们不必要搜索整个解空间。 为了使搜索更加有效， 我们常常在搜索过程中加一些判断以决定搜索 是否该终止或改变路线。通常采用两种策略来避免无效的搜索，提高 回溯法的搜索效率。 其一是使用约束函数在扩展顶点处剪去不满足约 束的子树；其二是用限界函数（后面将阐述）剪去不能得到最优解的 子树。这两种函数统称为剪枝函数。 运用回溯法解题通常包括以下三个步骤： 1).针对所给问题，定义问题的解空间； 2).确定易于搜索的解空间结构； 3).以深度优先的方式搜索解空 间，并且在搜索过程中用剪枝函 数避免无效的搜索。 §2.定和子集问题和 0/1 背包问题 定和子集问题可以描述成下列的数 学问题：确定所有向量 ),,,( 21 n xxxxL= 满足： Mxw nix i ni i i = =∈ ∑ ≤≤1 ,,2,1},1,0{L (7.1) 如果让w i 表示第i 件物品的重量，M 代表背包的容量，则0/1 背 包问题可以描述为：确定一个向量 ),,,( 21 n xxxxL= 满足 i ni i i ni i i xpts Mxw nix ∑ ∑ ≤≤ ≤≤ ≤ =∈ 1 1 max.. ,,2,1},1,0{L (7.2) 这是一个优化问题，与定和子集问题比较，它多出优化函数，但只要 求确定一个最优解，定和子集问题要求确定所有可行解。我们先来处 理定和子集问题。 (一).定和子集问题 用回溯法求解的过程也即是生成解空间树的一棵子树的过程， 因为期 间将剪掉不能产生可行解的子 树（即不再对这样的子树进行搜索） 。 按照前面关于回溯算法的基本思想的说明， 搜索是采用深度优先的路 线，算法只记录当前路径。假设当前扩展顶点是当前路径的k 级，也 就是说当前路径上，x i ，1 ≤i≤k 已经确定，算法要决定下一步搜索目 标。此时，有两种情况： Mxw i ki i = ∑ ≤≤1 与 Mxw i ki i < ∑ ≤≤1 前一种情况说明当前路径已经建立一个可行解， 当前扩展顶点即是一 个答案顶点。此时应停止对该路径的继续搜索，返回到前面最近活顶 点。后一种情况出现，算法需要判断是否需要继续向前搜索。显然， 只有当 Mwxw nik ii ki i ≥+ ∑∑ ≤≤+≤≤ 11 时才有必要继续向前搜索。如果集合 },,,{ 2 1 n wwwAL= 中的元素是按不降的次序排列的，则上述继续搜 索的条件还可以加强为 MwxwandMwxw ki ki i nik ii ki i ≤+≥+ + ≤≤≤≤+≤≤ ∑∑∑ 1 111 (7.3) 上述不等式记做B k 。 定和子集问题的回溯算法伪代码 SumSubset(s,k,r) // 寻找W[1:n]中元素和为 M 的所有子集。 //W[1:n]中元素按不降次序排列， 进入此过程时， X[1], . . . , //X[k-1]的值已经确定。 记 ∑ ?≤≤ = 11 ][][ kj jXjWs ， ∑ ≤≤ = njk jWr ][ //假定W[1] ≤ M, ∑ ≤≤ ≥ nj MjW 1 ][ 1 global integer M, n; global real W[1:n]; 2 global boolean X[1:n]; 3 real r, s; integer k, j; //由于B k-1 =true，因此s + W[k] ≤ M 4 X[k]=1; // 生成左儿子。 5 if s + W[k]= M then print (X[j],j from 1 to k); 6 else 7 if s + W[k] + W[k+1] ≤ M then 8 SumSubset(s+W[k], k+1, r-W[k]); 9 endif 10 endif 11 if s + r – W[k] ≥ M and s + W[k+1] ≤ M then 12 X[k]=0; //生成右儿子 13 SumSubset(s,k+1,r-W[k]); 14 endif 15 end SumSubset 因为假定 W[1] ≤ M， ∑ ≤≤ ≥ nj MjW 1 ][ ，所以程序开始执行时， B 0 =true。同样，程序在递归执行过程中，总是以前提条件 B k-1 =true 开始处理第k级顶点的儿子们的生成过程，由第3～10语句完成，并 在此过程中决定是否转动生成下一级顶点的儿子的生成过程， 由11～ 14语句完成。语句 11是一个判断条件，如果这个条件不能满足，则 没有必要生成k级顶点的右儿子。而在左儿子被生成后，语句4 和语 句7决定是否沿着这个左儿子继续搜索。 所以该算法所生成的子树的 叶顶点或是某个左儿子，此时找到一个可行解；或者是某个右儿子， 此时由根顶点到该顶点的路径不能延伸为可行解。 例 子 ： n=6,M=30; W[1:6]=(5 ,10,12,13,15,18). 由 算 法 SumSubset所生成的解空间树的子树参看文档SumSubset树。 (二).0/1背包问题 0/1背包问题是一个优化问题,因此 不仅可以使用约束函数,而且可以 使用限界函数做剪枝函数.如果当前背 包中的物品总重量是 cw,前面 k-1 件物品都已经决定好是否放入包中,那么第 k 件物品是否放入包 中取决于不等式cw + w k ≤ M 是否满足.这即是搜索的约束函数.另外, 我们可以如下确定限界函数.回忆可分割的 0/1 背包问题的贪心算法, 当物品的按照 11 // ++ ≥ iiii wpwp 的规则排序时,最优解是 )0,,0,,1,,1(),,,,,,( 111 LLLLtxxxxx nlll = +? 的形式,其中, 10 ≤≤t . 设当前背包中物品的总效益值时cp,如下方式确定限界函数: 构造限界函数 BoundF(cp,cw,k,M) //返回效益值的当前限界 gloal n, p[1:n],w[1:n]; integer k,i; real b,c,cp,cw,M; B=cp;c=cw; for i from k+1 to n do c=c+w[i]; if c < M then b=b+p[i]; else return (b+(1-(c-M))/w[i])*p[i]; endif endfor return (b); end BoundF 这样确定的限界函数表明,从当前确定的 k-1 定子解空间中寻求到的 可行解所能达到的效益值以当前限界函数的值为 上界.所以,如果搜 索最优解的算法在此之前已经知道大于 这个限界值的效益,则没有必 要在当前确定的 k-1 定子解空间中搜索.据此我们给出 0/1 背包问题 的回溯算法. 0/1背包问题的回溯算法 BackKnap(M,n,W,P,fw, fp,X)//M是背包容量.n件物品,数W[1:n] //和P[1:n] 分别表示重量和价值,fw 是背包的最后重量,fp 是 //背包的最大效益.X[1:n]中美国元素取0或1值.若物品k未放 //入背包,则X[k]=0;否则,X[k]=1. 1 integer n,k,Y[1:n],I,X[1:n]; 2 real M,W[1:n],P[1:n],fw,fp,cw,cp; 3 cw=0; cp=0; k=1; fp=-1; 4 loop 5 while k≤n && cw+W[k]≤ M do //使用约束函数 6 cw=cw+W[k]; cp=cp+P[k]; Y[k]=1; k=k+1; 7 endwhile 8 if k>n then 9 fp=cp; fw=cw; k=n; X=Y;//修改解 10 else Y[k]=0; 11 endif 12 while BoundF(cp,cw,k,M)≤fp do 13 while k≠0 && Y[k]≠1 do 14 k=k-1; 15 endwhile 16 if k=0 then return endif 17 Y[k]=0;cw=cw-W[k];cp=cp-P[k]; 18 endwhile 19 k=k+1; 20 endloop 21 end BackKnap 算法采用一个大的循环搜索各条可能的 路径.当一条路径的搜索到某 一步不能继续往下搜索时,此时或是因 为约束函数不满足,或是因为 限界函数不满足.它们分别在语句 5 ~7 的子循环和语句 12~18 的子循 环中达到 .这是程序的两个主要部分 ,其余主要时处理边界条件 ,如 k > n 的验证等 . 第一种情况出现时 ,语句 8~11 给出部分处理 ,剩下的事情 交给语句 12~19 来处理 .这里给出了搜索退回的方案 . §3.n-皇后问题和旅行商问题 在第一节已经给出了这两个问题的解空间.如果用 ),,,( 21 n xxxL表示解,则它是自然数 },,2,1{ nL的一个排列.对于旅 行商问题,我们可以假定 1 1 =x ,表示售货员的驻地是城市 1.采用回 溯方法,对于 n 皇后问题,主要任务是给出约束函数,对于旅行商问题 主要是限界函数,因为此时我们可以假 定带权图是完全图,这只要将 实际不相邻的两个顶点间用带有权 ∞的边连接即可. (一).n-皇后问题 这里的约束条件是: 任何两个皇后都不能位于同一对角线上.如 果我们用 ),( ji 表示棋盘上第i行与第j列交叉的位置.则在同一条平 行于主对角线的对角线上的两点 ),( ji 和 ),( lk 满足关系式 lkji ?=? ; 而处于同一条平行于副对角线的对角线上的两点 ),( ji 和 ),( lk 则满足 关系式 lkji +=+ .将这两个关系式略作变形记得 |||| ljki ?=? (7.3.1) 反之,如果棋盘上的两点 ),( ji 和 ),( lk 满足关系式 (7.3.1),则它们一 定位于同一条对角线上.所以,如果 ),,,( 21 n xxxL是 n 皇后问题的一 个可行解,则对任何 ki ≠ ,等式 |||| ki xxki ?=? (7.3.2) 均不得成立.这即是约束条件. 如果假定前面的 k-1 个皇后位置已经 排好,现在要安排第 k 个皇后的位置,必须使得 ki xx ≠ ,而且等式 (7.3.2)不成立, 1,,2,1 ?= kiL.算法可以这样设计,对于 k x 所有可 能的取值,验证上述条件,对于满足条件的 k 取最大者.而对于每个取 值 k x ,验证它是否满足上述两个条件,用一个 boolean 函数 Place 来 完成. Place(k)//如果第k个皇后能放在第X[k]列,则返回true,否则返 //回false.X 是一个全程数组,进入此过程时已经设置了k 个值 global X[1:k]; integer i,k; i=1; while i<k do if X[i]=X[k] or |X[i]-X[k]|= |i-k| then return (false); endif i=i+1; endwhile return (true); end Place 使用函数Place 能使求n-皇后问题的回溯算法具有简单的形式 求n-皇后问题可行解的回溯算法 nQueens(n) integer k,n,X[1:n]; X[1]=0; k=1; //k是当前行,X[k]是当前列 while k>0 do X[k]=X[k]+1;//转到下一列 while X[k]≤ n && Place(k)=false do X[k]=X[k]+1; endwhile if X[k]≤ n then if k=n then Print(X); else k=k+1; X[k]=0; //转到下一行 endif else k=k-1;//回溯 endif endwhile end nQueens 程序 nQueens 处理 4- 皇后问题的执行过程参看文档”4-皇后结构 树”. (二).旅行商问题 用 1,2,…,n 代表 n 个顶点,一个周游 121 iiii n L用数组 ),,,( 21 n iiiL表 示,它是旅行商问题的一个可行解.如果可行解的前 k-1 个分量 121 ,,, ?k xxxL已经确定,则判定 kk xxxx 121 ? L能否形成一条路径,只 需做k-1 次比较: ,,,, 121 ? ≠≠≠ kkkk xxxxxxL (7.3.3) 此即构成旅行商问题的约束条件.用 w(i,j)记边(i,j)的权值.cl 记 当前路径 121 ?k xxxL的长度,即 ∑ ?≤≤ + = 21 1 ),( ki ii xxwcl .如果当前知道 的最短周游的线路路长度为fl,则当 flkkwcl >?+ ),1( (7.3.4) 时, kk xxxx 121 ? L不会是最短周游路线的一部分,在解空间树中,相 应的一枝被剪掉,(7.3.4)即是旅行商问题的限界条件.此外， 当 nk = 时，若 flkwkkwcl <+?+ )1,(),1( (7.3.5) 则算法需要更新 fl,令 )1,(),1( kwkkwclfl +?+= (7.3.6) 旅行商问题的约束条件函数 NextValue(k) //从顶点 1 出发的路径，如果第 k 个顶点是顶点 //X[k]，则返回 true,否则返回 false.X 是一个全程数组,进入 //此过程时已经设置了 k 个值，其中 X[1]=1, X[k]是当前扩展 //顶点。 global X[1:k]; integer i,k; i=1; while i<k do if X[i]=X[k] then return (false); endif i=i+1; endwhile return (true); end NextValue 使用函数NextValue能使求旅行商问题的回溯算法具有简单的形式 求旅行商问题的回溯算法 BackTSP(n,W) // 求图G的从顶点1出发的最短周游 （Hamilton圈） //路线。W是G的邻接矩阵。X[k]是当前路径的第k个顶点,c是 //当前路径的长度，fl 是当前所知道的最短的周游（Hamilton //圈）的长度 integer k,n,X[1:n]; real W[1:n,1:n],cl,fl; X[2]=1; k=2; cl=0; fl=+∞; while k>1 do X[k]=(X[k]+1) mod n;//给X[k]预分配一个值 for j to n do if NextValue(k)=true then exit; endif X[k]=(X[k]+1) mod n; endfor if [fl ≤ cl+W[k-1,k]] or [k=n and fl<cl+W[k-1,k] +W[X[n],1]] then k=k-1; //回溯 elif k=n && fl≥cl+W[k-1,k]+W[X[k],1] then fl= cl+W[k-1,k]+W[X[k],1]; k=k-1; //回溯 else cl= cl+W[k-1,k]; k=k+1;//继续纵深搜索 endif endwhile end BackTSP §4 图的着色问题 已知一个无向图G 和m 种颜色， 在只准使用这 m种颜色对图G的顶点 进行着色的情况下，是否有一种着色方法，使图种任何两个相邻的顶 点都具有不同的颜色？如果存在这样的着色方法，则说图 G 是 m-可 着色的，这样的着色称为图 G 的一种 m-着色。使得 G 是 m-可着色的 最小数m 称为图G 的色数。这一节所讨论的图的着色问题是： 给定无向图G 和m 种颜色，求出G 的所有m-着色 。 用 G 的邻接矩阵 W 表示图 G，W[i,j]=1 表示顶点 i 与 j 相邻（有 边相连） ，否则W[i,j]=0. m 种颜色分别用1，2，…,m 表示。图G 的 每一种m-着色都可以用一个 n-维数组 X[1:n]表示。 X[i]=k表示顶点 i 被着上颜色k。简单分析可知，解空间是一个完全的 m-叉树，共有 n+1 级。X 是可行解，当且仅当 W[i,j]=1 ? X[i]≠X[j], (7.4.1) 此即是约束条件。假如已经给前 j-1 个顶点着好颜色，即 X[1],…,X[j-1]已经确定，则确定第 j个顶点所着的颜色X[j]时,根 据约束条件，应该验证条件 W[i,j]=1 ? X[i]≠X[j], 1≤i<j (7.4.2) 是否满足。这可以由下面程序完成。 下一步选色算法 NextColor ( j ) //进入此过程前，X[1],…,X[j-1]已经确定且满足约 //束条件。本过程给 X[j]确定一个整数 k，0 ≤k≤m：如果还有一 //种颜色 k可以分配给顶点 j（满足约束条件） ，则令X[j]＝k； //否则，令X[j]＝//0。 global integer m, n, X[1:n], W[1:n, 1:n]; integer j, k; loop X[j]=(X[j]+1) mod (n+1); if X[k]=0 then return endif for i from 1 to j-1 do //验证约束条件 if W[i, j]=1 && X[i]=X[j] then exit endif endfor if i=j then return endif //找到一种颜色 endloop end NextColor 在程序 NextColor 开始执行之前，诸 X[k]均已经有值。这可在着色问 题的回溯算法初次调用该函数时赋予初值： X[i]=0,i=1,2,…,n。 图的着色问题回溯算法 GraphColor（ k） // 采用递归。 W[1:n, 1:n]是图 G 的邻接矩阵， 1, 2, // . . . , m 代表 m 种颜色。 k 是下一个要着色的顶点。 global integer m, n, X[1:n], W[1:n, 1:n] ; loop NextColor ( k ); // 确定 X[k]的取值 if X[k]=0 then exit endif //说明没有颜色可以分配给第 k 个点 if k=n then // 已经找到一种着色方法 print (X); else GraphColor ( k+1 ) ; //递归 endif endloop end GraphColor 例子 ： n＝ 4， m＝ 3， 无向图 G 如右图 G 1 4 3 2 x 1 = 1 2 3 x 2 = 2 3 1 3 1 2 x 3 = 1 3 1 2 2 3 1 2 2 3 1 3 x 4 =2 3 2 2 3 3 1 3 1 3 1 3 1 1 2 2 1 2 一个 4 顶点的图和所有可能的 3 着色 正好用 3 种颜色的解只有 12 个。 §5 回溯法的效率分析 回溯法是以深度优先的方式系统地搜索问题的解空间。 解空间是由 所有可能的决策序列 ),,,( 21 n xxxL构成。在搜索过程中，采用剪枝函 数尽量避免无意义的搜索。通过前面的具体实例的讨论容易看出，一 个回溯算法的效率在很大程度上依赖于以下几个因素： 1). 产生 k x 的时间； 2). k x 的取值范围； 3). 计算约束函数的时间； 4). 计算限界函数的时间； 5). 满足约条件及限界条件的 k x 的个数。 一般来说，一个好的约束函数能够显著地减少所生成的顶点的数 目。但是，这样的约束函数往往计算量较大。因此在选择约束函数是 通常存在着顶点数与约束函数计算量之间的折中。 我们希望总的计算 时间较少。为了提高效率，通常采用所谓的“重排原理” 。对于许多 问题而言，在进行搜索试探时，选取 k x 值的顺序是任意的。这提示 我们，在其它条件相当的前提下，让可取值最少的 k x 优先。这将会 更有效。如文档“解空间树比较” 中的图，是同一个问题的不同的解 空间树，从中可以体会到这种策略的效力。 在第一个图中，若从第 1 层剪去一棵子树，则从所有应当考虑三元 组中一次消去 12 个三元组；在第二个图中，虽然同样从第 1 层剪去 一棵子树，却只从应当考虑的三元组中一次消去 8 个三元组。前者的 效果显然比后者好。 解空间的结构一经选定，影响回溯法效率的前三个因素就可以确 定，只剩下生成顶点的数目是可变的，它将随问题的具体内容以及定 的不同生成方式而变动。即使是对于同一问题的不同实例，回溯法所 产生的顶点的数目也会有很大变化。对于一个实例，回溯法可能只产 生 )(nO 个顶点。而对于另一个相近的实例，回溯法可能产生解空间 中的所有顶点。如果解空间的顶点数是 n 2 或 !n ，则在最坏情况下， 回溯法的时间耗费一般为 )2)(( n npO 或 )!)(( nnqO 。其中， )(np 和 )(nq 均为 n的多项式。对于一个具体问题来说，回溯法的有效性往往 就体现在当问题实例的规模 n较大时，它能够用很少的时间求出问题 的解。而对于一个问题的具体实例，我们又很难预测回溯法的算法行 为。特别地，很难估计在解这一具体实例时所产生的顶点数。这是在 分析回溯法效率时遇到的主要困难。 下面所介绍的概率方法也许对解 决这个问题有所帮助。 当用回溯法解某一个具体问题实例时 ，可用蒙特卡罗方法估算回 溯法将要产生的顶点数目。 该方法基本思想是在解空间树上产生一条 随即路径，然后沿此路径来估算结空 间中满足约束条件的顶点数 m。 设 x 是所产生的随即路径上的一个顶点， 且位于解空间树的第 i 层上。 对于 x 的所有儿子顶点，用约束函数 检测出满足约束条件的顶点数 m i 。路径上的下一个顶点是从 x 的 m i 个满足约束条件的儿子顶点中 随机选取的。 这条路径一直延伸到一个叶顶点或一个所有儿子顶点都 不满足约束条件的顶点为止。通过这些 m i 的值，就可估计出解空间 树中满足约束条件的顶点的总数 m。 在用回溯法求问题的所有可行解 时，这个数特别有用。因为在这种情况下，解空间所有满足约束条件 的顶点都必须生成。若只要求用回溯法找出问题的一个解，则所生成 的顶点一般只是 m 个满足约束条件的顶点中的一部分。此时用 m 来 估计回溯法生成的顶点数就过于保守了。 为了从 m i 的值求出 m 的值，还需要对约束函数做一些假定。在估 计 m 时，假定所有约束函数是静态的，即在回溯法执行过程中，约 束函数并不随随算法所获得信息的多少而动态地改变。 进一步还假定 对解空间树中同一层的顶点所用的约束函数是相同的。 对于大多数回 溯法，这些假定都太强了。实际上，在大多数回溯法中，约束函数是 随着搜索过程的深入而逐渐加强的。在这种情形下，按照前面所做假 定来估计 m 就显得保守。如果将约束函数变化的因素也加进来考虑， 所得出的满足约束条件的顶点总数将会少于 m，而且会更精确些。 在静态约束函数假设下，第一层共有 m 0 个满足约束条件的顶点。 若解空间的同一层的顶点具有相同的出度， 则在第一层上的每个顶点 将会又 m 1 儿子满足约束条件。因此，第二层将会又 m 0 m 1 个满足约束 条件的顶点。同理，第三层上满足约束条件的顶点个数是 m 0 m 1 m 2 。 依此类推，第 i+1 层上满足约束条件的顶点的数目是 m 0 m 1 m 2 … m i .因 此，对于给定的实例，如果产生解空间树上的一条途径，并求出 m 0 ， m 1 ， m 2 ，…， m i ，…，则可以估计出回溯法要生成的满足约束条件的 顶点数目m= m 0 + m 0 m 1 + m 0 m 1 m 2 +…. 假定回溯法要找出所有的可行解。设 ),,,( 121 ?i xxxL是解空间树 中由根到一个顶点的路径，而 ),,,( 121 ?i xxxTL表示所有这样的 i x ， 使得 ),,,,( 121 ii xxxx ? L能够成为解空间树中的一条路径。 B k 表示第 k 层上约束函数， B k (X[1], …，X[k])=true 表示这条路径到目前为止 未违背约束条件。否则 B k (X[1], …，X[k])=false。 回溯法的递归流程 RecurBackTrack（k）//进入算法时，解向量X[1:n]的前k-1个分 //量X[1],…，X[k-1]已经赋值 global n, X[1:n]; for 每个满足 “X[k] ∈ T k (X[1], …，X[k-1]) && B k (X[1], …，X[k])=true” 的X[k] do if (X[1], …，X[k]) 是一条抵达某一答案顶点路径 then print (X[1], …，X[k]); endif RecurBackTrack（k+1） endfor end RecurBackTrack 根据前面的分析，我们不能给出回溯法递归流程生成的解空间树中 顶点数目m。 回溯法效率估计 Estimate //程序沿着解空间树中一条随机路径估计回溯法生成的顶 //点总数 m m=1; r=1; k=1; loop T k ={X[k]| X[k]∈ T k (X[1], …，X[k-1]) && B k (X[1], …， X[k])=true}; If T k ={} then exit endif r=r*size(T k ); m=m+r; X[k]=Choose(T k ); k=k+1; endloop return (m); end Estimate 其中 Choose(T k )是从 T k 中随机地挑选一个元素。 当用回溯法求解某个具体问题时， 可用算法 Estimate 估算回溯法 生成的顶点数。 若要估计得精确些， 可选取若干条不同的随机路径 （通 常不超过 20 条） ，分别对各随机路径估计顶点总数，然后以平均值作 为 m。 例如 8 皇后问题，回溯算法 nQueens 可以用 Estimate 来估计。 文档“效率分析例图 ”给出了算法 Estimate 产生的 5 条随机路径所相 应的 8× 8 棋盘状态。当需要在棋盘上某行放入一个皇后时，所放的 列时随机选取的。它与已在棋盘上的其它皇后互不攻击。在图中棋盘 下面列出了每层可能生成的满足约束条件的顶点数，即 m 0 ， m 1 ， m 2 ，…， m i ，…，以及由此随机路径算出的顶点总数 m 的值。这 5 个总点数的均值为1702。注意到8 皇后解空间树的顶点总数是： ∑∏ = = ?+ 7 0 0 )8(1 j j i i =109601 1702/109601≈1.55%，可见，回溯法效率远远高于穷举法。