0039算法笔记——【分支限界法】电路板排列问题程序.docx

问题描述? ? ?将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)当sn-1时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的密度node.cd。当node.cdbestd时，将该儿子结点N插入到活结点优先队列中。? ? ?算法具体实现如下：? ? 1、MinHeap2.h[cpp]?view plain?copy#include?iostream????templateclass?Type??class?Graph;????templateclass?T???class?MinHeap???{???????templateclass?Type??????friend?class?Graph;??????public:???????????MinHeap(int?maxheapsize?=?10);???????????~MinHeap(){delete?[]heap;}?????????????int?Size()?const{return?currentsize;}???????????T?Max(){if(currentsize)?return?heap[1];}?????????????MinHeapT?Insert(const?T?x);???????????MinHeapT?DeleteMin(T?x);?????????????void?Initialize(T?x[],?int?size,?int?ArraySize);???????????void?Deactivate();???????????void?output(T?a[],int?n);??????private:???????????int?currentsize,?maxsize;???????????T?*heap;???};?????template?class?T???void?MinHeapT::output(T?a[],int?n)???{???????for(int?i?=?1;?i?=?n;?i++)???????cout??a[i]???;???????cout??endl;???}?????template?class?T???MinHeapT::MinHeap(int?maxheapsize)???{???????maxsize?=?maxheapsize;???????heap?=?new?T[maxsize?+?1];???????currentsize?=?0;???}?????templateclass?T???MinHeap