fac6_8.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 225 页，例
//电路板排列问题的分支限界解法
//

class MinHeap 
   {                      //Min-heap impmentation
     static HeapNode [] Heap;  //Pointer to the heap array
     static int size;     //Maximum size of the heap
     static int n;        //Number of intents now in heapheapsoet
    public MinHeap(HeapNode [] h,int num,int max)//constructor
     { Heap=h;n=num;size=max;buildheap();}
    public int heapsize()//return current size of the heap
     {  return n;}
    public static boolean isLeaf(int pos)//true if pos is a leaf position
     { return(pos>=n/2)&&(pos<n);} 
    public static void Assert_notFalse(boolean p,String q)
     {if(!p)System.out.println((String)q);}
    public static int key( HeapNode  [] q,int p)
     {  return q[p].cd;}
  //return position for left child of pos
    public static int leftchild(int pos)
     { Assert_notFalse(pos<n/2,"position has no left child");
       return 2*pos+1;
     }
  //return position for right child of pos
    public static int rightchild(int pos)
     {Assert_notFalse(pos<(n-1)/2,"position has no right child");
     return 2*pos+2;
     }
    public static int parent(int pos)//return position for parent
     {Assert_notFalse(pos>0,"position has no parent");
     return (pos-1)/2;
     }
    public static  void buildheap() //Heapify contents of Heap
     {  for(int i=n/2-1;i>=0;i--)siftdown(i);}

    public static void swap(HeapNode [] q,int i,int j)
     {      
       HeapNode  temp;
       temp=q[i];q[i]=q[j];q[j]=temp;}

    private static void siftdown(int pos) //put intent in itscorrent place
     {Assert_notFalse((pos>=0) && (pos<n),"illegal heap position ");
     while(! isLeaf(pos))
      {
       int j=leftchild(pos);
       if((j<(n-1))&&(key(Heap,j)>key(Heap,j+1)))
         j++;// j is now index of child with greater value
       if(key(Heap,pos)<=key(Heap,j)) return;// Done
       swap(Heap,pos,j);
       pos=j;//Move down 
      }
     }
    public static void insert(HeapNode  val) //Insert value into heap
     {
     Assert_notFalse(n<size,"Heap is full ");
     int curr=n++;
     Heap[curr]=val;      //start t end of heap
     //Now sift up until curr's parent's key<curr's key
     while((curr!=0)&&(key(Heap,curr)<key(Heap,parent(curr))))
       {
         swap(Heap,curr,parent(curr));
         curr=parent(curr);
       }
      }
    public static HeapNode  removemin()  //remove minimum value
      {
       Assert_notFalse(n>0,"Removing from empty heap ");
       swap(Heap,0,--n);//swap minimum with last value
       if(n!=0)     //Not on last intent
       siftdown(0); //Put new heap root val in corrent place 
       return Heap[n];
     }
  //Remove intent at specified position 
    public static HeapNode  remove(int pos)
     {
      Assert_notFalse((pos>0)&&(pos<n),"illegal heap position ");
      swap(Heap,pos,--n);//swap with last value
      if(n!=0)     //Not on last intent
      siftdown(pos);//put new heap root val in corrent place
      return Heap[n];
     }
   public static void outMinHeap()
     {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i]+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最小堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removemin().cd+"  ");
     System.out.println( );    //removemin places min value at end of heap
    } 
 }// class MinHeap 
    
      class HeapNode implements Comparable
           {
             
               int s;       //x[1:s]是当前结点所相应的部分排列
               int cd;      //x[1:s]的密度
               int[] now;   //now[j]是 x[1:s]所含连接块 j中电路板数
               int[] x;      //x[1:n]记录电路板排列
           //构造方法
            HeapNode(int cdd,int[] noww,int ss,int []xx)
             {
               cd=cdd;
               now=noww;
               s=ss;
               x=xx;
             }
           public int compareTo(Object x) 
             {
              int  xcd=((HeapNode)x).cd;
               if(cd<xcd)return -1;
               if(cd==xcd)return 0;
               return 1;
             }
         }
         
   public class Fac6_8{

      public static int bbBoards(int[][] board,int m,int[] bestx)
        {//优先队列式分支限界法解电路板排列问题
          int n=board.length-1;
          HeapNode h1[]=new HeapNode[n];
          MinHeap heap=new MinHeap(h1,0,n);
         // 初始化        
          HeapNode enode=new HeapNode(0,new int[m+1],0,new int[n+1]);
          // total[i]=连接块i 中电路板      
          int [] total=new int[m+1];
          for(int i=1;i<=n;i++)
            {
            enode.x[i]=i;         //初始排列为12...n         
            for(int j=1;j<=m;j++) 
             total[j]+=board[i][j];    //连接块j中电路板数
            }
          int bestd=m+1;
          int[] x=null;
          do
            {//结点扩展
             if(enode.s==n-1)
              {//仅一个儿子结点
                int ld=0;        //最后一块电路板的密度
                for(int j=1;j<=m;j++)
                  ld+=board[enode.x[n]][j];
                if(ld<bestd)
                  {//找到密度更小的电路板排列
                    x=enode.x;
                    bestd=Math.max(ld,enode.cd);
                  }
               }
             else
               {//产生当前扩展结点的所有儿子结点
                for(int i=enode.s+1;i<=n;i++)
                  {
                   HeapNode node=new HeapNode(0,new int[m+1],0,new int[n+1]);
                  for(int j=1;j<=m;j++)
                    //新插入的电路板
                    node.now[j]=enode.now[j]+board[enode.x[i]][j];
                  int ld=0;  //新插入电路板的密度
                  for(int j=1;j<=m;j++)
                    if(node.now[j]>0 && total[j]!=node.now[j])ld++;
                  node.cd=Math.max(ld,enode.cd);
                  if(node.cd<bestd)
                    {//可能产生更好的叶结点
                     node.s=enode.s+1;
                     for(int j=1;j<=n;j++)node.x[j]=enode.x[j];
                     node.x[node.s]=enode.x[i];
                     node.x[i]=enode.x[node.s];
                     heap.insert(node);
                    }
                  }         
               }
  
    //取下一扩展结点
       enode=(HeapNode)heap.removemin();
       //
      }while(enode!=null && enode.cd<bestd);
       for(int i=1;i<=n;i++)
         bestx[i] =x[i];
       return bestd;    
 }//  
  
      public static void main(String args[])
      {
     
       int n1=8;
       int m1=5;
     //  int nm=0;
       int [][]bt=new int[n1+1][m1+1];
       int []x1=new int[n1+1];
       bt[1][1]=0;bt[1][2]=0;bt[1][3]=1;bt[1][4]=0;bt[1][5]=0;
       bt[2][1]=0;bt[2][2]=1;bt[2][3]=0;bt[2][4]=0;bt[2][5]=0;
       bt[3][1]=0;bt[3][2]=1;bt[3][3]=1;bt[3][4]=1;bt[3][5]=0;
       bt[4][1]=1;bt[4][2]=0;bt[4][3]=0;bt[4][4]=0;bt[4][5]=0;
       bt[5][1]=1;bt[5][2]=0;bt[5][3]=0;bt[5][4]=0;bt[5][5]=0;
       bt[6][1]=1;bt[6][2]=0;bt[6][3]=0;bt[6][4]=1;bt[6][5]=0;
       bt[7][1]=0;bt[7][2]=0;bt[7][3]=0;bt[7][4]=0;bt[7][5]=1;
       bt[8][1]=0;bt[8][2]=0;bt[8][3]=0;bt[8][4]=0;bt[8][5]=1;
      
      
      System.out.println("密度  "+ bbBoards(bt,m1,x1));
       System.out.println("电路板最佳排列顺序  ");
       for(int i=1;i<=n1;i++)
       System.out.print("  "+x1[i]);
       System.out.println("  ");
     
  }
}