文档章节

多种算法解决电路板排线问题

潘少online
 潘少online
发布于 2015/05/13 23:12
字数 2885
阅读 78
收藏 0

【回溯法】电路板排列问题

  问题描述:

     n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1, 2, …, n}n 电路板的集合,L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。NiB的一个子集,且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};其中两个可能的排列如图所示,则该电路板排列的密度分别是23



 左上图中,跨越插槽23,45,以及插槽56的连线数均为2。插槽67之间无跨越连线。其余插槽之间只有1条跨越连线。在设计机箱时,插槽一侧的布线间隙由电路板的排列的密度确定。因此,电路板排列问题要求对于给定的电路板连接条件(连接块),确定电路板的最佳排列,使其具有最小密度。

算法设计:

     电路板排列问题是NP难问题,因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树,找出电路板的最佳排列。设用数组B表示输入。B[i][j]的值为1当且仅当电路板i在连接块Nj中。设total[j]是连接块Nj中的电路板数。对于电路板的部分排列x[1:i],设now[j]x[1:i]中所包含的Nj中的电路板数。由此可知,连接块Nj的连线跨越插槽ii+1当且仅当now[j]>0now[j]=total[j]。用这个条件来计算插槽ii+1间的连线密度。

      在算法Backtrach中,当i=n时,所有n块电路板都已排定,其密度为cd。由于算法仅完成那些比当前最优解更好的排列,故cd肯定优于bestd。此时应更新bestd

      i<n时,电路板排列尚未完成。x[1:i-1]是当前扩展结点所相应的部分排列,cd是相应部分排列密度。在当前部分排列之后加入一块未排定的电路板,扩展当前部分排列产生当前结点的一个儿子结点。对于这个儿子结点,计算新的部分排列密度ld。仅当ld<bestd时,算法搜索相应子树,否则该子树被剪去。

按上述回溯搜索策略设计的解电路板排列问题的算法可描述如下:

 
#include "stdafx.h"
#include <iostream>
#include <fstream> 
using namespace std;
 
ifstream fin("5d11.txt"); 
 
class Board
{
       friend int Arrangement(int **B, int n, int m, int bestx[]);
       private:
              void Backtrack(int i,int cd);
              int n,             //电路板数
                     m,          //连接板数
                     *x,         //当前解
                     *bestx,//当前最优解
                     bestd,  //当前最优密度
                     *total, //total[j]=连接块j的电路板数
                     *now,   //now[j]=当前解中所含连接块j的电路板数
                     **B;    //连接块数组
};
 
template <class Type>
inline void Swap(Type &a, Type &b);
 
int Arrangement(int **B, int n, int m, int bestx[]);
 
int main()
{
       int m = 5,n = 8;
       int bestx[9];
 
       //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}
 
       cout<<"m="<<m<<",n="<<n<<endl;
       cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"<<endl;
       cout<<"二维数组B如下:"<<endl;
 
       //构造B
       int **B = new int*[n+1];
       for(int i=1; i<=n; i++)
       {
              B[i] = new int[m+1];
       }
 
       for(int i=1; i<=n; i++)
       {
              for(int j=1; j<=m ;j++)
              {
                     fin>>B[i][j];
                     cout<<B[i][j]<<" ";
              }
              cout<<endl;
       }
 
       cout<<"当前最优密度为:"<<Arrangement(B,n,m,bestx)<<endl;
       cout<<"最优排列为:"<<endl;
       for(int i=1; i<=n; i++)
       {
              cout<<bestx[i]<<" ";
       }
       cout<<endl;
 
       for(int i=1; i<=n; i++)
       {
              delete[] B[i];
       }
       delete[] B;
 
       return 0;
}
 
void Board::Backtrack(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])
                            {
                                   ld ++;
                            }
                     }
 
                     //更新ld
                     if(cd>ld)
                     {
                            ld = cd;
                     }
 
                     if(ld<bestd)//搜索子树
                     {
                            Swap(x[i],x[j]);
                            Backtrack(i+1,ld);
                            Swap(x[i],x[j]);
 
                            //恢复状态
                            for(int k=1; k<=m; k++)
                            {
                                   now[k] -= B[x[j]][k];
                            }
                     }
              }
       }     
}
 
int Arrangement(int **B, int n, int m, int bestx[])
{
       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;
 
       //初始化total和now
       for(int i=1; i<=m; i++)
       {
              X.total[i] = 0;
              X.now[i] = 0;
       }
 
 
       //初始化x为单位排列并计算total
       for(int i=1; i<=n; i++)
       {
              X.x[i] = i;
              for(int j=1; j<=m; j++)
              {
                     X.total[j] += B[i][j];
              }
       }
 
       //回溯搜索
       X.Backtrack(1,0);
       delete []X.x;
       delete []X.total;
       delete []X.now;
       return X.bestd;
}
 
template <class Type>
inline void Swap(Type &a, Type &b)
{  
       Type temp=a; 
       a=b; 
       b=temp;
}

算法效率

    在解空间排列树的每个节点处,算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。另外,生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1,而算法运行结束时bestd>=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。综上,解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。


【分支限界法】电路板排列问题

问题描述

    同上

算法设计

    电路板排列问题的解空间树是一棵排列树。采用优先队列式分支限界法找出所给电路板的最小密度布局。算法中庸最小堆表示活结点优先队列。最小堆中元素类型是BoardNode。每一个BoardNode类型的结点包含域x,表示结点所相应的的电路板排列;s表示该结点已确定的电路板排列x[1:s];cd表示当前密度;now[j]表示x[1:s]中所含连接块j中的电路板数。具体算法描述如下:

class BoardNode
{
      friend int BBArrangement(int **,int,int,int *&);
      public:
           operator int() const
           {
                 return cd;
           }
      private:
           int *x,            //x[1:n]记录电路板排列
                 s,              //x[1:s]是当前节点所相应的部分排列
                 cd,            //x[1:s]的密度
                 *now;       //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插入到活结点优先队列中。

    算法具体实现如下:

MinHeap2.h

#include <iostream>
 
template<class Type>
class Graph;
 
template<class T> 
class MinHeap 
{ 
   template<class Type>
   friend class Graph;
   public: 
       MinHeap(int maxheapsize = 10); 
       ~MinHeap(){delete []heap;} 
 
       int Size() const{return currentsize;} 
       T Max(){if(currentsize) return heap[1];} 
 
       MinHeap<T>& Insert(const T& x); 
       MinHeap<T>& 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 MinHeap<T>::output(T a[],int n) 
{ 
   for(int i = 1; i <= n; i++) 
   cout << a[i] << " "; 
   cout << endl; 
} 
 
template <class T> 
MinHeap<T>::MinHeap(int maxheapsize) 
{ 
   maxsize = maxheapsize; 
   heap = new T[maxsize + 1]; 
   currentsize = 0; 
} 
 
template<class T> 
MinHeap<T>& MinHeap<T>::Insert(const T& x) 
{ 
   if(currentsize == maxsize) 
   { 
       return *this; 
   } 
   int i = ++currentsize; 
   while(i != 1 && x < heap[i/2]) 
   { 
       heap[i] = heap[i/2]; 
       i /= 2; 
   } 
 
   heap[i] = x; 
   return *this; 
} 
 
template<class T> 
MinHeap<T>& MinHeap<T>::DeleteMin(T& x) 
{ 
   if(currentsize == 0) 
   { 
       cout<<"Empty heap!"<<endl; 
       return *this; 
   } 
 
   x = heap[1]; 
 
   T y = heap[currentsize--]; 
   int i = 1, ci = 2; 
   while(ci <= currentsize) 
   { 
       if(ci < currentsize && heap[ci] > heap[ci + 1]) 
       { 
          ci++; 
       } 
 
       if(y <= heap[ci]) 
       { 
          break; 
       } 
       heap[i] = heap[ci]; 
       i = ci; 
       ci *= 2; 
   } 
 
   heap[i] = y; 
   return *this; 
} 
 
template<class T> 
void MinHeap<T>::Initialize(T x[], int size, int ArraySize) 
{ 
   delete []heap; 
   heap = x; 
   currentsize = size; 
   maxsize = ArraySize; 
 
   for(int i = currentsize / 2; i >= 1; i--) 
   { 
       T y = heap[i]; 
       int c = 2 * i; 
       while(c <= currentsize) 
       { 
          if(c < currentsize && heap[c] > heap[c + 1]) 
              c++; 
          if(y <= heap[c]) 
              break; 
          heap[c / 2] = heap[c]; 
          c *= 2; 
       } 
       heap[c / 2] = y; 
   } 
} 
 
template<class T> 
void MinHeap<T>::Deactivate() 
{ 
   heap = 0; 
}

source.cpp

//电路板排列问题 优先队列分支限界法求解 
#include "stdafx.h"
#include "MinHeap2.h"
#include <iostream>
#include <fstream>
using namespace std;
 
ifstream fin("6d8.txt");
 
class BoardNode
{
       friend int BBArrangement(int **,int,int,int *&);
       public:
              operator int() const
              {
                     return cd;
              }
       private:
              int *x,                   //x[1:n]记录电路板排列
                     s,                   //x[1:s]是当前节点所相应的部分排列
                     cd,                 //x[1:s]的密度
                     *now;            //now[j]是x[1:s]所含连接块j中电路板数
};
 
int BBArrangement(int **B,int n,int m,int *&bestx);
 
int main()
{
       int m = 5,n = 8;
       int *bestx;
 
       //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}
 
       cout<<"m="<<m<<",n="<<n<<endl;
       cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"<<endl;
       cout<<"二维数组B如下:"<<endl;
 
       //构造B
       int **B = new int*[n+1];
       for(int i=1; i<=n; i++)
       {
              B[i] = new int[m+1];
       }
 
       for(int i=1; i<=n; i++)
       {
              for(int j=1; j<=m ;j++)
              {
                     fin>>B[i][j];
                     cout<<B[i][j]<<" ";
              }
              cout<<endl;
       }
 
       cout<<"当前最优密度为:"<<BBArrangement(B,n,m,bestx)<<endl;
       cout<<"最优排列为:"<<endl;
       for(int i=1; i<=n; i++)
       {
              cout<<bestx[i]<<" ";
       }
       cout<<endl;
 
       for(int i=1; i<=n; i++)
       {
              delete[] B[i];
       }
       delete[] B;
 
       return 0;
}
 
//解电路板排列问题的优先队列式分支限界法
int BBArrangement(int **B,int n,int m,int *&bestx)
{
       MinHeap<BoardNode> H(1000);//活节点最小堆
       BoardNode E;
       E.x = new int[n+1];
       E.s = 0;
       E.cd = 0;
 
       E.now = new int[m+1];
       int *total = new int[m+1];
       //now[i] = x[1:s]所含连接块i中电路板数
       //total[i] = 连接块i中的电路板数
 
       for(int i=1; i<=m; i++)
       {
              total[i] = 0;
              E.now[i] = 0;
       }
 
       for(int i=1; i<=n; i++)
       {
              E.x[i] = i;//初始排列为1,2,3……n
              for(int j=1;j<=m;j++)
              {
                     total[j] += B[i][j];//连接块中电路板数
              }
       }
 
       int bestd = m + 1;
       bestx = 0;
 
       do//节点扩展
       {
              if(E.s == n-1)//仅一个儿子节点
              {    
                     int ld  = 0;//最后一块电路板的密度
                     for(int j=1; j<=m; j++)
                     {
                            ld += B[E.x[n]][j];
                     }
                     if(ld<bestd)//密度更小的电路排列
                     {
                            delete[] bestx;
                            bestx = E.x;
                            bestd = max(ld,E.cd);
                     }
                     else
                     {
                            delete []E.x;
                     }
                     delete []E.now;
              }
              else//产生当前扩展节点的所有儿子节点
              {
                     for(int i=E.s+1;i<=n;i++)
                     {
                            BoardNode N;
                            N.now = new int[m+1];
                            for(int j=1; j<=m; j++)
                            {
                                   //新插入的电路板
                                   N.now[j] = E.now[j] + B[E.x[i]][j];
                            }
                            int ld = 0;//新插入的电路板密度
                            for(int j=1; j<=m; j++)
                            {
                                   if(N.now[j]>0 && total[j]!=N.now[j])
                                   {
                                          ld++;
                                   }
                            }
                            N.cd = max(ld,E.cd);
                            if(N.cd<bestd)//可能产生更好的叶子节点
                            {
                                   N.x = new int[n+1];
                                   N.s = E.s + 1;
                                   for(int j=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);
                            }
                            else
                            {
                                   delete []N.now;
                            }
                     }
                     delete []E.x;
              }//完成当前节点扩展
              if(H.Size() == 0)
              {
                     return bestd;//无扩展节点
              }
              H.DeleteMin(E);                 
       }while(E.cd<bestd);
 
       //释放做小堆中所有节点
       do
       {
              delete []E.x;
              delete []E.now;
              if(H.Size() == 0)
              {
                     break;
              }
              H.DeleteMin(E);
       }while(true);
       return bestd;
}


© 著作权归作者所有

潘少online
粉丝 12
博文 58
码字总数 107019
作品 2
深圳
程序员
私信 提问
Xilinx RocketIO模块的介绍

摘要: 在高速电路系统设计中,差分串行通信方式正在取代并行总线方式,以满足系统对高带宽数据通信的需求。RocketIO是Virtex2 Pro以上系列FPGA中集成的专用高速串行数据收发模块,可用于实现...

mshgocn
2018/04/18
0
0
C++ 服务端 性能优化

编写正常运行的程序很容易,但一旦数据量大起来,对代码的性能就需要认真考虑了。对于服务器来说,如果客户端一次访问,就需要话费几百毫秒,那么一旦每秒的访问次数多起来,后续的请求就会造...

lxfeng
2016/05/22
144
0
玩转树莓派——支持XBOX手柄

作为最早玩XBOX 360和Kinect的一批玩家,家里的XBOX已经很久没开过了。改过电源、刷过脉冲,现在又在琢磨在树莓派上折腾XBOX手柄了。 之前写过,用RetroPie作为平台运行游戏模拟器等,Retro...

技术小胖子
2017/11/07
0
0
50元制作PS2键盘无线监控装置

0×00 什么是Arduino Arduino实际上就是一种开发板,将微控制器和必需的元件集成在一块电路板上,扩展出完善的接口和针脚,就可以接上各种各样的传感器,完成你心中的设计,你也可以把它理解...

广岛秋泽
2015/12/05
0
0
10 步跟我拆小米手机(多图+大图)

之前发布了《小米手机开箱图集抢先看【超多高清图】》,紧接着开始拆机。 小米手机1999的价格公布后,网上旋即出现了“1200成本”论。对此雷军表示,小米手机用的全是世界顶级材料, 欢迎国内...

红薯
2011/08/28
11.1K
54

没有更多内容

加载失败,请刷新页面

加载更多

约瑟夫环(报数游戏)java实现

开端 公司组织考试,一拿到考题,就是算法里说的约瑟夫环,仔细想想 以前老师将的都忘了,还是自己琢磨把~ package basic.gzy;import java.util.Iterator;import java.util.LinkedList;...

无极之岚
25分钟前
0
0
Kernel字符设备驱动框架

Linux设备分为三大类:字符设备,块设备和网络设备,这三种设备基于不同的设备框架。相较于块设备和网络设备,字符设备在kernel中是最简单的,也是唯一没有基于设备基础框架(device结构)的...

yepanl
今天
3
0
Jenkins 中文本地化的重大进展

本文首发于:Jenkins 中文社区 我从2017年开始,参与 Jenkins 社区贡献。作为一名新成员,翻译可能是帮助社区项目最简单的方法。 本地化的优化通常是较小的改动,你无需了解项目完整的上下文...

Jenkins中文社区
昨天
4
0
Spring中如何使用设计模式

关于设计模式,如果使用得当,将会使我们的代码更加简洁,并且更具扩展性。本文主要讲解Spring中如何使用策略模式,工厂方法模式以及Builder模式。 1. 策略模式 关于策略模式的使用方式,在S...

爱宝贝丶
昨天
4
0
前后端分离-前端搭建(vue)

前端使用vue,那么怎么搭建vue呢 先安装nodejs以及npm 现在基本的nodejs都包含有npm,下载安装后, 可以在cmd命令里输入 node -v 和npm -v 分别查看安装的版本 两个都显示了版本就是安装ok ...

咸鱼-李y
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部