分枝定界算法.txt

分枝定界算法描述

r e t u r n ; }

// 不是叶子, 添加到队列中

QNode<T> *b;

b = new QNode<T>;

b->weight = wt;

b->parent = E;

b->LChild = ch;

Q . A d d ( b ) ;

}

template<class T>

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

{// 返回最优装载值，并在b e s t x中返回最优装载

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

// 初始化层1

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

Q . A d d ( 0 ) ; // 0 代表本层的尾部

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

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

bestw = 0; // 迄今得到的最优值

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

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

r += w[i];

QNode<T> *E = 0, // 当前的E-节点

* b e s t E ; // 目前最优的E-节点

// 搜索子集空间树

while (true) {

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

T wt = Ew + w[i];

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

if (wt > bestw) bestw = wt;

AddLiveNode(Q, wt, i, n, bestw, E, bestE, bestx, true);}

// 检查右孩子

if (Ew + r > bestw) AddLiveNode(Q, Ew, i, n, bestw, E, bestE, bestx, false);

Q . D e l e t e ( E ) ; // 下一个E-节点

if (!E) { // 层的尾部

if (Q.IsEmpty()) break;

Q . A d d ( 0 ) ; // 层尾指针

Q . D e l e t e ( E ) ; // 下一个E-节点

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

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

Ew = E-> w e i g h t ; // 新的E-节点的重量

}

// 沿着从b e s t E到根的路径构造x[ ] ， x [ n ]由A d d L i v e N o d e来设置

for (j = n - 1; j > 0; j--) {

bestx[j] = bestE->LChild; // 从b o o l转换为i n t

bestE = bestE-> p a r e n t ;

}

return bestw;

}

4. 最大收益分枝定界

在对子集树进行最大收益分枝定界搜索时，活节点列表是一个最大优先级队列，其中每个活节点x都有一个相应的重量上限（最大收益）。这个重量上限是节点x 相应的重量加上剩余货箱的总重量，所有的活节点按其重量上限的递减顺序变为E-节点。需要注意的是，如果节点x的重量上限是x . u w e i g h t，则在子树中不可能存在重量超过x.uweight 的节点。另外，当叶节点对应的重量等于它的重量上限时，可以得出结论：在最大收益分枝定界算法中，当某个叶节点成为E-节点并且其他任何活节点都不会帮助我们找到具有更大重量的叶节点时，最优装载的搜索终止。

上述策略可以用两种方法来实现。在第一种方法中，最大优先级队列中的活节点都是互相独立的，因此每个活节点内部必须记录从子集树的根到此节点的路径。一旦找到了最优装载所对应的叶节点，就利用这些路径信息来计算x 值。在第二种方法中，除了把节点加入最大优先队列之外，节点还必须放在另一个独立的树结构中，这个树结构用来表示所生成的子集树的一部分。当找到最大装载之后，就可以沿着路径从叶节点一步一步返回到根，从而计算出x 值。

最大优先队列可用HeapNode 类型的最大堆来表示（见程序1 7 - 5）。uweight 是活节点的重量上限，level 是活节点所在子集树的层， ptr 是指向活节点在子集树中位置的指针。子集树中节点的类型是b b n o d e（见程序1 7 - 5）。节点按u w e i g h t值从最大堆中取出。

程序17-5 bbnode 和HeapNode 类

class bbnode {

p r i v a t e :

bbnode *parent; // 父节点指针

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

} ;

template<class T>

class HeapNode {

p u b l i c :

operator T () const {return uweight;}

p r i v a t e :

bbnode *ptr; // 活节点指针

T uweight; // 活节点的重量上限

int level; // 活节点所在层

} ;

程序1 7 - 6中的函数A d d L i v e N o d e用于把b b n o d e类型的活节点加到子树中，并把H e a p N o d e类型的活节点插入最大堆。A d d L i v e N o d e必须被定义为b b n o d e和H e a p N o d e的友元。

程序17-6

template<class T>

void AddLiveNode(MaxHeap<HeapNode<T> > &H, bbnode *E, T wt, bool ch, int lev)

{// 向最大堆H中增添一个层为l e v上限重量为w t的活节点

// 新节点是E的一个孩子

// 当且仅当新节点是左孩子ch 为t r u e

bbnode *b = new bbnode;

b->parent = E;

b->LChild = ch;

HeapNode<T> N;

N.uweight = wt;

N.level = lev;

N.ptr = b;

H . I n s e r t ( N ) ;

}

template<class T>

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

{// 返回最优装载值，最优装载方案保存于b e s t x

// 使用最大收益分枝定界算法

// 定义一个最多有1 0 0 0个活节点的最大堆

MaxHeap<HeapNode<T> > H(1000);

// 第一剩余重量的数组

// r[j] 为w [ j + 1 : n ]的重量之和

T *r = new T [n+1];

r[n] = 0;

for (int j = n-1; j > 0; j--)

r[j] = r[j+1] + w[j+1];

// 初始化层1

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

bbnode *E = 0; // 当前E-节点

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

// 搜索子集空间树

while (i != n+1) {// 不在叶子上

// 检查E-节点的孩子

if (Ew + w[i] <= c) {// 可行的左孩子

AddLiveNode(H, E, Ew+w[i]+r[i], true, i+1);}

// 右孩子

AddLiveNode(H, E, Ew+r[i], false, i+1);

// 取下一个E-节点

HeapNode<T> N;

H.DeleteMax(N); // 不能为空

i = N.level;

E = N.ptr;

Ew = N.uweight - r[i-1];

}

// 沿着从E-节点E到根的路径构造b e s t x [ ]

for (int j = n; j > 0; j--) {

bestx[j] = E->LChild; // 从b o o l转换为i n t

E = E-> p a r e n t ;

}

return Ew;

}

函数M a x L o a d i n g（见程序1 7 - 6）首先定义了一个容量为1 0 0 0的最大堆，因此，可以用它来解决优先队列中活节点数在任何时候都不超过1 0 0 0的装箱问题。对于更大型的问题，需要一个容量更大的最大堆。接着，函数M a x L o a d i n g初始化剩余重量数组r。第i + 1层的节点（即x [ 1 : i ]的值都已确定）对应的剩余容器总重量可以用如下公式求出：

 r [i]=n ?j=i + 1w[ j ]。

变量E指向子集树中的当前E-节点，Ew 是该节点对应的重量， i 是它所在的层。初始时，根节点是E-节点，因此取i=1, Ew=0。由于没有明确地存储根节点，因此E的初始值取为0。while 循环用于产生当前E-节点的左、右孩子。如果左孩子是可行的（即它的重量没有超出容量），则将它加入到子集树中并作为一个第i + 1层节点加入最大堆中。一个可行的节点的右孩子也被认为是可行的，它总被加入子树及最大堆中。在完成添加操作后，接着从最大堆中取出下一个E-节点。如果没有下一个E-节点，则不存在可行的解。如果下一个E-节点是叶节点（即是一个层为n + 1的节点），则它代表着一个最优的装载，可以沿着从叶到根的路径来确定装载方案。

5. 说明

1) 使用最大堆来表示活节点的最大优先队列时，需要预测这个队列的最大长度（程序1 7 - 6

中是1 0 0 0）。为了避免这种预测，可以使用一个基于指针的最大优先队列来取代基于数组的队列，这种表示方法见9 . 4节的左高树。

2) bestw表示当前所有可行节点的重量的最大值，而优先队列中可能有许多其u w e i g h t不超过b e s t w的活节点，因此这些节点不可能帮助我们找到最优的叶节点，这些节点浪费了珍贵的队列空间，并且它们的插入/删除动作也浪费了时间，所以可以将这些节点删除。有一种策略可以减少这种浪费，即在插入某个节点之前检查是否有u w e i g h t < b e s t w。然而，由于b e s t w在算法执行过程中是不断增大的，所以目前插入的节点在以后并不能保证u w e i g h t < b e s t w。另一种更好的方法是在每次b e s t w增大时，删除队列中所有u w e i g h t < b e s e w的节点。这种策略要求删除具有最小u w e i g h t的节点。因此，队列必须支持如下的操作：插入、删除最大节点、删除最小节点。这种优先队列也被称作双端优先队列（ double-ended priority queue）。这种队列的数据结构描述见第9章的参考文献。

5.2.2  0/1背包问题

0 / 1背包问题的最大收益分枝定界算法可以由程序1 6 - 6发展而来。可以使用程序1 6 - 6的B o u n d函数来计算活节点N的收益上限u p ,使得以N为根的子树中的任一节点的收益值都不可能超过u p r o f i t。活节点的最大堆使用u p r o f i t作为关键值域，最大堆的每个入口都以H e a p N o d e作为其类型，H e a p N o d e有如下私有成员：uprofit, profit, weight，l e v e l，p t r，其中l e v e l和p t r的定义与装箱问题（见程序1 7 - 5）中的含义相同。对任一节点N，N . p r o f i t是N的收益值，N uprofit是它的收益上限， N. weight 是它对应的重量。b b n o d e类型如程序1 7 - 5中的定义，各节点按其u p r o f i t值从最大堆中取出。

程序1 7 - 7使用了类Knap, 它类似于回溯法中的类K n a p（见程序1 6 - 5）。两个K n a p版本中数据成员之间的区别见程序1 7 - 7：1) bestp 不再是一个成员； 2) bestx 是一个指向int 的新成员。新增成员的作用是：当且仅当物品j 包含在最优解中时， b e s t x [ j ] = 1。函数A d d L i v e N o d e用于将新的b b n o d e类型的活节点插入子集树中，同时将H e a p N o d e类型的活节点插入到最大堆中。这个函数与装箱问题（见程序1 7 - 6）中的对应函数非常类似，因此相应的代码被省略。

程序17-7 0/1背包问题的最大收益分枝定界算法

template<class Tw, class Tp>

Tp Knap<Tw, Tp>::MaxProfitKnapsack()

{// 返回背包最优装载的收益

// bestx[i] = 1 当且仅当物品i 属于最优装载

// 使用最大收益分枝定界算法

// 定义一个最多可容纳1 0 0 0个活节点的最大堆

H = new MaxHeap<HeapNode<Tp, Tw> > (1000);