回溯法——最大团问题（Maximum Clique Problem, MCP）

时间：2022-12-21 14:03:17

概述：

　　最大团问题（Maximum Clique Problem, MCP）是图论中一个经典的组合优化问题，也是一类NP完全问题。最大团问题又称为最大独立集问题（Maximum Independent Set Problem）。目前，求解MCP问题的算法主要分为两类：确定性算法和启发式算法。确定性算法有回溯法、分支限界法等，启发式算法、蚁群算法、顺序贪婪算法、DLS-MC算法和智能搜索算法等。

问题描述：

　　给定无向图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'的最大独立集。

算法分析：

　　无向图G的最大团和最大独立集问题都可以用回溯法在O（n2n）时间内解决。图G的最大团和最大独立集问题都可以看作是图G的顶点集V的子集选取问题。因此可用子集树表示问题的解空间。
　　设当前扩展节点Z位于解空间树的第 i 层。在进入左子树前，必须确认从顶点 i 到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。

算法描述：

 #include <fstream>

 #include <iostream>

 #include <stdlib.h>

 #include <conio.h>

 using namespace std;

 #define MAX_v 50 //定义一个最大顶点个数

 typedef struct{

     int a[MAX_v][MAX_v]; //无向图G的邻接矩阵

     int v; //无向图G的顶点

     int e; //无向图G的边

     int x[]; //顶点与当前团的连接，x[i]=1 表示有连接——即x[i]==1代表在当前最大团的解内

     int bestx[]; //当前最优解

     int cnum; //当前团的顶点数目

     int bestn; //最大团的顶点数目

 }MCP;

 void Creat(MCP &G);

 void Backtrack(MCP &G,int i);

 void Creat(MCP &G){

     int i,j;

     ifstream fin("data.txt");

     if (!fin)

     {

         cout<<"不能打开文件:"<<"data.txt"<<endl;

         exit();

     }

     fin>>G.v;

     for (int i=;i<=G.v;i++)

         for (int j=;j<=G.v;j++)

             fin>>G.a[i][j];

     for(i=;i<=G.v;i++) //初始化

     {

         G.bestx[i]=;

         G.x[i]=;

         G.bestn=;

         G.cnum=;

     }

     cout<<"———回溯法求解最大团问题———"<<endl;

     cout<<"输入初始化无向图矩阵为:"<<endl; //初始化

     for(i=;i<=G.v;i++)

     {

         for(j=;j<=G.v;j++)

             cout<<G.a[i][j]<<" ";

         cout<<endl;

     }

 }

 void Backtrack(MCP &G,int i){

     if (i>G.v){        //output()阶段

         for (int j=; j<=G.v; j++)

             G.bestx[j] = G.x[j];    //记录最优解

         G.bestn =G.cnum;

         return ;

     }

     //检查顶点i与当前团的连接

     int OK = ;

     for (int j=; j<=i ; j++)

         if (G.x[j]&& G.a[i][j]==){        //G.x[j]:顶点j在当前解的最大团内；G.a[i][j]:待考察i顶点与最大团中前i-1个顶点间边的关系

             //i不与j相连

             OK = ;

             break;

         }

         if (OK) {        //进入左子树

             G.x[i] = ;//把i加入团

             G.cnum++;

             Backtrack(G,i+);

             G.x[i]=;

             G.cnum-- ;

         }

         if (G.cnum+G.v- i>G.bestn){        //进入右子树——剪枝函数

             G.x[i] = ;

             Backtrack(G,i+);

         }

 }

 int main(){

     MCP G;

     Creat(G);

     Backtrack(G,);

     cout<<"最大团包含的顶点数为:"<<G.bestn<<endl;

     cout<<"最大团方案为:( ";

     for (int i=;i<=G.v;i++)

         if(G.bestx[i]==){

             cout<<i<<" ";

         }

         cout<<")"<<endl;

         getch();

 }

 注：问题在于这种解法只能求得其中的一个最大团解！

最大团问题百度百科：http://baike.baidu.com/view/7343867.htm

相关文章