【精品】回溯算法24

【精品】回溯算法24 回溯算法 寻找问的解的一种可靠的方法是首先列出所有候选解～然后依次检查每一个～在检查完所有或部分候选解后～即可找到所需要的解。理论上～当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时～上述方法是可行的。不过～在实际应用中～很少使用这种方法～因为候选解的数量通常都非常大,比如指数级～甚至是大数阶乘,～即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统检查的方法有多种～其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少,无论对于最坏情形还是对于一般情形,。事实上～这些方法可以使我们避免对很大的候选解集合进行检查～同时能够保证算法运行结束时可以找到所需要的解。因此～这些方法通常能够用来求解规模很大的问题。 本章集中阐述回溯方法～这种方法被用来货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。 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 )两个位臵。对于本例～两种移动都是可行的～因为在每一个 。假定选择移动到( 1 , 2 )～m a z e( 1 , 2 )被臵为1以避免再次位臵都有一个值0 经过该点。迷宫当前状态如图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 )。继续下去～能到达点( 3 , 3 )。可移动到( 2 , 1 )。现在活节点为( 1 , 1 ) 此时～活节点表为( 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个。因此～每一个对树中所有节点进行遍历的算法都必须耗时, ( 2n )。当要求解的问题需要根据一个n 元素的排列来优化某些函数时～解空间树被称作排列树,permutation tree,。这样的树有n! 个叶节点～所以每一个遍历树中所有节点的算法都必须耗时, (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,从开始节点起最长路径的长度,。这个特性非常重要～因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话～再多的空间也不够用。 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 ,, , ～ , ,～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 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 void Loading::maxLoading(int i) {// 从第i 层节点搜索 if (i > n) {// 位于叶节点 if (cw > bestw) bestw = cw; r e t u r n ; } // 检查子树 if (cw + w[i] <= c) {// 尝试x[i] = 1 cw += w[i]; m a x L o a d i n g ( i + 1 ) ; cw -= w[i];} maxLoading(i+1);// 尝试x[i] = 0 } template T MaxLoading(T w[], T c, int n) {// 返回最优装载的重量 Loading 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 )。这个函数使用的递归栈空间为(n)。 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 ,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 void Loading::maxLoading(int i) {// // 从第i 层节点搜索 if (i > n) {// 在叶节点上 bestw = cw; r e t u r n ; } // 检查子树 r -= w[i]; if (cw + w[i] <= c) {//尝试x[i] = 1 cw += w[i]; m a x L o a d i n g ( i + 1 ) ; cw -= w[i];} if (cw + r > bestw) //尝试x[i] = 0 m a x L o a d i n g ( i + 1 ) ; r += w[i]; } template T MaxLoading(T w[], T c, int n) {// 返回最优装载的重量 Loading 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[i]; // 计算最优装载的重量 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 void Loading::maxLoading(int i) { / /从第i 层节点搜索 if (i > n) {// 在叶节点上 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestw = cw; return;} // 检查子树 r -= w[i]; if (cw + w[i] <= c) {//尝试x[i] = 1 x[i] = 1; cw += w[i]; m a x L o a d i n g ( i + 1 ) ; cw -= w[i];} if (cw + r > bestw) {//尝试x[i] = 0 x[i] = 0; m a x L o a d i n g ( i + 1 ) ; } r += w[i]; } template T MaxLoading(T w[], T c, int n, int bestx[]) {// 返回最优装载及其值 Loading 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[i]; 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 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[i] <= c) { // 移向左孩子 r -= w[i]; cw += w[i]; x[i] = 1; i + + ; } if (i > n) {// 到达叶子 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestw = cw;} else {// 移向右孩子 r -= w[i]; x[i] = 0; i + + ; } // 必要时返回 while (cw + r <= bestw) { // 本子树没有更好的叶子～返回 i - - ; while (i > 0 && !x[i]) { // 从一个右孩子返回 r += w[i]; i - - ; } if (i == 0) {delete [] x; return bestw;} // 移向右子树 x[i] = 0; cw -= w[i]; i + + ; } } } 4.2.2 0/1背包问题 复杂问题～为了解决该问题～在1 . 4节采用了贪0 / 1背包问题是一个N P- 婪算法～在3 . 2节又采用了动态规划算法。在本节～将用回溯算法解决该问题。既然想选择一个对象的子集～将它们装入背包～以便获得的收益最大～则解空间应组织成子集树的形状,如图1 6 - 2所示,。该回溯算法与4 . 2节的装载问题很类似。首先形成一个递归算法～去找到可获得的最大收益。然后～对该算法加以改进～形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。 与程序1 6 - 2一样～左孩子表示一个可行的节点～无论何时都要移动到它,当右子树可能含有比当前最优解还优的解时～移动到它。一种决定是否要移动到右子树的简单方法是令r 为还未遍历的对象的收益之和～将r 加到c p,当前节点所获收益,之上～若, r + c p,?b e s t p,目前最优解的收益,～则不需搜索右子树。一种更有效的方法是按收益密度pi / wi 对剩余对象排序～将对象按密度递减的顺序去填充背包的剩余容量～当遇到第一个不能全部放入背包的对象时～就使用它的一部分。 n= 4～c= 7～p= [ 9 , 1 0 , 7 , 4 ]～w= [ 3 , 5 , 2 , 1 ]。例4-7 考察一个背包例子: 这些对象的收益密度为[ 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 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 Tp Knap::Bound(int i) {// 返回子树中最优叶子的上限值Return upper bound on value of // best leaf in subtree. Tw cleft = c - cw; // 剩余容量 Tp b = cp; // 收益的界限 // 按照收益密度的次序装填剩余容量 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i + + ; } // 取下一个对象的一部分 if (i <= n) b += p[i]/w[i] * cleft; return b; } 程序16-7 0/1背包问题的迭代函数 template void Knap::Knapsack(int i) {// 从第i 层节点搜索 if (i > n) {// 在叶节点上 bestp = cp; r e t u r n ; } // 检查子树 if (cw + w[i] <= c) {//尝试x[i] = 1 cw += w[i]; cp += p[i]; K n a p s a c k ( i + 1 ) ; cw -= w[i]; cp -= p[i];} if (Bound(i+1) > bestp) // 尝试x[i] = 0 K n a p s a c k ( i + 1 ) ; } 在执行程序1 6 - 7的函数Kn a p s a c k之前～需要按密度对对象排序～也要确保对象的重量总和超出背包的容量。为了完成排序～定义了类O b j e c t,见 ,能按程序1 6 - 8,。注意定义操作符< =是为了使归并排序程序,见程序1 4 - 3密度递减的顺序排序。 程序16-8 Object类 class Object { friend int Knapsack(int *, int *, int, int); p u b l i c : int operator<=(Object a) const {return (d >= a.d);} p r i v a t e : int ID; // 对象号 float d; // 收益密度 } ; 程序1 6 - 9首先验证重量之和超出背包容量～然后排序对象～在执行K n a p : : K n a p s a c k之前完成一些必要的初始化。K n a p : K n a p s a c k的复杂性是O (n2n )～因为限界函数的复杂性为O (n)～且该函数在O ( 2n )个右孩子处被计算。 程序16-9 程序1 6 - 7的预处理代码 template Tp Knapsack(Tp p[], Tw w[], Tw c, int n) {// 返回最优装包的值 // 初始化 Tw W = 0; // 记录重量之和 Tp P = 0; // 记录收益之和 // 定义一个按收益密度排序的对象数组 Object *Q = new Object [n]; for (int i = 1; i <= n; i++) { // 收益密度的数组 Q[i-1].ID = i; Q[i-1].d = 1.0*p[i]/w[i]; P += p[i]; W += w[i]; } if (W <= c) return P; // 可容纳所有对象 MergeSort(Q,n); // 按密度排序 // 创建K n a p的成员 K n a p < Tw, Tp> K; K.p = new Tp [n+1]; K.w = new Tw [n+1]; for (i = 1; i <= n; i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = w[Q[i-1].ID]; } K.cp = 0; K.cw = 0; K.c = c; K.n = n; K.bestp = 0; // 寻找最优收益 K . K n a p s a c k ( 1 ) ; delete [] Q; delete [] K.w; delete [] K.p; return K.bestp; } 4.2.3 最大完备子图 令U为无向图G的顶点的子集～当且仅当对于U中的任意点u 和v～(u , v)是图G的一条边时～U定义了一个完全子图,complete subgraph,。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在G的一个更大的完全子图中时～它是图G的一个完备子图。最大的完备子图是具有最大尺寸的完备子图。 例4-8 在图16-7a 中～子集{ 1 , 2 }定义了一个尺寸为2的完全子图。这个子图不是一个完备子图～因为它被包含在一个更大的完全子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 }定义了该图的一个最大的完备子图。点集{ 1 , 4 , 5 }和{ 2 , 3 , 5 }定义了其他的最大的完备子图。 当且仅当对于U中任意点u 和v～(u , v) 不是G的一条边时～U定义了一个空子图。当且仅当一个子集不被包含在一个更大的点集中时～该点集是图G的一个独立集,independent set,～同时它也定义了图G的空子图。最大独立集是具有最大尺寸的独立集。对于任意图G～它的补图,c o m p l e m e n t, 是有同样点集的图～且当且仅当, u,v,不是G的一条边时～它是的一条边。 例4-9 图16-7b 是图16-7a 的补图～反之亦然。{ 2 , 4 }定义了16-7a 的一个空子图～它也是该图的一个最大独立集。虽然{ 1 , 2 }定义了图16-7b 的一个空子图～它不是一个独立集～因为它被包含在空子图{ 1 , 2 , 5 }中。{ 1 , 2 , 5 } 是图16-7b 中的一个最大独立集。 如果U定义了G的一个完全子图～则它也定义了的一个空子图～反之亦然。所以在G的完备子图与的独立集之间有对应关系。特别的～ G的一个最大完备子图定义了的一个最大独立集。 最大完备子图问题是指寻找图G的一个最大完备子图。类似地～最大独立集问题是指寻找图G的一个最大独立集。这两个问题都是N P-复杂问题。当用算法解决其中一个问题时～也就解决了另一个问题。例如～如果有一个求解最大完备子图问题的算法～则也能解决最大独立集问题～方法是首先计算所给图的补图～然后寻找补图的最大完备子图。 例4-10 假定有一个n 个动物构成的集合。可以定义一个有n 个顶点的相 容图,c o m p a t i b i l i t yg r a p h,G。当且仅当动物u 和v 相容时～,u,v,是G的一条边。G的一个最大完备子图定义了相互间相容的动物构成的最大子集。 3 . 2节考察了如何找到一个具有最大尺寸的互不交叉的网组的集合问题。可以把这个问题看作是一个最大独立集问题。定义一个图～图中每个顶点表示一个网组。当且仅当两个顶点对应的网组交叉时～它们之间有一条边。所以该图的一个最大独立集对应于非交叉网组的一个最大尺寸的子集。当网组有一个端点在路径顶端～而另一个在底端时～非交叉网组的最大尺寸的子集能在多项式时间,实 2 ),内用动态规划算法得到。当一个网组的端点可能在平面中的任意地际上是(n 方时～不可能有在多项式时间内找到非交叉网组的最大尺寸子集的算法。最大完备子图问题和最大独立集问题可由回溯算法在O (n2n )时间内解决。两个问题都可使用子集解空间树,如图1 6 - 2所示,。考察最大完备子图问题～该递归回溯算法与程序1 6 - 3非常类似。当试图移动到空间树的i 层节点Z的左孩子时～需要证明从顶点i 到每一个其他的顶点j,xj = 1且j 在从根到Z的路径上,有一条边。当试图移动到Z的右孩子时～需要证明还有足够多的顶点未被搜索～以便在右子树有可能找到一个较大的完备子图。 回溯算法可作为类A d j a c e n c y G r a p h,见程序1 2 - 4,的一个成员来实现～为此首先要在该类 中加入私有静态成员x,整型数组～用于存储到当前节点的路径,～b e s t x,整型数组～保存目 前的最优解,～b e s t n,b e s t x中点的数量,～c n,x 中点的数量,。所以类A d j a c e c y G r a p h的所有实 例都能共享这些变量。 函数m a x C l i q u e,见程序1 6 - 1 0,是类A d j a c e n c y G r a p h的一个私有成员～而M a x C l i q u e是一个 共享成员。函数m a x C l i q u e对解空间树进行搜索～而M a x C i q u e初始化必要的变量。M a x c l i q u e ( v ) 的执行返回最大完备子图的尺寸～同时它也设臵整型数组v～当且仅当顶点i 不是所找到的最大 完备子图的一个成员时～v [ i ] = 0。 程序16-10 最大完备子图 void AdjacencyGraph::maxClique(int i) {// 计算最大完备子图的回溯代码 if (i > n) {// 在叶子上 // 找到一个更大的完备子图～更新 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; r e t u r n ; } // 在当前完备子图中检查顶点i是否与其它顶点相连 int OK = 1; for (int j = 1; j < i; j++) if (x[j] && a[i][j] == NoEdge) { // i 不与j 相连 OK = 0; b r e a k ; } if (OK) {// 尝试x[i] = 1 x[i] = 1; // 把i 加入完备子图 c n + + ; m a x C l i q u e ( i + 1 ) ; x[i] = 0; c n - - ; } if (cn + n - i > bestn) {// 尝试x[i] = 0 x[i] = 0; m a x C l i q u e ( i + 1 ) ; } } int AdjacencyGraph::MaxClique(int v[]) {// 返回最大完备子图的大小 // 完备子图的顶点放入v [ 1 : n ] // 初始化 x = new int [n+1]; cn = 0; bestn = 0; bestx = v; // 寻找最大完备子图 m a x C l i q u e ( 1 ) ; delete [] x; return bestn; } 4.2.4 旅行商问题 旅行商问题,例4 . 3,的解空间是一个排列树。这样的树可用函数P e r m (见程序1 - 1 0 )搜索～并可生成元素表的所有排列。如果以x=[1, 2, ., n] 开始～那么通过产生从x2 到xn 的所 有排列～可生成n 顶点旅行商问题的解空间。由于P e r m产生具有相同前缀的所有排列～因此可以容易地改造P e r m～使其不能产生具有不可行前缀,即该前缀没有定义路径,或不可能比当前最优旅行还优的前缀的排列。注意在一个排列空间树中～由任意子树中的叶节点定 义的排列有相同的前缀,如图1 6 - 5所示,。因此～考察时删除特定的前缀等价于搜索期间不 进入相应的子树。旅行商问题的回溯算法可作为类A d j a c e n c y W D i g r a p h ,见程序1 2 - 1,的一个成员。在其他例子中～有两个成员函数: t S P和T S P。前者是一个保护或私有成员～后者是一个共享成员。函数G . T S P ( v )返回最少耗费旅行的花费～旅行自身由整型数组v 返回。若网络中无旅行～则返回N o E d g e。t S P在排列空间树中进行递归回溯搜索～ T S P是其一个必要的预处理过程。T S P假定x,用来保存到当前节点的路径的整型数组,～b e s t x,保存目前发现的最优旅行的整型数组,～ c c,类型为T的变量～保存当前节点的局部旅行的耗费,～b e s t c,类型为T的变量～保存目前最优解的耗费,已被定义为A d j a c e n c y W D i g r a p h 中的静态数据成员。T S P见程序1 6 - 11。t S P ( 2 )搜索一棵包含x [ 2 : n ]的所 有排列的树。 程序1 6 - 11 旅行商回溯算法的预处理程序 template T AdjacencyWDigraph::TSP(int v[]) {// 用回溯算法解决旅行商问题 // 返回最优旅游路径的耗费～最优路径存入v [ 1 : n ] / /初始化 x = new int [n+1]; // x 是排列 for (int i = 1; i <= n; i++) x[i] = i; bestc = NoEdge; bestx = v; // 使用数组v来存储最优路径 cc = 0; // 搜索x [ 2 : n ]的各种排列 t S P ( 2 ) ; delete [] x; return bestc; } 函数t S P见程序1 6 - 1 2。它的结构与函数P e r m相同。当i=n 时～处在排列树的叶节点的父节点上～并且需要验证从x[n-1] 到x[n] 有一条边～从x[n] 到起点x[1] 也有一条边。若两条边都存在～则发现了一个新旅行。在本例中～需要验证是否该旅行是目前发现的最优旅行。若是～则将旅行和它的耗费分别存入b e s t x与b e s t c中。 当i,n 时～检查当前i-1 层节点的孩子节点～并且仅当以下情况出现时～移动到孩子节点之一:1) 有从x[i-1] 到x[i] 的一条边,如果是这样的话～ x [ 1 : i ]定义了网络中的一条路径,,2 )路径x[1:i] 的耗费小于当前最优解的耗费。变量cc 保存目前所构造的路径的耗费。 每次找到一个更好的旅行时～除了更新bestx 的耗费外～ tS P需耗时O ( (n- 1 ) ! )。因为需发生O ( (n-1)!) 次更新且每一次更新的耗费为(n) 时间～因此更新所需时间为O (n* (n- 1 ) ! )。通过使用加强的条件,练习1 6,～能减少由tS P搜索的树节点的数量。 程序16-12 旅行商问题的迭代回溯算法 void AdjacencyWDigraph::tSP(int i) {// 旅行商问题的回溯算法 if (i == n) {// 位于一个叶子的父节点 // 通过增加两条边来完成旅行 if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge)) {// 找到更优的旅行路径 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];} } else {// 尝试子树 for (int j = i; j <= n; j++) / /能移动到子树x [ j ]吗? if (a[x[i-1]][x[j]] != NoEdge && (cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge)) {//能 // 搜索该子树 Swap(x[i], x[j]); cc += a[x[i-1]][x[i]]; t S P ( i + 1 ) ; cc -= a[x[i-1]][x[i]]; Swap(x[i], x[j]);} } } 4.2.5 电路板排列 在大规模电子系统的设计中存在着电路板排列问题。这个问题的经典形式为将 n个电路板放臵到一个机箱的许多插槽中～,如图1 6 - 8所示,。n个电路板的每一种排 列定义了一种放臵方法。令B= {b1 , ., bn }表示这n个电路板。m个网组集合L= , {N1 ., Nm }由电路板定义～Ni 是B的子集～子集中的元素需要连接起来。实际中用电线 将插有这些电路板的插槽连接起来。 例4 - 11 令n=8, m= 5。集合B和L如下: B= {b1, b2, b3, b4, b5, b6, b7, b8 } L= {N1, N2, N3, N4, N5 } N1 = {b4, b5, b6 } N2 = {b2, b3 } N3 = {b1, b3 } N4 = {b3, b6 } N5 = {b7, b8 } 令x 为电路板的一个排列。电路板xi 被放臵到机箱的插槽i 中。d e n s i t y(x) 为机箱中任意一对相邻插槽间所连电线数目中的最大值。对于图1 6 - 9中的排列～d e n s i t y为2。有两根电线连接了插槽2和3～插槽4和5～插槽5和6。插槽6和7之间无电线～余下的相邻插槽都只有一根电线。板式机箱被设计成具有相同的相邻插槽间距～因此这个间距决定了机箱的大小。该间距必须保证足够大以便容纳相邻插槽间的连线。因此这个距离,继而机箱的大小,由d e n s i t y(x)决定。 电路板排列问题的目标是找到一种电路板的排列方式～使其有最小的d e n s i t y。既然该问题是一个N P-复杂问题～故它不可能由一个多项式时间的算法来解决～而象回溯这样的搜索方法则是解决该问题的一种较好方法。回溯算法为了找到最优的电路板排列方式～将搜索一个排列空间。 用一个n×m 的整型数组B表示输入～当且仅当Nj 中包含电路板bi 时～B [ i ] [ j ] = 1。令t o t a l [ j ]为Nj 中电路板的数量。对于任意部分的电路板排列x [ 1 : i ]～令n o w [ j ]为既在x [ 1 : i ]中又被包含在Nj 中的电路板的数量。当且仅当n o w [ j ] > 0且n o w [ j ]?t o t a l [ j ]时～Nj 在插槽i 和i + 1之间有连线。插槽i 和i + 1间的线密度可利用该测试方法计算出来。在插槽k和k + 1 ( 1?k?i ) 间的线密度的最大值给出了局部排列的密度。 为了实现电路板排列问题的回溯算法～使用了类B o a r d,见程序1 6 - 1 3,。程序1 6 - 1 4给出了私有方法B e s t O r d e r～程序1 6 - 1 5给出了函数A r r a n g e B o a r d s。ArrangeBoards 返回最优的电路板排列密度～最优的排列由数组bestx 返回。ArrangeBoards 创建类Board 的一个成员x 并初始化与之相关的变量。尤其是total 被初始化以使total[j] 等于Nj 中电路板的数量。now[1:n] 被臵为0～与一个空的局部排列相对应。调用x .BestOrder(1,0) 搜索x[1:n] 的排列树～以从密度为0的空排列中找到一个最优的排列。通常～x.BestOrder(i,cd) 寻找最优的局部排列x [ 1 : i - 1 ]～该局部排列密度为c d。函数B e s t O r d e r,见程序1 6 - 1 4,和程序1 6 - 1 2有同样的结构～它也搜索一个排列空间。当i=n 时～表示所有的电路板已被放臵且cd 为排列的密度。既然这个算法只寻找那些比当前最优排列还优的排列～所以不必验证cd 是否比beste 要小。当i 0 && total[k] != now[k]) l d + + ; } // 更新ld 为局部排列的总密度 if (cd > ld) ld = cd; // 仅当子树中包含一个更优的排列时～搜索该子树 if (ld < bestd) {// 移动到孩子 Swap(x[i], x[j]); BestOrder(i+1, ld); Swap(x[i], x[j]);} // 重臵 for (k = 1; k <= m; k++) now[k] -= B[x[j]][k]; } } 程序16-15 BestOrder(程序1 6 - 1 4)的预处理代码 int ArrangeBoards(int **B, int n, int m, int bestx[ ]) {// 返回最优密度 // 在b e s t x中返回最优排列 Board X; // 初始化X X.x = new int [n+1]; X.total = new int [m+1]; X.now = new int [m+1]; X.B = B; X.n = n; X.m = m; X.bestx = bestx; X.bestd = m + 1; // 初始化t o t a l和n o w for (int i = 1; i <= m; i++) { X.total[i] = 0; X.now[i] = 0; } // 初始化x并计算t o t a l for (i = 1; i <= n; i++) { X.x[i] = i; for (int j = 1; j <= m; j++) X.total[j] += B[i][j]; } // 寻找最优排列 X . B e s t O r d e r ( 1 , 0 ) ; delete [] X.x; delete [] X.total; delete [] X.now; return X.bestd;