分枝定界算法.txt

分枝定界算法描述

第 5 章 分枝定界

 

任何美好的事情都有结束的时候。现在我们学习的是本书的最后一章。幸运的是，本章用到的大部分概念在前面各章中已作了介绍。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间（常用的树结构是第1 6章所介绍的子集树和排列树）。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。

 

5.1 算法思想

 

分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。

有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：

1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。

2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。

例5-1 [迷宫老鼠] 考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。使用F I F O分枝定界，初始时取（1，1）作为E-节点且活动队列为空。迷宫的位置（ 1 , 1）被置为1，以免再次返回到这个位置。（1，1）被扩充，它的相邻节点（ 1，2）和（2，1）加入到队列中（即活节点表）。为避免再次回到这两个位置，将位置（ 1，2）和（2，1）置为1。此时迷宫如图1 7 - 1 a所示，E-节点（1，1）被删除。

节点（1，2）从队列中移出并被扩充。检查它的三个相邻节点（见图1 6 - 1的解空间），只有（1，3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫位置置为1，所得到的迷宫状态如图17-1b 所示。节点（1，2）被删除，而下一个E-节点（2，1）将会被取出，当此节点被展开时，节点（3，1）被加入队列中，节点（3，1）被置为1，节点（2，1）被删除，所得到的迷宫如图17-1c 所示。此时队列中包含（1，3）和（3，1）两个节点。随后节点（1，3）变成下一个E-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，节点（3，1）成为新的E-节点，将队列清空。节点（ 3，1）展开，（3，2）被加入队列中，而（3，1）被删除。（3，2）变为新的E-节点，展开此节点后，到达节点（3，3），即迷宫的出口。

使用F I F O搜索，总能找出从迷宫入口到出口的最短路径。需要注意的是：利用回溯法找到的路径却不一定是最短路径。有趣的是，程序6 - 11已经给出了利用F I F O分枝定界搜索从迷宫的（1，1）位置到（n，n） 位置的最短路径的代码。

例5-2 [0/1背包问题] 下面比较分别利用F I F O分枝定界和最大收益分枝定界方法来解决如下背包问题：n=3, w=[20,15,15], p=[40,25,25], c= 3 0。F I F O分枝定界利用一个队列来记录活节点，节点将按照F I F O顺序从队列中取出；而最大收益分枝定界使用一个最大堆，其中的E-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。本例所使用的背包问题与例1 6 . 2相同，并且有相同的解空间树。

使用F I F O分枝定界法搜索，初始时以根节点A作为E-节点，此时活节点队列为空。当节点

A展开时，生成了节点B和C，由于这两个节点都是可行的，因此都被加入活节点队列中，节点A被删除。下一个E-节点是B，展开它并产生了节点D和E，D是不可行的，被删除，而E被加入队列中。下一步节点C成为E-节点，它展开后生成节点F和G，两者都是可行节点，加入队列中。下一个E-节点E生成节点J和K，J不可行而被删除，K是一个可行的叶节点，并产生一个到目前为止可行的解，它的收益值为4 0。

下一个E-节点是F，它产生两个孩子L、M，L代表一个可行的解且其收益值为5 0，M代表另一个收益值为1 5的可行解。G是最后一个E-节点，它的孩子N和O都是可行的。由于活节点队列变为空，因此搜索过程终止，最佳解的收益值为5 0。

可以看到，工作在解空间树上的F I F O分枝定界方法非常象从根节点出发的宽度优先搜索。它们的主要区别是在F I F O分枝定界中不可行的节点不会被搜索。最大收益分枝定界算法以解空间树中的节点A作为初始节点。展开初始节点得到节点B和C，两者都是可行的并被插入堆中，节点B获得的收益值是4 0（设x1 = 1），而节点C得到的收益值为0。A被删除，B成为下一个E-节点，因为它的收益值比C的大。当展开B时得到了节点D和E，D是不可行的而被删除，E加入堆中。由于E具有收益值4 0，而C为0，因为E成为下一个E-节点。

展开E时生成节点J和K，J不可行而被删除，K是一个可行的解，因此K为作为目前能找到的最优解而记录下来，然后K被删除。由于只剩下一个活节点C在堆中，因此C作为E-节点被展开，生成F、G两个节点插入堆中。F的收益值为2 5，因此成为下一个E-节点，展开后得到节点L和M，但L、M都被删除，因为它们是叶节点，同时L所对应的解被作为当前最优解记录下来。最终，G成为E-节点，生成的节点为N和O，两者都是叶节点而被删除，两者所对应的解都不比当前的最优解更好，因此最优解保持不变。此时堆变为空，没有下一个E-节点产生，搜索过程终止。终止于J的搜索即为最优解。

犹如在回溯方法中一样，可利用一个定界函数来加速最优解的搜索过程。定界函数为最大收益设置了一个上限，通过展开一个特殊的节点可能获得这个最大收益。如果一个节点的定界函数值不大于目前最优解的收益值，则此节点会被删除而不作展开，更进一步，在最大收益分枝定界方法中，可以使节点按照它们收益的定界函数值的非升序从堆中取出，而不是按照节点的实际收益值来取出。这种策略从可能到达一个好的叶节点的活节点出发，而不是从目前具有较大收益值的节点出发。

例5-3 [旅行商问题] 对于图1 6 - 4的四城市旅行商问题，其对应的解空间为图1 6 - 5所示的排列树。F I F O分枝定界使用节点B作为初始的E-节点，活节点队列初始为空。当B展开时，生成节点C、D和E。由于从顶点1到顶点2，3，4都有边相连，所以C、D、E三个节点都是可行的并加入队列中。当前的E-节点B被删除，新的E-节点是队列中的第一个节点，即节点C。因为在图1 6 - 4中存在从顶点2到顶点3和4的边，因此展开C，生成节点F和G，两者都被加入队列。下一步，D成为E-节点，接着又是E，到目前为止活节点队列中包含节点F到K。下一个E-节点是F，展开它得到了叶节点L。至此找到了一个旅行路径，它的开销是5 9。展开下一个E-节点G，得到叶节点M，它对应于一个开销为6 6的旅行路径。接着H成为E-节点，从而找到叶节点N，对应开销为2 5的旅行路径。下一个E-节点是I，它对应的部分旅行1 - 3 - 4的开销已经为2 6，超过了目前最优的旅行路径，因此， I不会被展开。最后，节点J，K成为E-节点并被展开。经过这些展开过程，队列变为空，算法结束。找到的最优方案是节点N所对应的旅行路径。

如果不使用F I F O方法，还可以使用最小耗费方法来搜索解空间树，即用一个最小堆来存储活节点。这种方法同样从节点B开始搜索，并使用一个空的活节点列表。当节点B展开时，生成节点C、D和E并将它们加入最小堆中。在最小堆的节点中， E具有最小耗费（因为1 - 4的局部旅行的耗费是4），因此成为E-节点。展开E生成节点J和K并将它们加入最小堆，这两个节点的耗费分别为1 4和2 4。此时，在所有最小堆的节点中，D具有最小耗费，因而成为E-节点，并生成节点H和I。至此，最小堆中包含节点C、H、I、J和K，H具有最小耗费，因此H成为下一个E-节点。展开节点E，得到一个完整的旅行路径1 - 3 - 2 - 4 - 1，它的开销是2 5。节点J是下一个E-节点，展开它得到节点P，它对应于一个耗费为2 5的旅行路径。节点K和I是下两个E-节点。由于I的开销超过了当前最优的旅行路径，因此搜索结束，而剩下的所有活节点都不能使我们找到更优的解。

对于例5 - 2的背包问题，可以使用一个定界函数来减少生成和展开的节点数量。这种函数将确定旅行的最小耗费的下限，这个下限可通过展开某个特定的节点而得到。如果一个节点的定界函数值不能比当前的最优旅行更小，则它将被删除而不被展开。另外，对于最小耗费分枝定界，节点按照它在最小堆中的非降序取出。

在以上几个例子中，可以利用定界函数来降低所产生的树型解空间的节点数目。当设计定界函数时，必须记住主要目的是利用最少的时间，在内存允许的范围内去解决问题。而通过产生具有最少节点的树来解决问题并不是根本的目标。因此，我们需要的是一个能够有效地减少计算时间并因此而使产生的节点数目也减少的定界函数。

回溯法比分枝定界在占用内存方面具有优势。回溯法占用的内存是O（解空间的最大路径长度），而分枝定界所占用的内存为O（解空间大小）。对于一个子集空间，回溯法需要(n)的内存空间，而分枝定界则需要O ( 2n ) 的空间。对于排列空间，回溯需要(n) 的内存空间，分枝定界需要O (n!) 的空间。虽然最大收益（或最小耗费）分枝定界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的节点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。

练习

1. 假定在一个L I F O分枝定界搜索中，活节点列表的行为与堆栈相同，请使用这种方法来解决例5 - 2的背包问题。L I F O分枝定界与回溯有何区别？

2. 对于如下0 / 1背包问题：n=4, p=[4,3,2,1], w=[1,2,3,4], c =6。

1) 画出有四个对象的背包问题的解空间树。

2) 像例1 7 - 2那样，描述用F I F O分枝定界法解决上述问题的过程。

3) 使用程序1 6 - 6的B o u n d函数来计算子树上任一叶节点可能获得的最大收益值，并根据每一步所能得到的最优解对应的定界函数值来判断是否将节点加入活节点列表中。解空间中哪些节点是使用以上机制的F I F O分枝定界方法产生的？

4) 像例1 7 - 2那样，描述用最大收益分枝定界法解决上述问题的过程。

5) 在最大收益分枝定界中，若使用3）中的定界函数，将产生解空间树中的哪些节点？

 

5.2 应用

 

5.2.1 货箱装船

1. FIFO分枝定界

4 . 2 . 1节的货箱装船问题主要是寻找第一条船的最大装载方案。这个问题是一个子集选择

问题，它的解空间被组织成一个子集树。对程序1 6 - 1进行改造，即得到程序1 7 - 1中的F I F O分枝定界代码。程序1 7 - 1只是寻找最大装载的重量。

程序17-1 货箱装船问题的F I F O分枝定界算法

template<class T>

void AddLiveNode(LinkedQueue<T> &Q, T wt,

T& bestw, int i, int n)

{// 如果不是叶节点，则将节点权值w t加入队列Q

if (i == n) {// 叶子

if (wt > bestw) bestw = wt;}

else Q.Add(wt); // 不是叶子

}

template<class T>

T MaxLoading(T w[], T c, int n)

{// 返回最优装载值

// 使用F I F O分枝定界算法

// 为层次1 初始化

LinkedQueue<T> Q; // 活节点队列

Q.Add(-1); //标记本层的尾部

int i = 1; // E-节点的层

T Ew = 0, // E-节点的权值

bestw = 0; // 目前的最优值

// 搜索子集空间树

while (true) {

// 检查E-节点的左孩子

if (Ew + w[i] <= c) // x[i] = 1

AddLiveNode(Q, Ew + w[i], bestw, i, n);

// 右孩子总是可行的

AddLiveNode(Q, Ew, bestw, i, n); // x[i] = 0

Q.Delete(Ew); // 取下一个E-节点

if (Ew == -1) { // 到达层的尾部

if (Q.IsEmpty()) return bestw;

Q.Add(-1); //添加尾部标记

Q.Delete(Ew); // 取下一个E-节点

i++;} // Ew的层

}

}

其中函数MaxLoading 在解空间树中进行分枝定界搜索。链表队列Q用于保存活节点，其中记录着各活节点对应的权值。队列还记录了权值- 1，以标识每一层的活节点的结尾。函数AddLiveNode 用于增加节点（即把节点对应的权值加入活节点队列），该函数首先检验i（当前E-节点在解空间树中的层）是否等于n，如果相等，则已到达了叶节点。叶节点不被加入队列中，因为它们不被展开。搜索中所到达的每个叶节点都对应着一个可行的解，而每个解都会与目前的最优解来比较，以确定最优解。如果i＜n，则节点i 就会被加入队列中。

M a x L o a d i n g函数首先初始化i = 1（因为当前E-节点是根节点），b e s t w = 0（目前最优解的对应值），此时，活节点队列为空。下一步， A - 1被加入队列以说明正处在第一层的末尾。当前E-节点对应的权值为Ew。在while 循环中，首先检查节点的左孩子是否可行。如果可行，则调用A d d L i v e N o d e，然后将右孩子加入队列（此节点必定是可行的），注意到A d d l i v e N o d e可能会失败，因为可能没有足够的内存来给队列增加节点。A d d L i v e N o d e并没有去捕获Q . A d d中的N o M e m异常，这项工作留给用户完成。

如果E-节点的两个孩子都已经被生成，则删除该E-节点。从队列中取出下一个E-节点，此时队列必不为空，因为队列中至少含有本层末尾的标识- 1。如果到达了某一层的结尾，则从下一层寻找活节点，当且仅当队列不为空时这些节点存在。当下一层存在活节点时，向队列中加入下一层的结尾标志并开始处理下一层的活节点。

M a x L o a d i n g函数的时间和空间复杂性都是O ( 2n )。

2. 改进

我们可以尝试使用程序1 6 - 2的优化方法改进上述问题的求解过程。在程序1 6 - 2中，只有当右孩子对应的重量加上剩余货箱的重量超出b e s t w时，才选择右孩子。而在程序1 7 - 1中，在i变为n之前，b e s t w的值一直保持不变，因此在i等于n之前对右孩子的测试总能成功，因为b e s t w = 0且r > 0。当i等于n时，不会再有节点加入队列中，因此这时对右孩子的测试不再有效。

如想要使右孩子的测试仍然有效，应当提早改变b e s t w的值。我们知道，最优装载的重量是子集树中可行节点的重量的最大值。由于仅在向左子树移动时这些重量才会增大，因此可以在每次进行这种移动时改变b e s t w的值。根据以上思想，我们设计了程序1 7 - 2。当活节点加入队列时，w t不会超过b e s t w，故b e s t w不用更新。因此用一条直接插入M a x L o a d i n g的简单语句取代了函数A d d L i v e N o d e。

程序17-2 对程序1 7 - 1改进之后

template<class T>

T MaxLoading(T w[], T c, int n)

{// 返回最优装载值

// 使用F I F O分枝定界算法

// 为层1初始化

LinkedQueue<T> Q; // 活节点队列

Q . A d d ( - 1 ) ; / /标记本层的尾部

int i = 1; // E-节点的层

T Ew = 0, // E-节点的重量

bestw = 0; // 目前的最优值

r = 0; // E-节点中余下的重量

for (int j = 2; j <= n; j++)

r += w[i];

// 搜索子集空间树

while (true) {

// 检查E-节点的左孩子

T wt = Ew + w[i]; // 左孩子的权值

if (wt <= c) { // 可行的左孩子

if (wt > bestw) bestw = wt;

// 若不是叶子，则添加到队列中

if (i < n) Q.Add(wt);}

// 检查右孩子

if (Ew + r > bestw && i < n)

Q.Add(Ew); // 可以有一个更好的叶子

Q.Delete(Ew); // 取下一个E-节点

if (Ew == -1) { // 到达层的尾部

if (Q.IsEmpty()) return bestw;

Q.Add(-1); //添加尾部标记

Q.Delete(Ew); // 取下一个E-节点

i++; // E-节点的层

r -= w[i];} // E-节点中余下的重量

}

}

3. 寻找最优子集

为了找到最优子集，需要记录从每个活节点到达根的路径，因此在找到最优装载所对应的叶节点之后，就可以利用所记录的路径返回到根节点来设置x的值。活节点队列中元素的类型是Q N o d e (见程序1 7 - 3 )。这里，当且仅当节点是它的父节点的左孩子时， L C h i l d为t r u e。

程序17-3 类Q N o d e

template<class T>

class QNode {

p r i v a t e :

QNode *parent; // 父节点指针

bool LChild; // 当且仅当是父节点的左孩子时，取值为t r u e

T weight; // 由到达本节点的路径所定义的部分解的值

} ;

程序1 7 - 4是新的分枝定界方法的代码。为了避免使用大量的参数来调用A d d L i v e N o d e，可以把该函数定义为一个内部函数。使用内部函数会使空间需求稍有增加。此外，还可以把A d d L i v e N o d e和M a x L o a d i n g定义成类成员函数，这样，它们就可以共享诸如Q , i , n , b e s t w, E , b e s t E和bestw 等类成员。

程序1 7 - 4并未删除类型为Q N o d e的节点。为了删除这些节点，可以保存由A d d L i v e N o d e创建的所有节点的指针，以便在程序结束时删除这些节点。

程序17-4 计算最优子集的分枝定界算法

template<class T>

void AddLiveNode(LinkedQueue<QNode<T>*> &Q, T wt, int i, int n, T bestw, QNode<T> *E,

QNode<T> *&bestE, int bestx[], bool ch)

{// 如果不是叶节点，则向队列Q中添加一个i 层、重量为w t的活节点

// 新节点是E的一个孩子。当且仅当新节点是左孩子时， c h为t r u e。

// 若是叶子，则c h取值为b e s t x [ n ]

if (i == n) {// 叶子

if (wt == bestw) {

// 目前的最优解

bestE = E;

bestx[n] = ch;}