最大团问题的各种算法和源代码

I最大团问题目录1.MCP问题描述..........................................................................................................11.1MCP问题基本概念..........................................................................................11.2MCP问题数学描述..........................................................................................12.MCP问题应用背景..................................................................................................23.求解MCP问题的常用算法....................................................................................23.1顺序贪婪启发式算法......................................................................................23.2局部搜索启发式算法......................................................................................23.3智能搜索启发式算法......................................................................................33.3.1遗传算法.................................................................................................33.3.2模拟退火算法.........................................................................................33.3.3禁忌算法.................................................................................................43.3.4神经网络算法.........................................................................................43.4改进蚁群算法-AntMCP..................................................................................43.5其它启发式算法..............................................................................................53.6回溯法..............................................................................................................63.6.1算法基本思想.........................................................................................63.6.2算法设计思想.........................................................................................63.6.3实例分析.................................................................................................7II3.6.4程序设计及测试.....................................................................................83.7分支限界法....................................................................................................113.7.1算法描述...............................................................................................113.7.2算法求解流程.......................................................................................123.7.3优先队列式分支限界法求解MCP问题............................................123.7.4实例分析...............................................................................................133.7.5程序设计及测试...................................................................................134.回溯法与分支限界法比较....................................................................................181最大团问题及其求解算法研究最大团问题（MaximumCliqueProblem,MCP）是图论中一个经典的组合优化问题，也是一类NP完全问题，在国际上已有广泛的研究，而国内对MCP问题的研究则还处于起步阶段，因此，研究最大团问题具有较高的理论价值和现实意义。最大团问题又称为最大独立集问题（MaximumIndependentSetProblem），在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。目前，求解MCP问题的算法主要分为两类：确定性算法和启发式算法。确定性算法有回溯法、分支限界法等，启发式算法蚁群算法、顺序贪婪算法、DLS-MC算法和智能搜索算法等。不管哪种算法，都要求在多项式时间内求得MCP问题的最优解或近似解。图分为有向图和无向图，本文主要研究确定性算法求解无向图最大团问题。1.MCP问题描述1.1MCP问题基本概念给定无向图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'的最大独立集。1.2MCP问题数学描述最大团问题作为一个整数规划问题有许多等价的描述，整数规划问题描述如下：设t:(0,1)n→2v，t(x)={iV:xi=1}，x{0,1}n，S2v，则x=t-1(S)={xi:i=1,2,…,n}，其中SiSixi,0,1，n为图的顶点数。niixxf1)(min(1)s.t.njixEjixx}1,0{,),(,1。如果x*是式(1)的最优解，则集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。由于xi,xj{0,1}，xi+xj1，(i,j)E当且仅当xixj=0，有xIAxxxxxfGTjiEjijinii)(2)(,),(1，其中GA为图G的补图G'的邻接矩阵。MCP问题等价于下面的全局二次0/1问题：2AxxxfT)(min(2)s.t.x{0,1}n其中A=AG'-I。如果x*是式(2)的最优解，则集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。2.MCP问题应用背景MCP问题是现实世界中一类真实问题，在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。自1957年Hararv和Ross首次提出求解最大团问题的确定性算法以来，研究者们已提出了多种确定性算法来求解最大团问题。但随着问题规模的增大（顶点增多和边密度变大），求解问题的时间复杂度越来越高，确定性算法显得无能为力，不能有效解决这些NP完全问题。20世纪80年代末，研究者们开始尝试采用启发式算法求解最大团问题，提出了各种各样的启发式算法，如顺序贪婪启发式算法、遗传算法、模拟退火算法、禁忌搜索算法、神经网络算法等，并且取得了令人满意的效果。在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、边密度的增加而变得越来越小。唯一的缺点就是不一定能找到最优值，有时只能找到近优值。近年来研究表明，单独使用一种启发式算法求解最大团问题，算法性能往往并不是很好，因此，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题。当前求解该问题最好的启发式算法有反作用禁忌搜索（ReactiveTabuSearch,RTS）算法、基于遗传算法的简单启发式算法（SimpleHeuristicBasedGeneticAlgorithm,HGA）、DLS-MC算法等。3.求解MCP问题的常用算法本节首先对求解最大团问题的常用算法进行简要的阐述，然后重点对回溯法和分支限界法求解最大团问题进行着重分析，并用C++语言在VisualStudio2008环境下编程实现。3.1顺序贪婪启发式算法顺序贪婪启发式算法是最早的求解最大团的启发式算法。这类算法通过给一个团重复进行加点操作得到一个极大团或者对一组并不是团的子图重复进行删除顶点操作以得到一个团。1987年，Kopf和Ruhe把这类型算法分为Bestin和Worstout两类。(1)Bestin方法的基本思路：由一个团出发，和这个团中顶点相连的顶点组成候选集；然后以一定的启发式信息，从中选择顶点加入团中，以后反复进行，直到最后得到一个极大团。(2)Worstout方法的基本思路：从整个顶点集开始，然后按一定的启发式信息，从中反复进行删除顶点操作，直到最后得到一个团。顺序贪婪启发式算法有很大不足，该算法一旦找见一个极大团，搜索就停止，因此找到最大团的概率相对较低。3.2局部搜索启发式算法假设SG为图的所有极大团的集合，由于顺序贪婪启发式算法仅能找见SG中的一个极大团，因此，为了提高解的质量，应当扩大在SG的搜索区域，比如，可以在极大团S的邻居中继续进行搜索，以扩