电路板排列问题（ 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
// 初始化第一个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 < bestx =" E.x;" bestd =" max(ld," i =" E.s" now =" new" j =" 1;" ld =" 0;" j =" 1;"> 0 &&amp; total[j] != N.now[j]) ld++;
N.cd = max(ld, E.cd);
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的排列。
没有评论:
发表评论