分枝定界算法.txt

分枝定界算法描述

MinHeapNode<T> N;

N.x = new int [n];

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

N.x[j] = E.x[j];

N.x[E.s+1] = E.x[i];

N.x[i] = E.x[E.s+1];

N.cc = cc;

N.s = E.s + 1;

N.lcost = b;

N.rcost = rcost;

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

} // 结束可行的孩子

delete [] E.x;} // 对本节点的处理结束

try {H.DeleteMin(E);} // 取下一个E-节点

catch (OutOfBounds) {break;} // 没有未处理的节点

}

if (bestc == NoEdge) return NoEdge; // 没有旅行路径

// 将最优路径复制到v[1:n] 中

for (i = 0; i < n; i++)

v[i+1] = E.x[i];

while (true) {// 释放最小堆中的所有节点

delete [] E.x;

try {H.DeleteMin(E);}

catch (OutOfBounds) {break;}

}

return bestc;

}

while 循环不断地展开E-节点，直到找到一个叶节点。当s = n - 1时即可说明找到了一个叶节点。旅行路径前缀是x [ 0 : n - 1 ]，这个前缀中包含了有向图中所有的n个顶点。因此s = n - 1的活节点即为一个叶节点。由于算法本身的性质，在叶节点上lcost 和cc 恰好等于叶节点对应的旅行路径的耗费。由于所有剩余的活节点的lcost 值都大于等于从最小堆中取出的第一个叶节点的lcost 值，所以它们并不能帮助我们找到更好的叶节点，因此，当某个叶节点成为E-节点后，搜索过程即终止。

while 循环体被分别按两种情况处理，一种是处理s = n - 2的E-节点，这时，E-节点是某个单独叶节点的父节点。如果这个叶节点对应的是一个可行的旅行路径，并且此旅行路径的耗费小于当前所能找到的最小耗费，则此叶节点被插入最小堆中，否则叶节点被删除，并开始处理下一个E-节点。

其余的E-节点都放在while 循环的第二种情况中处理。首先，为每个E-节点生成它的两个子节点，由于每个E-节点代表着一条可行的路径x [ 0 : s ]，因此当且仅当< x[s],x[i] > 是有向图的边且x [ i ]是路径x [ s + 1 : n - 1 ]上的顶点时，它的子节点可行。对于每个可行的孩子节点，将边<x[s],x[i] > 的耗费加上E.cc 即可得到此孩子节点的路径前缀( x [ 0 : s ]，x[i]) 的耗费c c。由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边，因此任何叶节点对应的耗费都不可能小于cc 加上离开各剩余顶点的出边耗费的最小值之和，因而可以把这个下限值作为E-节点所生成孩子的lcost 值。如果新生成孩子的lcost 值小于目前找到的最优旅行路径的耗费b e s t c，则把新生成的孩子加入活节点队列（即最小堆）中。

如果有向图没有旅行路径，程序1 7 - 9返回N o E d g e；否则，返回最优旅行路径的耗费，而最优旅行路径的顶点序列存储在数组v 中。

5.2.5 电路板排列

电路板排列问题（ 1 6 . 2 . 5节）的解空间是一棵排列树，可以在此树中进行最小耗费分枝定界搜索来找到一个最小密度的电路板排列。我们使用一个最小优先队列，其中元素的类型为B o a r d N o d e，代表活节点。B o a r d N o d e类型的对象包含如下域： x（电路板的排列），s（电路板x[1:s]) 依次放置在位置1 到s 上），c d（电路板排列x [ 1 : s ]的密度，其中包括了到达x[s] 右边的连线），n o w（now[j] 是排列x[1:s] 中包含j 的电路板的数目）。当一个BoardNode 类型的对象转换为整型时，其结果即为对象的cd 值。代码见程序1 7 - 1 0。

程序17-10 电路板排列问题的最小耗费分枝定界算法

int BBArrangeBoards(int **B, int n, int m, int* &bestx)

{// 最小耗费分枝定界算法, m个插槽, n块板

MinHeap<BoardNode> H(1000); // 容纳活节点

// 初始化第一个E节点、t o t a l和b e s t d

BoardNode E;

E.x = new int [n+1];

E.s = 0; // 局部排列为E . x [ 1 : s ]

E.cd = 0; // E.x[1:s]的密度

E.now = new int [m+1];

int *total = new int [m+1];

// now[i] = x[1:s]中含插槽i的板的数目

// total[i] = 含插槽i的板的总数目

for (int i = 1; i <= m; i++) {

total[i] = 0;

E.now[i] = 0;

}

for (i = 1; i <= n; i++) {

E.x[i] = i; // 排列为1 2 3 4 5 . . . n

for (int j = 1; j <= m; j++)

total[j] += B[i][j]; // 含插槽j的板

}

int bestd = m + 1; / /目前的最优密度

bestx = 0; // 空指针

do {// 扩展E节点

if (E.s == n - 1) {// 仅有一个孩子

int ld = 0; // 最后一块板的局部密度

for (int j = 1; j <= m; j++)

ld += B[E.x[n]][j];

if (ld < bestd) {// 更优的排列

delete [] bestx;

bestx = E.x;

bestd = max(ld, E.cd);

}

else delete [] E.x;

delete [] E.now;}

else {// 生成E-节点的孩子

for (int i = E.s + 1; i <= n; i++) {

BoardNode N;

N.now = new int [m+1];

for (int j = 1; j <= m; j++)

// 在新板中对插槽计数

N.now[j] = E.now[j] + B[E.x[i]][j];

int ld = 0; // 新板的局部密度

for (j = 1; j <= m; j++)

if (N.now[j] > 0 && total[j] != N.now[j]) ld++;

N.cd = max(ld, E.cd);

if (N.cd < bestd) {// 可能会引向更好的叶子

N.x = new int [n+1];

N.s = E.s + 1;

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

N.x[j] = E.x[j];

N.x[N.s] = E.x[i];

N.x[i] = E.x[N.s];

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

else delete [] N.now;}

delete [] E.x;} // 处理完当前E-节点

try {H.DeleteMin(E);} // 下一个E-节点

catch (OutOfBounds) {return bestd;} //没有E-节点

} while (E.cd < bestd);

// 释放最小堆中的所有节点

do {delete [] E.x;

delete [] E.now;

try {H.DeleteMin(E);}

catch (...) {break;}

} while (true);

return bestd;

}

程序1 7 - 1 0首先初始化E-节点为排列树的根，此节点中没有任何电路板，因此有s=0, cd=0,n o w [ i ] = 0（1≤i≤n），x是整数1到n 的任意排列。接着，程序生成一个整型数组t o t a l，其中total[i] 的值为包含i 的电路板的数目。目前能找到的最优的电路板排列记录在数组bestx 中，对应的密度存储在bestd 中。程序中使用一个do-while 循环来检查每一个E-节点，在每次循环的尾部，将从最小堆中选出具有最小cd 值的节点作为下一个E-节点。如果某个E-节点的cd 值大于等于bestd，则任何剩余的活节点都不能使我们找到密度小于bestd的电路板排列，因此算法终止。

d o - w h i l e循环分两种情况处理E-节点，第一种是处理s = n - 1时的情况，此种情况下，有n - 1个电路板被放置好， E-节点即解空间树中的某个叶节点的父节点。节点对应的密度会被计算出来，如果需要，bested 和bestx 将被更新。在第二种情况中，E-节点有两个或更多的孩子。每当一个孩子节点N生成时，它对应的部分排列( x [ 1 : s + 1 ] )的密度N . c d就会被计算出来，如果N . c d < b e s t d ,则N被存放在最小优先队列中；如果N . c d≥b e s t d，则它的子树中的所有叶节点对应的密度都满足d e n s i t y≥b e s t d，这就意味着不会有优于b e s t x的排列。

练习

3. 在程序1 7 - 4中增加代码，将指向由函数A d d L i v e N o d e生成的节点的指针存储在一个链表队列中。M a x L o a d i n g必须利用这些指针信息在程序终止之前删除所有生成的节点。

4. 本节所使用的A d d L i v e N o d e函数直到程序终止前才删除所生成的节点。实际上，没有活动孩子且不产生叶节点的那些节点都可以被立即删除。类似地，在第n 层节点中，若节点没有重量为b e s t w的孩子，则可以立即删除该节点。讨论怎样尽快删除不需要的节点。描述实现这种方法时所涉及的时间/空间变化。你推荐使用上述方法吗？

5. 在程序1 7 - 6中，定义一个b e s t w来记录目前生成的可行节点所对应的重量的最大值。修改程序1 7 - 6，使得如果活节点的重量大于等于b e s t w，则将它加入子集树及最大堆中。此外，还必须增加初始化和更新b e s t w的代码。

6. 只使用一个最大优先队列，来实现用最大收益分枝定界方法求解货箱装船问题，即不要使用程序1 7 - 6中所用到的部分解空间树，而在每个优先队列的节点中都加入通向根节点的路径信息。

7. 修改程序1 7 - 6，把删除b b n o d e类型和H e a p N o d e类型节点的任务放在程序结尾处。

8. 只使用一个最大优先队列，利用最大收益分枝定界法求解0 / 1背包问题，即不必保存一个部分解空间树，所有优先队列中的节点都记录着通往根节点的路径。

9. 修改程序1 7 - 7，使得删除b b n o d e和H e a p N o d e类型的节点的任务放在程序的结尾处执行。

10. 1) 程序1 7 - 8中，若右孩子的u n值大于等于b e s t n，则将它加入最大堆中，如果将条件设为u n > b e s t n，程序能否正确执行呢？为什么？

2) 程序是否将u n≥b e s t n的左孩子加入最大堆中？

3) 修改程序，使得只将u n > b e s t n的节点加入到最大堆和生成的解空间树中。

11. 考察最大完备子图问题的解空间树。对于任意层（第i层）的子树中的节点x，令MinDegree(x) 为x 所包含的顶点的度的最小值。

1) 证明任何以x为根的子树的叶节点都不可能表示一个尺寸超过X . u n＝min{ X.cn+n-i+1,M i n D e g r e e (X)+1 }的完备子图。

2) 使用以上X . u n的定义重写B B M a x C l i q u e。

3) 比较两种B B M a x C l i q u e版本在运行时间及产生解空间树节点的数目上的不同。

12. 只使用最大优先队列，实现最大完备子图问题的最大收益分枝定界算法。即：不必保存一个部分解空间树，而在每一个最大优先队的节点内包含通向根的路径。

13. 修改程序1 7 - 8，使得删除b b n o d e和C l i q u e N o d e类型的节点的工作放在程序结尾处执行。

14. 修改程序1 7 - 9，使得s = n - 2的节点不进入优先队列，并且，将当前最优排列放在数组b e s t p中。当下一个E-节点的lcostbestc 时，算法终止。

15. 使用指向父节点的指针来实现部分解空间树，并使用包含l c o s t，c c，r c o s t和p t r（指向解空间树中对应节点的指针）域的优先队列来实现程序1 7 - 9。

16. 写出用F I F O分枝定界方法求解电路板排列问题的代码。代码必须输出最优电路板排列的排列次序及对应的密度。使用合适的数据来测试代码的正确性。

17. 用F I F O分枝定界方法来搜索一种电路板的排列，使得最长的网组的长度最小（参见4章练习1 7）。

18. 使用最小耗费分枝定界法来完成练习1 7。

19. 用最小耗费分枝定界算法求解4章练习1 8的顶点覆盖问题。

20. 用最大收益分枝定界算法求解4章练习1 9的简易最大切割问题。

21. 用最小耗费分枝定界算法求解4章练习2 0的机器设计问题。

22. 用最小耗费分枝定界算法求解4章练习2 1的网络设计问题。

23. 用F I F O分枝定界算法求解4章练习2 2的n -皇后放置问题。

* 24. 用F I F O分枝定界完成4章练习2 3。

* 25. 用F I F O分枝定界完成4章练习2 4。

* 26. 用F I F O分枝定界完成4章练习2 5。

* 27. 用最小耗费分枝定界完成4章练习2 3。

* 28. 用最小耗费分枝定界完成4章练习2 4。

* 29. 用最小耗费分枝定界完成4章练习2 5。

* 30. 用任意的分枝定界方法完成4章的练习2 5。在本练习中，必须把增加活节点的函数以及选择下一个E-节点的函数作为函数的参数。