常用算法(五)

文章作者：午夜晨光
责任编辑：　录入时间：2004-10-04 19:22:05 来源：第七频道
频道声明：本频道的文章除部分特别声明禁止转载的专稿外，可以自由转载.但请务必注明出出处和原始作者文章版权归本频道与文章作者所有.对于被频道转载文章的个人和网站,我们表示深深的谢意.

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++;

此新闻共有10页第 1 2 3 4 5 6 7 8 9 10 页