bbclique.java

来自「用分支界限法解决的几个问题:包括0-1背包问题,最大团问题,电路布线问题,最大装」· Java 代码 · 共 77 行

/*
 * BBClique.java
 *
 * Created on 2006年4月19日, 下午2:10
 *
 * 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;

/**
 *
 * @author michael
 */
public class BBClique {
    public static int[][] a={{1,1,0,1,1},
                               {1,1,1,0,1},
                               {0,1,1,0,1},
                               {1,0,0,1,1},
                               {1,1,1,1,1}}; //图G的邻接矩阵
    static CMaxHeap heap;        //活结点优先队列
    /** Creates a new instance of BBClique */
    public BBClique() {

    }
    public static int maxClique(int bestx[]){
        //解最大团问题的优先队列式分支限界法
        int n=bestx.length-1;
        heap = new CMaxHeap();
        //Initialize
        CBBnode enode = null;
        int i=1;
        int cn=0;
        int bestn=0;
        //搜索子集空间树
        while (i!=n+1){
            //非叶子结点
            //检查顶点i与当前团中其他顶点之间是否有边相连
            boolean ok = true;
            CBBnode bnode = enode;
            for (int j=i-1;j>0;j--){
                if (bnode.leftChild && a[i][j]==0){
                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);
            //取一下扩展结点
            CHeapNode node=(CHeapNode)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;
    }
    private static void addLiveNode(int up,int size,int lev,CBBnode par,boolean ch){
     //将活结点加入到子集空间树中并插入最大堆中
        CBBnode b = new CBBnode(par,ch);
        CHeapNode node = new CHeapNode(b,up,size,lev);
        heap.insert(node);
    }
}