第七章 回溯法.pdf

第六章回溯法
§ 1. 回溯法的基本思想
回溯法有“通用的解题法”之称。应用回溯法解问题时,首先应
该明确问题的解空间。一个复杂问题的解决往往由多部分构成,即,
一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们
构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题
的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来,
解任何问题都有一个目标,在约束条件下使目标达优的可行解称为该
问题的最优解。在解空间中,前 k 项决策已经确定的所有决策序列之
集称为 k 定子解空间。0 定子解空间即是该问题的解空间。
例 : 某售货员要到若干个城市去推销商品。已知各
个城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个
城市一次,最后回到驻地的路线,使得总的路程(或总旅费)最短。
我们用一个带权图 G(V, E)来表示,顶点代表城市,边表示城市之
间的道路。图中各边所带的权即是城市间的距离(或城市间的旅费)。

30
A B

5
4
6 10


20
C D
具有四个顶点的带权图
则旅行商问题即是:在带权图 G 中找到一条路程最短的周游路线,即
权值之和最小的 Hamilton 圈。
如果假定城市 A 是驻地。则推销员从A 地出发,第一站有3 种选
择:城市 B、C 或城市 D;第一站选定后,第二站有两种选择:如第
一站选定 B,则第二站只能选 C、D 两者之一。当第一、第二两站都
选定时,第三站只有一种选择:比如,当第一、第二两站先后选择了
B 和 C 时,第三站只能选择 D。最后推销员由城市 D 返回驻地 A。推
销员所有可能的周游路线可由下面的图反映出来。
例 : 已知一个正实数的集合 A = {w , w , , w }
1 2 L n
和正实数 A 的所有子集 S,使得 S 中的数之和等于 M。
这个问题的解可以表示成 0/1 数组(x1, x2, . . . , xn ),依据 wi 是否
n
属于 S,xi 分别取值 1 或 0。故解空间中共有 2 个元素。它的树结构
是一棵完全二叉树。
例 皇后问题: 在 4×4 棋盘上放置 4 个皇后,且使得每两个之
间都不能互相攻击,即任意两个皇后都不能放在同一行、同一列及同
一对角线上。
将 4 个皇后分别给以 1 到 4 的编号,这个问题的解决就是要安排
4 个皇后的位置。因而,每个决策序列由 4 个决策组成:P1,P2,P3,
P4,这里 Pk 代表安排第 k 个皇后的位置,因而有 16 种可能。该问题
的解空间有 164 个决策序列。这时的约束条件是: 任意两个皇后均不
能位于同一行、同一列及同一个对角线上。注意到这个解空间比较大,
从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不
在同一行”也放在问题中考虑,即:将 4 个皇后放在 4×4 棋盘的不
同行上,使得每两个皇后均不能位于同一列、同一对角线上。则解
空间中共有 44 个决策序列,因为此时可以假定第 k 个皇后处于第 k
行上。此时的约束条件为:任意两个皇后均不能位于同一列及同一个
对角线上。事实上,我们还可以用另一种方法描述,使得解空间进一
步缩小。将问题陈述为:将 4 个皇后放在 4×4 棋盘的不同行、不同
列上,使得任意两个皇后均不能处在同一对角线上。这时的解空间应
当由 4!个决策序列构成。因为此时每个决策序列实际上对应于{1, 2,
3, 4}的一个排列。我们可以用树来描述解空间。
从例 3 来看,解空间的确定与我们对问题的描述有关。如何组织
解空间的结构会直接影响对问题的求解效率。这是因为回溯方法的基
本思想是通过搜索解空间来找到问题的可行解以至最优解。当所给的
问题是从 n 个元素的集合 S 中找出满足某种性质的子集时,相应的解
空间树称为子集合树。此时,解空间有2n 个元素,遍历子集树的任
何算法均需Ω(2n ) 的计算时间。如例 2。当所给的问题是确定 n 个元
素的满足某种性质的排列时,相应的解空间树称为排列树,此时,解
空间有 n!个元素。遍历排列树的任何算法均需Ω(n!) 计算时间,如例
1 和例 3。本章只讨论具有上两类解空间树的求解问题。
确定了解空间的组织结构后,回溯法就从开始顶点(解空间树的
根顶点)出发,以深度优先的方式搜索整个解空间。这个开始顶点就
成为一个活顶点,同时也成为当前的扩展顶点。在当前的扩展顶点处,
搜索向纵深方向移至一个新顶点。这个新顶点就成为一个新的活顶
点,并