2010-5-14 计算机算法设计与分析 1
第六章
分支限界法
2010-5-14 计算机算法设计与分析 2
分支限界法是最佳优先搜索法
? 分支限界法就是最佳优先 (包括广度优先在内 )
的搜索法。
? 分支限界法将要搜索的结点按评价函数的优劣
排序，让好的结点优先搜索，将坏的结点剪去。
所以准确说，此方法应称为界限剪支法。
? 分支限界法中有两个要点：
? (1)评价函数的构造；
? (2)搜索路径的构造。
2010-5-14 计算机算法设计与分析 3
评价函数的构造
? 评价函数要能够提供一个评定候选扩展结点的
方法，以便确定哪个结点最有可能在通往目标
的最佳路径上。
? 一个评价函数 f(d)通常可以由两个部分构成：
⑴从开始结点到结点 d的已有耗损值 g(d),和⑵
再从结点 d到达目标的期望耗损值 h(d)。 即：
f(d) = g(d) + h(d)
? 通常 g(d)的构造较易,h(d)的构造较难。
2010-5-14 计算机算法设计与分析 4
搜索路径的构造
? 在回溯法中，每次仅考察一条路径，因
而只需要构造这一条路径即可：前进时
记下相应结点，回溯时删去最末尾结点
的记录。这比较容易实现。
? 在分支限界法中，是同时考察若干条路
径，那么又该如何构造搜索的路径呢？
对每一个扩展的结点，建立三个信息：
? (1)该结点的名称；
? (2)它的评价函数值；
? (3)指向其前驱的指针；
这样一旦找到目标，即可逆向构造其路径。
? 用一个表保存准备扩展的结点，称为 Open表。
? 用一个表保存已搜索过的结点, 称为 Closed表。
2010-5-14 计算机算法设计与分析 5
分支限界法的一般算法
? ⑴计算初始结点 s的 f(s); [s,f(s),nil]放入 Open;
? ⑵ while (Open ≠Φ) {
? ⑶ 从 Open中取出 [p,f(p),x](f(p)为最小 );
? ⑷ 将 [p,f(p),x]放入 Closed;
? ⑸ 若 p是目标，则成功返回；否则
? ⑹ { 产生 p的后继 d并计算 f(d) ；对每个后继 d
有二种情况,① d?Closed || d ?Open；
② d?Open && d?Closed。
? ⑺ {若 ([d,f’(d),p]?Closed || [,f’(d),]?Open)
&& f(d)＜ f’(d)，则删去旧结点并将 [d,f( ),p]
重新插入到 Open中 ; 否则
? ⑻ 将 [d,f(d),p] 插入到 Open中 }}}。
2010-5-14 计算机算法设计与分析 6
分支限界法求单源最短路径
? 单源最短路径问题的评价函数的构造：
? g(d)定义为从源 s到结点 d所走的路径长度：
g(d) = g(p) + C[p][d]
这里 p为 d的前驱结点,C[p][d]为 p到 d的距离。
? h(d)定义为 0。 于是 f(d) = g(d)。
? 源 s的评价函数 f(s) = 0。
? 评价函数的下界为 0；上界初始时为 ∞，以后不
断用取得的更短路径的长度来替代。
2010-5-14 计算机算法设计与分析 7
分支限界法求最短路径举例
1
2 5
43
10
20
50
100
30
10 60
赋权图 G
初始时，将源 [1,0,0]放入 Open,Closed为空。
Open表
[1,0,0]
Closed表
取出 [1,0,0]放入 Closed； 生成其后继 [2,10,1]、
[4,30,1]和 [5,100,1]，并依序放入 Open。
[1,0,0][5,100,1]
[4,30,1]
[2,10,1]
取出 2 10,1]放入 Closed； 生成其后继 [3,60,2]，
并依序插入 Open。
[2,10,1]3,60,2]
4,30,1]
取出 [4,30,1]放入 losed； 生成其后继 [3,50,4]
和 [5,90,4],修订 Open中已有的两个结点并依
序排列 。
[4,30,1]
[5,90,4]
50,4]
取出 3 5 4 放入 ； 生成其后继 2,1 0,3]
和 6 3,前者因劣于 Closed中的 [2,10,1]而
被抛弃，后者修订了 Open中的 [5,90,4]。
[3,50,4]
60,3]
取出 5,6,3,因其已经是目标结点，算法成
功并终止。
依据逆向指针可得最短路径为 1→4→3→5 。
2010-5-14 计算机算法设计与分析 8
界限 (Bounding)
? 评价函数 f(d)关系着算法的效率乃至成败。
? 因为在大多数问题中 f(d)只是个估计值，所以
单靠 f(d)是不够的。通常还要设计它的上下界
函数 U(d)和 L(d)。 L(d)≤f(d)≤U(d)。
? 所谓分支限界法就是通过评价函数及其上下界
函数的计算，将状态空间中不可能产生最佳解
的子树剪去，减少搜索的范围，提高效率。因
而更准确的称呼应是“界限剪支法”
2010-5-14 计算机算法设计与分析 9
用分支限界法求 TSP
? TSP是求排列的问题，不是仅找一条路径而已。
因而需要对分支限界法的一般算法作些修改：
? (1)待扩展的结点如果在本路径上已经出现，则
不再扩展，但若是在其他路径上出现过，则仍
需要扩展。
? (2)新结点，无论其优劣，既不影响其它路径上
的结点，也不受其它路径上的结点的影响。
? (3)依据上界函数决定结点是否可以剪去。
2010-5-14 计算机算法设计与分析 10
分支限界法求排列
? ⑴计算初始结点 s的 f(s); [s,f(s),nil]放入 Open;
? ⑵ while (Open ≠Φ) {
? ⑶ 从 Open中取出 [p,f(p),L]; //L是路径已有结点
? ⑷ 若 f(p)≥U,则抛弃该路径；
? ⑸ 若 p是目标，则考虑修改上界函数值；否则
? ⑹ {将 [p,f(p),L]放入 Closed;
? ⑺ 在该路径上扩展结点 p；对每个后继 d
? ⑻ {计算 f(d)；
? ⑼ 若 f(d)＜ U,则 {L = L ?{p};
? 将 [d,f(d),L]依序放入 Open。 }
? } } }
2010-5-14 计算机算法设计与分析 11
分支限界法求 TSP举例
? 设有向图 G = (V,E)的边的代价矩阵为 C = [cij]。
若不存在有向边 <i,j>∈ E,则定义 cij=∞且规定
cii=∞。 不失一般性，设周游路线均以顶点 1为起
点。左下为一个有向图 G的代价矩阵 C。
∞ 25 40 31 27
5 ∞ 17 30 25
19 15 ∞ 6 1
9 50 24 ∞ 6
22 8 7 10 ∞
? 评价函数 f(d)为 1到 d的代
价减去已经过的边数。
? 初始时 f(1) = 0;
? f(d) = f(p) + cpd – 1,这里
p是 d的前驱。
2010-5-14 计算机算法设计与分析 12
分支限界法求 TSP的搜索
∞ 25 40 31 27
5 ∞ 17 30 25
19 15 ∞ 6 1
9 50 24 ∞ 6
22 8 7 10 ∞
10
224 339 430 526
340 453 548 233 332 435279 353 545
246 4373
49
4
62
284 358
286
找到了第一条周游路
线 1→5→3→4→2→1,
其长度为 95。
这不是最短周游路线，需要修改上界后继续搜索。
2010-5-14 计算机算法设计与分析 13
归约矩阵以及约数
? 前面的搜索的效率不高，几乎要搜索全
部的状态空间。其原因是评价函数以及
上下界的估计太低。为了设计求解 TSP
问题的更好的评价函数，先定义其代价
矩阵的归约矩阵和约数。
给定代价矩阵 C,从 C的任何行 i(或列 i)的
各元素中减去此行 (或此列 )的最小元素的
值 r(i)(或 r’(i)),称为对 i行 (或 i列 )的归约。
将 C的各行和各列都归约后的矩阵称为 C
的归约矩阵。和数
r = ∑i≤n r(i) + ∑i≤n r’(i)
称为 C的约数。
2010-5-14 计算机算法设计与分析 14
例子中的归约矩阵和约数
? 计算前面例子中的归约矩阵及其约数如下：
∞ 25 40 31 27
5 ∞ 17 30 25
19 15 ∞ 6 1
9 50 24 ∞ 6
22 8 7 10 ∞
先做行归约：
r(1)=25∞ 0 15 6 2
r(2)=50 ∞ 12 25 20
r(3)=118 14 ∞ 5 0
r(4)=63 44 21 ∞ 0
r(5)=715 1 0 3 ∞
再做列归约：
r’(1)=r’(2)=r’(3)=r’(5)=0 r’(4)=3
3
22
2
∞
0
? 约数 r = 47。
2010-5-14 计算机算法设计与分析 15
约数是周游路线长度的下界
? 定理：设 C是图 G的代价矩阵,P是周游路线，
则 P的代价，即 ∑<i,j>∈ P cij = r + ∑<i,j>∈ P c’ij,
式中 C’ = [c’ij]是 C的归约矩阵,r为约数。
? 证明：由归约矩阵的构造可知：
c’ij = cij – r(i) –r’(j)
即 cij = c’ij + r(i) + r’(j)。
? 任何周游路线包含 n条边并且对应在 C中的
每行每列有且仅有一条边。于是
∑<i,j>∈ P cij = ∑<i,j>∈ P(c’ij + r(i) + r’(j))。r + ∑<i,j>∈ P c’ij 。
2010-5-14 计算机算法设计与分析 16
定义期望函数 h(d)
? 对开始结点 1，令 g(1) = 0,h(1) = r,f(1) = r。
? 若从结点 1选择了一条边，不妨设边 <1,2>，则
令 g(2) = f(1)+从 1到 2的距离 l, 显然 l应该是 c’12，
而不应该再是 c12了。
? 那么 h(2) =？
? 自然可以想到 h(2)可以是从 2开始的路线的下界
r2。 是否也可用类似求 r一样去求新的约数 r2呢？
? 可以，但在此之前应将边 <1,2>和所有边 <1,k>
和边 <k,2>都删去，即置 c’12,c’1k和 c’k2为 ∞。
? 设 C’p为某路线上结点 p的归约矩阵。从 p选择边
<p,d>所得到结点 d的归约矩阵 C’d和约数 rd为：
? (1)将 C’p中的 c’pd,c’pk和 c’kd置为 ∞,1≤k≤n；
? (2)依照求归约矩阵 C’的方法对 C’p进行行归约
和列归约，便得到了 C’d和 rd 。
? 令 f(1) = g(1) + h(1),其中 g(1) = 0,h(1) = r。
? 对任意路线上的结点 d,设 p是其前驱结点，则
f(d) = g(d) + h(d)，
其中,g(d) = f(p) + C’p[p][d],h(d) = rd。
2010-5-14 计算机算法设计与分析 17
用新的评价函数求 TSP
? 下面用新的评价函数求前面的例子，我们已经
求得了它的归约矩阵 C’和约数 r = 47。
∞ 0 15 3 2
0 ∞ 12 22 20
18 14 ∞ 2 0
3 44 18 ∞ 0
15 1 0 0 ∞
147
2
g(2) = 47 + 0 = 47
∞ ∞ ∞ ∞
∞
∞
∞
∞
0 10 8
0
15
12
h(2) = 12 + 3 = 15
f(2) = 47 +15 = 62
62 3
3) + 15 = 62 ∞ ∞
∞
∞0
43
13
3) = 1
3) = 63
63 4
类似地可求出
f(4) = 51。
51 5
类似地可求出
5) = 50。
50
下面优先扩展的是结
点 5。
2
此时 C’2是在 C’5的基
础上进行。右边就是
C’5。
∞ ∞ ∞ ∞ ∞
0 ∞ 12 22 ∞
18 14 ∞ 2 ∞
3 44 18 ∞ ∞
∞ 0 0 0
g(2) = 50 + 0 = 50
∞ ∞ ∞
∞
∞ 016
0 15
0
3
h 2) = 17
f(2) = 67
67 3
类似地计算出 f(3) = 68
68 4
类似地计算出 4) = 81
81
下面扩展 f(4) = 51的结
点 4。并用同样方法计
算它们的评价函数值。
2121 369 464
下面要扩展的结点
是 f(2)= 62的结点 2。
右边是其对应的归
约矩阵 C’2。
∞ ∞ ∞ ∞
∞ ∞ 0 10 8
15 ∞ ∞ 2 0
0 ∞ 18 ∞ 0
12 ∞ 0 0 ∞
3
g(3) = 62 + 0 = 62；
对 C’2进行归约，
∞ ∞ ∞
∞
得
h(3) = 0； 于是
f(3) = 62。
62
对结点 2的另外两个
儿子进行同样的计
算，得：
f(4) = 84,f(5) = 72。
484 572
下面对 f(3) = 62的结
点 3进行扩展。它有
两个后继结点。
4 5
对结点 4，
g(4) = 62 + 2 = 64。 ∞ ∞
0
h(4) = 12, 于是
f(4) = 64 + 12 = 76
76 对结点 5，
5) + 0 。
∞ ∞ ∞
∞ ∞ 0
∞ 0 ∞
∞
∞
∞
5) = 0,于是
5) = 62 + 0 = 62
62
对结点 5(f(5) = 62)
再进行扩展。4
g = 62 + 0 = 62，
h(4) = 0,f(4) = 62。
62
结点 4是目标结点，
找到了第一条路线。
这条路线的长度为
62，以其为上界。
其余未扩展的结点
的评价函数值均超
过上界，因而不再
需要扩展了。
×
× × ×××
×
×× ×
于是找到了一条最
短的周游路线：
1→2→3→5→4→1 。
2010-5-14 计算机算法设计与分析 18
分支边与二叉树
? 在构造求 TSP的搜索树时，还有另外一种算法
稍有点不同，就是将搜索树构造成二叉树。
? 给定一条最短周游路线 P,对于任一条边 <i,j>
只有两种情况，即 <i,j>?P或者 <i,j>?P。
? 这就可以表示成右边的二叉树,k
m
<i,j>
n
____
<i,j>? 其中
____
<i,j>表示 <i,j>?P。
? 这样的边称为分支边。
2010-5-14 计算机算法设计与分析 19
用二叉树求 TSP
1<2,1>
250
____
<2,1>
3 62<4,5>
453
____
<4,5>
5 68
<1,4>
664
____
<1,4>
7 65
<4,1>
862
____
<4,1>
9 74<2,3>
1062
____
<2,3>
11 70<3,5>
1262
___
<3,5>
13 66<5,4>
1462
___
<5,4>
15 66<1,2>
16 62
____
<1,2>
17 ∞
结点 16给出了一条
最短周游路线：
1→2→3→5→4→1
2010-5-14 计算机算法设计与分析 20
分支限界法的效率
? 从 TSP问题的计算可看出，分支限界法搜索的
状态空间为 O(2n)。
? 对每个结点的计算时间为 O(n2)。
? 因此在最坏情况下，分支限界法计算 TSP的时
间复杂性为 O(n22n)。
? 显然，用分支限界法计算 TSP的空间复杂性为
O(n22n)。 因为对每个结点需要 n2的空间。
2010-5-14 计算机算法设计与分析 21
对评价函数的讨论
? 分支限界法总耗时为 O(n22n),它与回溯法、动
态规划法等在时间复杂性上没有本质的区别。
? 然而，如果评价函数选择得好，采用分支限界
法可能有一个小得多的常数因子。
? 好的评价函数应该有一个尽可能高的下界估计
和一个尽可能低的上界估计，从而使得搜索空
间能够得到有效的压缩，从而提高效率。
? 在理论上可以证明好的评价函数所搜索的结点
不会多于坏的评价函数所搜索的结点。
2010-5-14 计算机算法设计与分析 22
关系、传递闭包与搜索
? 定义在集合 S上关系 R是笛卡儿直积 S× S的一个
子集,R?S× S。
? 关系 R的传递闭包是包含 R的最小的具有传递性
质的关系。
? 若 S是有限的,|S| = n,则 R可表示为一个 n× n
的关系矩阵 M或 n个结点的有向图 G。
? 求关系 R的传递闭包实际上也就是在有向图 G
上的搜索。而反过来，在有向图 G上的搜索也
就是求某种关系的传递闭包。
2010-5-14 计算机算法设计与分析 23
传递闭包的集合算法
? 给定关系 R以及 S中的元素 a,求 R*(a)。
初始化,U = A = {a}; q = true;
while (q) {
for (?p∈ A) U = U ∪ {d | d∈ S 且 pRd}；
if (U == A) q = false;
else A = U }
? 这个算法稍加修改即可变成求 R*(a)中满足某性
质的元素的算法。
? 不难看出此算法实际也就是分支限界法。
2010-5-14 计算机算法设计与分析 24
传递闭包的矩阵算法
? 若 |S| = n,则 R可表示为一个矩阵 M。 于是 R的
传递闭包 R*的矩阵 M*为：
i=nM* = ∪ Mi = M0∪ M1∪ … ∪ Mn
i=0
其中 M0为单位矩阵 E,Mi为 M的 i次幂。
? M* = E;
for (i=1; i<=n; i++) M* = M* ∪ M*M
? 不难看出此算法的时间复杂性为 O(n4)。
2010-5-14 计算机算法设计与分析 25
传递闭包的 Warshall算法
? 下面给出求传递闭包的 Warshall算法：
? for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (M[j][i] == 1)
for (k = 1; k <= n; k++)
M[j][k] = M[j][k] + M[i][k]
? 此算法含三重循环，时间复杂性显然为 O(n3)。
? 算法的正确性可用归纳法证明，请同学们自己
去证明一下。
2010-5-14 计算机算法设计与分析 26
分支限界法小结
? 分支限界法是最佳优先 (包括广度优先在内 )的
搜索法，也是一种较为通用的算法。
? 其搜索的控制是采用有序的队列，即每次优先
搜索评价函数值最小的结点，从而希望较快地
找到 最佳的路径 或 排列 。
? 与其它算法相比，时间复杂性无本质区别。但
好的评价函数可有小的常数，提高了效率。
? 评价函数应该能正确有效地压缩状态空间。
第六章
分支限界法
2010-5-14 计算机算法设计与分析 2
分支限界法是最佳优先搜索法
? 分支限界法就是最佳优先 (包括广度优先在内 )
的搜索法。
? 分支限界法将要搜索的结点按评价函数的优劣
排序，让好的结点优先搜索，将坏的结点剪去。
所以准确说，此方法应称为界限剪支法。
? 分支限界法中有两个要点：
? (1)评价函数的构造；
? (2)搜索路径的构造。
2010-5-14 计算机算法设计与分析 3
评价函数的构造
? 评价函数要能够提供一个评定候选扩展结点的
方法，以便确定哪个结点最有可能在通往目标
的最佳路径上。
? 一个评价函数 f(d)通常可以由两个部分构成：
⑴从开始结点到结点 d的已有耗损值 g(d),和⑵
再从结点 d到达目标的期望耗损值 h(d)。 即：
f(d) = g(d) + h(d)
? 通常 g(d)的构造较易,h(d)的构造较难。
2010-5-14 计算机算法设计与分析 4
搜索路径的构造
? 在回溯法中，每次仅考察一条路径，因
而只需要构造这一条路径即可：前进时
记下相应结点，回溯时删去最末尾结点
的记录。这比较容易实现。
? 在分支限界法中，是同时考察若干条路
径，那么又该如何构造搜索的路径呢？
对每一个扩展的结点，建立三个信息：
? (1)该结点的名称；
? (2)它的评价函数值；
? (3)指向其前驱的指针；
这样一旦找到目标，即可逆向构造其路径。
? 用一个表保存准备扩展的结点，称为 Open表。
? 用一个表保存已搜索过的结点, 称为 Closed表。
2010-5-14 计算机算法设计与分析 5
分支限界法的一般算法
? ⑴计算初始结点 s的 f(s); [s,f(s),nil]放入 Open;
? ⑵ while (Open ≠Φ) {
? ⑶ 从 Open中取出 [p,f(p),x](f(p)为最小 );
? ⑷ 将 [p,f(p),x]放入 Closed;
? ⑸ 若 p是目标，则成功返回；否则
? ⑹ { 产生 p的后继 d并计算 f(d) ；对每个后继 d
有二种情况,① d?Closed || d ?Open；
② d?Open && d?Closed。
? ⑺ {若 ([d,f’(d),p]?Closed || [,f’(d),]?Open)
&& f(d)＜ f’(d)，则删去旧结点并将 [d,f( ),p]
重新插入到 Open中 ; 否则
? ⑻ 将 [d,f(d),p] 插入到 Open中 }}}。
2010-5-14 计算机算法设计与分析 6
分支限界法求单源最短路径
? 单源最短路径问题的评价函数的构造：
? g(d)定义为从源 s到结点 d所走的路径长度：
g(d) = g(p) + C[p][d]
这里 p为 d的前驱结点,C[p][d]为 p到 d的距离。
? h(d)定义为 0。 于是 f(d) = g(d)。
? 源 s的评价函数 f(s) = 0。
? 评价函数的下界为 0；上界初始时为 ∞，以后不
断用取得的更短路径的长度来替代。
2010-5-14 计算机算法设计与分析 7
分支限界法求最短路径举例
1
2 5
43
10
20
50
100
30
10 60
赋权图 G
初始时，将源 [1,0,0]放入 Open,Closed为空。
Open表
[1,0,0]
Closed表
取出 [1,0,0]放入 Closed； 生成其后继 [2,10,1]、
[4,30,1]和 [5,100,1]，并依序放入 Open。
[1,0,0][5,100,1]
[4,30,1]
[2,10,1]
取出 2 10,1]放入 Closed； 生成其后继 [3,60,2]，
并依序插入 Open。
[2,10,1]3,60,2]
4,30,1]
取出 [4,30,1]放入 losed； 生成其后继 [3,50,4]
和 [5,90,4],修订 Open中已有的两个结点并依
序排列 。
[4,30,1]
[5,90,4]
50,4]
取出 3 5 4 放入 ； 生成其后继 2,1 0,3]
和 6 3,前者因劣于 Closed中的 [2,10,1]而
被抛弃，后者修订了 Open中的 [5,90,4]。
[3,50,4]
60,3]
取出 5,6,3,因其已经是目标结点，算法成
功并终止。
依据逆向指针可得最短路径为 1→4→3→5 。
2010-5-14 计算机算法设计与分析 8
界限 (Bounding)
? 评价函数 f(d)关系着算法的效率乃至成败。
? 因为在大多数问题中 f(d)只是个估计值，所以
单靠 f(d)是不够的。通常还要设计它的上下界
函数 U(d)和 L(d)。 L(d)≤f(d)≤U(d)。
? 所谓分支限界法就是通过评价函数及其上下界
函数的计算，将状态空间中不可能产生最佳解
的子树剪去，减少搜索的范围，提高效率。因
而更准确的称呼应是“界限剪支法”
2010-5-14 计算机算法设计与分析 9
用分支限界法求 TSP
? TSP是求排列的问题，不是仅找一条路径而已。
因而需要对分支限界法的一般算法作些修改：
? (1)待扩展的结点如果在本路径上已经出现，则
不再扩展，但若是在其他路径上出现过，则仍
需要扩展。
? (2)新结点，无论其优劣，既不影响其它路径上
的结点，也不受其它路径上的结点的影响。
? (3)依据上界函数决定结点是否可以剪去。
2010-5-14 计算机算法设计与分析 10
分支限界法求排列
? ⑴计算初始结点 s的 f(s); [s,f(s),nil]放入 Open;
? ⑵ while (Open ≠Φ) {
? ⑶ 从 Open中取出 [p,f(p),L]; //L是路径已有结点
? ⑷ 若 f(p)≥U,则抛弃该路径；
? ⑸ 若 p是目标，则考虑修改上界函数值；否则
? ⑹ {将 [p,f(p),L]放入 Closed;
? ⑺ 在该路径上扩展结点 p；对每个后继 d
? ⑻ {计算 f(d)；
? ⑼ 若 f(d)＜ U,则 {L = L ?{p};
? 将 [d,f(d),L]依序放入 Open。 }
? } } }
2010-5-14 计算机算法设计与分析 11
分支限界法求 TSP举例
? 设有向图 G = (V,E)的边的代价矩阵为 C = [cij]。
若不存在有向边 <i,j>∈ E,则定义 cij=∞且规定
cii=∞。 不失一般性，设周游路线均以顶点 1为起
点。左下为一个有向图 G的代价矩阵 C。
∞ 25 40 31 27
5 ∞ 17 30 25
19 15 ∞ 6 1
9 50 24 ∞ 6
22 8 7 10 ∞
? 评价函数 f(d)为 1到 d的代
价减去已经过的边数。
? 初始时 f(1) = 0;
? f(d) = f(p) + cpd – 1,这里
p是 d的前驱。
2010-5-14 计算机算法设计与分析 12
分支限界法求 TSP的搜索
∞ 25 40 31 27
5 ∞ 17 30 25
19 15 ∞ 6 1
9 50 24 ∞ 6
22 8 7 10 ∞
10
224 339 430 526
340 453 548 233 332 435279 353 545
246 4373
49
4
62
284 358
286
找到了第一条周游路
线 1→5→3→4→2→1,
其长度为 95。
这不是最短周游路线，需要修改上界后继续搜索。
2010-5-14 计算机算法设计与分析 13
归约矩阵以及约数
? 前面的搜索的效率不高，几乎要搜索全
部的状态空间。其原因是评价函数以及
上下界的估计太低。为了设计求解 TSP
问题的更好的评价函数，先定义其代价
矩阵的归约矩阵和约数。
给定代价矩阵 C,从 C的任何行 i(或列 i)的
各元素中减去此行 (或此列 )的最小元素的
值 r(i)(或 r’(i)),称为对 i行 (或 i列 )的归约。
将 C的各行和各列都归约后的矩阵称为 C
的归约矩阵。和数
r = ∑i≤n r(i) + ∑i≤n r’(i)
称为 C的约数。
2010-5-14 计算机算法设计与分析 14
例子中的归约矩阵和约数
? 计算前面例子中的归约矩阵及其约数如下：
∞ 25 40 31 27
5 ∞ 17 30 25
19 15 ∞ 6 1
9 50 24 ∞ 6
22 8 7 10 ∞
先做行归约：
r(1)=25∞ 0 15 6 2
r(2)=50 ∞ 12 25 20
r(3)=118 14 ∞ 5 0
r(4)=63 44 21 ∞ 0
r(5)=715 1 0 3 ∞
再做列归约：
r’(1)=r’(2)=r’(3)=r’(5)=0 r’(4)=3
3
22
2
∞
0
? 约数 r = 47。
2010-5-14 计算机算法设计与分析 15
约数是周游路线长度的下界
? 定理：设 C是图 G的代价矩阵,P是周游路线，
则 P的代价，即 ∑<i,j>∈ P cij = r + ∑<i,j>∈ P c’ij,
式中 C’ = [c’ij]是 C的归约矩阵,r为约数。
? 证明：由归约矩阵的构造可知：
c’ij = cij – r(i) –r’(j)
即 cij = c’ij + r(i) + r’(j)。
? 任何周游路线包含 n条边并且对应在 C中的
每行每列有且仅有一条边。于是
∑<i,j>∈ P cij = ∑<i,j>∈ P(c’ij + r(i) + r’(j))。r + ∑<i,j>∈ P c’ij 。
2010-5-14 计算机算法设计与分析 16
定义期望函数 h(d)
? 对开始结点 1，令 g(1) = 0,h(1) = r,f(1) = r。
? 若从结点 1选择了一条边，不妨设边 <1,2>，则
令 g(2) = f(1)+从 1到 2的距离 l, 显然 l应该是 c’12，
而不应该再是 c12了。
? 那么 h(2) =？
? 自然可以想到 h(2)可以是从 2开始的路线的下界
r2。 是否也可用类似求 r一样去求新的约数 r2呢？
? 可以，但在此之前应将边 <1,2>和所有边 <1,k>
和边 <k,2>都删去，即置 c’12,c’1k和 c’k2为 ∞。
? 设 C’p为某路线上结点 p的归约矩阵。从 p选择边
<p,d>所得到结点 d的归约矩阵 C’d和约数 rd为：
? (1)将 C’p中的 c’pd,c’pk和 c’kd置为 ∞,1≤k≤n；
? (2)依照求归约矩阵 C’的方法对 C’p进行行归约
和列归约，便得到了 C’d和 rd 。
? 令 f(1) = g(1) + h(1),其中 g(1) = 0,h(1) = r。
? 对任意路线上的结点 d,设 p是其前驱结点，则
f(d) = g(d) + h(d)，
其中,g(d) = f(p) + C’p[p][d],h(d) = rd。
2010-5-14 计算机算法设计与分析 17
用新的评价函数求 TSP
? 下面用新的评价函数求前面的例子，我们已经
求得了它的归约矩阵 C’和约数 r = 47。
∞ 0 15 3 2
0 ∞ 12 22 20
18 14 ∞ 2 0
3 44 18 ∞ 0
15 1 0 0 ∞
147
2
g(2) = 47 + 0 = 47
∞ ∞ ∞ ∞
∞
∞
∞
∞
0 10 8
0
15
12
h(2) = 12 + 3 = 15
f(2) = 47 +15 = 62
62 3
3) + 15 = 62 ∞ ∞
∞
∞0
43
13
3) = 1
3) = 63
63 4
类似地可求出
f(4) = 51。
51 5
类似地可求出
5) = 50。
50
下面优先扩展的是结
点 5。
2
此时 C’2是在 C’5的基
础上进行。右边就是
C’5。
∞ ∞ ∞ ∞ ∞
0 ∞ 12 22 ∞
18 14 ∞ 2 ∞
3 44 18 ∞ ∞
∞ 0 0 0
g(2) = 50 + 0 = 50
∞ ∞ ∞
∞
∞ 016
0 15
0
3
h 2) = 17
f(2) = 67
67 3
类似地计算出 f(3) = 68
68 4
类似地计算出 4) = 81
81
下面扩展 f(4) = 51的结
点 4。并用同样方法计
算它们的评价函数值。
2121 369 464
下面要扩展的结点
是 f(2)= 62的结点 2。
右边是其对应的归
约矩阵 C’2。
∞ ∞ ∞ ∞
∞ ∞ 0 10 8
15 ∞ ∞ 2 0
0 ∞ 18 ∞ 0
12 ∞ 0 0 ∞
3
g(3) = 62 + 0 = 62；
对 C’2进行归约，
∞ ∞ ∞
∞
得
h(3) = 0； 于是
f(3) = 62。
62
对结点 2的另外两个
儿子进行同样的计
算，得：
f(4) = 84,f(5) = 72。
484 572
下面对 f(3) = 62的结
点 3进行扩展。它有
两个后继结点。
4 5
对结点 4，
g(4) = 62 + 2 = 64。 ∞ ∞
0
h(4) = 12, 于是
f(4) = 64 + 12 = 76
76 对结点 5，
5) + 0 。
∞ ∞ ∞
∞ ∞ 0
∞ 0 ∞
∞
∞
∞
5) = 0,于是
5) = 62 + 0 = 62
62
对结点 5(f(5) = 62)
再进行扩展。4
g = 62 + 0 = 62，
h(4) = 0,f(4) = 62。
62
结点 4是目标结点，
找到了第一条路线。
这条路线的长度为
62，以其为上界。
其余未扩展的结点
的评价函数值均超
过上界，因而不再
需要扩展了。
×
× × ×××
×
×× ×
于是找到了一条最
短的周游路线：
1→2→3→5→4→1 。
2010-5-14 计算机算法设计与分析 18
分支边与二叉树
? 在构造求 TSP的搜索树时，还有另外一种算法
稍有点不同，就是将搜索树构造成二叉树。
? 给定一条最短周游路线 P,对于任一条边 <i,j>
只有两种情况，即 <i,j>?P或者 <i,j>?P。
? 这就可以表示成右边的二叉树,k
m
<i,j>
n
____
<i,j>? 其中
____
<i,j>表示 <i,j>?P。
? 这样的边称为分支边。
2010-5-14 计算机算法设计与分析 19
用二叉树求 TSP
1<2,1>
250
____
<2,1>
3 62<4,5>
453
____
<4,5>
5 68
<1,4>
664
____
<1,4>
7 65
<4,1>
862
____
<4,1>
9 74<2,3>
1062
____
<2,3>
11 70<3,5>
1262
___
<3,5>
13 66<5,4>
1462
___
<5,4>
15 66<1,2>
16 62
____
<1,2>
17 ∞
结点 16给出了一条
最短周游路线：
1→2→3→5→4→1
2010-5-14 计算机算法设计与分析 20
分支限界法的效率
? 从 TSP问题的计算可看出，分支限界法搜索的
状态空间为 O(2n)。
? 对每个结点的计算时间为 O(n2)。
? 因此在最坏情况下，分支限界法计算 TSP的时
间复杂性为 O(n22n)。
? 显然，用分支限界法计算 TSP的空间复杂性为
O(n22n)。 因为对每个结点需要 n2的空间。
2010-5-14 计算机算法设计与分析 21
对评价函数的讨论
? 分支限界法总耗时为 O(n22n),它与回溯法、动
态规划法等在时间复杂性上没有本质的区别。
? 然而，如果评价函数选择得好，采用分支限界
法可能有一个小得多的常数因子。
? 好的评价函数应该有一个尽可能高的下界估计
和一个尽可能低的上界估计，从而使得搜索空
间能够得到有效的压缩，从而提高效率。
? 在理论上可以证明好的评价函数所搜索的结点
不会多于坏的评价函数所搜索的结点。
2010-5-14 计算机算法设计与分析 22
关系、传递闭包与搜索
? 定义在集合 S上关系 R是笛卡儿直积 S× S的一个
子集,R?S× S。
? 关系 R的传递闭包是包含 R的最小的具有传递性
质的关系。
? 若 S是有限的,|S| = n,则 R可表示为一个 n× n
的关系矩阵 M或 n个结点的有向图 G。
? 求关系 R的传递闭包实际上也就是在有向图 G
上的搜索。而反过来，在有向图 G上的搜索也
就是求某种关系的传递闭包。
2010-5-14 计算机算法设计与分析 23
传递闭包的集合算法
? 给定关系 R以及 S中的元素 a,求 R*(a)。
初始化,U = A = {a}; q = true;
while (q) {
for (?p∈ A) U = U ∪ {d | d∈ S 且 pRd}；
if (U == A) q = false;
else A = U }
? 这个算法稍加修改即可变成求 R*(a)中满足某性
质的元素的算法。
? 不难看出此算法实际也就是分支限界法。
2010-5-14 计算机算法设计与分析 24
传递闭包的矩阵算法
? 若 |S| = n,则 R可表示为一个矩阵 M。 于是 R的
传递闭包 R*的矩阵 M*为：
i=nM* = ∪ Mi = M0∪ M1∪ … ∪ Mn
i=0
其中 M0为单位矩阵 E,Mi为 M的 i次幂。
? M* = E;
for (i=1; i<=n; i++) M* = M* ∪ M*M
? 不难看出此算法的时间复杂性为 O(n4)。
2010-5-14 计算机算法设计与分析 25
传递闭包的 Warshall算法
? 下面给出求传递闭包的 Warshall算法：
? for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (M[j][i] == 1)
for (k = 1; k <= n; k++)
M[j][k] = M[j][k] + M[i][k]
? 此算法含三重循环，时间复杂性显然为 O(n3)。
? 算法的正确性可用归纳法证明，请同学们自己
去证明一下。
2010-5-14 计算机算法设计与分析 26
分支限界法小结
? 分支限界法是最佳优先 (包括广度优先在内 )的
搜索法，也是一种较为通用的算法。
? 其搜索的控制是采用有序的队列，即每次优先
搜索评价函数值最小的结点，从而希望较快地
找到 最佳的路径 或 排列 。
? 与其它算法相比，时间复杂性无本质区别。但
好的评价函数可有小的常数，提高了效率。
? 评价函数应该能正确有效地压缩状态空间。
