第5 章
回溯与分支限界
本章介绍算法设计的第四种方法:回溯算法.先用例子说明回溯算法设计的基本思想
和适用条件,然后给出主要设计步骤和效率分析方法,最后给出求解优化问题的一种改进回
溯方法:分支限界.
5.1 回溯算法的基本思想和适用条件
有些问题,如搜索问题和优化问题,它们的解分布在一个解空间里,求解这些搜索问题
的算法就是一种遍历搜索解空间的系统方法,所以解空间又称为搜索空间.求解搜索问题
就是在搜索空间中找到一个或全部解,求解组合优化问题就是找到该问题的一个最优解或
所有的最优解.
回溯算法将搜索空间看作一定的结构,通常为树形结构,一个解对应于树中的一片树
叶.算法从树根(即初始状态)出发,尝试所有可达的结点.当不能前行时,就后退一步或若
干步,再从另一个结点继续搜索,直到所有的结点都试探过.回溯算法遍历一棵树可以用深
度优先、宽度优先或者宽度-深度结合等多种方法.为加快搜索,人们又给出了分支限界等
各种在树中剪枝的方法,以改善算法的运行时间.简单来说,回溯(backtracking)是一种遵
照某种规则(避免遗漏)、跳跃式(带裁剪)地搜索解空间的技术.
5.1.1 几个典型的例子
例5.1 8皇后问题.在有8×8个方格的棋盘中放置8个皇后,使得任何两个皇后之
间不能互相攻击,即在同一行、同一列不能有两个及以上的皇后,在与主对角线、副对角线的
平行线上也不能有两个及以上的皇后,试给出所有的放置方法.
解 首先找出所有可行解,即所有可能的放置方法.由于每行不能有两个及以上皇后,
而棋盘共有8行,要放置的皇后个数也恰有8个,所以在可行解中每行正好有一个皇后.这
样,每个可行解可以表示成一个8维向量<x1,x2,…,x8>,其中xi 表示第i 行放置皇后的
位置(列号).例如<4,2,7,1,3,5,8,6>,表示第一行中皇后放在第4列,…,第8行中皇后
放在第6列.所以所有可行解为如下8维向量构成的集合{<x1,x2,…,x8>|1≤xi ≤8,
1≤i≤8}.将这些可行解按一定的结构进行排列.在本例中,我们将之排成完全8叉树,即
搜索空间.搜索树有8层,最下层有88 个叶结点.如图5.1所示.
回溯与分支限界
第
章
115
图5.
18
皇后问题的搜索空间
回溯算法用深度优先策略遍历整棵树,找出所有解.算法从树根开始,经过结点<1>,
<1,1>,<1,1,1>,…, 最后到结点<8,8,…,8> 为止,然后回溯到根,算法停止,恰好按深
度优先顺序跳跃式搜索了所有的可行解向量.在实际搜索过程中不是真正遍历所有的结
点,如果发现向下搜索不可能达到解结点,那么就回头.搜索过程是解向量不断生成的过程
.
根结点为空向量,算法依次对x1,x2,…,xn
进行赋值.每进行一次赋值需要检查“互不攻
击”的条件.当不满足条件时,算法不再继续向下搜索,而是从这个结点回到父结点.一旦对
x2,…,进行了赋值,算法就到达某个结点,将该结点标记为向量<x1,x2,…,称
为部分向量.从根结点到解结点的路径上的所有标记正是从空向量到可行解的生成过程
.
例如,算法从根结点沿着边x1=1走到第一层最左边的那个结点,表示第1行的皇后放在第
1列,该结点的标记是<1>.按深度优先策略算法沿x2=1走到第二层最左边的那个结点,
表示第2行的皇后放在第1列,这违反了同一列不能有两个及以上的皇后的放置规则,不满
足约束条件,算法回溯到父结点<1>.下一个选择是x2=2,走到第二层从左边数的第二个
结点,表示第2行的皇后放在第2列,这违反了与主对角线平行的平行线上不能有两个及以
上的皇后的放置原则,所以也不可能找到解.于是,算法又回溯到父结点<1>.这相当于把
这两个分支对应的子树从整棵树中裁剪掉了.接着算法沿着x2=3走到第二层左边数的第
三个结点,表示第2行的皇后放在第3列,这符合放置规则,该结点标记为<1,3>.再按照
深度优先策略往下探查,显然沿x3=1,2,3,4的方向向下的搜索都违背了放
x1,xk
xk
>,
x3=x3=x3=
置规则,只能回溯到<1,下面可以选择x3=对应于该结点的部分向量记为<1,3,5>.
3>
.
5,
照这样不断向下搜索,如果得到一个满足约束条件的8维向量,它就是8皇后问题的一个
解.如果从某个结点向下分支的所有方向都破坏了约束条件,部分向量不能继续扩张,则意
味着以这个结点为根的子树中没有可行解存在.算法从这个结点继续向上回溯到其父结点,
接着探查父结点其他可能的向下分支.如此下去,可以得到第一个解<1,5,8,6,3,7,2,4>,
按此策略再遍历其他结点,可得到其余解,共有92 个解
.
一般地,对于
n
皇后问题,搜索树有1+n+n2+…+nn
个结点,而
1+n+n2+
…+nn
=nn+1-
-
11≤nn+1
=2nn n
≥2
nn
2
在每个结点处,要判断此位置的皇后与已经放置的皇后是否相互攻击,最多要看3n
个
位置(沿列方向、主与副对角线方向)是否已有皇后,故
n
皇后问题的该算法在最坏情形下
3n×2n=n.
的时间复杂度为O(
n
)O(n+1)这是一个粗略的上界估计.实际运行中由于搜索
树的剪枝,时间要少得多
.
0-1背包问题.一个旅行者准备随身携带一个背包.可以放入背包的物品有
例5.2
116
算法设计与分析(第3版)
n
种,每种物品只有一个,重量和价值分别为wj
和vj
,1≤j≤n.如果背包的最大重量限制
是B,问怎样选择放入背包的物品,使得背包的价值最大?
解一个可行解就是对每个物品的选择,选择其是放入背包还是不放,放入背包就标记
n
为1,不放入背包就标记为0.这样,所有可行解是满足Σwixi
≤
B
的
n
维布尔向量
i=1
<x1,x2,…,xn
>,其中xi=1或xi=0,1≤
i
≤n.
搜索空间的每片树叶对应了物品的一个子集,所有的树叶构成集合{<x1,x2,…,xn
>|
xi=1或0,1≤i≤n}, 整个搜索空间可以排成一棵完全二叉树.对于每个内结点来说,到达
左子结点的边代表1,到达右子结点的边代表0.这样的完全二叉树称为子集树,该树有
2n
个树叶,代表了选入物品子集的特征序列
.
搜索策略还是深度优先方法.下面以一个实例说明0-1背包问题的回溯算法的运行过程:
设n=4, 12,9,重量向量为W={6,3}, 13.
价值向量为V={11,8}, 8,4,背包承载量为B=
按深度优先策略,从根结点开始,沿着边x1=1走到第一层最左边的那个结点,表示第
一个物品被选中放入背包,此时背包中只有第一个物品,其重量是8,不超过背包承载量13,
可以继续选择.于是,搜索按深度优先策略向下层进行.算法沿着x2=1走到第二层最左边
的那个结点,表示第二个物品也被选中放入背包,此时背包中物品的重量达到14,大于背包
的承载量,破坏了约束条件,回溯到父结点.接着按深度优先策略沿边x2=0向下搜索,表
示第二个物品不放入背包,此时背包中物品重量是8,还可以继续选择物品放入.继续沿着
左边的x3=1走到其左儿子,表示第三个物品被选中放入背包,此时背包中物品的重量是
12,小于承载量13.继续向下,沿着x4=1走到其左儿子,表示第四个物品被选中放入背包,
此时背包中物品的重量将达到15,大于承载量13,破坏约束条件,回溯到父结点.于是算法
只能沿着右边的x4=0走到其右儿子,表示第四个物品不放入背包,此时背包中物品的重
量是12,小于承载量13,从而得到第一个可行解<1,0,1,0>,即将第1个和第3个物品放
入背包,第2个和第4个物品不放,此时放入背包物品的价值为21,现在还不知道这个可行
解是不是最优解.如此下去,算法搜索到<0,0,0,0> 结点以后,将沿着树中最右边的路径
算法结束,2所示.
逐步回溯,直到树根, 如图5.此时已经找到了所有的可行解,所有这些价
值中的最大值即为最优值,对应的解即为最优解.在这个实例中,<0,1,1,1> 是最优解,即
将第2个、第3个和第4个物品放入背包,背包中物品总价值最大达到28.
图5.1背包问题的一个实例
2
0
该子集树有1+2+22+…+2n
=2n+1-1≤2×2n
=O(2n
)个结点.在每个结点处要计
算放入背包物品的重量是否超过背包的承载量,父结点已经记录了在此结点之前已经放入
回溯与分支限界
第5章
1 17
背包物品的重量.再加上当前新放入背包物品的重量,就可得到该结点处放入背包物品的
重量.在最坏的情况下,该算法只进行了1次加法和一次大小比较,即进行了O(1)次运算,
从而该算法在最坏的情况下的时间复杂性为O(2n).
对于一般的背包问题,其可行解和0-1背包问题类似,也是n 维向量<x1,x2,…,xn >,
只是其分量xi 是整数,不一定只是0或1.由于背包承载量是一个定值B,所以第i 种物品
放入背包的最大个数xi 满足0≤xi≤.B/wi.,1≤i≤n.在构造解空间结构时,根结点的分
支个数为.B/w1.,第一层结点的分支个数为.B/w2. .以此类推,可以构造完整的搜索树.搜
索策略仍然是深度优先方法,此处略.
例5.3 货郎问题(TSP).某售货员要到若干城市去推销商品,各城市之间的距离为
已知.他要选定一条从驻地出发经过所有城市最后回到驻地的周游路线,使得总的路程最
短.其数学模型是:已知一个带权完全图(结点代表城市,边代表城市之间的道路,权代表城
市之间的距离,如两个城市之间无直接连接的道路,设其权为∞,所以权为正数或无穷),求
权和最短的一条哈密顿回路.
货郎问题中,带权图又可分为有向图和无向图。下面的算法对有向图和无向图都适用.
解 一个可行解是n 个城市的一个排列,排列的第一个元素是售货员的驻地。最后一
个元素是其最后周游的城市,由此城市又回到驻地.如果将城市编号为1,2,…,n,且驻地为
城市1,则一个可行解即为首元素是1的一个n 元排列.
这些排列可以安排成如下的搜索树:从根到叶结点的一条路径对应了{1,2,…,n}的排
列,根结点只有一个子结点,其余各结点分支数不同.第一层结点有n-1个分支,第二层结
点有n-2个分支,…,第n-1层有1个分支,这样的树称为排列树.
搜索策略依然是深度优先.
图5.3的右边给出货郎问题的一个实例,其对应的搜索树为左边的排列树.按深度优先
策略,可求出最优解为<1,2,4,3>,对应于巡回路线:1→2→4→3→1,巡回路径的长度为
5+2+7+9=23.
图5.3 货郎问题的一个实例
该排列树有Kn =1+1+(n-1)+(n-1)(n-2)+…+((n-1)(n-2)…2)+(n-
1)! 个结点.而
Kn =1+ (n -1)! × 1
(n -1)! + 1
(n -2)! + 1
(n -3)! + … 1
1! +1 .
è .
.
. ÷
≤1+ (n -1)! × 1
2n-2 + 1
2n-3 + … +12
+1+1 .
è .
.
. ÷
算法设计与分析(第3 版)
11 8
≤1+ (n -1)! ×
.
è ..
1
1-12
+1
.
. ÷÷
=1+3(n -1)!=O((n -1)!)
而在每个结点处要计算已得到的路径长度,这只要将父结点得到的路径长度加上父结
点到本结点的距离即可;在叶结点处还要计算得到的回路长度,并判断得到的回路是否为当
前的最短回路,所以算法在每个结点处最多进行两次加法和一次大小比较,故该算法最坏情
形的时间复杂性为O((n-1)!)×O(1)=O((n-1)!).
由这些例子可以看出回溯算法的共同特征:
(1)可求解搜索问题和优化问题,搜索问题可定义如下:
一个搜索问题π有实例集Dπ,对于π中的任何实例I,有一个有穷的解集合Sπ[I].
如果存在算法A ,对于任何实例I∈Dπ,A 都停止,并且如果Sπ[I]=.,则回答无解,
否则给出Sπ[I]中的一个解,那么称A 解搜索问题π.
(2)搜索空间是一棵树,每个结点对应了部分向量,满足约束条件的树叶对应了可行
解,在优化问题中不一定是最优解.
(3)搜索过程一般采用深度优先、宽度优先、函数优先或宽深结合等策略隐含遍历搜索
树.所谓隐含遍历是指:不是真正访问到每个结点,需要从搜索树中进行裁剪.
(4)判定条件(分支与回溯条件):满足约束条件则分支扩张解向量;不满足约束条件,
回溯到该结点的父结点.
5.1.2 回溯算法的适用条件
要使回溯算法得到正确应用,必须满足如下的多米诺性质:
假设P(x1,x2,…,xi)是关于向量<x1,x2,…,xi>的某个性质(如例5.1中的前i 个皇
后放置在彼此不能攻击的位置),那么P(x1,x2,…,xi+1)是真蕴涵P(x1,x2,…,xi)为真,即
P(x1,x2,…,xk+1)→P(x1,x2,…,xk), 0<k <n
其中n 代表解向量的维数.
下面是一个不满足多米诺性质因而使用回溯算法不能得到正确解的反例.
例5.4 求满足下列不等式的所有整数解:
5x1 +4x2 -x3 ≤10
1≤xi ≤3, i=1,2,3
P(x1,x2,…,xk)表示将x1,x2,…,xk 代入原不等式的相应部分使得左边小于或等于
10,如P(x1,x2,x3)表示5x1+4x2-x3≤10.存在<x1,x2,x3>=<1,2,3>,使得P(x1,
x2,x3)为真,但是P(x1,x2)表示5x1+4x2≤10,显然为假,因而P 不满足多米诺性质,不
能使用回溯算法.如果使用回溯算法,其执行过程是:
搜索空间是{<x1,x2,x3>|1≤xi≤3,i=1,2,3},是一棵完全3叉树,如图5.4所示.
搜索策略还是深度优先.
回溯算法很容易求出<1,1,1>,<1,1,2>,<1,1,3>是其解,但当算法搜索到结点
A 时,x1=1,x2=2,此时5x1+4x2=13>10,不满足条件,算法将回溯到其父结点,进而搜
回溯与分支限界
索结点B,从而丢掉<1,2,3> 这个解.如果令x'3=4-x3,那么不
等
式将改
为
5x1+4x2+x'3≤14
1≤xi,x'3≤3,i=1,2
则该不等式满足多米诺性质,可以使用回溯算法.对所得到的解x1,
x3很容易地转换成原来不等式的解x1,x3.
图5.不等式求解
第5章
119
x2,'x2,4
回溯算法中,结点状态随算法的进行会改变,结点一般有三种状的搜索树
态:白结点(尚未访问)、灰结点(正在访问以该结点为根的树中结
点)、黑结点(该结点为根的子树遍历完成)
.
5.回溯算法的设计步骤
2
回溯算法设计的主要步骤如下:
(1)定义搜索问题的解向量和每个分量的取值范围
.
(2)确定子结点的排列规则
.
(3)判断是否满足多米诺性质
.
(4)确定搜索策略:深度优先、宽度优先、宽深结合等
.
(5)确定每个结点能够分支的约束条件
.
(6)确定存储搜索路径的数据结构
.
回溯算法一般可以如下描述:设解向量为<x1,x2,…,xn
>,xi
的可能取值的集合为
Xi,=xk
1,2,…,设当x1,x2,…,1确定以后xk
的取值集合为Sk
,显然Sk
.Xk.回溯
算法的实现可以有两种方法:递归回溯和迭代递归.下面给出算法的伪码
.
in.
5.1
回溯算法的递归实现和迭代实现
2.
算法5.k(
x2,…,
1
ReBack)
1.ifk>nthen<x1,xn
>是
解
2.elsewhileSk
≠.do
3. xk
←Sk
中最小值
4. Sk
←Sk
-{xk
}
5. 计算Sk+1
6. RBck+1)
eak(
算法5.2
递归回溯RBctak(
输入:
n
eakrcn)
输出:所有的
解
1.fori←1tondo计算Xk
2.S1←X1
3.ReBack(1)
算法5.迭代回溯Bctak(
输入:
n 3
akrcn)
输出:所有的
解
120
算法设计与分析(第3版)
1. 对于i=1,n,
2,…,确定Xi
2.k←
1
3. 计算Sk
4.whileSk
≠.
d
5. xk
←Sk
小值;Sk
←Sk
-{xk
}中最(o)
6. ifk<nthn
7. ;计算Skk←k+1(e)
8. else<x1,x2,…,xn
>是
解
9.ifk>1thenk←k-1;goto4
以4皇后问题为例,上述算法执行的部分过程如下:
初始:X1=X2=X3=X4={1,2,3,4}
.
k=1,1,3,取x1=修改S1={3,
.
S1={2,4}, 1, 2,4}
k=2,S2={3,4}, 取x2=3,修改S2={4}
.
k=3,S3=.,回溯
.
k=2,S2={4}, 取x2=4,修改S2=.
.
k=3,S3={2}, 取x3=2,修改S3=.
.
k=4,S4=.,回溯
.
k=3,S3=.,回溯
.
k=2,S2=.,回溯
.
k=1,2,4}, 2, 3,
.
S1={3,取x1=修改S1={4}
k=2,S2={4}, 取x2=4,修改S2=.
.
k=3,S3={1}, 取x3=1,修改S3=.
.
k=4,3}, 3, 得到解<2,1,
S4={取x4=修改S4=., 4,3>
.
k=3,S3=.,回溯
.
k=2,S2=.,回溯
.
k
.
=1,S1={3,4}, 取x1=3,修改S1={4}
.
上面描述了算法在左子树中的执行情况,后面右子树的过程与前面类似,不再重复.下
面给出几个典型的回溯算法例子
.
2.几个典型的例子
5.2
例5.5
装载问题.
n
个集装箱装上两艘载重分别为c1 和c2 的轮船,wi
为集装箱
i
的
重量,且
Σ(n) wi
≤c1+c2
i=1
问是否存在一种合理的装载方案,将
n
个集装箱装上轮船? 如果有,给出一种方案
.
解可以证明:如果装载问题有解,则存在一个使得第一条船装载量与c1 的差达到最
小的解.从而有如下解题思路:
(1)用回溯算法确定使第一条船装载量W1 与c1 的差达到最小的装载方案<x1,
x2,…,xn
>,即使得第一条船装载量达到最大值W1 的装载方案;
n
(2)如果Σwi-W1≤c2,则回答Yes,否则回答No.
i=1
回溯与分支限界
第5章
1 21
算法设计步骤如下:
(1)解向量是<x1,x2,…,xn >,其中xi∈{1,0},1≤i≤n.搜索空间是子集树.
(2)在结点<x1,x2,…,xk >的约束条件:
Σk
i=1
wixi ≤c1
(3)满足多米诺条件:令P(x1,x2,…,xk)为Σk
i=1
wixi >c1,从而
Σk
i=1
wixi >c1.Σk+1
i=1
wixi >c1
(4)搜索策略:深度优先.
上述回溯算法的伪码如下.其中B 为目前空隙,best为目前为止最优解的空隙.
算法5.4 Loading(W ,c1)
输入:集装箱重量W =<w1,w2,…,wn >,c1 是第一条船的载重
输出:使得第一条船装载量最大的装载方案<x1,x2,…,xn >,其中xi=0,1
1. B←c1;best←c1;i←1
2. whilei≤n do
3. if装入i 后重量不超过c1
4. thenB←B-wi;x[i]←1;i←i+1
5. elsex[i]←0;i←i+1
6. ifB<bestthen记录解;best←B;i←i-1
7. Backtrack(i)
8. ifi=1thenreturn最优解
9. elsegoto3
算法5.5 Backtrack(i)
1.whilei>1andx[i]=0do
2. i←i-1 //回溯到父结点
3.ifx[i]=1thenx[i]←0;B←B+wi;i←i+1 //搜索右分支
下面以实例说明算法执行过程.实例:W =<90,80,40,30,20,12,10>,c1=152,c2=
图5.5 装载问题
的实例
130.回溯算法使用深度优先搜索策略,搜索过程如图5.5所示.虚线表
示回溯.算法首先给出第一个可行解<1,0,1,0,1,0,0>,其装载量为
150,但其后给出第二个可行解<1,0,1,0,0,1,1>,其装载量为152,恰
好为第一条船的承载量,因而也是最大的装载量.第一条船装载后,货
物剩下的重量为80+30+20=130,正好可装入第二条船.所以本实例
的解为:第1、第3、第6和第7集装箱装入第一条船,第2、第4和第5
集装箱装入第二条船.
在最坏的情况下,算法要遍历图中几乎所有的点,叶结点有
2n 个,结点总数为O(2n)个.每个结点要计算装载量以判定是否回溯,
达到叶结点的计算时间为O(1),所以算法的计算时间复杂度为O(2n).
例5.6 图的m 着色问题.给定无向连通图G 和m 种颜色,用这些颜色给图的顶点着
色,每个顶点一种颜色.如果要求G 的每条边的两个顶点着不同颜色.给出所有可能的着色
122
算法设计与分析(第3版)
方案;如果不存在着这样的方案,则回答No.
2,…
,
解设
G
有
n
个顶点,将顶点编号为1,n,则搜索空间为深度
n
的
m
叉完全树
.
将颜色编号为1,2,…,m,树的结点<x1,x2,…,xk
>(x1,x2,…,xk
∈{1,2,…,
m
},1≤
k≤n)表示顶点1着颜色x1,顶点2着颜色x2,…, 顶点
k
着颜色xk.
约束条件:该顶点邻接表中已着色的顶点与该顶点没有同色的
.
搜索策略:深度优先
.
图5.其中顶点数n=颜色数m=按照1,3,5,7
6给出了一个图着色的实例, 7,3.
2,4,6,
顺序构造搜索树.按深度优先策略可以得到第一个着3色方案(图中粗线路径所示)是:顶
点1、顶点3和顶点5着色1;顶点2和顶点6着色2;顶点4和顶点7着色3.在<1,2> 的
路径上只有这一个可行解.在<1,3> 的路径上也只有一个可行解:顶点1、顶点3和顶点5
着色1;顶点4和顶点7着色2;顶点2和顶点6着色3.其实这个解只是将第一个解中的颜
色2和颜色3交换而已.根据对称性,在这棵树中只需搜索1/3的空间即可,搜索算法共可
得到6个解
.
图5.一个图着色问题的实例
6
该搜索树中有
mn+1-1 mn+1
mn
1+
m
+m2+
…+mn=
m-1≤ m=2(
m
≥2)
2
个结点,在每个结点处要判断当前顶点的着色与已着色的顶点是否颜色冲突,最坏情况下与
其他所有顶点的颜色都要进行比较,即进行n-1次比较,故该算法在最坏情况下的时间复
杂性为O(mn
).
n
5.回溯算法的效率估计和改进途径
3
回溯算法的时间复杂度一般取决于在搜索空间中真正遍历的结点个数以及在每个结点
的工作量,而结点个数通常是指数量级.在最坏的情况下,算法的裁剪策略几乎没有用处,
往往需要遍历整个搜索空间,而平均情况下算法的复杂度比起蛮力算法会好一些.为了估
计算法运行的效率,可以用在搜索树中真正遍历的结点数作为度量标准,通常采用概率方法
中的蒙特卡洛(MonteCarlo)方法来做出估计.从根开始,算法在每个结点从所有可行的分
支中随机选择一个分支.当算法最终到达某片树叶,就得到一条随机选择的路径.把其他的
路径按照这条路径的形式进行复制,从而生成一棵对称的树,以这棵树的结点数作为本次遍
回溯与分支限界
历的结点数的估计.图5.假若算法某次抽样的路径是<1,
7给出了一个4皇后问题的估计
.
4,2>.在根结点,S1={1,2,3,4}, 因此根有4个儿子,这棵树第一层的4条路径与
<1,4,2> 具有相同的结构.当第二次随机选择时,S2={3,4}, 有两种选择,因此第二层的
每个结点都有2个分支.当算法选择了4之后,下一步进行第三次随机选择时,S3={2}, 这
时算法只有一种选择,这意味着该结点只有1个分支,只能到达<1,4,2> 结点.因此,这棵
树的第三层的每个结点都是1个分支.到此为止,7中标记为
最终形成的树就是在图5.
<1,3>,
4,2> 的树.类似地,如果随机选择的路径是<1,3> 和<2,4,1,可以得到图中的
另外两棵树.而算法真正遍历的树就是搜索空间所表示的树.在多次抽样中,每次形成的树
可能是<1,2>,<1,3> 和<2,1,对每次抽样得到的树的结点数取平
4,4,3> 三种树之一
.
均值,就得到一个平均情况下算法真正遍历结点数的估计值
.
图5.nteCarlo估计
74
皇后问题的Mo
设
t
为取样次数,um 为
t
次取样遍历结点的平均数,
m
为本次取样树中结点总数,
sk
为目前访问结点的层数,r2 为路径中的上层分支数,
r1 为在路径中的本层分支数,
n
为树的
层数.下面的伪码给出上述估计方法的算法
.
算法5.6
MoteCl
输入:n和t为正(n) n
为皇后数
,
整数,(o) (r) (a) t
为抽样次
数
输出:sum,即
t
次抽样平均访问的结点
数
1.sum←
0
2.fori←1totdo
3. m←Etmae(//Etmae(是第
i
次抽样得到的树中的结点数
sitn) sitn)
4. sum←sum+
m
5.sum←sum/
t
算法5.7
Etmae(
itn)
1.m←1;r2←(s) 1;k←
1
2.Whilek≤ndo
3.ifSk
=.thenreturnm
4.r1←|Sk|*r2 // 计算第
k
层的结点数
5. m←m+r1 // 第
k
层以上各层的结点总数
6. xk
←随机选择Sk
的元素
7.r2←r1
8. k←k+1
第
章
123