最大团算法研究课件

1、2009最大团算法研究主要介绍：Company Logo最大团定义以其研究进展1最大团的算法介绍2回溯法和分支限界法详细介绍3最大团的应用4MCP描述Company Logo最大团问题 (Maximum Clique Problem, MCP)描述： 对于给定图G( V，E)， 其中，V =(1，n)是图G的顶点集，E VxV是图G的边集。图G的团就是一两两之间有边的顶点集合。如果一个团不被其它任一团所包含，即它不是其它任一团的真子集，则称该团为图G的极大团。顶点最多的极大团，称之为图G的最大团。 最大团问题的目标就是要找到给定图的最大团。MCP数学描述Company Logo MCP作为一个

2、整数规划问题有许多等价的描述。整数规划问题的描述(二次0-1问题)：则设其中，n为图的顶点数。MCP数学描述Company Logo由于（1） 如果 是（1）的最优解，那么集合C= 是图G的最大团，且MCP数学描述Company Logo因此有其中： 图G的补图 的邻接矩阵。MCP等价于下面的全局二次0-1问题其中：如果 是（2）的最优解，那么集合 是图G的一个最大团，且（2）算法研究进展Company Logo神经网络模拟退火禁忌搜索基于连续的启发式算法遗传算法19901989198719571993now反作用禁忌搜索算法、简单启发式算法、DLSMC 1957年，Hararv和Ross首次

3、提出求解最大团问题的确定性算法 。但随着研究的深入，遇到的问题复杂度越来越高(顶点增多和边密度变大)，确定性算法显得无能为力，不能有效解决这些NP完全问题，典型地体现是运行时间过长。 在20世纪80年代末开始采用启发式算法求解最大团问题，并且取得了令人满意的效果。在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、密度的增加而变得越来越小。唯一的缺点就是不一定能找到最优值，有时只能找到近优值。 研究表明，单独使用一种启发式算法求解最大团问题，算法性能并不是很好，因此，需要算法之间互相取长补短，形成新的混合算法来求解最大团问题。当前求解该问题最好的

4、启发式算法有反作用禁忌搜索算法(Reactive Tabu Search)、简单启发式算法(Simple Heuristic Based Genetic Algorithm，HGA)和DLSMC等。MCP启发式算法介绍Company Logo 局部搜索启发式算法存在一个问题是：仅能够找见一个局部最优值。所以为了提高求解的质量，该算法和其它算法相混合得到新性能好的算法。假设 为图的所有极大团的集合，扩大 在的搜索区域，比如，可以在极大团S的邻居中继续进行搜索，以扩大搜索区域，进而提高解的质量 。依赖不同的邻居定义，局部搜索启发式算法可以得到不同的解。局部搜索启发式算法DLSMC算法plateau

5、 search局部搜索启发式和算法迭代改善法相混合得到的，该方法中引入了顶点惩罚函数，函数在算法的求解过程中能够动态改变；在算法执行过程中迭代改善法和plateau search算法轮流执行来提高解的质量。MCP启发式算法介绍Company Logo智能搜索算法遗传算法其他算法禁忌算法模拟退火算法神经网络MCP启发式算法介绍Company Logo 一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和自然遗传过程中发生的复制、交叉和变异现象，适应度函数起着非常关键的作用。遗传算法简单启发式算法 HGA 算法由两部分组成：简单遗传算法(SGA)和简单的贪婪启发式局部搜索算法。在基准图上对

6、算法HGA的性能进行测试，证明了该算法在解的质量和计算速度方面都优于基于遗传算法的其它算法。MCP详细算法介绍Company Logo回溯法分支限界法MCP回溯法详细介绍Company Logo问题描述 给定无向图G=(V，E)。如果U V，且对任意u，v U有(u，v) E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 下图G中，子集1，2是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图1，2，5包含。1，2，5是G的最大团。1，4，5和2，3，5也是G的最大团。 12453MCP回溯法详细

7、介绍Company Logo回溯法基本思想 回溯法按照深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死结点。此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点。 回溯法以这种方式

8、递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点为止。MCP回溯法详细介绍Company Logo算法设计 无向图G的最大团问题可以看作是图G的顶点集V的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点Z位于解空间树的第i层。在进入左子树前，必须确认从顶点i到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。 用邻接矩阵表示图G，n为G的顶点数，cn存储当前团的顶点数，bestn存储最大团的顶点数。cn+n-i为进入右子树的上界函数，当cn+n-ibestn时，右子树中可能含有最优解，此时将右儿

9、子结点加入到子集树中并插入到活结点优先队列中。优先队列式分支限界法求最大团 终止条件 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。34343优先队列式分支限界法求最大团示例说明1132224333343XX244444444444RXXXXXX55XXXXXXXXXXXXXXXXXXXXXXXXcliqueSize CSupper

10、Size USBestn BNCS=1 BN=1 US=5 CS=0 BN=1 US=40节点 CS=0 BN=0 US=5CS=2 BN=2 US=5CS=1 BN=2 US=4CS=1BN=2 US=3CS=1 BN=2 US=4CS=0 BN=2 US=312345678910111213141516R1112223CS=2 BN=2 US=41222332CS=2 BN=2 US=43CS=2 BN=2 US=334CS=2 BN=2 US=323CS=1 BN=2 US=33CS=0 BN=2 US=234CS=1BN=2 US=24CS=2 BN=2 US=35CS=3 BN=3 US=3CS=US 出现最大团 BN=3算法比较MCP分支限界法与回溯法的比较MCP应用 最大团问题是图论中的一个经