I
import
Unregistered / Unconfirmed
GUEST, unregistred user!
常用算法（4）回溯算法 --------------------------------------------------------------------------------
作者:liuchaohai 来源: 类别:数据算法 日期:2002.09.19 今日/总浏览: 4/9
第 4 章 回溯
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。
本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
4.1 算法思想
回溯（b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；在具有n 个对象的0 / 1背包问题中（见1 . 4节和2 . 2节），解空间的一个合理选择是2n 个长度为n 的0 / 1向量的集合，这个集合表示了将0或1分配给x的所有可能方法。当n= 3时，解空间为{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图1 6 - 1用图的形式给出了一个3×3迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了3×3迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。
图1 6 - 2用树形结构给出了含三个对象的0 / 1背包问题的解空间。从i 层节点到i+ 1层节点的一条边上的数字给出了向量x 中第i个分量的值xi ，从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A到叶节点H的路径定义了解x= [ 1 , 1 , 1 ]。根据w 和c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点( 1 , 1 )；在0 / 1背包问题中，开始节点为根节点A。开始节点既是一个活节点又是一个E-节点（expansion node）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。
例4-1 [迷宫老鼠] 考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图1 6 -1给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图1 6 - 1中从( 1 , 1 )到( 3 , 3 )的一条路径相对应。然而，图1 6 - 1中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口的路径。搜索从点( 1 , 1 )开始，该点是目前唯一的活节点，它也是一个E-节点。为避免再次走过这个位置，置m a z e( 1 , 1 )为1。从这个位置，能移动到( 1 , 2 )或( 2 , 1 )两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值0。假定选择移动到( 1 , 2 )，m a z e( 1 , 2 )被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为E-节点。
在图1 6 - 1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置，并置m a z e( 1 , 3 )为1以避免再次经过该点，此时迷宫状态为1 6 - 3 c。图1 6 - 1中，从( 1 , 3 )出发有两个可能的移动，但没有一个是可行的。所以E-节点( 1 , 3 )死亡，回溯到最近被检查的活节点( 1 , 2 )。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是( 1 , 1 )。这个节点再次变为E-节点，它可移动到( 2 , 1 )。现在活节点为( 1 , 1 )，( 2 , 1 )。继续下去，能到达点( 3 , 3 )。此时，活节点表为( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，这即是到达出口的路径。
程序5 - 1 3是一个在迷宫中寻找路径的回溯算法。
例4-2 [0/1背包问题] 考察如下背包问题：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。从根节点开始搜索图1 6 - 2中的树。根节点是当前唯一的活节点，也是E-节点，从这里能够移动到B或C点。假设移动到B，则活节点为A和B。B是当前E-节点。在节点B，剩下的容量r 为1 0，而收益c p 为4 0。从B点，能移动到D或E。移到D是不可行的，因为移到D所需的容量w2 为1 5。到E的移动是可行的，因为在这个移动中没有占用任何容量。E变成新的E-节点。这时活节点为A , B , E。在节点E，r= 1 0，c p= 4 0。从E，有两种可能移动（到J 和K），到J 的移动是不可行的，而到K的移动是可行的。节点K变成了新的E-节点。因为K是一个叶子，所以得到一个可行的解。这个解的收益为c p= 4 0。x 的值由从根到K的路径来决定。这个路径（ A , B , E , K）也是此时的活节点序列。既然不能进一步扩充K，K节点死亡，回溯到E，而E也不能进一步扩充，它也死亡了。接着，回溯到B，它也死亡了，A再次变为E-节点。它可被进一步扩充，到达节点C。此时r= 3 0，c p= 0。从C点能够移动到F或G。假定移动到F。F变为新的E-节点并且活节点为A, C,F。在F，r= 1 5，c p= 2 5。从F点，能移动到L或M。假定移动到L。此时r= 0，c p= 5 0。既然L是一个叶节点，它表示了一个比目前找到的最优解（即节点K）更好的可行解，我们把这个解作为最优解。节点L死亡，回溯到节点F。继续下去，搜索整棵树。在搜索期间发现的最优解即为最后的解。
例4-3 [旅行商问题] 在这个问题中，给出一个n 顶点网络（有向或无向），要求找出一个包含所有n 个顶点的具有最小耗费的环路。任何一个包含网络中所有n 个顶点的环路被称作一个旅行（t o u r）。在旅行商问题中，要设法找到一条最小耗费的旅行。
图1 6 - 4给出了一个四顶点网络。在这个网络中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行2 , 4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一样。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。旅行1 , 2 , 4 , 3 , 1的耗费为6 6；而1 , 3 , 2 , 4 , 1的耗费为2 5；1 , 4 , 3 , 2 , 1为5 9。故1 , 3 , 2 , 4 , 1是该网络中最小耗费的旅行。
顾名思义，旅行商问题可被用来模拟现实生活中旅行商所要旅行的地区问题。顶点表示旅行
商所要旅行的城市（包括起点）。边的耗费给出了在两个城市旅行所需的时间（或花费）。旅行表示当旅行商游览了所有城市再回到出发点时所走的路线。
旅行商问题还可用来模拟其他问题。假定要在一个金属薄片或印刷电路板上钻许多孔。孔的位置已知。这些孔由一个机器钻头来钻，它从起始位置开始，移动到每一个钻孔位置钻孔，然后回到起始位置。总共花的时间是钻所有孔的时间与钻头移动的时间。钻所有孔所需的时间独立于钻孔顺序。然而，钻头移动时间是钻头移动距离的函数。因此，希望找到最短的移动路径。
另有一个例子，考察一个批量生产的环境，其中有一个特殊的机器可用来生产n 个不同的产品。利用一个生产循环不断地生产这些产品。在一个循环中，所有n 个产品被顺序生产出来，然后再开始下一个循环。在下一个循环中，又采用了同样的生产顺序。例如，如果这台机器被用来顺序为小汽车喷红、白、蓝漆，那么在为蓝色小汽车喷漆之后，我们又开始了新一轮循环，为红色小汽车喷漆，然后是白色小汽车、蓝色小汽车、红色小汽车，..，如此下去。一个循环的花费包括生产一个循环中的产品所需的花费以及循环中从一个产品转变到另一个产品的花费。虽然生产产品的花费独立于产品生产顺序，但循环中从生产一个产品转变到生产另一个产品的花费却与顺序有关。为了使耗费最小化，可以定义一个有向图，图中的顶点表示产品，边＜(i , j)＞上的耗费值为生产过程中从产品i 转变到产品j 所需的耗费。一个最小耗费的旅行定义了一个最小耗费的生产循环。
既然旅行是包含所有顶点的一个循环，故可以把任意一个点作为起点（因此也是终点）。
针对图1 6 - 4，任意选取点1作为起点和终点，则每一个旅行可用顶点序列1, v2 ,., vn , 1来描述，
v2 , ., vn 是(2, 3, ., n) 的一个排列。可能的旅行可用一个树来描述，其中每一个从根到叶的路
径定义了一个旅行。图1 6 - 5给出了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一个旅行（还要附加1作为终点）。例如，到节点L的路径表示了旅行1 , 2 , 3 , 4 , 1，而到节点O的路径表示了旅行1 , 3 , 4 , 2 , 1。网络中的每一个旅行都由树中的一条从根到叶的确定路径来表示。因此，树中叶的数目为(n- 1 )！。
回溯算法将用深度优先方式从根节点开始，通过搜索解空间树发现一个最小耗费的旅行。对图1 6 - 4的网络，利用图1 6 - 5的解空间树，一个可能的搜索为A B C F L。在L点，旅行1 , 2 , 3 , 4 , 1作为当前最好的旅行被记录下来。它的耗费是5 9。从L点回溯到活节点F。由于F没有未被检查的孩子，所以它成为死节点，回溯到C点。C变为E-节点，向前移动到G，然后是M。这样构造出了旅行1 , 2 , 4 , 3 , 1，它的耗费是6 6。既然它不比当前的最佳旅行好，抛弃它并回溯到G，然后是C , B。从B点，搜索向前移动到D，然后是H , N。这个旅行1 , 3 , 2 , 4 , 1的耗费是2 5，比当前的最佳旅行好，把它作为当前的最好旅行。从N点，搜索回溯到H，然后是D。在D点，再次向前移动，到达O点。如此继续下去，可搜索完整个树，得出1 , 3 , 2 , 4 , 1是最少耗费的旅行。
当要求解的问题需要根据n 个元素的一个子集来优化某些函数时，解空间树被称作子集树（subset tree）。所以对有n 个对象的0 / 1背包问题来说，它的解空间树就是一个子集树。这样一棵树有2n 个叶节点，全部节点有2n+ 1－1个。因此，每一个对树中所有节点进行遍历的算法都必须耗时W ( 2n )。当要求解的问题需要根据一个n 元素的排列来优化某些函数时，解空间树被称作排列树（permutation tree）。这样的树有n! 个叶节点，所以每一个遍历树中所有节点的算法都必须耗时W (n! )。图1 6 - 5中的树是顶点{ 2 , 3 , 4 }的最佳排列的解空间树，顶点1是旅行的起点和终点。
通过确定一个新近到达的节点能否导致一个比当前最优解还要好的解，可加速对最优解的搜索。如果不能，则移动到该节点的任何一个子树都是无意义的，这个节点可被立即杀死，用来杀死活节点的策略称为限界函数（ bounding function）。在例1 6 - 2中，可使用如下限界函数：杀死代表不可行解决方案的节点；对于旅行商问题，可使用如下限界函数：如果目前建立的部分旅行的耗费不少于当前最佳路径的耗费，则杀死当前节点。如果在图1 6 - 4的例子中使用该限界函数，那么当到达节点I时，已经找到了具有耗费2 5的1 , 3 , 2 , 4 , 1的旅行。在节点I，部分旅行1 , 3 , 4的耗费为2 6，若旅行通过该节点，那么不能找到一个耗费小于2 5的旅行，故搜索以I为根节点的子树毫无意义。
小结
回溯方法的步骤如下：
1) 定义一个解空间，它包含问题的解。
2) 用适于搜索的方式组织该空间。
3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E-节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。
练习
1. 考察如下0 / 1背包问题：n= 4，w= [ 2 0 , 2 5 , 1 5 , 3 5 ]，p= [ 4 0 , 4 9 , 2 5 , 6 0 ]，c= 6 2。
1) 画出该0 / 1背包问题的解空间树。
2) 对该树运用回溯算法（利用给出的p s , w s , c值），依回溯算法遍历节点的顺序标记节点。确定回溯算法未遍历的节点。
2. 1) 当n= 5时，画出旅行商问题的解空间树。
2) 在该树上，运用回溯算法（使用图1 6 - 6的例子）。依回溯算法遍历节点的顺序标记节点。确定未被遍历的节点。
3. 每周六， Mary 和Joe 都在一起打乒乓球。她们每人都有一个装有1 2 0个球的篮子。
这样一直打下去，直到两个篮子为空。然后她们需要从球桌周围拾起2 4 0个球，放入各自
的篮子。Mary 只拾她这边的球，而Joe 拾剩下的球。描述如何用旅行商问题帮助Mary 和
Joe 决定她们拾球的顺序以便她们能走最少的路径。
4.2 应用
4.2.1 货箱装船
1. 问题
在1 . 3节中，考察了用最大数量的货箱装船的问题。现在对该问题做一些改动。在新问题中，有两艘船， n 个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi 是货箱i 的重量且
n åi = 1wi≤c1+c2。我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有的话，找出该方法。
例4-4 当n= 3，c1 =c2 = 5 0，w=[10,40,40] 时，可将货箱1 , 2装到第一艘船上，货箱3装到第二艘船上。如果w= [ 2 0 , 4 0 , 4 0 ]，则无法将货箱全部装船。当n åi = 1wi＝c1+c2 时，两艘船的装载问题等价于子集之和（ s u m - o f - s u b s e t）问题，即有n 个数字，要求找到一个子集（如果存在的话）使它的和为c1。当c1=c2 且n åi = 1wi＝2c1 时，两艘船的装载问题等价于分割问题（ partition problem），即有n个数字ai , ( 1≤i≤n)，要求找到一个子集（若存在的话），使得子集之和为( n åi = 1ai)/ 2。分割问题和子集之和问题都是N P-复杂问题。而且即使问题被限制为整型数字，它们仍是N P-复杂问题。所以不能期望在多项式时间内解决两艘船的装载问题。当存在一种方法能够装载所有n 个货箱时，可以验证以下的装船策略可以获得成功： 1) 尽可能地将第一艘船装至它的重量极限； 2) 将剩余货箱装到第二艘船。为了尽可能地将第一艘船装满，需要选择一个货箱的子集，它们的总重量尽可能接近c1。这个选择可通过求解0 / 1背包问题来实现，即寻找m ax (n åi = 1wi xi )，其中n åi = 1wi xi≤c1，xi Î{ 0 , 1 }，1≤i≤n。当重量是整数时，可用1 5 . 2节的动态规划方法确定第一艘船的最佳装载。用元组方法所需时间为O ( m i n {c1 , 2 n }）。可以使用回溯方法设计一个复杂性为O ( 2n ) 的算法，在有些实例中，该方法比动态规划算法要好。
2. 第一种回溯算法
既然想要找到一个重量的子集，使子集之和尽量接近c1，那么可以使用一个子集空间，并将其组织成如图1 6 - 2那样的二叉树。可用深度优先的方法搜索该解空间以求得最优解。使用限界函数去阻止不可能获得解答的节点的扩张。如果Z是树的j+ 1层的一个节点，那么从根到O的路径定义了xi（1≤i≤j）的值。使用这些值，定义c w（当前重量）为n åi = 1wi xi 。若c w>c1，则以O为根的子树不能产生一个可行的解答。可将这个测试作为限界函数。当且仅当一个节点的c w值大于c1 时，定义它是不可行的。
例4-5 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = 1 2。解空间树为图1 6 - 2的树再加上一层节点。搜索从根A开始且c w= 0。若移动到左孩子B则c w= 8，c w≤c1 = 1 2。以B为根的子树包含一个可行的节点，故移动到节点B。从节点B不能移动到节点D，因为c w+w2 >c1。移动到节点E，这个移动未改变c w。下一步为节点J，c w= 1 0。J的左孩子的c w值为1 3，超出了c1，故搜索不能移动到J的左孩子。
可移动到J的右孩子，它是一个叶节点。至此，已找到了一个子集，它的c w= 1 0。xi 的值由从A到J的右孩子的路径获得，其值为[ 1 , 0 , 1 , 0 ]。
回溯算法接着回溯到J，然后是E。从E，再次沿着树向下移动到节点K，此时c w= 8。移动到它的左子树，有c w= 11。既然已到达了一个叶节点，就看是否c w的值大于当前的最优c w 值。结果确实大于最优值，所以这个叶节点表示了一个比[ 1 , 0 , 1 , 0 ]更好的解决方案。到该节点的路径决定了x 的值[ 1 , 0 , 0 , 1 ]。从该叶节点，回溯到节点K，现在移动到K的右孩子，一个具有c w= 8的叶节点。这个叶节点中没有比当前最优cw 值还好的cw 值，所以回溯到K , E , B直到A。从根节点开始，沿树继续向下移动。算法将移动到C并搜索它的子树。
当使用前述的限界函数时，便产生了程序1 6 - 1所示的回溯算法。函数M a x L o a d i n g返回≤c的最大子集之和，但它不能找到产生该和的子集。后面将改进代码以便找到这个子集。
M a x L o a d i n g调用了一个递归函数m a x L o a d i n g，它是类L o a d i n g的一个成员，定义L o a d i n g类是为了减少M a x L o a d i n g中的参数个数。maxLoading(1) 实际执行解空间的搜索。MaxLoading(i) 搜索以i层节点（该节点已被隐式确定）为根的子树。从根到该节点的路径定义的子解答有一个重量值c w，目前最优解答的重量为b e s t w，这些变量以及与类L o a d i n g的一个成员相关联的其他变量，均由M a x L o a d i n g初始化。
程序16-1 第一种回溯算法
template<class T>
class Loading {
friend MaxLoading(T [], T, int);
p r i v a t e :
void maxLoading(int i);
int n; // 货箱数目
T *w, // 货箱重量数组
c, // 第一艘船的容量
c w, // 当前装载的重量
bestw; // 目前最优装载的重量
}
template<class T>
void Loading<T>::maxLoading(int i)
{// 从第i 层节点搜索
if (i > n) {// 位于叶节点
if (cw > bestw) bestw = cw;
r e t u r n }
// 检查子树
if (cw + w <= c) {// 尝试x = 1
cw += w;
m a x L o a d i n g ( i + 1 )
cw -= w;}
maxLoading(i+1);// 尝试x = 0
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最优装载的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// 计算最优装载的重量
X . m a x L o a d i n g ( 1 )
return X.bestw;
}
如果i＞n，则到达了叶节点。被叶节点定义的解答有重量c w，它一定≤c，因为搜索不会移动到不可行的节点。若c w > b e s t w，则目前最优解答的值被更新。当i≤n 时，我们处在有两个孩子的节点Z上。左孩子表示x [ i ] = 1的情况，只有c w + w [ i ]≤c 时，才能移到这里。当移动到左孩子时， cw 被置为c w + w [ i ]，且到达一个i + 1层的节点。以该节点为根的子树被递归搜索。当搜索完成时，回到节点Z。为了得到Z的cw 值，需用当前的cw 值减去w [ i ]，Z的右子树还未搜索。既然这个子树表示x [ i ] = 0的情况，所以无需进行可行性检查就可移动到该子树，因为一个可行节点的右孩子总是可行的。
注意：解空间树未被m a x L o a d i n g显示构造。函数m a x L o a d i n g在它到达的每一个节点上花费( 1 )时间。到达的节点数量为O ( 2n )，所以复杂性为O ( 2n )。这个函数使用的递归栈空间为
。
3. 第二种回溯方法
通过不移动到不可能包含比当前最优解还要好的解的右子树，能提高函数m a x L o a d i n g的性能。令b e s t w为目前最优解的重量， Z为解空间树的第i 层的一个节点， c w的定义如前。以Z为根的子树中没有叶节点的重量会超过c w + r，其中r=n &aring;j = i + 1w[ j ] 为剩余货箱的重量。因此，当c w + r≤b e s t w时，没有必要去搜索Z的右子树。
例4-6 令n, w, c1 的值与例4 - 5中相同。用新的限界函数，搜索将像原来那样向前进行直至到达第一个叶节点J（它是J的右孩子）。bestw 被置为1 0。回溯到E，然后向下移动到K的左孩子，此时b e s t w被更新为11。我们没有移动到K的右孩子，因为在右孩子节点c w = 8，r = 0，c w + r≤b e s t w。回溯到节点A。同样，不必移动到右孩子C，因为在C点c w = 0，r = 11且c w + r≤b e s t w。加强了条件的限界函数避免了对A的右子树及K的右子树的搜索。
当使用加强了条件的限界函数时，可得到程序1 6 - 2的代码。这个代码将类型为T的私有变量r 加到了类L o a d i n g的定义中。新的代码不必检查是否一个到达的叶节点有比当前最优解还优的重量值。这样的检查是不必要的，因为加强的限界函数不允许移动到不能产生较好解的节点。因此，每到达一个新的叶节点就意味着找到了比当前最优解还优的解。虽然新代码的复杂性仍是O ( 2n )，但它可比程序1 6 - 1少搜索一些节点。
程序16-2 程序1 6 - 1的优化
template<class T>
void Loading<T>::maxLoading(int i)
{// // 从第i 层节点搜索
if (i > n) {// 在叶节点上
bestw = cw;
r e t u r n }
// 检查子树
r -= w;
if (cw + w <= c) {//尝试x = 1
cw += w;
m a x L o a d i n g ( i + 1 )
cw -= w;}
if (cw + r > bestw) //尝试x = 0
m a x L o a d i n g ( i + 1 )
r += w;
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最优装载的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// r的初始值为所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w;
// 计算最优装载的重量
X . m a x L o a d i n g ( 1 )
return X.bestw;
}
4. 寻找最优子集
为了确定具有最接近c 的重量的货箱子集，有必要增加一些代码来记录当前找到的最优子集。为了记录这个子集，将参数bestx 添加到Maxloading 中。bestx 是一个整数数组，其中元素可为0或1，当且仅当b e s t x [ i ] = 1时，货箱i 在最优子集中。新的代码见程序1 6 - 3。
程序16-3 给出最优装载的代码
template<class T>
void Loading<T>::maxLoading(int i)
{ / /从第i 层节点搜索
if (i > n) {// 在叶节点上
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw; return;}
// 检查子树
r -= w;
if (cw + w <= c) {//尝试x = 1
x = 1;
cw += w;
m a x L o a d i n g ( i + 1 )
cw -= w;}
if (cw + r > bestw) {//尝试x = 0
x = 0;
m a x L o a d i n g ( i + 1 ) }
r += w;
}
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最优装载及其值
Loading<T> X;
// 初始化X
X.x = new int [n+1];
X.w = w;
X.c = c;
X.n = n;
X.bestx = bestx;
X.bestw = 0;
X.cw = 0;
// r的初始值为所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w;
X . m a x L o a d i n g ( 1 )
delete [] X.x;
return X.bestw;
}
这段代码在L o a d i n g中增加了两个私有数据成员： x 和b e s t x。这两个私有数据成员都是整型的一维数组。数组x 用来记录从搜索树的根到当前节点的路径（即它保留了路径上的xi 值），b e s t x记录当前最优解。无论何时到达了一个具有较优解的叶节点， bestx 被更新以表示从根到叶的路径。为1的xi 值确定了要被装载的货箱。数据x 的空间由MaxLoading 分配。
因为bestx 可以被更新O ( 2n )次，故maxLoading 的复杂性为O (n2n )。使用下列方法之一，复杂性可降为O ( 2n )：
1) 首先运行程序1 6 - 2的代码，以决定最优装载重量，令其为W。然后运行程序1 6 - 3的一个修改版本。该版本以b e s t w = W开始运行，当c w + r≥b e s t w时搜索右子树，第一次到达一个叶节点时便终止（即i > n）。
2) 修改程序1 6 - 3的代码以不断保留从根到当前最优叶的路径。尤其当位于i 层节点时，则到最优叶的路径由x [ j ]（1≤j<i）和b e s tx [ j ]（j≤i≤n）给出。按照这种方法，算法每次回溯一级，并在b e s t x中存储一个x [ i ]。由于算法回溯所需时间为O ( 2n )，因此额外开销为O ( 2n )。
5. 一个改进的迭代版本
可改进程序1 6 - 3的代码以减少它的空间需求。因为数组x 中记录可在树中移动的所有路径，故可以消除大小为的递归栈空间。如例4 - 5所示，从解空间树的任何节点，算法不断向左孩子移动，直到不能再移动为止。如果一个叶子已被到达，则最优解被更新。否则，它试图移动到右孩子。当要么到达一个叶节点，要么不值得移动到一个右孩子时，算法回溯到一个节点，条件是从该节点向其右孩子移动有可能找到最优解。这个节点有一个特性，即它是路径中具有x [ i ] = 1的节点中离根节点最近的节点。如果向右孩子的移动是有效的，那么就这么做，然后再完成一系列向左孩子的移动。如果向右孩子的移动是无效的，则回溯到x [ i ] = 1的下一个节点。
该算法遍历树的方式可被编码成与程序1 6 - 4一样的迭代（即循环）算法。不像递归代码，这种代码在检查是否该向右孩子移动之前就移动到了右孩子。如果这个移动是不可行的，则回溯。迭代代码的时间复杂性与程序1 6 - 3一样。
程序16-4 迭代代码
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最佳装载及其值
// 迭代回溯程序
// 初始化根节点
int i = 1; // 当前节点的层次
// x[1:i-1] 是到达当前节点的路径
int *x = new int [n+1];
T bestw = 0, // 迄今最优装载的重量
cw = 0, // 当前装载的重量
r = 0; // 剩余货箱重量的和
for (int j = 1; j <= n; j++)
r += w[j];
// 在树中搜索
while (true) {
// 下移，尽可能向左
while (i <= n && cw + w <= c) {
// 移向左孩子
r -= w;
cw += w;
x = 1;
i + +
}
if (i > n) {// 到达叶子
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw;}
else {// 移向右孩子
r -= w;
x = 0;
i + + }
// 必要时返回
while (cw + r <= bestw) {
// 本子树没有更好的叶子，返回
i - -
while (i > 0 && !x) {
// 从一个右孩子返回
r += w;
i - -
}
if (i == 0) {delete [] x;
return bestw;}
// 移向右子树
x = 0;
cw -= w;
i + +
}
}
}
4.2.2 0/1背包问题
0 / 1背包问题是一个N P-复杂问题，为了解决该问题，在1 . 4节采用了贪婪算法，在3 . 2节又采用了动态规划算法。在本节，将用回溯算法解决该问题。既然想选择一个对象的子集，将它们装入背包，以便获得的收益最大，则解空间应组织成子集树的形状（如图1 6 - 2所示）。该回溯算法与4 . 2节的装载问题很类似。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。
与程序1 6 - 2一样，左孩子表示一个可行的节点，无论何时都要移动到它；当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是令r 为还未遍历的对象的收益之和，将r 加到c p（当前节点所获收益）之上，若（ r + c p）≤b e s t p（目前最优解的收益），则不需搜索右子树。一种更有效的方法是按收益密度pi / wi 对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放入背包的对象时，就使用它的一部分。
例4-7 考察一个背包例子： n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。这些对象的收益密度为[ 3 , 2 , 3 . 5 , 4 ]。当背包以密度递减的顺序被填充时，对象4首先被填充，然后是对象3、对象1。在这三个对象被装入背包之后，剩余容量为1。这个容量可容纳对象2的0 . 2倍的重量。将0 . 2倍的该对象装入，产生了收益值2。被构造的解为x= [ 1 , 0 . 2 , 1 , 1 ]，相应的收益值为2 2。尽管该解不可行（x2 是0 . 2，而实际上它应为0或1），但它的收益值2 2一定不少于要求的最优解。因此，该0 / 1背包问题没有收益值多于2 2的解。
解空间树为图1 6 - 2再加上一层节点。当位于解空间树的节点B时，x1= 1，目前获益为c p= 9。该节点所用容量为c w= 3。要获得最好的附加收益，要以密度递减的顺序填充剩余容量c l e f t=ccw= 4。也就是说，先放对象4，然后是对象3，然后是对象2的0 . 2倍的重量。因此，子树A的最优解的收益值至多为2 2。当位于节点C时，c p=c w= 0，c l e f t= 7。按密度递减顺序填充剩余容量，则对象4和3被装入。然后是对象2的0 . 8倍被装入。这样产生出收益值1 9。在子树C中没有节点可产生出比1 9还大的收益值。
在节点E，c p= 9，c w= 3，c l e f t= 4。仅剩对象3和4要被考虑。当对象按密度递减的顺序被考虑时，对象4先被装入，然后是对象3。所以在子树E中无节点有多于c p+ 4 + 7 = 2 0的收益值。如果已经找到了一个具有收益值2 0或更多的解，则无必要去搜索E子树。
一种实现限界函数的好方法是首先将对象按密度排序。假定已经做了这样的排序。定义类K n a p（见程序1 6 - 5）来减少限界函数B o u n d（见程序1 6 - 6）及递归函数K n a p s a c k（见程序1 6 - 7）的参数数量，该递归函数用于计算最优解的收益值。参数的减少又可引起递归栈空间的减少以及每一个K n a p s a c k的执行时间的减少。注意函数K n a p s a c k和函数m a x L o a d i n g（见程序1 6 - 2）的相似性。同时注意仅当向右孩子移动时，限界函数才被计算。当向左孩子移动时，左孩子的限界函数的值与其父节点相同。
程序16-5 Knap类
template<class Tw, class Tp>
class Knap {
friend Tp Knapsack(Tp *, Tw *, Tw, int);
p r i v a t e :
Tp Bound(int i);
void Knapsack(int i);
Tw c; / /背包容量
int n; // 对象数目
Tw *w; // 对象重量的数组
Tp *p; // 对象收益的数组
Tw cw; // 当前背包的重量
Tp cp; // 当前背包的收益
Tp bestp; // 迄今最大的收益
}
程序16-6 限界函数
template<class Tw, class Tp>
Tp Knap<Tw, Tp>::Bound(int i)
{// 返回子树中最优叶子的上限值Return upper bound on value of
// best leaf in subtree.
作者: liuchaohai
作者:liuchaohai 来源: 类别:数据算法 日期:2002.09.19 今日/总浏览: 4/9
第 4 章 回溯
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。
本章集中阐述回溯方法，这种方法被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
4.1 算法思想
回溯（b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；在具有n 个对象的0 / 1背包问题中（见1 . 4节和2 . 2节），解空间的一个合理选择是2n 个长度为n 的0 / 1向量的集合，这个集合表示了将0或1分配给x的所有可能方法。当n= 3时，解空间为{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。
下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图1 6 - 1用图的形式给出了一个3×3迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了3×3迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。
图1 6 - 2用树形结构给出了含三个对象的0 / 1背包问题的解空间。从i 层节点到i+ 1层节点的一条边上的数字给出了向量x 中第i个分量的值xi ，从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A到叶节点H的路径定义了解x= [ 1 , 1 , 1 ]。根据w 和c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。
一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点( 1 , 1 )；在0 / 1背包问题中，开始节点为根节点A。开始节点既是一个活节点又是一个E-节点（expansion node）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。
例4-1 [迷宫老鼠] 考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图1 6 -1给出的解空间图来搜索迷宫。
从迷宫的入口到出口的每一条路径都与图1 6 - 1中从( 1 , 1 )到( 3 , 3 )的一条路径相对应。然而，图1 6 - 1中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口的路径。搜索从点( 1 , 1 )开始，该点是目前唯一的活节点，它也是一个E-节点。为避免再次走过这个位置，置m a z e( 1 , 1 )为1。从这个位置，能移动到( 1 , 2 )或( 2 , 1 )两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值0。假定选择移动到( 1 , 2 )，m a z e( 1 , 2 )被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为E-节点。
在图1 6 - 1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置，并置m a z e( 1 , 3 )为1以避免再次经过该点，此时迷宫状态为1 6 - 3 c。图1 6 - 1中，从( 1 , 3 )出发有两个可能的移动，但没有一个是可行的。所以E-节点( 1 , 3 )死亡，回溯到最近被检查的活节点( 1 , 2 )。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是( 1 , 1 )。这个节点再次变为E-节点，它可移动到( 2 , 1 )。现在活节点为( 1 , 1 )，( 2 , 1 )。继续下去，能到达点( 3 , 3 )。此时，活节点表为( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，这即是到达出口的路径。
程序5 - 1 3是一个在迷宫中寻找路径的回溯算法。
例4-2 [0/1背包问题] 考察如下背包问题：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。从根节点开始搜索图1 6 - 2中的树。根节点是当前唯一的活节点，也是E-节点，从这里能够移动到B或C点。假设移动到B，则活节点为A和B。B是当前E-节点。在节点B，剩下的容量r 为1 0，而收益c p 为4 0。从B点，能移动到D或E。移到D是不可行的，因为移到D所需的容量w2 为1 5。到E的移动是可行的，因为在这个移动中没有占用任何容量。E变成新的E-节点。这时活节点为A , B , E。在节点E，r= 1 0，c p= 4 0。从E，有两种可能移动（到J 和K），到J 的移动是不可行的，而到K的移动是可行的。节点K变成了新的E-节点。因为K是一个叶子，所以得到一个可行的解。这个解的收益为c p= 4 0。x 的值由从根到K的路径来决定。这个路径（ A , B , E , K）也是此时的活节点序列。既然不能进一步扩充K，K节点死亡，回溯到E，而E也不能进一步扩充，它也死亡了。接着，回溯到B，它也死亡了，A再次变为E-节点。它可被进一步扩充，到达节点C。此时r= 3 0，c p= 0。从C点能够移动到F或G。假定移动到F。F变为新的E-节点并且活节点为A, C,F。在F，r= 1 5，c p= 2 5。从F点，能移动到L或M。假定移动到L。此时r= 0，c p= 5 0。既然L是一个叶节点，它表示了一个比目前找到的最优解（即节点K）更好的可行解，我们把这个解作为最优解。节点L死亡，回溯到节点F。继续下去，搜索整棵树。在搜索期间发现的最优解即为最后的解。
例4-3 [旅行商问题] 在这个问题中，给出一个n 顶点网络（有向或无向），要求找出一个包含所有n 个顶点的具有最小耗费的环路。任何一个包含网络中所有n 个顶点的环路被称作一个旅行（t o u r）。在旅行商问题中，要设法找到一条最小耗费的旅行。
图1 6 - 4给出了一个四顶点网络。在这个网络中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行2 , 4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一样。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。旅行1 , 2 , 4 , 3 , 1的耗费为6 6；而1 , 3 , 2 , 4 , 1的耗费为2 5；1 , 4 , 3 , 2 , 1为5 9。故1 , 3 , 2 , 4 , 1是该网络中最小耗费的旅行。
顾名思义，旅行商问题可被用来模拟现实生活中旅行商所要旅行的地区问题。顶点表示旅行
商所要旅行的城市（包括起点）。边的耗费给出了在两个城市旅行所需的时间（或花费）。旅行表示当旅行商游览了所有城市再回到出发点时所走的路线。
旅行商问题还可用来模拟其他问题。假定要在一个金属薄片或印刷电路板上钻许多孔。孔的位置已知。这些孔由一个机器钻头来钻，它从起始位置开始，移动到每一个钻孔位置钻孔，然后回到起始位置。总共花的时间是钻所有孔的时间与钻头移动的时间。钻所有孔所需的时间独立于钻孔顺序。然而，钻头移动时间是钻头移动距离的函数。因此，希望找到最短的移动路径。
另有一个例子，考察一个批量生产的环境，其中有一个特殊的机器可用来生产n 个不同的产品。利用一个生产循环不断地生产这些产品。在一个循环中，所有n 个产品被顺序生产出来，然后再开始下一个循环。在下一个循环中，又采用了同样的生产顺序。例如，如果这台机器被用来顺序为小汽车喷红、白、蓝漆，那么在为蓝色小汽车喷漆之后，我们又开始了新一轮循环，为红色小汽车喷漆，然后是白色小汽车、蓝色小汽车、红色小汽车，..，如此下去。一个循环的花费包括生产一个循环中的产品所需的花费以及循环中从一个产品转变到另一个产品的花费。虽然生产产品的花费独立于产品生产顺序，但循环中从生产一个产品转变到生产另一个产品的花费却与顺序有关。为了使耗费最小化，可以定义一个有向图，图中的顶点表示产品，边＜(i , j)＞上的耗费值为生产过程中从产品i 转变到产品j 所需的耗费。一个最小耗费的旅行定义了一个最小耗费的生产循环。
既然旅行是包含所有顶点的一个循环，故可以把任意一个点作为起点（因此也是终点）。
针对图1 6 - 4，任意选取点1作为起点和终点，则每一个旅行可用顶点序列1, v2 ,., vn , 1来描述，
v2 , ., vn 是(2, 3, ., n) 的一个排列。可能的旅行可用一个树来描述，其中每一个从根到叶的路
径定义了一个旅行。图1 6 - 5给出了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一个旅行（还要附加1作为终点）。例如，到节点L的路径表示了旅行1 , 2 , 3 , 4 , 1，而到节点O的路径表示了旅行1 , 3 , 4 , 2 , 1。网络中的每一个旅行都由树中的一条从根到叶的确定路径来表示。因此，树中叶的数目为(n- 1 )！。
回溯算法将用深度优先方式从根节点开始，通过搜索解空间树发现一个最小耗费的旅行。对图1 6 - 4的网络，利用图1 6 - 5的解空间树，一个可能的搜索为A B C F L。在L点，旅行1 , 2 , 3 , 4 , 1作为当前最好的旅行被记录下来。它的耗费是5 9。从L点回溯到活节点F。由于F没有未被检查的孩子，所以它成为死节点，回溯到C点。C变为E-节点，向前移动到G，然后是M。这样构造出了旅行1 , 2 , 4 , 3 , 1，它的耗费是6 6。既然它不比当前的最佳旅行好，抛弃它并回溯到G，然后是C , B。从B点，搜索向前移动到D，然后是H , N。这个旅行1 , 3 , 2 , 4 , 1的耗费是2 5，比当前的最佳旅行好，把它作为当前的最好旅行。从N点，搜索回溯到H，然后是D。在D点，再次向前移动，到达O点。如此继续下去，可搜索完整个树，得出1 , 3 , 2 , 4 , 1是最少耗费的旅行。
当要求解的问题需要根据n 个元素的一个子集来优化某些函数时，解空间树被称作子集树（subset tree）。所以对有n 个对象的0 / 1背包问题来说，它的解空间树就是一个子集树。这样一棵树有2n 个叶节点，全部节点有2n+ 1－1个。因此，每一个对树中所有节点进行遍历的算法都必须耗时W ( 2n )。当要求解的问题需要根据一个n 元素的排列来优化某些函数时，解空间树被称作排列树（permutation tree）。这样的树有n! 个叶节点，所以每一个遍历树中所有节点的算法都必须耗时W (n! )。图1 6 - 5中的树是顶点{ 2 , 3 , 4 }的最佳排列的解空间树，顶点1是旅行的起点和终点。
通过确定一个新近到达的节点能否导致一个比当前最优解还要好的解，可加速对最优解的搜索。如果不能，则移动到该节点的任何一个子树都是无意义的，这个节点可被立即杀死，用来杀死活节点的策略称为限界函数（ bounding function）。在例1 6 - 2中，可使用如下限界函数：杀死代表不可行解决方案的节点；对于旅行商问题，可使用如下限界函数：如果目前建立的部分旅行的耗费不少于当前最佳路径的耗费，则杀死当前节点。如果在图1 6 - 4的例子中使用该限界函数，那么当到达节点I时，已经找到了具有耗费2 5的1 , 3 , 2 , 4 , 1的旅行。在节点I，部分旅行1 , 3 , 4的耗费为2 6，若旅行通过该节点，那么不能找到一个耗费小于2 5的旅行，故搜索以I为根节点的子树毫无意义。
小结
回溯方法的步骤如下：
1) 定义一个解空间，它包含问题的解。
2) 用适于搜索的方式组织该空间。
3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E-节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。
练习
1. 考察如下0 / 1背包问题：n= 4，w= [ 2 0 , 2 5 , 1 5 , 3 5 ]，p= [ 4 0 , 4 9 , 2 5 , 6 0 ]，c= 6 2。
1) 画出该0 / 1背包问题的解空间树。
2) 对该树运用回溯算法（利用给出的p s , w s , c值），依回溯算法遍历节点的顺序标记节点。确定回溯算法未遍历的节点。
2. 1) 当n= 5时，画出旅行商问题的解空间树。
2) 在该树上，运用回溯算法（使用图1 6 - 6的例子）。依回溯算法遍历节点的顺序标记节点。确定未被遍历的节点。
3. 每周六， Mary 和Joe 都在一起打乒乓球。她们每人都有一个装有1 2 0个球的篮子。
这样一直打下去，直到两个篮子为空。然后她们需要从球桌周围拾起2 4 0个球，放入各自
的篮子。Mary 只拾她这边的球，而Joe 拾剩下的球。描述如何用旅行商问题帮助Mary 和
Joe 决定她们拾球的顺序以便她们能走最少的路径。
4.2 应用
4.2.1 货箱装船
1. 问题
在1 . 3节中，考察了用最大数量的货箱装船的问题。现在对该问题做一些改动。在新问题中，有两艘船， n 个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi 是货箱i 的重量且
n &aring;i = 1wi≤c1+c2。我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有的话，找出该方法。
例4-4 当n= 3，c1 =c2 = 5 0，w=[10,40,40] 时，可将货箱1 , 2装到第一艘船上，货箱3装到第二艘船上。如果w= [ 2 0 , 4 0 , 4 0 ]，则无法将货箱全部装船。当n &aring;i = 1wi＝c1+c2 时，两艘船的装载问题等价于子集之和（ s u m - o f - s u b s e t）问题，即有n 个数字，要求找到一个子集（如果存在的话）使它的和为c1。当c1=c2 且n &aring;i = 1wi＝2c1 时，两艘船的装载问题等价于分割问题（ partition problem），即有n个数字ai , ( 1≤i≤n)，要求找到一个子集（若存在的话），使得子集之和为( n &aring;i = 1ai)/ 2。分割问题和子集之和问题都是N P-复杂问题。而且即使问题被限制为整型数字，它们仍是N P-复杂问题。所以不能期望在多项式时间内解决两艘船的装载问题。当存在一种方法能够装载所有n 个货箱时，可以验证以下的装船策略可以获得成功： 1) 尽可能地将第一艘船装至它的重量极限； 2) 将剩余货箱装到第二艘船。为了尽可能地将第一艘船装满，需要选择一个货箱的子集，它们的总重量尽可能接近c1。这个选择可通过求解0 / 1背包问题来实现，即寻找m ax (n &aring;i = 1wi xi )，其中n &aring;i = 1wi xi≤c1，xi &Icirc;{ 0 , 1 }，1≤i≤n。当重量是整数时，可用1 5 . 2节的动态规划方法确定第一艘船的最佳装载。用元组方法所需时间为O ( m i n {c1 , 2 n }）。可以使用回溯方法设计一个复杂性为O ( 2n ) 的算法，在有些实例中，该方法比动态规划算法要好。
2. 第一种回溯算法
既然想要找到一个重量的子集，使子集之和尽量接近c1，那么可以使用一个子集空间，并将其组织成如图1 6 - 2那样的二叉树。可用深度优先的方法搜索该解空间以求得最优解。使用限界函数去阻止不可能获得解答的节点的扩张。如果Z是树的j+ 1层的一个节点，那么从根到O的路径定义了xi（1≤i≤j）的值。使用这些值，定义c w（当前重量）为n &aring;i = 1wi xi 。若c w>c1，则以O为根的子树不能产生一个可行的解答。可将这个测试作为限界函数。当且仅当一个节点的c w值大于c1 时，定义它是不可行的。
例4-5 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = 1 2。解空间树为图1 6 - 2的树再加上一层节点。搜索从根A开始且c w= 0。若移动到左孩子B则c w= 8，c w≤c1 = 1 2。以B为根的子树包含一个可行的节点，故移动到节点B。从节点B不能移动到节点D，因为c w+w2 >c1。移动到节点E，这个移动未改变c w。下一步为节点J，c w= 1 0。J的左孩子的c w值为1 3，超出了c1，故搜索不能移动到J的左孩子。
可移动到J的右孩子，它是一个叶节点。至此，已找到了一个子集，它的c w= 1 0。xi 的值由从A到J的右孩子的路径获得，其值为[ 1 , 0 , 1 , 0 ]。
回溯算法接着回溯到J，然后是E。从E，再次沿着树向下移动到节点K，此时c w= 8。移动到它的左子树，有c w= 11。既然已到达了一个叶节点，就看是否c w的值大于当前的最优c w 值。结果确实大于最优值，所以这个叶节点表示了一个比[ 1 , 0 , 1 , 0 ]更好的解决方案。到该节点的路径决定了x 的值[ 1 , 0 , 0 , 1 ]。从该叶节点，回溯到节点K，现在移动到K的右孩子，一个具有c w= 8的叶节点。这个叶节点中没有比当前最优cw 值还好的cw 值，所以回溯到K , E , B直到A。从根节点开始，沿树继续向下移动。算法将移动到C并搜索它的子树。
当使用前述的限界函数时，便产生了程序1 6 - 1所示的回溯算法。函数M a x L o a d i n g返回≤c的最大子集之和，但它不能找到产生该和的子集。后面将改进代码以便找到这个子集。
M a x L o a d i n g调用了一个递归函数m a x L o a d i n g，它是类L o a d i n g的一个成员，定义L o a d i n g类是为了减少M a x L o a d i n g中的参数个数。maxLoading(1) 实际执行解空间的搜索。MaxLoading(i) 搜索以i层节点（该节点已被隐式确定）为根的子树。从根到该节点的路径定义的子解答有一个重量值c w，目前最优解答的重量为b e s t w，这些变量以及与类L o a d i n g的一个成员相关联的其他变量，均由M a x L o a d i n g初始化。
程序16-1 第一种回溯算法
template<class T>
class Loading {
friend MaxLoading(T [], T, int);
p r i v a t e :
void maxLoading(int i);
int n; // 货箱数目
T *w, // 货箱重量数组
c, // 第一艘船的容量
c w, // 当前装载的重量
bestw; // 目前最优装载的重量
}
template<class T>
void Loading<T>::maxLoading(int i)
{// 从第i 层节点搜索
if (i > n) {// 位于叶节点
if (cw > bestw) bestw = cw;
r e t u r n }
// 检查子树
if (cw + w <= c) {// 尝试x = 1
cw += w;
m a x L o a d i n g ( i + 1 )
cw -= w;}
maxLoading(i+1);// 尝试x = 0
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最优装载的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// 计算最优装载的重量
X . m a x L o a d i n g ( 1 )
return X.bestw;
}
如果i＞n，则到达了叶节点。被叶节点定义的解答有重量c w，它一定≤c，因为搜索不会移动到不可行的节点。若c w > b e s t w，则目前最优解答的值被更新。当i≤n 时，我们处在有两个孩子的节点Z上。左孩子表示x [ i ] = 1的情况，只有c w + w [ i ]≤c 时，才能移到这里。当移动到左孩子时， cw 被置为c w + w [ i ]，且到达一个i + 1层的节点。以该节点为根的子树被递归搜索。当搜索完成时，回到节点Z。为了得到Z的cw 值，需用当前的cw 值减去w [ i ]，Z的右子树还未搜索。既然这个子树表示x [ i ] = 0的情况，所以无需进行可行性检查就可移动到该子树，因为一个可行节点的右孩子总是可行的。
注意：解空间树未被m a x L o a d i n g显示构造。函数m a x L o a d i n g在它到达的每一个节点上花费( 1 )时间。到达的节点数量为O ( 2n )，所以复杂性为O ( 2n )。这个函数使用的递归栈空间为
。3. 第二种回溯方法
通过不移动到不可能包含比当前最优解还要好的解的右子树，能提高函数m a x L o a d i n g的性能。令b e s t w为目前最优解的重量， Z为解空间树的第i 层的一个节点， c w的定义如前。以Z为根的子树中没有叶节点的重量会超过c w + r，其中r=n &aring;j = i + 1w[ j ] 为剩余货箱的重量。因此，当c w + r≤b e s t w时，没有必要去搜索Z的右子树。
例4-6 令n, w, c1 的值与例4 - 5中相同。用新的限界函数，搜索将像原来那样向前进行直至到达第一个叶节点J（它是J的右孩子）。bestw 被置为1 0。回溯到E，然后向下移动到K的左孩子，此时b e s t w被更新为11。我们没有移动到K的右孩子，因为在右孩子节点c w = 8，r = 0，c w + r≤b e s t w。回溯到节点A。同样，不必移动到右孩子C，因为在C点c w = 0，r = 11且c w + r≤b e s t w。加强了条件的限界函数避免了对A的右子树及K的右子树的搜索。
当使用加强了条件的限界函数时，可得到程序1 6 - 2的代码。这个代码将类型为T的私有变量r 加到了类L o a d i n g的定义中。新的代码不必检查是否一个到达的叶节点有比当前最优解还优的重量值。这样的检查是不必要的，因为加强的限界函数不允许移动到不能产生较好解的节点。因此，每到达一个新的叶节点就意味着找到了比当前最优解还优的解。虽然新代码的复杂性仍是O ( 2n )，但它可比程序1 6 - 1少搜索一些节点。
程序16-2 程序1 6 - 1的优化
template<class T>
void Loading<T>::maxLoading(int i)
{// // 从第i 层节点搜索
if (i > n) {// 在叶节点上
bestw = cw;
r e t u r n }
// 检查子树
r -= w;
if (cw + w <= c) {//尝试x = 1
cw += w;
m a x L o a d i n g ( i + 1 )
cw -= w;}
if (cw + r > bestw) //尝试x = 0
m a x L o a d i n g ( i + 1 )
r += w;
}
template<class T>
T MaxLoading(T w[], T c, int n)
{// 返回最优装载的重量
Loading<T> X;
// 初始化X
X.w = w;
X.c = c;
X.n = n;
X.bestw = 0;
X.cw = 0;
// r的初始值为所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w;
// 计算最优装载的重量
X . m a x L o a d i n g ( 1 )
return X.bestw;
}
4. 寻找最优子集
为了确定具有最接近c 的重量的货箱子集，有必要增加一些代码来记录当前找到的最优子集。为了记录这个子集，将参数bestx 添加到Maxloading 中。bestx 是一个整数数组，其中元素可为0或1，当且仅当b e s t x [ i ] = 1时，货箱i 在最优子集中。新的代码见程序1 6 - 3。
程序16-3 给出最优装载的代码
template<class T>
void Loading<T>::maxLoading(int i)
{ / /从第i 层节点搜索
if (i > n) {// 在叶节点上
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw; return;}
// 检查子树
r -= w;
if (cw + w <= c) {//尝试x = 1
x = 1;
cw += w;
m a x L o a d i n g ( i + 1 )
cw -= w;}
if (cw + r > bestw) {//尝试x = 0
x = 0;
m a x L o a d i n g ( i + 1 ) }
r += w;
}
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最优装载及其值
Loading<T> X;
// 初始化X
X.x = new int [n+1];
X.w = w;
X.c = c;
X.n = n;
X.bestx = bestx;
X.bestw = 0;
X.cw = 0;
// r的初始值为所有重量之和
X.r = 0;
for (int i = 1; i <= n; i++)
X.r += w;
X . m a x L o a d i n g ( 1 )
delete [] X.x;
return X.bestw;
}
这段代码在L o a d i n g中增加了两个私有数据成员： x 和b e s t x。这两个私有数据成员都是整型的一维数组。数组x 用来记录从搜索树的根到当前节点的路径（即它保留了路径上的xi 值），b e s t x记录当前最优解。无论何时到达了一个具有较优解的叶节点， bestx 被更新以表示从根到叶的路径。为1的xi 值确定了要被装载的货箱。数据x 的空间由MaxLoading 分配。
因为bestx 可以被更新O ( 2n )次，故maxLoading 的复杂性为O (n2n )。使用下列方法之一，复杂性可降为O ( 2n )：
1) 首先运行程序1 6 - 2的代码，以决定最优装载重量，令其为W。然后运行程序1 6 - 3的一个修改版本。该版本以b e s t w = W开始运行，当c w + r≥b e s t w时搜索右子树，第一次到达一个叶节点时便终止（即i > n）。
2) 修改程序1 6 - 3的代码以不断保留从根到当前最优叶的路径。尤其当位于i 层节点时，则到最优叶的路径由x [ j ]（1≤j<i）和b e s tx [ j ]（j≤i≤n）给出。按照这种方法，算法每次回溯一级，并在b e s t x中存储一个x [ i ]。由于算法回溯所需时间为O ( 2n )，因此额外开销为O ( 2n )。
5. 一个改进的迭代版本
可改进程序1 6 - 3的代码以减少它的空间需求。因为数组x 中记录可在树中移动的所有路径，故可以消除大小为
的递归栈空间。如例4 - 5所示，从解空间树的任何节点，算法不断向左孩子移动，直到不能再移动为止。如果一个叶子已被到达，则最优解被更新。否则，它试图移动到右孩子。当要么到达一个叶节点，要么不值得移动到一个右孩子时，算法回溯到一个节点，条件是从该节点向其右孩子移动有可能找到最优解。这个节点有一个特性，即它是路径中具有x [ i ] = 1的节点中离根节点最近的节点。如果向右孩子的移动是有效的，那么就这么做，然后再完成一系列向左孩子的移动。如果向右孩子的移动是无效的，则回溯到x [ i ] = 1的下一个节点。该算法遍历树的方式可被编码成与程序1 6 - 4一样的迭代（即循环）算法。不像递归代码，这种代码在检查是否该向右孩子移动之前就移动到了右孩子。如果这个移动是不可行的，则回溯。迭代代码的时间复杂性与程序1 6 - 3一样。
程序16-4 迭代代码
template<class T>
T MaxLoading(T w[], T c, int n, int bestx[])
{// 返回最佳装载及其值
// 迭代回溯程序
// 初始化根节点
int i = 1; // 当前节点的层次
// x[1:i-1] 是到达当前节点的路径
int *x = new int [n+1];
T bestw = 0, // 迄今最优装载的重量
cw = 0, // 当前装载的重量
r = 0; // 剩余货箱重量的和
for (int j = 1; j <= n; j++)
r += w[j];
// 在树中搜索
while (true) {
// 下移，尽可能向左
while (i <= n && cw + w <= c) {
// 移向左孩子
r -= w;
cw += w;
x = 1;
i + +
}
if (i > n) {// 到达叶子
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw;}
else {// 移向右孩子
r -= w;
x = 0;
i + + }
// 必要时返回
while (cw + r <= bestw) {
// 本子树没有更好的叶子，返回
i - -
while (i > 0 && !x) {
// 从一个右孩子返回
r += w;
i - -
}
if (i == 0) {delete [] x;
return bestw;}
// 移向右子树
x = 0;
cw -= w;
i + +
}
}
}
4.2.2 0/1背包问题
0 / 1背包问题是一个N P-复杂问题，为了解决该问题，在1 . 4节采用了贪婪算法，在3 . 2节又采用了动态规划算法。在本节，将用回溯算法解决该问题。既然想选择一个对象的子集，将它们装入背包，以便获得的收益最大，则解空间应组织成子集树的形状（如图1 6 - 2所示）。该回溯算法与4 . 2节的装载问题很类似。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。
与程序1 6 - 2一样，左孩子表示一个可行的节点，无论何时都要移动到它；当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是令r 为还未遍历的对象的收益之和，将r 加到c p（当前节点所获收益）之上，若（ r + c p）≤b e s t p（目前最优解的收益），则不需搜索右子树。一种更有效的方法是按收益密度pi / wi 对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放入背包的对象时，就使用它的一部分。
例4-7 考察一个背包例子： n= 4，c= 7，p= [ 9 , 1 0 , 7 , 4 ]，w= [ 3 , 5 , 2 , 1 ]。这些对象的收益密度为[ 3 , 2 , 3 . 5 , 4 ]。当背包以密度递减的顺序被填充时，对象4首先被填充，然后是对象3、对象1。在这三个对象被装入背包之后，剩余容量为1。这个容量可容纳对象2的0 . 2倍的重量。将0 . 2倍的该对象装入，产生了收益值2。被构造的解为x= [ 1 , 0 . 2 , 1 , 1 ]，相应的收益值为2 2。尽管该解不可行（x2 是0 . 2，而实际上它应为0或1），但它的收益值2 2一定不少于要求的最优解。因此，该0 / 1背包问题没有收益值多于2 2的解。
解空间树为图1 6 - 2再加上一层节点。当位于解空间树的节点B时，x1= 1，目前获益为c p= 9。该节点所用容量为c w= 3。要获得最好的附加收益，要以密度递减的顺序填充剩余容量c l e f t=ccw= 4。也就是说，先放对象4，然后是对象3，然后是对象2的0 . 2倍的重量。因此，子树A的最优解的收益值至多为2 2。当位于节点C时，c p=c w= 0，c l e f t= 7。按密度递减顺序填充剩余容量，则对象4和3被装入。然后是对象2的0 . 8倍被装入。这样产生出收益值1 9。在子树C中没有节点可产生出比1 9还大的收益值。
在节点E，c p= 9，c w= 3，c l e f t= 4。仅剩对象3和4要被考虑。当对象按密度递减的顺序被考虑时，对象4先被装入，然后是对象3。所以在子树E中无节点有多于c p+ 4 + 7 = 2 0的收益值。如果已经找到了一个具有收益值2 0或更多的解，则无必要去搜索E子树。
一种实现限界函数的好方法是首先将对象按密度排序。假定已经做了这样的排序。定义类K n a p（见程序1 6 - 5）来减少限界函数B o u n d（见程序1 6 - 6）及递归函数K n a p s a c k（见程序1 6 - 7）的参数数量，该递归函数用于计算最优解的收益值。参数的减少又可引起递归栈空间的减少以及每一个K n a p s a c k的执行时间的减少。注意函数K n a p s a c k和函数m a x L o a d i n g（见程序1 6 - 2）的相似性。同时注意仅当向右孩子移动时，限界函数才被计算。当向左孩子移动时，左孩子的限界函数的值与其父节点相同。
程序16-5 Knap类
template<class Tw, class Tp>
class Knap {
friend Tp Knapsack(Tp *, Tw *, Tw, int);
p r i v a t e :
Tp Bound(int i);
void Knapsack(int i);
Tw c; / /背包容量
int n; // 对象数目
Tw *w; // 对象重量的数组
Tp *p; // 对象收益的数组
Tw cw; // 当前背包的重量
Tp cp; // 当前背包的收益
Tp bestp; // 迄今最大的收益
}
程序16-6 限界函数
template<class Tw, class Tp>
Tp Knap<Tw, Tp>::Bound(int i)
{// 返回子树中最优叶子的上限值Return upper bound on value of
// best leaf in subtree.
作者: liuchaohai