| 首页 >> 网络编程 >> 程序基础 >> 新闻正文 | [字体：大 中 小] [打印文档] [关闭] |
|
|
|
令x 为电路板的一个排列。电路板xi 被放置到机箱的插槽i 中。d e n s i t y(x) 为机箱中任意一对相邻插槽间所连电线数目中的最大值。对于图1 6 - 9中的排列，d e n s i t y为2。有两根电线连接了插槽2和3，插槽4和5，插槽5和6。插槽6和7之间无电线，余下的相邻插槽都只有一根电线。板式机箱被设计成具有相同的相邻插槽间距，因此这个间距决定了机箱的大小。该间距必须保证足够大以便容纳相邻插槽间的连线。因此这个距离（继而机箱的大小）由d e n s i t y(x)决定。 电路板排列问题的目标是找到一种电路板的排列方式，使其有最小的d e n s i t y。既然该问题是一个N P-复杂问题，故它不可能由一个多项式时间的算法来解决，而象回溯这样的搜索方法则是解决该问题的一种较好方法。回溯算法为了找到最优的电路板排列方式，将搜索一个排列空间。 用一个n×m 的整型数组B表示输入，当且仅当Nj 中包含电路板bi 时，B [ i ] [ j ] = 1。令t o t a l [ j ]为Nj 中电路板的数量。对于任意部分的电路板排列x [ 1 : i ]，令n o w [ j ]为既在x [ 1 : i ]中又被包含在Nj 中的电路板的数量。当且仅当n o w [ j ] > 0且n o w [ j ]≠t o t a l [ j ]时，Nj 在插槽i 和i + 1之间有连线。插槽i 和i + 1间的线密度可利用该测试方法计算出来。在插槽k和k + 1 ( 1≤k≤i ) 间的线密度的最大值给出了局部排列的密度。 为了实现电路板排列问题的回溯算法，使用了类B o a r d（见程序1 6 - 1 3）。程序1 6 - 1 4给出了私有方法B e s t O r d e r，程序1 6 - 1 5给出了函数A r r a n g e B o a r d s。ArrangeBoards 返回最优的电路板排列密度，最优的排列由数组bestx 返回。ArrangeBoards 创建类Board 的一个成员x 并初始化与之相关的变量。尤其是total 被初始化以使total[j] 等于Nj 中电路板的数量。now[1:n] 被置为0，与一个空的局部排列相对应。调用x .BestOrder(1,0) 搜索x[1:n] 的排列树，以从密度为0的空排列中找到一个最优的排列。通常，x.BestOrder(i,cd) 寻找最优的局部排列x [ 1 : i - 1 ]，该局部排列密度为c d。函数B e s t O r d e r（见程序1 6 - 1 4）和程序1 6 - 1 2有同样的结构，它也搜索一个排列空间。当i=n 时，表示所有的电路板已被放置且cd 为排列的密度。既然这个算法只寻找那些比当前最优排列还优的排列，所以不必验证cd 是否比beste 要小。当i<n 时，排列还未被完成。x[1:i-1] 定义了当前节点的局部排列，而cd 是它的密度。这个节点的每一个孩子通过在当前排列的末端增加一个电路板而扩充了这个局部排列。对于每一个这样的扩充，新的密度l d被计算，且只有ld<bestd 的节点被搜索，其他的节点和它们的子树不被搜索。在排列树的每一个节点处，函数B e s t O r d e r花费(m)的时间计算每一个孩子节点的密度。所以计算密度的总时间为O (m n! )。此外，产生排列的时间为O (n!) 且更新最优排列的时间为O (m n)。 注意每一个更新至少将b e s t d的值减少1，且最终b e s t d≥0。所以更新的次数是O (m)。B e s t O r d e r的整体复杂性为O (m n! )。 程序16-13 Board的类定义 class Board { friend ArrangeBoards(int**, int, int, int []); p r i v a t e : void BestOrder(int i, int cd); int *x, // 到达当前节点的路径 * b e s t x , // 目前的最优排列 * t o t a l , // total[j] = 带插槽j的板的数目 * n o w, // now[j] = 在含插槽j的部分排列中的板的数目 b e s t d , // bestx的密度 n , / /板的数目 m , // 插槽的数目 * * B ; // 板的二维数组 } ; 程序16-14 搜索排列树 void Board::BestOrder(int i, int cd) {// 按回溯算法搜索排列树 if (i == n) { for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestd = cd;} else // 尝试子树 for (int j = i; j <= n; j++) { // 用x[j] 作为下一块电路板对孩子进行尝试 // 在最后一个插槽更新并计算密度 int ld = 0; for (int k = 1; k <= m; k++) { now[k] += B[x[j]][k]; if (now[k] > 0 && total[k] != now[k]) l d + + ; } // 更新ld 为局部排列的总密度 if (cd > ld) ld = cd; // 仅当子树中包含一个更优的排列时，搜索该子树 if (ld < bestd) {// 移动到孩子 Swap(x[i], x[j]); BestOrder(i+1, ld); Swap(x[i], x[j]);} // 重置 for (k = 1; k <= m; k++) now[k] -= B[x[j]][k]; } } 程序16-15 BestOrder(程序1 6 - 1 4)的预处理代码 int ArrangeBoards(int **B, int n, int m, int bestx[ ]) {// 返回最优密度 // 在b e s t x中返回最优排列 Board X; // 初始化X X.x = new int [n+1]; X.total = new int [m+1]; X.now = new int [m+1]; X.B = B; X.n = n; X.m = m; X.bestx = bestx; X.bestd = m + 1; // 初始化t o t a l和n o w for (int i = 1; i <= m; i++) { X.total[i] = 0; X.now[i] = 0; } // 初始化x并计算t o t a l for (i = 1; i <= n; i++) { X.x[i] = i; for (int j = 1; j <= m; j++) X.total[j] += B[i][j]; } // 寻找最优排列 X . B e s t O r d e r ( 1 , 0 ) ; delete [] X.x; delete [] X.total; delete [] X.now; return X.bestd; |
版权所有