第八章 分支限界法 §1 算法基本思想 本章叙述中为了区别图中的顶点和解空间树中的顶点， 凡是在解 空间树中出线队顶点一律称为结点。 分支限界法同回溯法类似， 它也是在解空间中搜索问题的可行解 或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝纵深 方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到 问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上 最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支 定界法则采用宽度优先的方式搜索解空间树， 它将活结点存放在一个 特殊的表中。其策略是：在扩展结点处 ，先生成其所有的儿子结点, 将那些导致不可行解或导致非最优解的儿子舍弃， 其余儿子加入活结 点表中。此后，从活结点表中 取出一个结点 作为当前扩展结点。并重 复上述结点扩展过程。所以，分支限界法与回溯法的本质区别在于搜 索方式的不同。回溯法更适于处理那些求所有可行解的问题，而分支 限界法更适于处理那些只确定一个可行解，特别是最优化问题。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限 界法。最常见的有以下两种方式： 1).队列式（FIFO）分支限界法：将活结点表组织成一个队列， 并按队列的 先进先出 原则选取下一个结点作为当前扩展结点。 2).优先队列式分支限界法： 将活 结点表组织成一个优先队列， 并按优先队列给结点规定的优先级选取 优先级最高的下一个结点作 为当前扩展结点。 队列式分支限界法的搜索解空间树的方式类似于解空间树的宽 度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经 被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是 因为，按照规则，这样的结点未被列入活结点表。 优先队列式分支限界法的搜索方式是根据活结点的优先级确定 下一个扩展结点。 结点的优先级常用一个与该结点有关的数值p 来表 示。最大优先队列规定p值较大的结点点的优先级较高。在算法实现 时通常用一个最大堆来实现最大优先队列， 用最大堆的 Deletemax 运 算抽取堆中的下一个结点作为当前扩展结点， 体现最大效益优先的原 则。类似地，最小优先队列规定p值较小的结点的优先级较高。在算 法实现时，常用一个最小堆来实现，用最小堆的Deletemin 运算抽取 堆中下一个结点作为当前扩展结点，体现最小优先的原则。采用优先 队列式分支定界算法解决具体问题时， 应根据问题的特点选用最大优 先或最小优先队列，确定各个结点点的p 值。 例1 旅行商问题，n=4，其解空间树是一棵排列树。如文档“旅 行商搜索树 ” 。赋权图G 给出如下： 30 6 10 求赋权图G的 5 4 最小权Hamilton圈 20 采用队列式分支限界法以排列树中的结点B 作为初始扩展结点。 1 4 2 3 此时，活结点队列为空。由于从图 G 的顶点 1 到顶点 2、3 和 4 均有 边相连，B 的儿子 C、D 和 E 都是可行结点，它们被依次加入到活结 点队列中，并舍弃当前扩展结点 B。当前活结点队列中的队首结点 C 成为下一个扩展结点。由于图G的顶点2到顶点3和4 有边相连，故 结点C 的二个儿子 F 和G 均为可行结点，可以加入活结点队列。接下 来，结点 D和结点 E相继成为扩展结点。此时活结点队列中的结点依 次为 F、G、H、I、J、K。结点 F 成为下一个扩展结点，但其儿子 L 是解空间树的叶结点，我们找到了一条Hamilton圈（1，2，3，4，1） ， 其费用为 59。下一个扩展结点 G 的儿子 M 也是叶结点，得到另一条 Hamilton 圈（1，2，4，3，1） ，其费用为 66。结点 H 成为当前扩展 结点，其儿子N也是叶结点，得到第三条Hamilton圈，其费用为 25， 这是当前知道的最短 Hamilton 圈。下一个扩展结点是 I，由于从根 结点到结点 I 的费用 26 已经超过当前最优值，故没有必要扩展 I， 以I为根的子树被剪掉。最后J和K 被依次扩展，活结点队列称为空 集，算法终止。算法搜索到的最优值是 25，相应的最优解是从根结 点到结点N 的路径（1，3，2，4，1） 。 采用优先队列式分支限界法，用一个最小堆存储活结点表，优先 级函数是结点的当前费用。 算法还是排列树的结点B和空优先队列开 始。结点 B 被扩展后，它的 3 个儿子 C、D 和 E 被依次插入堆中。此 时，由于 E 是堆中具有最小当前费用（为4）的结点，所以处于堆顶 的位置，它自然成为下一个扩展结点。结点E 被扩展后，其儿子 J 和 K 被插入当前堆中，它们的费用分别为 1 4 和 24。此时，堆顶元素是 D，它成为下一个扩展结点。它的2 个儿子H 和I被插入堆中。此时， 堆中元素是结点 C、H、I、J、K。在这些结点中，H 具有最小费用， 成为下一个扩展结点。扩展结点H后得到一条 Hamilton圈（1，3，2， 4，1） ，相应的费用为25。接下来，结点J 成为扩展结点，并由此得 到一条Hamilton圈（1，4，2，3，1） ，费用仍为25。此后的两个扩 展结点是 K 和 I。由结点 K 得到的 Hamilton 圈的费用高于当前所知 最小费用，结点I 当前的费用已经高于当前所知最小费用，因而，它 们都不能得到最优解。最后，优先队列为空，算法终止。 §2 优先级的确定与 LC-检索 对于优先队列式分支限界法， 结点优先级的确定直接影响着算法 性能。我们当然希望这样的活结点X 成为当前扩展结点： 1).以X 为根的子树中含有问题的答案结点； 2).在所有满足条件1)的活结点中，X 距离答案结点“最近” 。 但是，要给出可能导致答案结点的活结点附以优先级，必须要附加若 干计算工作，即要付出代价。对于任一结点，要付出的代价可以使用 两种标准来度量： (i).在生成一个答案结点之前，子树X 需要生成的结点数； (ii).在子树X 中离X 最近的那个答案结点到X 的路径长度。 容易看出，如果使用度量(i)， 在对于每一种分枝限界算法，总是生 成最小数目的结点；如果采用度量(i i),则要成为扩展结点的结点只 是由根到最近的那个答案结点路径上的那些结点。用c(·)表示一个 理想的优先级函数，定义如下： a).如果 X 是答案结点，则 c(X)是解空间树中，由根结点到 X 的 成本(即所用的代价，如级数、计算复杂度等)； b).如果X不是答案结点，而且以 X为根的子树中不含答案结点， 则c(X)定义为 ∞； c).如果X 不是答案结点，但是以 X 为根的子树中含答案结点，则 c(X)是具有最小成本的答案结点的成本。 如果能够获得这样的优先级函数， 则优先队列式分支限界法将以 最少的搜索时间找到问题的解。然而，这样的优先级函数的计算工作 量不亚于解原问题。实际问题中都是采用一个估计函数 ?，它由两部 分决定：解空间树的根结点到 X 的成本 f(X)和 X 到答案结点的估计 成本g(X)，即 ?(X)= f(X)+g(X). ? 称为成本估计函数。根据成本估 计函数选择下一个扩展结点的策略总是选取 ?(·)值最小的活结点作 为下一个扩展结点。这种搜索策略称为最小成本检索（Least Cost search） ，简称LC-检索。如果取g=0,f(X)等于X在解空间树中的级， 则LC-检索即是宽度优先搜索(BFS)；如果f=0，且g 满足： Y是X的儿子 ? g(Y)≤ g(X) (8.2.1) 则LC-检索即是深度优先搜索(DFS).在以后所提到的成本函数 ? 中， 函数g 都满足(8.2.1)式。 例子 15 迷问题 在一个分成 4×4 的棋盘上排列 15 块号牌，如图(a)。其中会出 现一个空格。 棋盘上号牌的一次合法移动是指将位于空格上、 下、 左、 右的一块号牌移入空格。要求通过一系列合法移动，将号牌的初始排 列转换成自然排列，如图(b). 1 3 4 15 1 2 3 4 ＃ ＃ 2 5 12 5 6 7 8 ＃ ＃ 7 6 11 14 9 10 11 12 ＃ ＃ 8 9 10 13 13 14 15 ＃ ＃ 图 (a) 图 (b) 图 (c) 如果将棋盘的各个位置按照号牌的自然排列发给序号， 右下角发 给 16 号。则号牌的每一种排列都可以看作是 0，1，…，15 这 16 个 数的排列，其中，0 的位置代表空格。如图(a)对应的排列是 (1,3,4,15,2,0,5,12,7,6,11,14,8,9,10,13).事实上， 不是号牌的每 一种排列都能够经过一系列合法移动转换成自然排列的。用Less(i) 记排列P 中位于i 后面且号比i 小的号牌数， 则排列P 可以经一系列 合法移动转换成自然排列的充要条件是 ∑ ≤≤ + 151 )( i XiLess 是偶数 （8.2.2） 其中，当空格在图(c)的某个＃位置时， X=1; 否则 X=0.以后记 ∑ ≤≤ = 151 )()( i iLessPτ ,称为排列P的逆序数。例如，图(a)中排列的逆序 数为16， X=0,所以图(a)中排列可经一系列合法移动转换成自然排列。 在处理实际问题中，一般是根据具体问题的特性，确定成本估 计函数 ?(X)= f(X)+g(X)中的函数f(X)和g(X).在本例中， 我们令f(x) 是由根到结点X 的路径的长度，g(X)是以X 为根的子树中，由X 到目 标状态(自然排列)的一条最短路径长度的估计值。为此，g(X)至少应 是把状态 X转换成目标状态所需的最小移动数。 对它的一种可能的选 择是 g(X)= 排列X的不在自然位置的牌的数目 (8.2.3) 图(a)的排列中，不在自然位置的牌号分别是：3，4，15，2，5，12， 7，6，14，8，9，10，13，共13个。g(X)=13.将图(a)中的排列转换 成自然排列至少需要13次合法的移动。可见，估价函数 ?(X)是函数 c(X)的下界。按照这样成本估价函数，则 15 迷问题解空间树的搜索 过程可以从文档“15 迷空间树” 的图(1)中看出。 首先以结点1作为扩展结点，生成4 个儿子：2，3，4，5后死 去。这4 个儿子的成本估值分别为： ?(2)=1+4; ?(3)=1+4; ?(4)=1+2; ?(5)=1+4.因而结点 4 成为当前扩展 结点，生成 4 个儿子，但有一个 儿子同其祖父相同被舍弃。剩下的 3 个儿子的成本估值分别为 ?(10)=2+1； ?(11)=2+3； ?(12)=2+3，此时，活结点表中共有 6 个结 点：2，3，5，10，11，12，其中结点 10的成本估值最小。故以结点 10 作为新的扩展结点。它能生成 3 个儿子，其中有一个因同其祖父 相同而被舍弃。剩下的 2 个儿子是结点 22 和 23。但结点 23 所表示 的号牌排列是自然的，至此得到可行解。 如果采用队列式分枝限界法，即采用宽度优先搜索，势必将图 (1)中的所有状态全部搜索。如果采用深度优先搜索，则图(2)中也只 给出了一部分搜索步骤，而且结点 12 表示的号牌排列与自然排列还 相距甚远。 由此看出选择合适的优先级函数对于分枝限界法效率的影 响甚大。 值得注意的是按照成本估价函数 ?(X)确定的优先级进行搜索， 所得到的答案结点未必是最小成本答案结点。例如，下面的解空间树 中，每个结点X旁有两个数：上面的是最下成本c(X),下面的是成本 估价 ?(X)。整个解空间树中有两个答案结点。如果按照估价函数进 行搜索，根结点 1 首先成为扩展结点，然后是结点 2，在扩展结点 2 时，得到一个答案结点4，它时结点 2的一个儿子。这个答案结点的 成本是20，比另一个答案结点6 的成本大。 10 0 20 10 2 4 20 ∞ ∞ 10 20 ∞ ∞ 10 定理 8.1 在有限的解空间树中，如果对每对结点X 和Y，成本函 数c与成本估价函数 ? 均满足： “c(X) < c(Y)” ＝> “?(X) < ?(Y)” , 则按照成本估价函数搜索能够达到最小成本答案结点。 一般情况下，不易找到定理 8.1 中要求的成本估价函数。对于成 本估价函数，一般有一个基本要求： ?(X)≤ c(X), 对任意结点 X； (8.2.4) ?(X)＝c(X)，当X是答案结点时。 (8.2.5) 在以下给出的算法中， 要求搜索一直继续到一个答案结点变成扩 展结点为止。 搜索最小成本答案结点LC－检索 LeastCost(T, ?)//T 是问题的解空间树 1 E=T; //第一个扩展结点 2 置活结点表为空; 1 2 3 65 4 7 3 loop 4 if E 是答案结点 then 5 输出从E 到T 的路径； return； 6 endif 7 for E的每个儿子X do 8 Add(X); Parent(X)=E; 9 endfor 10 if 不再有活结点 then 11 print(‘no answer node’); stop; 12 endif 13 Least(E); 14 endloop 15 end LeastCost 其中，Least(X)是从活结点表中找一个具有最小 ? 值的活结点，从活 结点表中删除该结点，再将该结点赋给变量X；Add(X)是将新的活结 点加到活结点表中。Parent(X)将活结点X 与它的父亲相连接。 在算法LeastCost中，由于答案结点 E是扩展结点，所以，对于 活结点表中的每个结点L均有 ?(E)≤ ?(L).再由假设 ?(E)=c(E)， ?(L) ≤ c(L)，得c(E) ≤ c(L)，即E 是一个最小成本答案结点。 综上所述，采用优先队列式分枝限界 法，其搜索解空间树的算法 主要决定于三个因素：约束函数、限界函数和优先级函数。前两项主 要是限制被搜索的结点数量，而优先级 函数则是用来确定搜索的次 序。但是，在处理实际问题中，未必把这三种函数全部列出来，特别 是优先级函数往往同限界函数合为一体。 以下给出处理极小化最优问 题的优先队列式分枝限界法的一般流程。 找最小成本结点的LC-分枝限界算法 LCBB(T, ?,u, ε,cost) //假定解空间树 T 包含一个解结点且 ?(X) ≤ //c(X) ≤ u(X)。c(X)是最小成本函数， ?(X)是成本估价函数， //u(X)是限界函数;当X是答案结点时， cost(X)是X所对应的解 //的成本。 ε 是一个充分小的正数。 1 E＝T; Parent(E)=0; 2 if T 是解结点 then U=min(cost(T),u(T)+ε); ans=T; 3 else U=u(T)+ε; ans=0; 4 endif 5 将活结点表初始化为空集； 6 loop 7 for E 的每个儿子X do 8 if ?(X)<U && X是一个可行结点 then 9 Add(X); Parent(X)=E; 10 case 11 :X是解结点 && cost(X)<U: 12 U=min(cost(X),u(X)+ε); ans=X; 13 :u(X)+ε<U: 14 U=u(X)+ε; 15 endcase 16 endif 17 endfor 18 if 不再有活结点 or 下一个扩展结点满足 ?≥U then 19 print(‘least cost=’,U); 20 while ans≠0 do 21 print(ans); ans=Parent(ans); 22 endwhile 23 return; 24 endif 25 Least(E); 26 endloop 27end LCBB 这里我们将选择扩展结点的任务交给函数Least(E).所谓的“成本” 是指目标函数的值。所以，当X是可行解的答案结点时，c(X)表示该 可行解的目标函数值；当X 是不可行结点时，c(X)= ∞;当 X 是可行结 点但不是答案结点时， c(X)表示以X 为根的子树中 最小成本结点 的成 本。此时，成本估价函数 ?(X)即变成对于结点 X（作为部分解）的目 标函数值的一个估计。我们要求 ?(X) ≤ c(X)。算法中的U 是一个上 界值，开始时，U 可以取为一个充分大的数。 例如 ，假定一个可行解需要确定 n 个数 n xxx ,,, 21 L，而每个取 值 i x 会使得成本开销增加 ii xc ，于是，一个可行解X= ),,,( 21 n xxxL的 总开销为 ∑ ≤≤ = ni ii xcXc 1 )( .若当前只确定了前 k 个数 k xxx ,,, 21 L，用 结点X 表示当前之一状态， 则以这k 个数为部分解的可行解的开销一 定不小于 ∑ ≤≤ = ki ii xcXc 1 )(? ，不大于 u(X)= + ∑ ≤≤+ njk jj xp 1 ∑ ≤≤ ki ii xc 1 ,其中 i x 是 i x 可取的最大值。这样选取的函数 ?(X)和 u(X)就会满足上面我 们提出的要求： ?(X) ≤ c(X)≤ u(X)。 从上面的例子可以看出：如果X 是成本值为cost(X)的解结点， 且cost(X)<U,则可用min{cost(X),u(X)}更新U的值； 或者X 不是解 结点，但 u(X)< U，可用u(X)更新U的值。如果 U是某个可行解（或 答案结点）的成本值（开销） ，则当 ?(X)≥ U 时，可以杀死结点 X。 但是，当 U 只是一个简单的上界，不 是可行解的成本值时，应该谨慎 考虑 ?(X)=U 的情况。因为，如果 X 不是答案结点，则 X 的某个子孙 Y可能是答案结点，以X为根的子树中含有答案结点。如果前面盲目 地杀死结点X，则可能丢失一些最小成本答案结点。所以，在这种情 况下，不能杀死结点X。为此，在用 u(X)更新U值时，常常多加一个 微量 ε（ ε的选取应当满足： “u(X)<u(Y) ? u(X)+ ε <u(Y)” ） ， 即用u(X)+ ε 更新U。于是，U 的更新可以描述为：设E 是当前扩展结点，X 是 E 的一个儿子: (1). 当 X 是一个解结点，而且 cost(X)<U 时，可用 min(cost(X),u(X)+ ε)来更新U； (2).当X不是解结点， 而且u(X)+ δ<U时， 直接用u(X)+ δ 更新U。 由于函数u(X)是对于结点X 的成本值上界的一个估计，具有某 种预测功能，常常用它来作为优先级函数。 §3. 0/1 背包问题的分枝限界法 我们分两种方式解这一问题： a).转化成极小化问题，利用 LC- 分枝限界法解决；b).采用优 先队列式分枝限界法，直接解极大化问 题。 （一）.转化成极小化问题 nix Mxw xp i ni ii ni ii ,,2,1},1,0{ )min( 1 1 L=∈ ≤ ? ∑ ∑ ≤≤ ≤≤ (8.3.1) 解空间树是n+1 级的完整二叉树。 若从根结点到叶结点 X的路径形成 问题的一个可行解，则叶结点X是答案结点。为了使最小成本答案结 点与最优解相对应，需要对每个答案结点 X 定义 ∑ ≤≤ ?= ni ii xpXc 1 )( ; 对于其余的叶结点X则定义 ∞=)(Xc ;而对于非叶结点X将递归地定 义为 )}(),(min{)( rl XcXcXc = ,其中 rl XX , 分别是 X 的左儿子和右 儿子。以下构建限界函数 )(? Xc 和优先级函数 )(Xu ，使得 )()()(? XuXcXc ≤≤ .假设X 是j级上的一个结点，1 ≤j≤n+1。在结点 X 处已经对前 j-1 个变量 i x 确定取值，则当前背包的成本值 c 为 ∑ <≤ ? ji ii xp 1 ，背包中现有物品的重量w 为 ∑ <≤ ji ii xw 1 。在这种情况下，以 X 为根的子树中答案结点的成本应该不小于 LB，不大于 UB，其中 LB 和UB 分别由下面两个算法确定： 确定UB的算法 UBValue(c,w,j,M)//c,w,j,M的含义同前面说明， W[i],P[i]分别、 //代表第 i 件物品的重量和价值，并假定物品的序号是按 //W[i]/P[i]≥ W[i+1]/P[i+1]的次序排出的。 global W[1:n],P[1:n]; integer i,j,n; real a,b; a=w;b=c; for i from j to n do if a+W[i]≤ M then a=a+W[i]; b=b-P[i]; endif endfor return (b); end UBValue 确定LB 的算法 LBValue(c,w,j,M)//c,w,k,M 的含义同前面说明，W[i],P[i]分别 //代表第 i 件物品的重量和价值，并假定物品的序号是按 //W[i]/P[i]≥ W[i+1]/P[i+1]的次序排出的。 global W[1:n],P[1:n]; integer i,j,n; real a,b; a=w;b=c; for i from j to n do if a+W[i]≤ M then a=a+W[i]; b=b-P[i]; else return (b-(M-a)P[i]/W[i]); endif endfor return (b); end UBValue 于是，可以取LB 和UB 分别为 )(? Xc 和 )(Xu 。 例子 考虑 0/1 背包问题 ： ),18,12,10,10(),,,(,4 4321 == ppppn 15),9,6,4,2(),,,( 4321 == Mwwww . 利用上面所定义的 )(? ?c 和 )(?u ，LC－分枝限界法 LCBB 搜索解空间 树过程如下： 开始将根作为 E-结点， 32)1(,38)1(? ?=?= uc .由于它不是答案 结点，因此 LCBB 置 ans=0 和 U=-32+ ε；扩展此结点，生成它的两个 儿子结点 2 和 3。经计算得 32)2(,38)2(? ?=?= uc ,32)3(? ?=c 22)3( ?=u 。将结点 2，3 放入活结点表，而且因为 )3()2( uu < ，结 点2被选为下一个扩展结点。扩展结点2，生成两个儿子结点4 和5。 计算得 32)4(,38)4(? ?=?= uc , ,36)5(? ?=c 22)5( ?=u 将结点 4，5 放入活结点表，目前活结点表中共有三个结点，而以结点4的成本上 界最小，所以，结点4被选为下一个扩展结点。扩展结点4，生成两 个儿子结点 6 和 7。计算得 ,38)6(? ?=c 32)6( ?=u , ,38)7(? ?=c 38)7( ?=u ,将它们放入活结点表。注意结点 6 和 7 的成本上界均小 于当前 U 值，U 的值应该更新。采用 ε+?38 更新 U 的值。目前活结 点表中共有四个结点，而以结点7 的成本上界最小，所以结点7 被选 为当前扩展结点。扩展结点 7，生成两个儿子结点 8 和 9。计算得 38)8(,38)8(? ?=?= uc , ,20)9(? ?=c 20)9( ?=u .因为结点 8 是答案结 点，而且由 Uct <?== 38)8(?)8(cos ,应该用-38 更新 U。由于 Uc >?= 20)9(? ,所以结点 9 被杀死，只有结点 8 放入活结点表。目 前，活结点表中共有4个活结点，依照它们的成本上界值从小到大排 列，依次是：8，6，3，5。下一个扩 展结点是 8。但是，8 是答案结 点，而且 Uc =)8(? ，程序终止检索，打印出值-38和路径8，7，4， 2，1，算法结束。由路径转换成解，还应该在算法 LCBB 的实现过程 中保留一些能反映 i x 取值情况的附加信息。 一种解决的办法是在每个 解增设一个位信息段tag，由答案结点到根结点的这一系列tag位给 出这些 i x 的值。例如，上面问题中，tag(2)=tag(4)=tag(6) =tag(8)=1;tag(3)=tag(5)=tag(7)=tag(9)=0.对应于路径8，7，4， 2，1 的一系列 tag 是 1011，因此，所得解是 1 4 =x , ,1,0 23 == xx 1 1 =x . -38 -32 x 1 =1 x 1 =0 x -38 -32 -32 -22 x 2 =1 x 2 =0 -38 -36 -32 -22 x 3 =1 x 3 =0 -38 -38 -32 -38 x 4 =1 x 4 =0 -38 -20 -38 -20 算法LCBB的执行过程 上述将0/1 背包问题化为极小化问题，采用LC-分枝限界法求解的算 法的详细步骤可以从下面直接解极大化问题的算法中获得，此略。 1 2 4 5 7 3 8 6 9 (二). 用优先队列式分枝限界法直接解极大化问题 LC-分枝限界法是优先队列式分枝限界法的基本形式之一，因为 任何极大化问题均可以转化成极小化问题， 正像前面解决0/1背包问 题一样。从上面的算法分析中可见，用优先队 列式分枝限界法解决 0/1 背包问题(作为极大化问题)，需要确定以下四个问题：解空间树 中结点的结构、如何生成一个给定结点的儿子、如何组织活结点表、 如何识别答案结点。 我们采用完整的二叉树作为解空间树， 放在活结点表中的每个结 点具有6 个信息段：Parent、Level、Tag、Cu、Cv、Pvu。其中Parent 是结点X 的父亲结点连接指针；Level标志出结点X在解空间树中的 级数，通过置 1 )( = XLevel X 表示生成 X 的左儿子，置 0 )( = XLevel X 表 示生成X 的右儿子；信息段 Tag用来出处最优解各个分量 i x 的值；信 息段 Cu 记录背包在结点 X 处的可用空间(即剩余空间)，在确定 X 左 儿子的可行性时用；Cv 记录在结点X 处背包中已装物品的价值(或效 益值)，等于 ∑ <≤ )(1 XLeveli ii xp ；信息段Pvu表示在结点X所表示的状态下， 可行解所能达到的可能值的上界。也即是说，当 11 ,, ?l xxL的值确定 后，可行解 nll xxxxLL,,,, 11 ? 所能达到的效益值的上界。类似地， 当 11 ,, ?l xxL的值确定后，可行解 nll xxxxLL,,,, 11 ? 所能达到的最大 效益值的下界记做 Pvl。如果到目前为止所知道的可行解的最大效益 值不小于 CL，则当 Pvu<CL 时，就应该杀死结点 X。所以，Pvu(X)可 以作为限界函数。同时，我们将以Pvl 作为优先级函数。关于它们的 计算将由一个子程序给出。 作为极大化问题处理的优先队列 式分枝限界法解 0/1 背包问题 的程序 LCKNAP，采用了六个子程序：LUBound、NewNode、Finish、 Init、GetNode 和 Largest。子程序 LUBound 计算 Pvl 和 Pvu 之用； NewNode生成一个具有六个信息段的结点，给各个信息段置入适当的 值并将此结点加入结点表；Finish 打印出最优解的值和此最优解中 1= i x 的物品；Init 对可用结点表和活结点表置初值；GetNode 取一 个可用结点；Largest 在活结点表中取一个具有最大Pvl 值结点作为 下一个扩展结点。 0/1背包问题的优先队列式分子限界算法 LCKNAP(P,W,M,N,ε)//假定物品的排列顺序遵循 //P[i]/W[i]≥P[i+1]/W[i+1]； real P[1:N],W[1:N],M,CL,Pvl,Pvu,cap,prof; integer ANS，X，N； 1． Init；//初始化可用结点表及活结点表 2． GenNode(E)；//生成根结点 3． Parent(E)=0;Level=1;Cu(E)=M;Cv(E)=0; 4． LUBound(P,W,M,N,1,Pvl,Pvu); 5． CL=Pvl- ε;UB(E)=Pvu; 6． loop 7． i=Level(E); cap=Cu(E);prof=Cv(E); 8. case 9. :i=N+1: //解结点 10. if prof>CL then 11. CL=prof; ANS=E; 12. endif 13. :else://E有两个儿子 14． if cap≥W[i] then //左儿子可行 15． NewNode(E,i+1,1,cap-W[i],prof+P[i],UB(E)); 16. endif 17. LUBound(P,W,cap,prof,N,i+1,Pvl,Pvu); 18. if Pvu>CL then //右儿子会活 19. NewNode(E,i+1,0,cap,prof,Pvu); CL=max(CL,Pvl-ε); 20. endif 21. endcase 22. if 不再有活结点 then exit endif 23. Largest(E)；//取下一个扩展结点 24. until UB(E)≤ CL; endloop 25. Finish(CL,ANS,N); 26. end LCKNAP 算法中有两点值得注意： (1).第6～24行的循环依次检查所生成 的每个结点。此循环在以下两种情况下终止：或者不再剩有活结点， 或者为了扩展而选择的结点 E（扩展结点）满足UB(E) ≤ CL.在后一种 情况下，由扩展结点的选法可知，对所有的扩展结点 X 均有 UB(X) ≤ UB(E) ≤ CL，因而它们都不能导致其值比 CL 更大的解。(2).在左儿 子 X 可行的情况下，由 LUBound 算出它的上界，并由此而得 UB(X)=UB(E).因为UB(E)>CL或者CL=Pvu- ε<Pvu，所以将 X加入活结 点表。由于左儿子的下界、上界与E 的相同，因而不必再计算。但是 右儿子则不同，所以需要调用函数 LUBound 来获取 UB(Y)=Pvu.如果 Pvu≤CL,则杀死结点Y。否则，将结点Y 加入活结点表，并修改 CL 的 值（第19 行） 。以下附上前面提到的几个子程序。 计算结点状态下的可能取得最大效益值的上、下界 LUBound(P,W,rw,cp,N,k,Pvl,Pvu)//rw 是背包的剩余容量， cp是已 //取得的效益值，还有物品k,…,N 要考虑 Pvl=cp; c=rw; for i from k to N do if c<W[i] then Pvu=Pvl+c*P[i]/W[i]; for j from i+1 to N do if c≥W[j] then c=c-W[j]; Pvl=Pvl+P[j]; endif endfor return endif c=c-W[i]; Pvl=Pvl+P[i]; endfor Pvu=Pvl; end LUBound 生成新结点算法 NewNode(par,lev,t,cap,prof,ub)//生成一个新结点J，并把它加到 //活结点表 GetNode(J); Parent(J)=par;Level(J)=lev;Tag(J)=t; Cu(J)=cap; Cv(J)=prof; UB(J)=ub; Add(J); end NewNode 打印答案程序 Finish(CL,ANS,N)//输出解 real CL; global Tag,Parent; print(‘OBJECTS IN KNAPSACK ARE’) for j from N by –1 to 1 do if Tag(ANS)=1 then print(j); endif ANS=Parent(ANS); endfor end Finish §4. 电路板布线问题 印刷电路板将布线区域分成 n×m 个方格阵列，如下图(a).精确的电 路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方 案。在布线时，电路只能沿直线或直角布线，如 下图(b)所示。为了 避免线路相交，已布了线的方格做了封锁标记，其它线路不允许穿过 被封锁的方格。 图(a) 图(b) 我们采用队列式分枝限界法解此问题，它的解空间树是图。首先结点 a作为第一个扩展结点。与该扩展结点相邻并且可以可达的方格成为 可行结点被加入到活结点队列，这些结点被加入队列的顺序是：右、 下、左、上。将这些方格标记为1，它表示从起始方格 a 到这些方格 的距离为1。 接着从活结点队列中取出队首结点作为下一个扩展结点， 并将与当前结点相邻且未标记过的方格标记 未 2，并以右、下、左、 上的顺序将这些结点存放到活结点队列中。 这个过程一直持续到算法 搜索到目标方格b 或者活结点队列为空时停止。注意到，搜索过程在 遇到标记封锁的方格时，自动放弃此方格。下图是在 7×7 方格阵列 中布线的例子。 其中， 起始点的位置是a=(3,2)， 目标是位置b=(4,6). 有！号的方格表示被封锁。搜索过程如下图(c)所示。 a b 3 2 !！ 2 1 !！ !！ 1 a 1 2 !! 2 1 2 !! !! b !! 2 3 4 !! !! !! !! 5 6 7 8 !! !! !! 6 7 8 图 (c) 图 (d) 本例中，a 到b 的最短距离是9。要构造出与最短距离相应的最短路 径，须从目标方格开始向起始方格回溯，逐步构造出最优解。每次向 比当前方格标号少 1的相邻方格移动， 直至到达起始方格为止。 图(d) 给出了该例子的最短路径，它是从目标方格 b 移动到(5,6)，然后移 至(6,6)，…,最终移至起始方格a。 在算法实现时，首先定义一个表示电路板上方格位置的类 Position，它有两个私有成员row 和 col，分别表示方格所在的行和 列。在电路板的任一方格处，布线可沿右、下、左、上四个方向进行， 分别记为移动 0，1，2，3。offs et[i].col=1 表示向右前进一步； offset[i].col=-1 表示向左前进一步。在这两种情况下，都有， offset[i].row=0。类似地讨论向下和向上前进的情况。 一般用一个二维数组 grid 表示所给的方格阵列。初始时， grid[i][j]=0,表示该方格允许布线， 而grid[i][j]=1表示该方格不 允许布线（有封锁标记） 。为了便于处理边界方格的情况，算法对所 给的方格阵列的四周设置一道“围墙” ，即增设标记为1 的附加方格。 算法开始时测试初始方格与目标方格是否相同。 若相同， 则不必计算， 直接返回最短距离 0。否则，算法设置方格阵列的围墙，初始化位移 !！ !！ !！ a !! !! !! b !! !! !! !! !! !! !! !! 矩阵offset。算法将起始位置的距离记为2。因为数字 0和1用于表 示方格的开放或封闭状态，所以，表示距离不用这两个数字，因而将 所有的距离值都加 2。实际距离应为 标记距离减 2。算法从起始位置 start开始， 首先标记所有标记距离为3的方格， 并存入活结点队列， 然后依次标记所有标记距离为4，5，… 的方格，直至到达目标方格 finish 或活结点队列为空时为止。 布线问题的队列式分枝限界算法 bool FindPath(Position start,Position finish,int& PathLen, Position * &path) {//计算从起点位置start到目标位置finish的最短布线路径， 找到 //最短布线路径则返回true，否则返回false if((start.row==finish.row) && (start.col==finish.col) {PathLen=0; return true;} //start=finish //设置方格阵列“围墙” for(int I=0; I<= m+1; I++) grid[0][I]=grid[n+1][I]=1; //顶部和底部 for(int I=0; I<= n+1; I++) gridi][0]=grid[i][m+1]=1; //左翼和右翼 //初始化相对位移 Position offset[4]; offset[0].row=0; offset[0].col=1;//右 offset[1].row=1; offset[1].col=0;//下 offset[2].row=0; offset[2].col=-1;//左 offset[3].row=-1; offset[3].col=0;//上 int NumOfNbrs=4;//相邻方格数 Position here,nbr; Here.row=start.row; Here.col=start.col; Grid[start.row][start.col]=2; //标记可达方格位置 LinkedQueue<Position> Q; Do {//标记相邻可达方格 For(int I=0; I<NumOfNbrs; I++){ Nbr.row=here.row + offset[I].row; Nbr.col=here.col+offset[I].col; If(grid[nbr.row][nbr.col]==0){ //该方格未被标记 grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; if((nbr.row==finish.row) && (nbr.col==finish.col)) break; //完成布线 Q.Add(nbr);} } //是否到达目标位置finish？ If((nbr.row==finish.row) (nbr.col==finish.col)) break;//完成布线 //活结点队列是否非空？ If(Q.IsEmpty()) return false;//无解 Q.Delete(here);//取下一个扩展结点 }while(true); //构造最短布线路径 PathLen=grid[finish.row][finish.col]-2; path=new Position[PathLen]; //从目标位置finish 开始向起始位置回溯 here=finish; for(int j=PathLen-1; j>=0; j--){ path[j]=here; //找前驱位置 for(int I=0; I<NumOfNbrs; I++){ nbr.row=here.row+offset[I].row; nbr.col=here.col+offset[I]; if(grid[nbr.row][nbr.col]==j+2) break; } here=nbr;//向前移动 } return true; } 由于每个方格成为活结点进入活结点队列最多 1 次， 活结点队列 中最多只处理O(mn)个活结点。扩展每个活结点需要O(1)时间，因此 共耗时O(mn)。构造相应的最短距离需要O(L)时间，其中，L是最短 路径的长度。 作业 ：试写出0/1 背包问题的优先队列式分枝限界算法程序，并 找一个物品件数为16 的例子检验程序的运行情况。