qkw_fac6_8.java

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

package qkw_fac6_8;

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

class MinHeap
   {        //Min-heap impmentation
     static HeapNode [] Heap; //Pointer to the heap array
     static int size; //Maximum size of the heap//(堆中的最多有多少结点qkw)
     static int n;//Number of intents now in heapheapsoet//(堆中当前结点数qkw)
    
    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
            }// j is now index of child with greater value
            if (key(Heap, pos) <= key(Heap, j)) {
                return; // Done
            }// Done
            swap(Heap, pos, j);
            pos = j;//Move down
        }
    }
    public  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  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
        } //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
        }//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();
    }

  public void heapsort()  //heapsort//static void 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 Qkw_Fac6_8{

      public static int bbBoards(int[][] board,int m,int[] bestx)
        {//优先队列式分支限界法解电路板排列问题   //m=m1=5;
          int n=board.length-1;

          HeapNode h1[]=new HeapNode[500];//优先队列//n的值最多为堆中最大结点数。
          MinHeap heap=new MinHeap(h1,0,500); //n为堆中最大结点数（qkw）


//          HeapNode h1[]=new HeapNode[500];     ///n问题//////qkw////////
//          MinHeap heap=new MinHeap(h1,0,500);  ///n有问题。/////qkw/////

         // 初始化
          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中电路板数
                 }    //连接块j中电路板数
           }
          int bestd=m+1;
          int[] x=null;
          do///断点跟踪/////qkw//////
            {//结点扩展
             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);///断点跟踪/////qkw//////

       for(int i=1;i<=n;i++) {///构造最优解//qkw////
            bestx[i] = x[i];    /////best[i]=x1[i]////(248行) qkw
        }
       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("  ");

  }
}