优先队列分支限界法解部落冲突问题

算法思路：

• 构建解空间树（二叉树）
• 以广度优先遍历解空间树，对每个结点进行约束函数和限界函数判断
• 约束函数：若要入选队伍，则必须与其他队员无仇

for(int j=i-1;j>0;bnode=bnode.parent,j--){  
                if(bnode.leftChild&&a[i][j]==1){  
                    ok=false;  
                    break;  
                }  

• 约束函数：当前团最大结点大于最有解

if(cn+n-i>=bestn){//右子树可能含有最优解  
                addLiveNode(cn+n-i,cn,i+1,enode,false);  
            }  

• 当遍历到其中一个叶子结点，则算法结束。

完整代码如下:

import java.util.Collections;  
import java.util.LinkedList;  
class BBnode{                                 //构建结点类
    BBnode parent;
    boolean leftChild;
    public BBnode(BBnode parent, boolean leftChild)
    {
        super();
        this.parent = parent;
        this.leftChild = leftChild;
    }
    
}
class HeapNode implements Comparable{   //构建队列结点
    BBnode liveNode;
    int upperSize;                                    //当前团最大结点数（已知+未知）
    int cliqueSize;                                    //当前团顶点数
    int level;                                             //所处层数
    
    public HeapNode(BBnode liveNode, int upperSize, int cliqueSize, int level)
    {
        super();
        this.liveNode = liveNode;
        this.upperSize = upperSize;
        this.cliqueSize = cliqueSize;
        this.level = level;
    }

    @Override
    public int compareTo(Object o)
    {
        // TODO Auto-generated method stub
        int xup=((HeapNode)o).upperSize;
        if(upperSize<xup)return 1;
        if(upperSize==xup)return 0;
        return -1;
    }
    
}
class MaxHeap{
    int[] value;
    int heapsize;
    public void put(HeapNode node){
        
    }
}
public class BBClique
{
    static int[] x;
    static int n;
    static int cn;//当前队伍人数
    static int bestn;//最大队伍人数
    static int[] bestx;
    static int[][] a;
    static  LinkedList<HeapNode> heap; 
    public BBClique(int[][] a){  
        this.a=a;  
        heap=new LinkedList<HeapNode>();  
    }
    public void addLiveNode(int up,int size,int lev,BBnode par,boolean ch){  
        BBnode enode=new BBnode(par,ch);  
        HeapNode h=new HeapNode(enode,up,size,lev);  
        heap.add(h);  
        Collections.sort(heap);  
    } 
    public int bbMaxClique(int[] bestx){  
        int n=bestx.length-1;  
        heap= new LinkedList<HeapNode>();
        //初始化(初始数据)  
        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]==1){  
                    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=heap.poll();  
            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 static void main(String[] args)
    {
        int[] c1={10,1,2,2,2,3,3,4,5,6,6,7,8,9};
        int[] c2={12,2,4,3,6,5,6,5,6,8,10,9,10,10};
        n=12;
        cn=0;
        bestn=0;
        bestx=new int[n+1];
        x=new int[n+1];
        a=new int[n+1][n+1];
        for(int h1=1;h1<a.length;h1++){
            a[0][h1]=h1;
            a[h1][0]=h1;
        }
        for(int h1=0;h1<c1.length;h1++){
            a[c1[h1]][c2[h1]]=1;
            a[c2[h1]][c1[h1]]=1;
        }
        BBClique bb=new BBClique(a);
        
        bestn=bb.bbMaxClique(bestx);
        System.out.println("*******优先队列分支界限法**********");
        System.out.println("敌对关系：");
        for(int h1=0;h1<c1.length;h1++){
            System.out.print(c1[h1]+" vs "+c2[h1]);
            System.out.println();
        }
        
        System.out.println("队伍最大人数达: "+bestn);
        System.out.print("分别是：");
        for(int h4=1;h4<bestx.length;h4++){
            if(bestx[h4]==1){
                System.out.print(h4+" ");
            }
        }
    }
}