fac6_7.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 float key( HeapNode [] q,int p)
     {  return q[p].lcost;}
  //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
     {//System.out.println(  "n="+n+"  size="+size);
     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].lcost+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最小堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removemin().lcost+"  ");
     System.out.println( );    //removemin places min value at end of heap
    } 
 }// class MinHeap 
    
     class HeapNode implements Comparable
         {
             float lcost;  //子树费用的下界
             float cc;     //当前费用
             float  rcost; //x[s:n-1]中顶点最小出边费用和
               int s;      //根结点到当前结点的路径为x[0:s]
               int [] x;   //需要进一步搜索的顶点是x[s+1,n-1]
           //构造方法
            HeapNode(float lc,float ccc,float rc,int ss,int []xx)
             {
               lcost=lc;
               cc=ccc;
               rcost=rc;
               s=ss;
               x=xx;
             }
           public int compareTo(Object x) 
             {
              float  xlc=((HeapNode)x).lcost;
               if(lcost<xlc)return -1;
               if(lcost==xlc)return 0;
               return 1;
             }
         }
   class BBTSP
      {      
        static float [][]a;   //图G的临界矩阵
     

      public static float bbTSP(int[] v)
      {  //解货郎担问题的优先队列式分支限界法
          int n=v.length-1;
          HeapNode []h1=new HeapNode[n+1];
          MinHeap heap=new MinHeap(h1,0,n+1);
         //minOut[i]=顶点i的最小出边费用
          float [] minOut=new float[n+1];
          float minSum=0;//最小出边费用和

          for(int i=1;i<=n;i++)
            {//计算minOut[i]和minSum
            float min=Float.MAX_VALUE;
            for(int j=1;j<=n;j++)            
             if(a[i][j]<Float.MAX_VALUE && a[i][j]<min)
              min=a[i][j];
             if(min==Float.MAX_VALUE)return Float.MAX_VALUE;//无回路
             minOut[i]=min;
             minSum+=min;
            }
            System.out.println("minOut[i]=顶点i的最小出边费用 " );
          for(int k=1;k<=n;k++)
            System.out.print(minOut[k]+"  ");
            System.out.println( "minsum="+minSum);
        //初始化
        int []x=new int[n];
        for(int i=0;i<n;i++)x[i]=i+1;  
        HeapNode enode=new HeapNode(0,0,minSum,0,x);
        float bestc=Float.MAX_VALUE;         
       //搜索排列空间树
        while(enode!=null && enode.s<n-1)
         {//非叶结点
           x=enode.x;
           if(enode.s==n-2)
            {//当前扩展结点是叶结点的父结点
             //再加2条边构成回路
             //所构成回路是否优于当前最优解
             if(a[x[n-2]][x[n-1]]<Float.MAX_VALUE && 
                a[x[n-1]][1]<Float.MAX_VALUE  &&
                enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][1]<bestc)
               {//找到费用更小的回路
                
                bestc=enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][1];
                enode.cc=bestc;
                enode.lcost=bestc;
                enode.s++;
                heap.insert(enode);
               }
           }
          else
           {//产生当前扩展结点的儿子结点
             for(int i=enode.s+1;i<n;i++)
               if(a[x[enode.s]][x[i]]<Float.MAX_VALUE)
                {
                  //可行儿子结点
                  float cc=enode.cc+a[x[enode.s]][x[i]];
                  float rcost=enode.rcost-minOut[x[enode.s]];
                  float b=cc+rcost;//下界
                  if(b<bestc)
                   {//子树可能含最优解，结点插入最小堆
                    int []xx=new int[n];
                    for(int j=0;j<n;j++)xx[j]=x[j];
                    xx[enode.s+1]=x[i];
                    xx[i]=x[enode.s+1];
                    HeapNode node=new HeapNode(b,cc,rcost,enode.s+1,xx);
                    heap.insert(node);
                   }
                }
           }
       //取下一扩展结点
       enode=(HeapNode)heap.removemin();
      } //将最优解复制到v[1:n]
       for(int i=0;i<n;i++)
         v[i+1]=x[i];
       return bestc;    
   }//
 }

   public class Fac6_7{
  
      public static void main(String args[])
  {
     BBTSP abc=new BBTSP();
     int n1=4; 
     float ff=Float.MAX_VALUE;  
     int v1[]=new int[n1+1];
     float a1[][]=new float [n1+1][n1+1];
      a1[1][1]=ff; a1[1][2]=30.0f; a1[1][3]=6.0f;  a1[1][4]=4.0f; 
      a1[2][1]=30.f; a1[2][2]=ff;  a1[2][3]=5.0f;  a1[2][4]=10.0f; 
      a1[3][1]=6.0f; a1[3][2]=5.0f;  a1[3][3]=ff;  a1[3][4]=20.0f; 
      a1[4][1]=4.0f; a1[4][2]=10.0f; a1[4][3]=20.0f; a1[4][4]=ff;
      for(int k=0;k<=n1;k++)      
        v1[k]=0;    
     abc.a=a1;                 
     System.out.println("货郎担问题的最优解   " + abc.bbTSP(v1));
     for(int k=1;k<=n1;k++)
     System.out.print("  "+v1[k]);
     System.out.println();
  }
}