bbload.java

用分支界限法解决的几个问题:包括0-1背包问题,最大团问题,电路布线问题,最大装载问题.作业最优处理问韪.

/*
 * BLoad.java
 *
 * Created on 2006年4月18日, 下午4:38
 *
 * To change this template, choose Tools | Options and locate the template under
 * the Source Creation and Management node. Right-click the template and choose
 * Open. You can then make changes to the template in the Source Editor.
 */

package test;
import test.*;
/**
 *
 * @author michael
 */
public class BBLoad {
       static int n;
       static int bestw;
       static MyQueue queue;
       static Qnode bestE;
       static Qnode flag = new Qnode(null, false,0);
       static int[] bestx;
    /** Creates a new instance of BLoad */
    public BBLoad(){}
    public static int maxLoad(int[]w,int c){
        //优先队列式分支限界法，返回最优载重量，bestx返回最优解

       n=w.length-1;
       bestx = new int[w.length];
       bestw=0;
       queue=new MyQueue();
       queue.enQueue(flag,-9);
       Qnode e= null;
       bestE=null;
       int i=1;
       int ew=0;
       int r=0;
       for (int j = 2;j <= n; j++)  r += w[j];
       
       //搜索子集空间树
       while (true){
           //检查左儿子结点
           int wt=ew+w[i];
           if (wt <= c){
               //可行结点
               if (wt > bestw) bestw=wt;
               enQueue(wt,i,e,true);
           }           
          // System.out.println("可行结点:wt="+wt + "bestw="+bestw +"ew="+ew+"r="+r+"i="+i);     
           //检查右儿子结点
           if (ew+r > bestw) {enQueue(ew,i,e,false);}
           e=(Qnode) queue.deQueue();   //同层结点尾部
           if (e == flag){
               if (queue.isEmpty()) break;
               queue.enQueue(flag, 0); 
               e=(Qnode) queue.deQueue();
               i++;
               r-=w[i];
           }
           ew = e.weight;
       }
       
       //构造当前最优解
       for (int j=n-1;j>0;j--) {
           bestx[j]=(bestE.leftChild)?1:0;
           bestE=bestE.parent;
           
       }
       for (int j=0;j<=n;j++) System.out.print(bestx[j]);
       return bestw;
    }
    
    private static void enQueue(int wt,int i,Qnode parent,boolean leftchild){
        //将活结点加入到活结点队列中
 System.out.println("bestw="+bestw+ "wt="+wt+"i="+i+"n="+n);    

        if (i==n){
            //可行叶结点
            if (wt==bestw){
                //当前最优载重量
                bestE=parent;
                bestx[n]=(leftchild)?1:0;
            }
            return;
        }
        
        //非叶结点
        Qnode b = new Qnode(parent,leftchild,wt);
        queue.enQueue(b,0);
    }
}