问题描述将n块电路板以最佳排列方式插入带有n个插槽的机箱中。

n块电路板的不同排列方式对应于不同的电路板插入方案。

设B={1, 2, …, n}是n块电路板的集合，L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。

Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。

设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。

x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。

例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中两个可能的排列如图所示，则该电路板排列的密度分别是2，3。

左上图中，跨越插槽2和3,4和5，以及插槽5和6的连线数均为2。

插槽6和7之间无跨越连线。

其余插槽之间只有1条跨越连线。

在设计机箱时，插槽一侧的布线间隙由电路板的排列的密度确定。

因此，电路板排列问题要求对于给定的电路板连接条件(连接块)，确定电路板的最佳排列，使其具有最小密度。

算法思路电路板排列问题的解空间是一颗排列树。

采用优先队列式分支限界法找出所给电路板的最小密度布局。

算法中采用最小堆表示活节点优先级队列。

最小堆中元素类型是BoradNode，每一个BoardNode类型的节点包含域x，表示节点所相应的电路板排列；s表示该节点已确定的电路板排列x[1:s]；cd表示当前密度，now[j]表示x[1:s]中所含连接块j中的电路板数。

算法开始时，将排列树的根结点置为当前扩展结点。

在do-while循环体内算法依次从活结点优先队列中取出具有最小cd值的结点作为当前扩展结点，并加以扩展。

算法将当前扩展节点分两种情形处理：1)首先考虑s=n-1的情形，当前扩展结点是排列树中的一个叶结点的父结点。

x表示相应于该叶结点的电路板排列。

计算出与x相应的密度并在必要时更新当前最优值和相应的当前最优解。

2)当s<n-1时，算法依次产生当前扩展结点的所有儿子结点。

对于当前扩展结点的每一个儿子结点node，计算出其相应的密度node.cd。

当node.cd<bestd时，将该儿子结点N插入到活结点优先队列中。

算法具体实现如下：1、MinHeap2.h[cpp]view plain copy1.#include <iostream>2.3.template<class Type>4.class Graph;5.6.template<class T>7.class MinHeap8.{9.template<class Type>10.friend class Graph;11.public:12. MinHeap(int maxheapsize = 10);13. ~MinHeap(){delete []heap;}14.15.int Size() const{return currentsize;}16. T Max(){if(currentsize) return heap[1];}18. MinHeap<T>& Insert(const T& x);19. MinHeap<T>& DeleteMin(T &x);20.21.void Initialize(T x[], int size, int ArraySize);22.void Deactivate();23.void output(T a[],int n);24.private:25.int currentsize, maxsize;26. T *heap;27.};28.29.template <class T>30.void MinHeap<T>::output(T a[],int n)31.{32.for(int i = 1; i <= n; i++)33. cout << a[i] << " ";34. cout << endl;35.}36.37.template <class T>38.MinHeap<T>::MinHeap(int maxheapsize)39.{40. maxsize = maxheapsize;41. heap = new T[maxsize + 1];42. currentsize = 0;43.}44.45.template<class T>46.MinHeap<T>& MinHeap<T>::Insert(const T& x)47.{48.if(currentsize == maxsize)49. {50.return *this;51. }52.int i = ++currentsize;53.while(i != 1 && x < heap[i/2])54. {55. heap[i] = heap[i/2];56. i /= 2;57. }58.59. heap[i] = x;60.return *this;62.63.template<class T>64.MinHeap<T>& MinHeap<T>::DeleteMin(T& x)65.{66.if(currentsize == 0)67. {68. cout<<"Empty heap!"<<endl;69.return *this;70. }71.72. x = heap[1];73.74. T y = heap[currentsize--];75.int i = 1, ci = 2;76.while(ci <= currentsize)77. {78.if(ci < currentsize && heap[ci] > heap[ci + 1])79. {80. ci++;81. }82.83.if(y <= heap[ci])84. {85.break;86. }87. heap[i] = heap[ci];88. i = ci;89. ci *= 2;90. }91.92. heap[i] = y;93.return *this;94.}95.96.template<class T>97.void MinHeap<T>::Initialize(T x[], int size, int ArraySize)98.{99.delete []heap;100. heap = x;101. currentsize = size;102. maxsize = ArraySize;103.104.for(int i = currentsize / 2; i >= 1; i--)105. {106. T y = heap[i];107.int c = 2 * i;108.while(c <= currentsize)109. {110.if(c < currentsize && heap[c] > heap[c + 1]) 111. c++;112.if(y <= heap[c])113.break;114. heap[c / 2] = heap[c];115. c *= 2;116. }117. heap[c / 2] = y;118. }119.}120.121.template<class T>122.void MinHeap<T>::Deactivate()123.{124. heap = 0;125.}2、6d8.cpp[cpp]view plain copy1.//电路板排列问题优先队列分支限界法求解2.#include "stdafx.h"3.#include "MinHeap2.h"4.#include <iostream>5.#include <fstream>ing namespace std;7.8.ifstream fin("6d8.txt");9.10.class BoardNode11.{12.friend int BBArrangement(int **,int,int,int *&);13.public:14. operator int() const15. {16.return cd;17. }18.private:19.int *x, //x[1:n]记录电路板排列20. s, //x[1:s]是当前节点所相应的部分排列21. cd, //x[1:s]的密度22. *now; //now[j]是x[1:s]所含连接块j中电路板数23.};24.25.int BBArrangement(int **B,int n,int m,int *&bestx);26.27.int main()28.{29.int m = 5,n = 8;30.int *bestx;31.32.//B={1,2,3,4,5,6,7,8}33.//N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}34.35. cout<<"m="<<m<<",n="<<n<<endl;36. cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"<<endl;37. cout<<"二维数组B如下："<<endl;38.39.//构造B40.int **B = new int*[n+1];41.for(int i=1; i<=n; i++)42. {43. B[i] = new int[m+1];44. }45.46.for(int i=1; i<=n; i++)47. {48.for(int j=1; j<=m ;j++)49. {50. fin>>B[i][j];51. cout<<B[i][j]<<" ";52. }53. cout<<endl;54. }55.56. cout<<"当前最优密度为:"<<BBArrangement(B,n,m,bestx)<<endl;57. cout<<"最优排列为："<<endl;58.for(int i=1; i<=n; i++)59. {60. cout<<bestx[i]<<" ";61. }62. cout<<endl;63.64.for(int i=1; i<=n; i++)65. {66.delete[] B[i];67. }68.delete[] B;69.70.return 0;71.}72.73.//解电路板排列问题的优先队列式分支限界法74.int BBArrangement(int **B,int n,int m,int *&bestx)75.{76. MinHeap<BoardNode> H(1000);//活节点最小堆77. BoardNode E;78. E.x = new int[n+1];79. E.s = 0;80. E.cd = 0;81.82. E.now = new int[m+1];83.int *total = new int[m+1];84.//now[i] = x[1:s]所含连接块i中电路板数85.//total[i] = 连接块i中的电路板数86.87.for(int i=1; i<=m; i++)88. {89. total[i] = 0;90. E.now[i] = 0;91. }92.93.for(int i=1; i<=n; i++)94. {95. E.x[i] = i;//初始排列为1,2,3……n96.for(int j=1;j<=m;j++)97. {98. total[j] += B[i][j];//连接块中电路板数99. }100. }101.102.int bestd = m + 1;103. bestx = 0;104.105.do//节点扩展106. {107.if(E.s == n-1)//仅一个儿子节点108. {109.int ld = 0;//最后一块电路板的密度110.for(int j=1; j<=m; j++)111. {112. ld += B[E.x[n]][j];113. }114.if(ld<bestd)//密度更小的电路排列115. {116.delete[] bestx;117. bestx = E.x;118. bestd = max(ld,E.cd);119. }120.else121. {122.delete []E.x;123. }124.delete []E.now;125. }126.else//产生当前扩展节点的所有儿子节点127. {128.for(int i=E.s+1;i<=n;i++)129. {130. BoardNode N;131. N.now = new int[m+1];132.for(int j=1; j<=m; j++)133. {134.//新插入的电路板135. N.now[j] = E.now[j] + B[E.x[i]][j]; 136. }137.int ld = 0;//新插入的电路板密度138.for(int j=1; j<=m; j++)139. {140.if(N.now[j]>0 && total[j]!=N.now[j]) 141. {142. ld++;143. }144. }145. N.cd = max(ld,E.cd);146.if(N.cd<bestd)//可能产生更好的叶子节点147. {148. N.x = new int[n+1];149. N.s = E.s + 1;150.for(int j=1;j<=n;j++)151. {152. N.x[j] = E.x[j];153. }154. N.x[N.s] = E.x[i]; 155. N.x[i] = E.x[N.s]; 156. H.Insert(N);157. }158.else159. {160.delete []N.now; 161. }162. }163.delete []E.x;164. }//完成当前节点扩展165.if(H.Size() == 0)166. {167.return bestd;//无扩展节点168. }169. H.DeleteMin(E);170. }while(E.cd<bestd);171.172.//释放做小堆中所有节点173.do174. {175.delete []E.x;176.delete []E.now;177.if(H.Size() == 0)178. {179.break;180. }181. H.DeleteMin(E);182. }while(true);183.return bestd;184.}程序运行结果如图：。