fac6_9.java

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

//本程序取自王晓东编著“算法分析与设计”第 232 页，例
//批作业调度问题的分支限界解法

  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].bb;}

  //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 ");
       if(n!=0){         //Not on last intent
       swap(Heap,0,--n);//swap minimum with last value
       
       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].bb+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最小堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removemin().bb+"  ");
     System.out.println( );    //removemin places min value at end of heap
    } 
 }// class MinHeap

   class HeapNode implements Comparable
  {
    int s,       // 已安排作业数
        sf2,     //  当前机器2 上完成时间和
        bb ;     //  当前完成时间和下界
    int []f;     // f[1]机器1上最后完成时间；f[2]机器2上最后完成时间 
    int []x ;     // 当前作业调度

       HeapNode(int n)
       {
         // 最小堆结点初始化
         x=new int[n];
         for(int i=0;i<n;i++)x[i]=i;
         s=0;
         f=new int[3];
         f[1]=0;
         f[2]=0;
         sf2=0;
          bb=0;
       }
      HeapNode(HeapNode e,int []ef,int ebb,int n)
       {
         //最小堆新结点
        x=new int[n];
        for(int i=0;i<n;i++)x[i]=e.x[i];
        f=ef;
        sf2=e.sf2+f[2];
        bb=ebb;
        s=e.s+1;
       }


    public int compareTo(Object x)
       {
        int xbb=((HeapNode) x).bb;
        if(bb<xbb) return -1;
        if(bb==xbb) return 0;
        return 1;
       }
   }
 
  class BBFlow 
  { 
     static int n,        // 作业数
               bestc;     // 最小完成时间和
     static int[][] m;    // 各作业所需的处理时间数组
     static int[][] b;    // 各作业所需的处理时间排序数组
     static int[][] a;    // 数组m和b的对应关系数组
     static int[] bestx;  // 最优解
     static boolean [][]y; // 工作数组

   
     public static void sort()
     {
         // 对各作业在机器1和2上所需时间排序
      int[] c=new int[n];
      for(int j=0;j<2;j++)
        {
           for(int i=0;i<n;i++)
             {
               b[i][j]=m[i][j];
               c[i]=i;
               System.out.print("  "+b[i][j]);
             }
           
           System.out.println(" ");
         for(int i=0;i<n-1;i++)
          for(int k=n-1;k>i;k--)
           if(b[k][j]<b[k-1][j])
            {
              swap(b,k,j,k-1,j);
              swap(c,k,k-1);
            }
         for(int i=0;i<n;i++)a[c[i]][j]=i;
       }
     }

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

    public static int bound(HeapNode enode,int[] f)
     {
       // 计算完成时间和下界
        for(int k=0;k<n;k++)
          for(int j=0;j<2;j++)
            y[k][j]=false;
        for(int k=0;k<=enode.s;k++)
          for(int j=0;j<2;j++)
            y[a[enode.x[k]][j]][j]=true;
        f[1]=enode.f[1]+m[enode.x[enode.s]][0];
        f[2]=((f[1]>enode.f[2])?f[1]:enode.f[2])+m[enode.x[enode.s]][1];
        int sf2=enode.sf2+f[2];
        int s1=0,s2=0,k1=n-enode.s,k2=n-enode.s,f3=f[2];
      //计算s1的值
        for(int j=0;j<n;j++)
         if(!y[j][0])
           {
             k1--;
             if(k1==n-enode.s-1)
             f3=(f[2]>f[1]+b[j][0])?f[2]:f[1]+b[j][0];
             s1+=f[1]+k1*b[j][0];
           }
      //计算s2的值
      for(int j=0;j<n;j++)
       if(! y[j][1])
         {
            k2--;
            s1+=b[j][1];
            s2+=f3+k2*b[j][1];
         }
      // 返回完成时间和下界
      return sf2+((s1>s2)? s1:s2);
     }

   public static int bbFlow(int nn)
   {
      //优先队列式分支限界法解批处理作业调度问题
       n=nn;
       
       sort();//对各作业在机器1和机器2上所需时间排序
       //初始化最小堆
      HeapNode [] e=new HeapNode[n];
      MinHeap heap=new MinHeap(e,0,n);
      HeapNode enode=new HeapNode(n);
      //搜索排列空间树
     do
      {
          if(enode.s==n)
             {//叶结点
                if(enode.sf2<bestc)
                  {
                    bestc=enode.sf2;
                    for(int i=0;i<n;i++)
                    bestx[i]=enode.x[i];
                  }
             }
          else //产生当前扩展结点的儿子结点
           for(int i=enode.s;i<n;i++)
             {
               swap(enode.x,enode.s,i);
               int[] f=new int[3];
               int bb=bound(enode,f);
               if(bb<bestc)
                 {
                  // 子树可能含最优解 
                  // 结点插入最小堆
                   HeapNode node=new HeapNode(enode,f,bb,n); 
                   heap.insert(node);
                 }
              swap(enode.x,enode.s,i);
             } // 完成结点扩展
          //  取下一扩展结点 
          enode=(HeapNode) heap.removemin();
      }while(enode !=null && enode.s<=n); 
      return bestc;     
    } 
  } 
      
 public class Fac6_9{
      public static void main(String args[])
  {
     BBFlow pzd=new BBFlow();
     int [][]m1={{2,1},{3,1},{2,3}};  
     int [][]a1={{0,0},{0,0},{0,0}};
     int n1=m1.length;
     boolean y1[][]=new boolean[n1][2];
     int bestx1[]=new int[n1+1]; 
     pzd.m=m1;
     pzd.b=a1;
     pzd.a=a1;
     pzd.y=y1;
     pzd.n=n1;    
     pzd.bestx=bestx1;        
    System.out.println(" 最优值  "+pzd.bbFlow(n1));    
    for(int i=1;i<n1;i++)
    System.out.print(pzd.bestx[i]+"  ");
    System.out.println();
  }
}