第六章回溯法 §1.回溯法的基本思想 回溯法有“通用的解题法”之称。应用回溯法解问题时,首先应 该明确问题的解空间。一个复杂问题的解决往往由多部分构成,即 一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们 构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题 的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来, 解任何问题都有一个目标,在约束条件下使目标达优的可行解称为该 问题的最优解。在解空间中,前k项决策已经确定的所有决策序列之 集称为k定子解空间。0定子解空间即是该问题的解空间。 例1.旅行商问题:某售货员要到若干个城市去推销商品。已知各 个城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个 城市一次,最后回到驻地的路线,使得总的路程(或总旅费)最短。 我们用一个带权图G(VE来表示,顶点代表城市,边表示城市之 间的道路。图中各边所带的权即是城市间的距离(或城市间的旅费)。 A 6 10 具有四个顶点的带权图 则旅行商问题即是:在带权图G中找到一条路程最短的周游路线,即
第六章 回 溯 法 § 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.定和子集问题:已知一个正实数的集合A={,2…,wn} 和正实数M.试求A的所有子集S,使得S中的数之和等于M 这个问题的解可以表示成0/数组(x1,x2,,xn),依据w是否 属于S,x1分别取值1或0。故解空间中共有2个元素。它的树结构 是一棵完全二叉树 例3.4皇后问题:在4×4棋盘上放置4个皇后,且使得每两个之 间都不能互相攻击,即任意两个皇后都不能放在同一行、同一列及同 对角线上。 将4个皇后分别给以1到4的编号,这个问题的解决就是要安排 4个皇后的位置。因而,每个决策序列由4个决策组成:P1,P2,P3, P4,这里P代表安排第k个皇后的位置,因而有16种可能。该问题 的解空间有164个决策序列。这时的约束条件是:任意两个皇后均不 能位于同一行、同一列及同一个对角线上。注意到这个解空间比较大, 从中搜索可行解较为困难。现在把约束条件中的“任意两个皇后均不 在同一行”也放在问题中考虑,即:将4个皇后放在4×4棋盘的不
权值之和最小的 Hamilton 圈。 如果假定城市 A 是驻地。则推销员从 A 地出发，第一站有 3 种选 择：城市 B、C 或城市 D；第一站选定后，第二站有两种选择：如第 一站选定 B，则第二站只能选 C、D 两者之一。当第一、第二两站都 选定时，第三站只有一种选择：比如，当第一、第二两站先后选择了 B 和 C 时，第三站只能选择 D。最后推销员由城市 D 返回驻地 A。推 销员所有可能的周游路线可由下面的图反映出来。 例 2．定和子集问题：已知一个正实数的集合 { , , , } A = w 1 w2 L wn 和正实数 M．试求 A 的所有子集 S，使得 S 中的数之和等于 M。 这个问题的解可以表示成 0/1 数组(x1, x2, . . . , xn )，依据 wi是否 属于 S，xi分别取值 1 或 0。故解空间中共有 2n个元素。它的树结构 是一棵完全二叉树。 例 3．4 皇后问题: 在 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中找出满足某种性质的子集时,相应的解 空间树称为子集合树。此时,解空间有2″个元素,遍历子集树的任 何算法均需Ω2(2")的计算时间。如例2。当所给的问题是确定n个元 素的满足某种性质的排列时,相应的解空间树称为排列树,此时,解 空间有n个元素。遍历排列树的任何算法均需Ω(nl)计算时间,如例 1和例3。本章只讨论具有上两类解空间树的求解问题。 确定了解空间的组织结构后,回溯法就从开始顶点(解空间树的 根顶点)出发,以深度优先的方式搜索整个解空间。这个开始顶点就 成为一个活顶点,同时也成为当前的扩展顶点。在当前的扩展顶点处, 搜索向纵深方向移至一个新顶点。这个新顶点就成为一个新的活顶 点,并且成为当前的扩展顶点。如果在当前的扩展顶点处不能再向纵
同行上，使得每两个皇后均不能位于同一列、同一对角线上。则解 空间中共有 44个决策序列，因为此时可以假定第 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背包问题 定和子集问题可以描述成下列的数学问题:确定所有向量 x=(x1,x2,…,xn)满足
深方向移动，则当前的扩展顶点就成为死顶点。此时应往回移动（回 溯）至最近一个活顶点处，并使这个活顶点成为当前扩展顶点。回溯 法即以这种工作方式递归地在解空间中搜索，直至找到要求的解或解 空间中已无活结点时为止。事实上，当我们将问题的有关数据以一定 的方式存储好以后（例如，旅行商问题存储赋权图的邻接矩阵、定和 子集问题是存储已知的 n+1 个数、4 皇后问题用整数对(i,j)表示棋 盘上各个位置），不必先建立一个解空间树，然后再搜索该树寻找所 需要的解。回溯法实际上在搜索的同时逐步生成解空间树（实际只需 要一部分）。也就是说，对于实际问题我们不必要搜索整个解空间。 为了使搜索更加有效，我们常常在搜索过程中加一些判断以决定搜索 是否该终止或改变路线。通常采用两种策略来避免无效的搜索，提高 回溯法的搜索效率。其一是使用约束函数在扩展顶点处剪去不满足约 束的子树；其二是用限界函数（后面将阐述）剪去不能得到最优解的 子树。这两种函数统称为剪枝函数。 运用回溯法解题通常包括以下三个步骤： 1).针对所给问题，定义问题的解空间； 2).确定易于搜索的解空间结构； 3).以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函 数避免无效的搜索。 §2.定和子集问题和 0/1 背包问题 定和子集问题可以描述成下列的数学问题：确定所有向量 ( , , , ) 1 2 n x = x x L x 满足：
x∈{0,1},=1,2,…,n ∑x1=M (7.1) 如果让w;表示第i件物品的重量,M代表背包的容量,则0/1背 包问题可以描述为:确定一个向量x=( xn)满足 0,1},=1,2 ∑x≤M (7.2) l≤i≤n s!.max∑px 这是一个优化问题,与定和子集问题比较,它多出优化函数,但只要 求确定一个最优解,定和子集问题要求确定所有可行解。我们先来处 理定和子集问题。 ).定和子集问题 用回溯法求解的过程也即是生成解空间树的一棵子树的过程,因为期 间将剪掉不能产生可行解的子树(即不再对这样的子树进行搜索)。 按照前面关于回溯算法的基本思想的说明,搜索是采用深度优先的路 线,算法只记录当前路径。假设当前扩展顶点是当前路径的k级,也 就是说当前路径上,x,1≤i≤k已经确定,算法要决定下一步搜索目 标。此时,有两种情况 ∑x1=M与∑w1x<M 前一种情况说明当前路径已经建立一个可行解,当前扩展顶点即是 个答案顶点。此时应停止对该路径的继续搜索,返回到前面最近活顶 点。后一种情况出现,算法需要判断是否需要继续向前搜索。显然 只有当∑wx+∑≥M时才有必要继续向前搜索。如果集合 l≤i≤k k+l≤i≤n
w x M x i n i i n i i = ∈ = ∑ 1≤ ≤ {0,1}, 1,2,L, (7.1) 如果让 wi表示第 i 件物品的重量，M 代表背包的容量，则 0/1 背 包问题可以描述为：确定一个向量 ( , , , ) 1 2 n x = x x L x 满足 i i n i i i n i i st p x w x M x i n ∑ ∑ ≤ ≤ ≤ ≤ ≤ ∈ = 1 1 . . max {0,1}, 1,2,L, (7.2) 这是一个优化问题，与定和子集问题比较，它多出优化函数，但只要 求确定一个最优解，定和子集问题要求确定所有可行解。我们先来处 理定和子集问题。 (一).定和子集问题 用回溯法求解的过程也即是生成解空间树的一棵子树的过程，因为期 间将剪掉不能产生可行解的子树（即不再对这样的子树进行搜索）。 按照前面关于回溯算法的基本思想的说明，搜索是采用深度优先的路 线，算法只记录当前路径。假设当前扩展顶点是当前路径的 k 级，也 就是说当前路径上，xi，1≤i≤k 已经确定，算法要决定下一步搜索目 标。此时，有两种情况： w xi M i k ∑ i = 1≤ ≤ 与 w xi M i k ∑ i < 1≤ ≤ 前一种情况说明当前路径已经建立一个可行解，当前扩展顶点即是一 个答案顶点。此时应停止对该路径的继续搜索，返回到前面最近活顶 点。后一种情况出现，算法需要判断是否需要继续向前搜索。显然， 只有当 w x w M k i n i i i k ∑ i + ∑ ≥ 1≤ ≤ +1≤ ≤ 时才有必要继续向前搜索。如果集合