最大團問題-分支限界

問題描述：

　　給定無向圖G=(V, E)，其中V是非空集合，稱為頂點集；

　　E是V中元素構成的無序二進制組的集合，稱為邊集，無向圖中的邊均是頂點的無序對，無序對常用圓括号“( )”表示。

　　如果U∈V，且對任意兩個頂點u，v∈U有(u, v)∈E，則稱U是G的完全子圖。

　　G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數最多的團。

　　如果U∈V且對任意u，v∈U有(u, v)∈E，則稱U是G的空子圖。G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子圖中。G的最大獨立集是G中所含頂點數最多的獨立集。

　　對于任一無向圖G=(V, E)，其補圖G'=(V', E')定義為：V'=V，且(u, v)∈E'當且僅當(u, v)∈E。

　　如果U是G的完全子圖，則它也是G'的空子圖，反之亦然。是以，G的團與G'的獨立集之間存在一一對應的關系。特殊地，U是G的最大團當且僅當U是G'的最大獨立集。

問題定義：

　　解空間樹中結點類型：bbnode

　　活結點優先隊列中元素類型為 CliqueNode（cn 表示與該節點相應的團的定點數，un表示結點為根的子樹中的最大頂點樹的上界。level表示結點在子集空間樹中所處的層次；ch 左右兒子的結點标記）

　　ch=1  左兒子  ch=0  右兒子

　　ptr 指向解空間樹中相應結點的指針

　　cn+n-level+1表示定點數上界的un值。

代碼描述：

相關結構體定義:

class bbnode{
    friend class Clique;
private:
    bbnode * parent;
    bool LChild;
};
class CliqueNode{
    friend class Clique;
public:
    operator int () const {return un;}
private:
    int cn,
        un,
        level;
    bbnode *ptr;
};
class Clique{
    friend void main(void);
public:
    int BBMaxClique(int []);
private:
    void AddLiveNode(MaxHeap<CliqueNode> &H,int cn,int un,int level,bbnode E[],bool ch);
    int * * a ,n;
};      

AddLiveNode：将目前構造的活結點 加入到子集空間樹中并插入活結點優先隊列中。

void Clique::AddLiveNode(MaxHeap<CliqueNode> &H,int cn,int un,int level,bbnode E[],bool ch)
{
    bbnode * b = new bbnode;
    b->parent = E;
    b->LChild = ch;
    CliqueNode N;
    N.cn = cn;
    N.level = level;
    N.un = un;
    N.Insert(N);
}      

算法核心代碼：BBMaxClique

子集樹的根節點是 初始擴充結點 cn為0      

i 表示目前擴充結點的解空間樹中所處的層次。

首先考察左兒子：

　　頂點加入目前團，檢查該頂點與目前團中其他頂點是否有邊相連。

　　都有邊，可行，納入 活結點 優先隊列中,AddLiveNode(),接着考察目前擴充結點的 右兒子結點，僅當un>bestn時，右子樹中可能含有最優解  ；

　　否則，不可行。

int Clique::BBMaxClique(int bestx[])
{
    MaxHeap<CliqueNode> H(1000);
    bbnode * E = 0;
    int i=1,
        cn = 0,
        bestn = 0;
    while(i != n+1)
    {
        bool OK = true;
        bbnode * B = E;
        for(int j = i-1;j>0;B=B->parent,j--)
        {
            if(B->LChild && a[i][j]==0)
            {
                OK = false;
                break;
            }
        }
        if(OK)
        {
            if(cn + 1 > bestn)
                bestn = cn + 1;
            AddLiveNode(H,cn+1,cn+n-i+1,i+1,E,true);
        }
        if(cn+n-i >= bestn)
            AddLiveNode(H,cn+1,cn+n-i+1,i+1,E,true);
        CliqueNode N;
        H.DeleteMax(N);
        E = N.ptr;
        cn = N.cn;
        i = N.level;
    }
    for(int j=n;j>0;j--)
    {
        bestx[j] = E->LChild;
        E = E->parent;
    }
    return bestn;
}      

作者：xingoo