计算机算法设计与分析最大团问题研究报告目录1. MCP问题描述 (1)1.1 MCP问题基本概念 (1)1.2 MCP问题数学描述 (1)2. MCP问题应用背景 (2)3. 求解MCP问题的常用算法 (2)3.1 顺序贪婪启发式算法 (2)3.2 局部搜索启发式算法 (2)3.3 智能搜索启发式算法 (3)3.3.1 遗传算法 (3)3.3.2 模拟退火算法 (3)3.3.3 禁忌算法 (4)3.3.4 神经网络算法 (4)3.4 改进蚁群算法-AntMCP (4)3.5 其它启发式算法 (5)3.6 回溯法 (6)3.6.1 算法基本思想 (6)3.6.2 算法设计思想 (6)3.6.3 实例分析 (7)3.6.4 程序设计及测试 (8)3.7 分支限界法 (11)3.7.1 算法描述 (11)3.7.2 算法求解流程 (12)3.7.3 优先队列式分支限界法求解MCP问题 (12)3.7.4 实例分析 (13)3.7.5 程序设计及测试 (13)4. 回溯法与分支限界法比较 (18)最大团问题及其求解算法研究最大团问题（Maximum Clique Problem, MCP ）是图论中一个经典的组合优化问题，也是一类NP 完全问题，在国际上已有广泛的研究，而国内对MCP 问题的研究则还处于起步阶段，因此，研究最大团问题具有较高的理论价值和现实意义。

最大团问题又称为最大独立集问题（Maximum Independent Set Problem ），在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。

目前，求解MCP 问题的算法主要分为两类：确定性算法和启发式算法。

确定性算法有回溯法、分支限界法等，启发式算法蚁群算法、顺序贪婪算法、DLS-MC 算法和智能搜索算法等。

不管哪种算法，都要求在多项式时间内求得MCP 问题的最优解或近似解。

图分为有向图和无向图，本文主要研究确定性算法求解无向图最大团问题。

1. MCP 问题描述1.1 MCP 问题基本概念给定无向图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.2 MCP 问题数学描述最大团问题作为一个整数规划问题有许多等价的描述，整数规划问题描述如下：设t : (0,1)n →2v ，t (x )={i ∈V : x i =1}，∀x ∈{0,1}n ，∀S ∈2v ，则x =t -1(S )={x i : i =1,2,…,n }，其中⎩⎨⎧∉∈=S i S i x i ,0,1，n 为图的顶点数。

∑=-=ni i x x f 1)(min (1)s.t. nj i x E j i x x }1,0{,),(,1∈'∈∀≤+。

如果x*是式(1)的最优解，则集合C =t (x*)是图G 的一个最大团，且|C |=-f (x*)。

由于x i , x j ∈{0,1}，x i +x j ≤1，∀(i , j )∈E '当且仅当x i x j =0，有x I A x x x x x f G T j i E j i j i n i i )(2)(,),(1-=+-='>'∈=∑∑，其中G A '为图G 的补图G'的邻接矩阵。

MCP 问题等价于下面的全局二次0/1问题：Ax x x f T =)(min (2)s.t. x ∈{0,1}n其中A =A G'-I 。

如果x*是式(2)的最优解，则集合C =t (x*)是图G 的一个最大团，且|C |=-f (x*)。

2. MCP 问题应用背景MCP 问题是现实世界中一类真实问题，在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。

自1957年Hararv 和Ross 首次提出求解最大团问题的确定性算法以来，研究者们已提出了多种确定性算法来求解最大团问题。

但随着问题规模的增大（顶点增多和边密度变大），求解问题的时间复杂度越来越高，确定性算法显得无能为力，不能有效解决这些NP 完全问题。

20世纪80年代末，研究者们开始尝试采用启发式算法求解最大团问题，提出了各种各样的启发式算法，如顺序贪婪启发式算法、遗传算法、模拟退火算法、禁忌搜索算法、神经网络算法等，并且取得了令人满意的效果。

在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、边密度的增加而变得越来越小。

唯一的缺点就是不一定能找到最优值，有时只能找到近优值。

近年来研究表明，单独使用一种启发式算法求解最大团问题，算法性能往往并不是很好，因此，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题。

当前求解该问题最好的启发式算法有反作用禁忌搜索（Reactive Tabu Search, RTS ）算法、基于遗传算法的简单启发式算法（Simple Heuristic Based Genetic Algorithm, HGA ）、DLS-MC 算法等。

3. 求解MCP 问题的常用算法本节首先对求解最大团问题的常用算法进行简要的阐述，然后重点对回溯法和分支限界法求解最大团问题进行着重分析，并用C++语言在Visual Studio 2008环境下编程实现。

3.1 顺序贪婪启发式算法顺序贪婪启发式算法是最早的求解最大团的启发式算法。

这类算法通过给一个团重复进行加点操作得到一个极大团或者对一组并不是团的子图重复进行删除顶点操作以得到一个团。

1987年，Kopf 和Ruhe 把这类型算法分为Best in 和Worst out 两类。

(1) Best in 方法的基本思路：由一个团出发，和这个团中顶点相连的顶点组成候选集；然后以一定的启发式信息，从中选择顶点加入团中，以后反复进行，直到最后得到一个极大团。

(2) Worst out 方法的基本思路：从整个顶点集开始，然后按一定的启发式信息，从中反复进行删除顶点操作，直到最后得到一个团。

顺序贪婪启发式算法有很大不足，该算法一旦找见一个极大团，搜索就停止，因此找到最大团的概率相对较低。

3.2 局部搜索启发式算法假设S G 为图的所有极大团的集合，由于顺序贪婪启发式算法仅能找见S G 中的一个极大团，因此，为了提高解的质量，应当扩大在S G 的搜索区域，比如，可以在极大团S 的邻居中继续进行搜索，以扩大搜索区域，进而提高解的质量。

在局部搜索启发式算法中，如果搜索S 的邻居越多，提高解的质量的机会就越大。

依赖不同的邻居定义，局部搜索启发式算法可以得到不同的解。

在局部搜索启发式算法中，比较有名的算法是K-interchange 启发式算法，它是一种基于K-neighbor邻居实现的，在解集S的K邻居中进行局部搜索的方法。

分析可知，局部搜索启发式算法存在一个问题，即仅能够找见一个局部最优值。

所以为了提高求解的质量，常把该算法和其它算法相混合，从而得到求解MCP问题的新的算法。

Wayne Pullan和Holger H．Hoos基于这一思想提出了求解最大团问题的DLS-MC算法，该算法是plateau search局部搜索启发式和算法迭代改善法相混合得到的，算法性能非常好，在该方法中引入了顶点惩罚函数，该函数在算法的求解过程中能够动态改变；在算法执行过程中迭代改善法和plateau search算法轮流执行来提高解的质量。

在基准图上对该算法进行了测试，性能非常好。

3.3 智能搜索启发式算法智能搜索算法主要有遗传算法、禁忌算法、模拟退火算法、神经网络等。

3.3.1 遗传算法遗传算法（Genetic Algorithm, GA）是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和自然遗传过程中发生的复制、交叉和变异现象。

1993年，Carter和Park首次提出使用遗传算法求解最大团问题，但由于所求解的质量差，计算复杂度高，因此，他们认为遗传算法并不适合求解最大团问题。

与此同时，Bäck和Khuri致力于最大独立集问题的求解，却得到了完全相反的结论，通过选用合适的适应度函数，取得了很好的效果。

因此在使用GA来解决最大团问题时，适应度函数起着非常关键的作用。

此后，基于遗传算法求解最大团问题的方法逐渐增多，但在提高解的质量，降低算法复杂度上方面却没有大幅度的提高。

l998年，Marchiori提出了一种基于遗传算法的简单启发式算法（simple heuristic based genetic algorithm, HGA)。

算法由两部分组成：简单遗传算法（simple genetic algorithm, SGA）和简单的贪婪启发式局部搜索算法（simple greedy heuristic local search algorithm, SGHLSA）。

在基准图上对算法HGA的性能进行测试，证明了该算法在解的质量和计算速度方面都优于基于遗传算法的其它算法。

因此，单纯使用遗传算法（改动变异、杂交、选择等算子）求解最大团问题时，算法的性能是比较差；要提高算法性能，遗传算法最好能和局部搜索算法相结合。

3.3.2 模拟退火算法模拟退火（Simulated Annealing, SA）算法是N. Metropolis在1953年提出的一种基于物质退火过程的随机搜索算法，是一种迭代求解的启发式随机搜索算法。

首先在高温下较快地进行搜索，使系统进入“热平衡”状态，大致地找到系统的低能区域。

随着温度的逐渐降低，搜索精度不断提高，可逐渐准确地找到最低能量的基态。

作为局部搜索算法的扩展，当邻域的一次操作使当前解的质量提高时，接受这个改进解作为新的当前解；反之，以一定的概率接受相对质量比较差的解作为新的当前解。