fac6_6.java

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

//本程序取自王晓东编著“算法分析与设计”第 222 页，例
//最大团问题的分支限界解法
   
   class MaxHeap 
   {                      //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 MaxHeap(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].upperSize;}
  //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 removemax()  //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 outMaxHeap()
     {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i].upperSize+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最大堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removemax().upperSize+"  ");
     System.out.println( );    //removemax places min value at end of heap
    } 
 }// class MaxHeap
 
    class BBnode
    {
       BBnode  parent;
       boolean leftChild;
    
      BBnode(BBnode par,boolean ch)
         {
           parent=par;
           leftChild=ch;
         }
    }
    class HeapNode implements Comparable
      {
           BBnode liveNode;
           int upperSize;
           int cliqueSize;
           int level;
        HeapNode(BBnode node,int up,int size,int lev)
           {
             liveNode=node;
             upperSize=up;
             cliqueSize=size;
             level=lev;
           }
        public int compareTo(Object x)
         {
           int xup=((HeapNode)x).upperSize;
           if(upperSize<xup)return -1;
           if(upperSize==xup)return 0;
           return 1;
         }
      } 
    class BBClique 
      {
           static boolean [][]a;
           static MaxHeap heap;     
 
       private static void addLiveNode(int up,int size,int lev,BBnode par,boolean ch)
         {
           BBnode b=new BBnode(par,ch);
           HeapNode node=new HeapNode(b,up,size,lev);
           heap.insert(node);
         }

      public static int bbMaxClique(int [] bestx)
        {
          int n=bestx.length-1;
          HeapNode[] h=new HeapNode[n];
          MaxHeap heap=new MaxHeap(h,0,n);
          //
          BBnode enode=null;
          int i=1;
          int cn=0;
          int bestn=0;
          while(i!=n+1)
           {
            //
            boolean ok=true;
            BBnode bnode=enode;
            for(int j=i-1;j>0;bnode=bnode.parent,j--)
              if(bnode.leftChild && !a[i][j]) 
                {
                  ok=false;
                  break;
                }
              if(ok)
                {//
                  if(cn+1>bestn)bestn=cn+1;
                   addLiveNode(cn+n-i+1,cn+1,i+1,enode,true);
                }
              if(cn+n-i>=bestn)
                //
              addLiveNode(cn+n-i,cn,i+1,enode,false);
              HeapNode node=(HeapNode)heap.removemax();
              enode=node.liveNode;
              cn=node.cliqueSize;
              i=node.level;
          }
            //
          for(int j=n;j>0;j--)
            {
              bestx[j]=(enode.leftChild)?1:0;
              enode=enode.parent;
            }
          return  bestn;
      } 
    }       
   
  public class Fac6_6{
   
      public static void main(String args[])
  {
       BBClique abc=new BBClique();
     int n1=5; 
     int ak[]=new int[n1+1];
     boolean [][] aw=new boolean[n1+1][n1+1];
      aw[1][1]=false;aw[1][2]=true; aw[1][3]=false; aw[1][4]=true; aw[1][5]=true;
      aw[2][1]=true; aw[2][2]=false;aw[2][3]=true;  aw[2][4]=false;aw[2][5]=true;
      aw[3][1]=false;aw[3][2]=true; aw[3][3]=false; aw[3][4]=false;aw[3][5]=true;
      aw[4][1]=true; aw[4][2]=false;aw[4][3]=false; aw[4][4]=false;aw[4][5]=true;
      aw[5][1]=true; aw[5][2]=true; aw[5][3]=true;  aw[5][4]=true; aw[5][5]=false; 
     abc.a=aw;    
     System.out.println("最大团顶点数为 " + abc.bbMaxClique(ak));
     for(int i=1;i<=n1;i++)
     System.out.print("  "+ak[i]);
     System.out.println();
        
    
  }
}