0037算法笔记——分支限界法最大团问题

1、问题描述     给定无向图G=(V, E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果UV，且对任意两个顶点u，vU有(u, v)E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。     如果UV且对任意u，vU有(u, v)不属于E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大

2、的空子图中。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'的最大独立集。     例：如图所示，给定无向图G=V, E，其中V=1,2,3,4,5，E=(1,2),

3、(1,4), (1,5),(2,3), (2,5), (3,5), (4,5)。根据最大团(MCP)定义，子集1,2是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图1,2,5之中。1,2,5是G的一个最大团。1,4,5和2,3,5也是G的最大团。右侧图是无向图G的补图G'。根据最大独立集定义，2,4是G的一个空子图，同时也是G的一个最大独立集。虽然1,2也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图1,2,5中。1,2,5是G'的最大独立集。1,4,5和2,3,5也是G'的最大独立集。  &

4、#160;  算法设计      最大团问题的解空间树也是一棵子集树。子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。 算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。     接着继续考察当前扩展结点的右儿子结点。当upperSize>bestn时

5、，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。    对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。     算法具体实现如下：     1、MaxHeap.hcpp view plain copy1

6、. template<class T>  2. class MaxHeap  3.   4.     public:  5.         MaxHeap(int MaxHeapSize = 10);  6.         MaxHe

7、ap() delete  heap;  7.         int Size() const return CurrentSize;  8.   9.         T Max()   10.       

8、            /查  11.            if (CurrentSize = 0)  12.              13.   

9、;              throw OutOfBounds();  14.              15.            return heap1; &#

10、160;16.           17.   18.         MaxHeap<T>& Insert(const T& x); /增  19.         MaxHeap<T>& Delet

11、eMax(T& x);   /删  20.   21.         void Initialize(T a, int size, int ArraySize);  22.   23.     private:  24.     

12、    int CurrentSize, MaxSize;  25.         T *heap;  / element array  26. ;  27.   28. template<class T>  29. MaxHeap<T>:MaxHeap(int 

13、MaxHeapSize)  30. / Max heap constructor.  31.     MaxSize = MaxHeapSize;  32.     heap = new TMaxSize+1;  33.     CurrentSize = 0;  34.

14、60; 35.   36. template<class T>  37. MaxHeap<T>& MaxHeap<T>:Insert(const T& x)  38. / Insert x into the max heap.  39.     if (CurrentSize = Max

15、Size)  40.       41.         cout<<"no space!"<<endl;   42.         return *this;   43.      

16、 44.   45.     / 寻找新元素x的位置  46.     / i初始为新叶节点的位置，逐层向上，寻找最终位置  47.     int i = +CurrentSize;  48.     while (i != 1 &&

17、0;x > heapi/2)  49.       50.         / i不是根节点，且其值大于父节点的值，需要继续调整  51.         heapi = heapi/2; / 父节点下降  52.   &#

18、160;     i /= 2;              / 继续向上，搜寻正确位置  53.       54.   55.    heapi = x;  56.    ret

19、urn *this;  57.   58.   59. template<class T>  60. MaxHeap<T>& MaxHeap<T>:DeleteMax(T& x)  61. / Set x to max element and delete max element from hea

20、p.  62.     / check if heap is empty  63.     if (CurrentSize = 0)  64.       65.         cout<<"Empty h

21、eap!"<<endl;   66.         return *this;   67.       68.   69.     x = heap1; / 删除最大元素  70.     / 重

22、整堆  71.     T y = heapCurrentSize-; / 取最后一个节点，从根开始重整  72.   73.     / find place for y starting at root  74.     int i = 1,&#

23、160; / current node of heap  75.        ci = 2; / child of i  76.   77.     while (ci <= CurrentSize)   78.    &

24、#160;  79.         / 使ci指向i的两个孩子中较大者  80.         if (ci < CurrentSize && heapci < heapci+1)  81.       &#

25、160;   82.             ci+;  83.           84.         / y的值大于等于孩子节点吗？  85.      

26、0;  if (y >= heapci)  86.           87.             break;   / 是，i就是y的正确位置，退出  88.       

27、60;   89.   90.         / 否，需要继续向下，重整堆  91.         heapi = heapci; / 大于父节点的孩子节点上升  92.         i = 

28、ci;             / 向下一层，继续搜索正确位置  93.         ci *= 2;  94.       95.   96.     heapi = y;&

29、#160; 97.     return *this;  98.   99.   100. template<class T>  101. void MaxHeap<T>:Initialize(T a, int size,int ArraySize)  102. / Initialize max heap to&#

30、160;array a.  103.     delete  heap;  104.     heap = a;  105.     CurrentSize = size;  106.     MaxSize = ArraySize;  107. &

31、#160; 108.     / 从最后一个内部节点开始，一直到根，对每个子树进行堆重整  109.    for (int i = CurrentSize/2; i >= 1; i-)  110.      111.         T y&

32、#160;= heapi; / 子树根节点元素  112.         / find place to put y  113.         int c = 2*i; / parent of c is target 

33、; 114.                    / location for y  115.         while (c <= CurrentSize)   116.   &

34、#160;       117.             / heapc should be larger sibling  118.             if (c < Curr

35、entSize && heapc < heapc+1)  119.               120.                 c+;  121.    &#

36、160;          122.             / can we put y in heapc/2?  123.             if (y

37、0;>= heapc)  124.               125.                 break;  / yes  126.      

38、0;        127.   128.             / no  129.             heapc/2 = heapc; / move child

39、0;up  130.             c *= 2; / move down a level  131.           132.         heapc/2 =&

40、#160;y;  133.       134.        2、6d6.cppcpp view plain copy1. /最大团问题 优先队列分支限界法求解   2. #include "stdafx.h"  3. #include "MaxHeap.h"  4. #include <i

41、ostream>  5. #include <fstream>  6. using namespace std;  7.   8. const int N = 5;/图G的顶点数  9. ifstream fin("6d6.txt");     10.   11. class bbnode 

42、 12.   13.     friend class Clique;  14.     private:  15.         bbnode *parent;     /指向父节点的指针  16.      

43、60;  bool LChild;        /左儿子节点标识  17. ;  18.   19. class CliqueNode  20.   21.     friend class Clique;  22.     public: 

44、60;23.         operator int() const  24.              25.             return un;  26.   &#

45、160;       27.     private:  28.         int cn,         /当前团的顶点数  29.           

46、0; un,         /当前团最大顶点数的上界  30.             level;      /节点在子集空间树中所处的层次  31.         bbnode *p

47、tr;    /指向活节点在子集树中相应节点的指针  32. ;  33.   34. class Clique  35.   36.     friend int main(void);  37.     public:  38.       &#

48、160; int BBMaxClique(int );  39.     private:  40.         void AddLiveNode(MaxHeap<CliqueNode>&H,int cn,int un,int level,bbnode E,bool ch);  41.  

49、60;      int *a,        /图G的邻接矩阵  42.             n;          /图G的顶点数  43. ;  44.

50、60; 45. int main()  46.   47.     int bestxN+1;  48.     int *a = new int *N+1;    49.     for(int i=1;i<=N;i+)     &

51、#160;50.           51.         ai = new intN+1;      52.        53.       54.    

52、0;cout<<"图G的邻接矩阵为:"<<endl;  55.     for(int i=1; i<=N; i+)    56.         57.         for(int j=1; j<=N; j+)

53、0;   58.             59.             fin>>aij;        60.           &

54、#160; cout<<aij<<" "      61.             62.         cout<<endl;    63.       64.

55、   65.     Clique c;  66.     c.a = a;  67.     c.n = N;  68.   69.     cout<<"图G的最大团顶点个数为："<<c.BBMaxClique(bestx)<<e

56、ndl;  70.     cout<<"图G的最大团解向量为："<<endl;  71.     for(int i=1;i<=N;i+)      72.          73.        

57、 cout<<bestxi<<" "  74.        75.     cout<<endl;  76.   77.     for(int i=1;i<=N;i+)      78.     

58、;     79.         delete ai;     80.        81.     delete a;  82.     return 0;  83.   84

59、.   85. /将活节点加入到子集空间树中并插入到最大堆中  86. void Clique:AddLiveNode(MaxHeap<CliqueNode> &H, int cn, int un, int level, bbnode E, bool ch)  87.   88.     bbnode *b =

60、0;new bbnode;  89.     b->parent = E;  90.     b->LChild = ch;  91.   92.     CliqueNode N;  93.     N.cn = cn;  9

61、4.     N.ptr = b;  95.     N.un = un;  96.     N.level = level;  97.     H.Insert(N);  98.   99.   100. /解最大团问题的优先队列式分支限界法 &#

62、160;101. int Clique:BBMaxClique(int bestx)  102.   103.     MaxHeap<CliqueNode> H(1000);  104.   105.     /初始化  106.     bbnode *E = 0;  107. &#

63、160;   int i = 1,  108.         cn = 0,  109.         bestn = 0;  110.   111.     /搜集子集空间树  112.

64、60;   while(i!=n+1)/非叶节点  113.       114.         /检查顶点i与当前团中其他顶点之间是否有边相连  115.         bool OK = true;  116.    &#

65、160;    bbnode *B = E;  117.         for(int j=i-1; j>0; B=B->parent,j-)  118.           119.       

66、0;     if(B->LChild && aij=0)  120.               121.                 OK = false;  122.                 break;  123.               124.