最大团问题
目录
编辑本段概述
编辑本段问题描述
编辑本段应用背景
Tabu Search, RTS)算法、基于遗传算法的简单启发式算法(Simple Heuristic Based Genetic Algorithm, HGA)、DLS-MC算法等。
编辑本段常用算法
顺序贪婪启发式算法
局部搜索启发式算法
search算法轮流执行来提高解的质量。在基准图上对该算法进行了测试,性能非常好。
智能搜索启发式算法
遗传算法
genetic algorithm, SGA)和简单的贪婪启发式局部搜索算法(simple greedy heuristic local search algorithm,SGHLSA)。在基准图上对算法HGA的性能进行测试,证明了该算法在解的质量和计算速度方面都优于基于遗传算法的其它算法。
模拟退火算法
禁忌算法
神经网络算法
改进蚁群算法-AntMCP
p(v i);
∈E}
其它启发式算法
Edge-Weight Network,HEWN)算法,郭长庚和潘晓伟设计了一个实现HEWN算法的数据结构,指出在HEWN算法中HEWN算法的存储宜采用邻接多重表和二叉表相结合的链表表示法,并进行了时间复杂度分析,得出HEWN算法的时间复杂度是指数级而不是O(n^8.5)。针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题,张雁、党群等提出了一种新的基于匹配教程的Memetic算法。算法中提出交叉匹配度的概念,用来估计两个体交叉所能获得的最佳适应值。通过匹配度的计算对交叉方向的选择进行控制,保证了交叉操作以较大的概率生成新的优良模式。测试结果表明,该算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法。DNA计算是应用分子生物技术进行计算的新方法,具有高度并行性、大容量、低能耗等特点。针对这一特点,李涛提出了用DNA算法求解最大团问题,开创了以生物技术为工具解决复杂问题的新纪元,为解决NP完全问题开辟了一条新途径。基于对粘贴模型的组成、基本实验及其生化实现过程的分析,根据最大团问题的需求,周康、刘朔等在粘贴模型中,提出了基于电泳技术和分离实验的DNA序列检测方法。基于分离实验提出了一种求解最大团问题的DNA算法,并给出了其生化实现过程。为了提高交叉熵算法求解最大团问题的性能,吕强、柏战华等提出了一种领导者-跟随者协作求解的并行策略来实现交叉熵算法,从而达到减少计算时间和保障解的质量两者的平衡。算法中领导者活跃在并行处理器之间采集数据,并根据当前获得信息对跟随者作出决策;受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间,完成各自的集团产生任务。实验结果表明该算法较基于种群的启发式算法有一定的性能改善。
回溯法
如图1所示,给定无向图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的最大团。图2是无向图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'的最大
独立集。以图1为例,利用回溯法搜索其空间树,具体搜索过程(见图3所示)如下:假设我们按照1®2®3®4®5的顺序深度搜索。开始时,根结点R是唯一活结点,也是当前扩展结点,位于第1层,此时当前团的顶点数cn=0,最大团的顶点数bestn=0。在这个扩展结点处,我们假定R和第二层的顶点1之间有边相连,则沿纵深方向移至顶点1处。此时结点R和顶点1都是活结点,顶点1成为当前的扩展结点。此时当前团的顶点数cn=1,最大团的顶点数bestn=0。继续深度搜索至第3层顶点2处,此时顶点1和2有边相连,都是活结点,顶点2成为当前扩展结点。此时当前团的顶点数cn=2,最大团的顶点数bestn=0。再深度搜索至第4层顶点3处,由于顶点3和2有边相连但与顶点1无边相连,则利用剪枝函数剪去该枝,此时由于cn+n-i=2+5-4=3>bestn=0,则回溯到结点2处进入右子树,开始搜索。此时当前团的顶点数cn=2,最大团的顶点数bestn=0。再深度搜索至第5层顶点4处,由于顶点3和4无边相连,剪去该枝,回溯到结点3处进入右子树,此时当前团的顶点数cn=2,最大团的顶点数bestn=0。继续深度搜索至第6层顶点5处,由于顶点5和4有边相连,且与顶点1和2都有边相连,则进入左子树搜索。由于结点5是一个叶结点,故我们得到一个可行解,此时当前团的顶点数cn=3,最大团的顶点数bestn=3。vi的取值由顶点1至顶点5所唯一确定,即v=(1,
2, 5)。此时顶点5已不能再纵深扩展,成为死结点,我们返回到结点4处。由于此时cn+n-i=3+5-6=2<bestn=3,不能在右子树中找到更大的团,利用剪枝函数可将结点4的右结点剪去。以此回溯,直至根结点R再次成为当前的扩展结点,沿着右子树的纵深方向移动,直至遍历整个解空间。最后得到图1的按照1®2®3®4®5的顺序深度搜索的最大团为U={1,2,5}。当然{1,4,5}和{2,3,5}也是其最大团。
分支限界法
poj1129_四色问题
题意:染色问题,图中之间有边的两个区域不能染成相同的颜色。求将图中每个区域全部染色后需要最少的颜色。
分析:参考染色定理得,无论图中有多少区域,最多需要4个区域。因此遍历这四种情况即可.
代码:
Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <memory.h> 4 using namespace std; 5 6 const int maxnum=27; 7 bool array[maxnum][maxnum]; 8 int num; 9 10 void fuction() 11 { 12 int i,j,k,l; 13 for(i=1;i<=num;i++) 14 for(j=1;j<=num;j++) 15 for(k=1;k<=num;k++) 16 for(l=1;l<=num;l++) 17 if(array[i][j]&&array[i][k]&&array[i][l]&&array[j][k]&&array[j][l]&&array[k][l]) 18 { 19 printf("4 channels needed.\n"); 20 return ; 21 } 22 for(i=1;i<=num;i++) 23 for(j=1;j<=num;j++) 24 for(k=1;k<=num;k++) 25 if(array[i][j]&& array[i][k]&&array[j][k]) 26 { 27 printf("3 channels needed.\n"); 28 return; 29 } 30 for(i=1;i<=num;i++) 31 for(j=1;j<=num;j++) 32 if(array[i][j]) 33 { 34 printf("2 channels needed.\n"); 35 return; 36 } 37 printf("1 channel needed.\n"); 38 } 39 40 int main() 41 { 42 int i; 43 bool flag; 44 char ch,tch; 45 while(scanf("%d",&num)!=EOF) 46 { 47 if(num==0) break; 48 memset(array,false,sizeof(array)); 49 flag=false; 50 getchar(); 51 for(i=0;i<num;i++) 52 { 53 scanf("%c%c",&ch,&tch); 54 int a=ch-'A'+1; 55 while(scanf("%c",&ch)!=EOF) 56 { 57 if(ch=='\n') break; 58 int b=ch-'A'+1; 59 array[a][b]=true; 60 array[b][a]=true; 61 } 62 } 63 fuction(); 64 } 65 return 0; 66 }
另一种方法是最大团,我用最大团做完之后发现,其实这个题用最大团的解法是错误的。比如:
5
A:BE
B:AC
C:BD
D:CE
E:AD
这组数据用最大团做,ans=2,但是这个题的答案应该是3.可见这个题的数据有问题,最大团的代码见下、
Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <memory.h> 4 using namespace std; 5 //148K 0MS 6 7 const int maxnum=27; 8 bool array[maxnum][maxnum]; 9 int use[maxnum]; 10 int num,cn,bestn; 11 12 13 void dfs(int i) 14 { 15 if(i>num) 16 { 17 bestn=cn; 18 return ; 19 } 20 bool flag=true; 21 int j; 22 for(j=1;j<i;j++) 23 if(use[j] && !array[j][i]) 24 { 25 flag=false; 26 break; 27 } 28 if(flag) 29 { 30 cn++; 31 use[i]=true; 32 dfs(i+1); 33 cn--; 34 use[i]=false; 35 } 36 if(cn+num-i>bestn) 37 { 38 use[i]=false; 39 dfs(i+1); 40 } 41 } 42 43 int main() 44 { 45 int i; 46 char ch,tch; 47 while(scanf("%d",&num)&& num!=0) 48 { 49 memset(array,false,sizeof(array)); 50 memset(use,false,sizeof(use)); 51 cn=0; 52 bestn=0; 53 getchar(); 54 for(i=0;i<num;i++) 55 { 56 scanf("%c%c",&ch,&tch); 57 int a=ch-'A'+1; 58 while(scanf("%c",&ch) && ch!='\n') 59 { 60 int b=ch-'A'+1; 61 array[a][b]=true; 62 array[b][a]=true; 63 } 64 } 65 dfs(1); 66 if(bestn==1) 67 printf("1 channel needed.\n"); 68 else 69 printf("%d channels needed.\n",bestn); 70 } 71 return 0; 72 } 73 /* 74 6 75 A:BEF 76 B:AC 77 C:BD 78 D:CEF 79 E:ADF 80 F:ADE 81 */
tju oj 1077
poj3692_最大团_二分图
题意:已知班级有g个女孩和b个男孩,所有女生之间都相互认识,所有男生之间也相互认识,给出m对关系表示哪个女孩与哪个男孩认识。现在要选择一些学生来组成一个团,使得里面所有人都认识,求此团最大人数。
思路:最大团问题。
定理:
原图的最大团=补图的最大独立集
原图的最大独立集=补图的最大团。
由于这个题的补图显然是一个二分图,而二分图的补图的最大独立集可以由匈牙利算法求的,所以该题的最大团问题可以转化成补图的最大独立集来做。
代码:
Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <memory.h> 4 using namespace std; 5 const int maxnum=201; 6 bool array[maxnum][maxnum]; 7 bool use[maxnum]; 8 int res[maxnum]; 9 int b,g,m; 10 11 bool find(int i) 12 { 13 int j; 14 for(j=1;j<=b;j++) 15 { 16 if(!use[j] && array[i][j]) 17 { 18 use[j]=true; 19 if(res[j]==0 || find(res[j])) 20 { 21 res[j]=i; 22 return true; 23 } 24 } 25 } 26 return false; 27 } 28 29 int main() 30 { 31 int p,q; 32 int i,ans; 33 int k=0; 34 while(scanf("%d%d%d",&g,&b,&m)!=EOF) 35 { 36 if(g==0 && b==0 && m==0) 37 break; 38 memset(array,true,sizeof(array)); 39 memset(res,0,sizeof(res)); 40 for(i=0;i<m;i++) 41 { 42 scanf("%d%d",&p,&q); 43 array[p][q]=false; //补图 44 } 45 ans=0; 46 for(i=1;i<=g;i++) 47 { 48 memset(use,false,sizeof(use)); 49 if(find(i)) 50 ans++; 51 } 52 k++; 53 printf("Case %d: %d\n",k,b+g-ans); 54 } 55 return 0; 56 }
poj1419_染色_最大独立集_最大团
题意:
经典的图的染色问题,求对于给定的无向图中,给每个结点染两种不同颜色(黑色和白色)的一种且相邻结点的颜色不同,求染成黑色的最多结点数。
分析:
这个题求的图的最大独立集,最大独立集即为黑色节点的个数。
由于原图的最大独立集=补图的最大团。
而这个题是普通图,所以用回溯法来做,时间复杂度O(n*2^n)
代码:
Code
1 #include <iostream> 2 #include <memory.h> 3 #include <stdio.h> 4 using namespace std; 5 6 const int maxnum=101; 7 bool array[maxnum][maxnum]; 8 bool use[maxnum]; //进入团的标号 9 bool bestx[maxnum]; 10 int cn,bestn,p,e; 11 12 void dfs(int i) 13 { 14 int j; 15 bool flag; 16 17 if(i>p) 18 { 19 bestn=cn; //cn的值是递增的 20 // printf("%d\n",bestn); 21 // for(j=1;j<=p;j++) 22 // if(use[j]) 23 // printf("%d ",j); 24 // printf("\n"); 在这里输出不一定是最大团 25 for(j=1;j<=p;j++) //而是应该赋值给另外一个数组, 26 bestx[j]=use[j]; 27 return ; 28 } 29 30 flag=true; 31 for(j=1;j<i;j++) 32 if(use[j]&&!array[j][i]) 33 { 34 flag=false; 35 break; 36 } 37 if(flag) 38 { 39 cn++; 40 use[i]=true; 41 dfs(i+1); 42 cn--; 43 } 44 if(cn+p-i>bestn) //剪枝 45 { 46 use[i]=false; 47 dfs(i+1); 48 } 49 } 50 51 int main() 52 { 53 int num,i,u,v; 54 scanf("%d",&num); 55 while(num--) 56 { 57 memset(array,true,sizeof(array)); 58 memset(use,false,sizeof(use)); 59 memset(bestx,false,sizeof(bestx)); 60 scanf("%d%d",&p,&e); 61 for(i=0;i<e;i++) 62 { 63 scanf("%d%d",&u,&v); 64 array[u][v]=false; 65 array[v][u]=false; 66 } 67 68 cn=bestn=0; 69 dfs(1); 70 printf("%d\n",bestn); 71 for (i=1; i<=p; i++) 72 if(bestx[i]) 73 printf("%d ",i); 74 printf("\n"); 75 } 76 77 return 0; 78 } 79 80 /* 81 1 82 5 7 83 1 2 84 1 4 85 1 5 86 2 3 87 2 5 88 3 5 89 4 5 90 */
最大团
问题描述:团就是最大完全子图。
给定无向图G=(V,E)。如果UV,且对任意u,vU 有(u,v)
E,则称U 是G 的完全子图。
G 的完全子图U是G的团当且仅当U不包含在G 的更大的完全子图中,即U就是最大完全子图。
G 的最大团是指G中所含顶点数最多的团。
例如:
(a) (b) (c) (d)
图a是一个无向图,图b、c、d都是图a的团,且都是最大团。
求最大团的思路:
首先设最大团为一个空团,往其中加入一个顶点,然后依次考虑每个顶点,查看该顶点加入团之后仍然构成一个团,如果可以,考虑将该顶点加入团或者舍弃两种情况,如果不行,直接舍弃,然后递归判断下一顶点。对于无连接或者直接舍弃两种情况,在递归前,可采用剪枝策略来避免无效搜索。
为了判断当前顶点加入团之后是否仍是一个团,只需要考虑该顶点和团中顶点是否都有连接。
程序中采用了一个比较简单的剪枝策略,即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数,可停止继续深度搜索,否则继续深度递归
当搜索到一个叶结点时,即可停止搜索,此时更新最优解和最优值。
以下是转载的某篇论文的,百度文库的
http://wenku.baidu.com/view/1bd93526a5e9856a561260e2.html
3.6 回溯法
3.6.1 算法基本思想
回溯法(Backtracking Algorithm, BA)有“通用的解题法”之称,用它可以系统地搜索一个问题的所有解或任一解,是一个既带有系统性又带有跳跃性的搜索算法。在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解,如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按照深度优先的策略进行搜索。BA在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而BA在用来求问题的任一解时,只要搜索到问题的一个解即可结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。
回溯法搜索解空间树时,根节点首先成为一个活结点,同时也成为当前的扩展节点。在当前扩展节点处,搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活结点,并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动,则当前的扩展节点就成为死结点。此时,往回回溯至最近的一个活节点处,并使这个活结点成为当前的扩展节点。
回溯法以这种方式递归地在解空间中搜索,直至找到所有要求的解或解空间已无活结点为止。
3.6.2 算法设计思想
搜索:回溯法从根结点出发,按深度优先策略遍历解空间树,搜索满足约束条件的解。
剪枝:在搜索至树中任一结点时,先判断该结点对应的部分解是否满足约束条件,或者是否超出目标函数的界;也即判断该结点是否包含问题的解,如果肯定不包含,则跳过对以该结点为根的子树的搜索,即剪枝(Pruning);否则,进入以该结点为根的子树,继续按照深度优先的策略搜索。
一般来讲,回溯法求解问题的基本步骤如下:
(1) 针对所给问题,定义问题的解空间;
(2) 确定易于搜索的解空间结构;
(3) 以深度优先方式搜索解空间,并在搜索过程中利用Pruning函数剪去无效的搜索。
无向图G的最大团问题可以看作是图G的顶点集V的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点Z位于解空间树的第i层。在进入左子树前,必须确认从顶点i到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前,必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。
用邻接矩阵表示图G,n为G的顶点数,cn存储当前团的顶点数,bestn存储最大团的顶点数。cn+n-i为进入右子树的上界函数,当cn+n-i<bestn时,不能在右子树中找到更大的团,利用剪枝函数可将Z的右结点剪去。
3.6.3 实例分析
如图1所示,给定无向图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的最大团。
图2是无向图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'的最大独立集。
以图1为例,利用回溯法搜索其空间树,具体搜索过程(见图3所示)如下:假设我们按照1®2®3®4®5的顺序深度搜索。开始时,根结点R是唯一活结点,也是当前扩展结点,位于第1层,此时当前团的顶点数cn=0,最大团的顶点数bestn=0。在这个扩展结点处,我们假定R和第二层的顶点1之间有边相连,则沿纵深方向移至顶点1处。此时结点R和顶点1都是活结点,顶点1成为当前的扩展结点。此时当前团的顶点数cn=1,最大团的顶点数bestn=0。继续深度搜索至第3层顶点2处,此时顶点1和2有边相连,都是活结点,顶点2成为当前扩展结点。此时当前团的顶点数cn=2,最大团的顶点数bestn=0。再深度搜索至第4层顶点3处,由于顶点3和2有边相连但与顶点1无边相连,则利用剪枝函数剪去该枝,此时由于cn+n-i=2+5-4=3>bestn=0,则回溯到结点2处进入右子树,开始搜索。此时当前团的顶点数cn=2,最大团的顶点数bestn=0。再深度搜索至第5层顶点4处,由于顶点3和4无边相连,剪去该枝,回溯到结点3处进入右子树,此时当前团的顶点数cn=2,最大团的顶点数bestn=0。继续深度搜索至第6层顶点5处,由于顶点5和4有边相连,且与顶点1和2都有边相连,则进入左子树搜索。由于结点5是一个叶结点,故我们得到一个可行解,此时当前团的顶点数cn=3,最大团的顶点数bestn=3。vi的取值由顶点1至顶点5所唯一确定,即v=(1,
2, 5)。此时顶点5已不能再纵深扩展,成为死结点,我们返回到结点4处。由于此时cn+n-i=3+5-6=2<bestn=3,不能在右子树中找到更大的团,利用剪枝函数可将结点4的右结点剪去。以此回溯,直至根结点R再次成为当前的扩展结点,沿着右子树的纵深方向移动,直至遍历整个解空间。最后得到图1的按照1®2®3®4®5的顺序深度搜索的最大团为U={1,2,5}。当然{1,4,5}和{2,3,5}也是其最大团。
代码:
Code
1 #include <iostream> 2 #include <memory.h> 3 #include <stdio.h> 4 using namespace std; 5 6 const int maxnum=101; 7 bool array[maxnum][maxnum]; 8 bool use[maxnum]; //进入团的标号 9 int cn,bestn,p,e; 10 11 void dfs(int i) 12 { 13 int j; 14 bool flag; 15 16 if(i>p) 17 { 18 bestn=cn; 19 printf("%d\n",bestn); 20 for(j=1;j<=p;j++) 21 if(use[j]) 22 printf("%d ",j); 23 printf("\n"); 24 return ; 25 } 26 27 flag=true; 28 for(j=1;j<i;j++) 29 if(use[j]&&!array[j][i]) 30 { 31 flag=false; 32 break; 33 } 34 if(flag) 35 { 36 cn++; 37 use[i]=true; 38 dfs(i+1); 39 cn--; 40 } 41 if(cn+p-i>bestn) //剪枝 42 { 43 use[i]=false; 44 dfs(i+1); 45 } 46 } 47 48 int main() 49 { 50 int num,i,u,v; 51 scanf("%d",&num); 52 while(num--) 53 { 54 memset(array,false,sizeof(array)); 55 memset(use,false,sizeof(use)); 56 scanf("%d%d",&p,&e); 57 for(i=0;i<e;i++) 58 { 59 scanf("%d%d",&u,&v); 60 array[u][v]=true; 61 array[v][u]=true; 62 } 63 64 cn=bestn=0; 65 dfs(1); 66 //printf("%d\n",bestn); 67 } 68 69 return 0; 70 } 71 72 /* 73 1 74 5 7 75 1 2 76 1 4 77 1 5 78 2 3 79 2 5 80 3 5 81 4 5 82 */