0039算法笔记——【分支限界法】电路板排列问题解说.docxVIP

问题描述 ? ? ?将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]? HYPERLINK /liufeng_king/article/details/8952161 \o view plain view plain? HYPERLINK /liufeng_king/article/details/8952161 \o copy 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;??? }??? ?? t