0037算法笔记——【分支限界法】最大团问题.doc

问题描述 给定无向图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的更大的空子图中。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), (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的最大独立集。 算法设计 最大团问题的解空间树也是一棵子集树。子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当upperSizebestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。 算法具体实现如下： 1、MaxHeap.hcppview plaincopy1. template2. classMaxHeap3. 4. public:5. MaxHeap(intMaxHeapSize=10);6. MaxHeap()deleteheap;7. intSize()constreturnCurrentSize;8. 9. TMax()10. /查11. if(CurrentSize=0)12. 13. throwOutOfBounds();14. 15. returnheap1;16. 17. 18. MaxHeap&Insert(constT&x);/增19. MaxHeap&DeleteMax(T&x);/删20. 21. voidInitialize(Ta,intsize,intArraySize);22. 23. private:24. intCurrentSize,MaxSize;25. T*heap;/elementarray26. ;27. 28. template29. MaxHeap:MaxHeap(intMaxHeapSize)30. /Maxheapconstructor.31. MaxSize=MaxHeapSize;32. heap=newTMaxSize+1;33. CurrentSize=0;34. 35. 36. template37. MaxHeap&MaxHeap:Insert(constT&x)38. /Insertxintothemaxheap.39. if(CurrentSize=MaxSize)40. 41. coutnospace!heapi/2)49. 50. /i不是根节点，且其值大于父节点的值，需要继续调整51. heapi=heapi/2;/父节点下降52. i/=2;/继续向上，搜寻正确位置53. 54. 55. heapi=x;56. return*this;57. 58. 59. template60. MaxHeap&MaxHeap:DeleteMax(T&x)61. /Setxtomaxelementanddeletemaxelementfromheap.62. /checkifheapisempty63. if(CurrentSize=0)64. 65. coutEmptyheap!endl;66. return*this;67. 68. 69. x=heap1;/删除最大元素70. /重整堆71. Ty=heapCurrentSize-;/取最后一个节点，从根开始重整72. 73. /findplaceforystartingatroot74. inti=1,/currentnodeofheap75. ci=2;/childofi76. 77. while(ci=CurrentSize)78. 79. /使ci指向i的两个孩子中较大者80. if(ciCurrentSize&heapci=heapci)86. 87. break;/是，i就是y的正确位置，退出88. 89. 90. /否，需要继续向下，重整堆91. heapi=heapci;/大于父节点的孩子节点上升92. i=ci;/向下一层，继续搜索正确位置93. ci*=2;94. 95. 96. heapi=y;97. return*this;98. 99. 100. template101. voidMaxHeap:Initialize(Ta,intsize,intArraySize)102. /Initializemaxheaptoarraya.103. deleteheap;104. heap=a;105. CurrentSize=size;106. MaxSize=ArraySize;107. 108. /从最后一个内部节点开始，一直到根，对每个子树进行堆重整109. for(inti=CurrentSize/2;i=1;i-)110. 111. Ty=heapi;/子树根节点元素112. /findplacetoputy113. intc=2*i;/parentofcistarget114. /locationfory115. while(c=CurrentSize)116. 117. /heapcshouldbelargersibling118. if(cCurrentSize&heapc=heapc)124. 125. break;/yes126. 127. 128. /no129. heapc/2=heapc;/movechildup130. c*=2;/movedownalevel131. 132. heapc/2=y;133. 134. 2、6d6.cppcppview plaincopy1. /最大团问题优先队列分支限界法求解2. #includestdafx.h3. #includeMaxHeap.h4. #include5. #include6. usingnamespacestd;7. 8. constintN=5;/图G的顶点数9. ifstreamfin(6d6.txt);10. 11. classbbnode12. 13. friendclassClique;14. private:15. bbnode*parent;/指向父节点的指针16. boolLChild;/左儿子节点标识17. ;18. 19. classCliqueNode20. 21. friendclassClique;22. public:23. operatorint()const24. 25. returnun;26. 27. private:28. intcn,/当前团的顶点数29. un,/当前团最大顶点数的上界30. level;/节点在子集空间树中所处的层次31. bbnode*ptr;/指向活节点在子集树中相应节点的指针32. ;33. 34. classClique35. 36. friendintmain(void);37. public:38. intBBMaxClique(int);39. private:40. voidAddLiveNode(MaxHeap&H,intcn,intun,intlevel,bbnodeE,boolch);41. int*a,/图G的邻接矩阵42. n;/图G的顶点数43. ;44. 45. intmain()46. 47. intbestxN+1;48. int*a=newint*N+1;49. for(inti=1;i=N;i+)50. 51. ai=newintN+1;52. 53. 54. cout图G的邻接矩阵为:endl;55. for(inti=1;i=N;i+)56. 57. for(intj=1;jaij;60. coutaij;61. 62. coutendl;63. 64. 65. Cliquec;66. c.a=a;67. c.n=N;68. 69. cout图G的最大团顶点个数为：c.BBMaxClique(bestx)endl;70. cout图G的最大团解向量为：endl;71. for(inti=1;i=N;i+)72. 73. coutbestxi;74. 75. coutendl;76. 77. for(inti=1;i=N;i+)78. 79. deleteai;80. 81. deletea;82. return0;83. 84. 85. /将活节点加入到子集空间树中并插入到最大堆中86. voidClique:AddLiveNode(MaxHeap&H,intcn,intun,intlevel,bbnodeE,boolch)87. 88. bbnode*b=newbbnode;89. b-parent=E;90. b-LChild=ch;91. 92. CliqueNodeN;93. N.cn=cn;94. N.ptr=b;95. N.un=un;96. N.level=level;97. H.Insert(N);98. 99. 100. /解最大团问题的优先队列式分支限界法101. intClique:BBMaxClique(intbestx)102. 103. MaxHeapH(1000);104. 105. /初始化106. bbnode*E=0;107. inti=1,108. cn=0,109. bestn=0;110. 111. /搜集子集空间树112. while(i!=n+1)/非叶节点113. 114. /检查顶点i与当前团中其他顶点之间是否有边相连115. boolOK=true;116. bbnode*B=E;117. for(intj=i-1;j0;B=B-parent,j-)118. 119. if(B-LChild&aij=0)120. 121. OK=false;122. break;123. 124. 125. 126. if(OK)/左儿子节点为可行结点127. 128. if(cn+1bestn)129. 130. bestn=cn+1;131. 132. AddLiveNode(H,cn+1,cn+n-i+1,i+1,E,true);133. 134. 135. if(cn+n-i=bestn)/右子树可能含有最优解136.