常用算法(五)

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

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的排列。

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