注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

电路板排列问题 完整 C++代码  

2008-12-12 20:04:59|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 ?电路板排列问题是大规模电子系统设计中提出的一个实际问题。

?该问题的经典提法是:将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)密度定义为跨越相邻电路板插槽的最大连线数。

?在设计机箱时,插槽一侧的布线间隙由电路板排列的密度索确定。因此,电路板排列问题要求对于给定的电路板连接条件,确定电路板的最佳排列,使其具有最小密度。

 

// dian.cpp : Defines the entry point for the console application.
//author:wanggang

//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include "minheap.h"

using namespace std;

int n,m;//全局变量
int * bestx;//最后的结果
int ** B;

int max(int a,int b){
 if(a<b)return b;
 else
  return a;
}
class BoardNode{
 friend int BBArrangement(int * *,int,int,int * &);
public:
 operator int() const{return cd;}
private:
 int *x,
  s,
  cd,
  *now;
};
//B指向输入的连接块的指针,相当于二维数组,n 电路板数,m连接块数 ,bestX是传引用,用于保存最后的结果
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 k=1;k<=n;k++){
  E.x[k]=k;//初始排列为12345...n
  
  for(int j=1;j<=m;j++)
   total[j]+=B[k][j];//连接块j中电路板数
 }
 int bestd=m+1;//当前最小密度
 bestx=0;
 do{//结点扩展
  //cout<<"now in do _while ,Begin thie loop "<<endl;
  if(E.s==n-1){//仅一个儿子结点
   //cout<<"now in n-1"<<endl;
   int ld=0;//最后一块电路板的密度
   for(int j=1;j<=m;j++)
    ld+=B[E.x[n]][j];
 
   if(ld<bestd){//密度更小的电路板排列
   // cout<<" now ld less than bestd: ld="<<ld<<" bestd="<<bestd<<endl;
    delete[]bestx;
    bestx=E.x;
   
    bestd=max(ld,E.cd);
    
   }
   else delete []E.x;
   delete[]E.now;
  }
  else{//产生当前扩展结点的所有儿子结点
  // cout<<"Extend node S="<<E.s<<endl;
   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( 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;
    }
   }//end for
   delete []E.x;
  }//完成当前的结点扩展
  try{
   if(H.isEmpty()){
    break;
   }
   //取下一扩展结点
   H.DeleteMin(E); //把值放入E
  }
  catch(exception){return bestd;}//无扩展结点OutOfBounds
 }while(E.cd<bestd);

 //释放最小堆中所有结点
 do{
  if(H.isEmpty()){//如果全部删除所有的节点,跳出循环
   
   break;
  }
  try{
   
   H.DeleteMin(E);
  }catch(exception){
   break;
  }
  try{
  delete[]E.x;
  delete[]E.now;
  }catch(exception){
   cout<<"now there have some problem"<<endl;
  }
 }while(true);
 return bestd;//返回结果
}
////////////////////////////处理文件输入输出
void getInput(istream&fin){
    int i;
 
    fin>>n;
    fin>>m; 
 B= new int*[n+1];
 for( i=1;i<=n;i++)
 {
  int * p= new int[m+1];
  for(int j=1;j<=m;j++)
  {
   fin>>p[j];
  }
  B[i]=p;
 } 
 bestx= new int [n+1];
}

void freememory(){
 for(int i=1;i<=n;i++){
  delete [] B[i];
 }
 delete [] B;
}
void printData()
{
 cout<<n<<" "<<m<<endl;
 for(int i=1;i<=n;i++)
 {
  for(int j=1;j<=m;j++)
  {
   cout<<B[i][j]<<" ";
  }
  cout<<endl;
 }
}
void outPutResult(int d)
{
 cout<<"----------------------------"<<endl;
 cout<<"best result "<<endl;
 cout<<"bestd="<<d<<endl;
 
 for(int i=1;i<=n;i++){
     cout<<bestx[i]<<" ";
     
 }
 cout<<endl;
}

int main(int argc, char* argv[])
{
 minHeap<BoardNode> h(1000);
 ifstream fin("c:\\input.txt");
 getInput(fin);
 printData();
 fin.close();
 
 int d =BBArrangement(B,n,m,bestx);
  outPutResult(d);
  freememory();
 return 0;
}
//file2

//HEAP-> HEAP IS A COMPLETE BINARY TREE WITH HAVING A CERTAIN RELATION
//BETWEEN PARENT AND CHILD
//A MIN HEAP IS THAT IN WHICH EACH CHILD HAVE VALUE LESS THEN IT'S PARENT..
/*
  Name: maxHeap
  Author: Rajat
  Date: 11/11/06 18:05
 
*/

#include<iostream>
using namespace std;
template<class T>
class minHeap
{
      private:
              int currentSize,maxSize;
              T *heap;
      public:
             minHeap(int max=10);
             ~minHeap();
             int size() const {return currentSize;}
             bool isEmpty(){return currentSize==0;}
             bool isFull() {return currentSize==maxSize;}
             T min()  {if(isEmpty())
                          {cout<<"\nThe heap is empty.\n"; return NULL;}
                       return heap[1];
                      }
            minHeap<T>& insert(const T& x);
            minHeap<T>& DeleteMin(T& x);
            void initialize(T a[],int size,int arraySize);
            void displayHeap();
};
template<class T>
minHeap<T>::minHeap(int max)
{
                        maxSize=max;
                        currentSize=0;
                        heap=new T[maxSize+1];
}
template<class T>
minHeap<T>::~minHeap()
{
                      delete [] heap;
}
template<class T>
minHeap<T>& minHeap<T>::insert(const T& x)
{
            if(isFull())
            {cout<<"\nThe Heap is full.\n"; return *this;}
            int i=++currentSize;
              heap[currentSize]=x;
            while(i!=1)
            {
                       if(heap[i]<heap[i/2])
                       {
                                            T temp;
                                            temp=heap[i];
                                            heap[i]=heap[i/2];
                                            heap[i/2]=temp;
                       }
                       i/=2; //updating i for loop continuation
            }
        //THIS INSERT IS SLIGHTLY DIFFERENT FROM SAHNI'S INSERT
            return *this;
}
template<class T>
minHeap<T>& minHeap<T>::DeleteMin(T& x)
{
            if(isEmpty())
            {cout<<"\nThe Heap is already empty.\n";return *this;}
            x=heap[1];//saving information
            T y=heap[currentSize--];
            int i=1,ci=2;
            while(ci<=currentSize)
            {
                                  if(ci<currentSize && heap[ci]>heap[ci+1])
                                  ci++;//index of the samller element
                                  if(y<=heap[ci])
                                  break;
                                 
                                  heap[i]=heap[ci];
                                  i=ci;
                                  ci*=2;
            }//ends while.........
            heap[i]=y;
             return *this;
}
template<class T>
void minHeap<T>::initialize(T a[],int size,int arraySize)
{
          delete [] heap;
          heap=a;
          currentSize=size;
          maxSize=arraySize;
         
          for(int i=currentSize/2 ; i>=1 ; i--)
          {
                  T y=heap[i];
                  //find place for y;
                  int ci=2*i;
                  while(ci<=currentSize)
            {
                                  if(ci<currentSize && heap[ci]>heap[ci+1])
                                  ci++;
                                  if(y<=heap[ci])
                                  break;
                                 
                                  heap[ci/2]=heap[ci];
                                 
                                  ci*=2;
            }//ends while.........
            heap[ci/2]=y;
            }//for loop ends............
             cout<<"\nThe minHeap has been initialized.\n";
             displayHeap();    
         return;        
 }
template<class T>
void minHeap<T>::displayHeap()
{
     if(isEmpty())
     {
                  cout<<"\nThe Heap is empty.\n";return;
     }
     for(int i=1; i<=currentSize ; i++)
     cout<<heap[i]<<"  ";  cout<<"\n\n";
     return;
}       

 

  评论这张
 
阅读(1839)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016