基于分支界限法的电路板排列问题算法

姓名：邢志强学号：11021213422019年11月12日1.分支限界法的基本思想2.电路板排列问题3.问题分析与算法描述1.分支限界法的基本思想1.1基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。1.分支限界法的基本思想1.2常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。•最大优先队列：使用最大堆，体现最大效益优先•最小优先队列：使用最小堆，体现最小费用优先2.电路板排列问题将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。N2N3N4N1N5板：21345678槽：12345678N2N3N4N1N5板：86123457槽：123456782.电路板排列问题设B={1,2,…,n}是n块电路板的集合，L={N1,N2,…,Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density(x)密度定义为跨越相邻电路板插槽的最大连线数。N2N3N4N1N5板：21345678槽：12345678N2N3N4N1N5板：86123457槽：123456782.电路板排列问题n=8,m=5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};其中一个可能的排列如图所示，则该电路板排列的密度是2N2N3N4N1N5板：21345678槽：12345678N2N3N4N1N5板：86123457槽：123456783.问题分析与算法描述算法开始时，将排列树的根结点置为当前扩展结点。在do-while循环体内算法依次从活结点优先队列中取出具有最小cd值的结点作为当前扩展结点，并加以扩展。首先考虑s=n-1的情形，当前扩展结点是排列树中的一个叶结点的父结点。x表示相应于该叶结点的电路板排列。计算出与x相应的密度并在必要时更新当前最优值和相应的当前最优解。当sn-1时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的密度node.cd。当node.cdbestd时，将该儿子结点N插入到活结点优先队列中。3.1问题分析3.问题分析与算法描述do{//结点扩展if(E.s==n-1){//仅一个儿子结点intld=0;//最后一块电路板的密度for(intj=1;j=m;j++)ld+=B[E.x[n]][j];if(ldbestd){//密度更小的电路板排列delete[]bestx;bestx=E.x;bestd=max(ld,E.cd);}else{//产生当前扩展结点的所有儿子结点for(inti=E.s+1;i=n;i++){BoardNodeN;N.now=newint[m+1];3.2算法描述3.问题分析与算法描述3.2算法描述for(intj=1;j=m;j++)//新插入的电路板N.now[j]=E.now[j]+B[E.x[i]][j];intld=0;//新插入电路板的密度for(intj=1;j=m;j++)if(N.now[j]0&&total[j]!=N.now[j])ld++;N.cd=max(ld,E.cd);if(N.cdbestd){//可能产生更好的叶结点N.x=newint[n+1];N.s=E.s+1;for(intj=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.Insert(N);}elsedelete[]N.now;}delete[]E.x;}