印尼
最大团问题（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中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果UV，且对任意两个顶点u，vU有(u, v)undefinedE，则称U是G的完全子图。G的完全子图数学模型的作用U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。
如果UundefinedV且对任意u，vU有(u, v)undefinedE，则称U是G的空子图。G京唐港邮编的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。
对于任一无向图G=(V, E)，其补图G'=(V', E')定义为：V'=V，且(u, v)undefinedE'当且仅当(u, v)undefinedE。
如果U是G的完全子图，则它也是G'的空子图，反之亦然。因此，G的团与G'的独立集之间
存在一一对应的关系。特殊地，U是G的最大团当且仅当U是G'的最大独立集。
1.2 MCP问题数学描述
最大团问题作为一个整数规划问题有许多等价的描述，整数规划问题描述如下：
设t: (0,1)n→2v，t(x)={iV: xi=1}，x{0,1}n，S2grid servicev，则x=t-1(S)={xi: i=1,2,…,n}，其中，n为图的顶点数。
(1)
s.t. 。如果x*是式(1)的最优解，则集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。
由于xi, xj{0,1}，xi+xj 1，(i, j)当且仅当xixj=0，有，其中为图G的补图G'的邻接矩阵。婚姻保卫战片尾曲>国际篮球规则
MCP问题等价于下面的全局二次0/1问题：
(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年代末，研究者们开始尝试采用启发式算法求解最大团问题，提出了各种各样的启发式算法，如顺序贪婪启发式算法、遗传算法、模拟退火算法、禁忌搜索算法、神经网
络算法等，并且取得了令人满意的效果。在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、边密度的增加而变得越来越小。唯一的缺点就是不一定能到最优值，有时只能到近优值。
近年来研究表明，单独使用一种启发式算法求解最大团问题，算法性能往往并不是很好，因此，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题。当前求解该问题最好的启发式算法有反作用禁忌搜索（Reactive Tabu Search, RTS）算法、基于遗传算法的简单启发式算法（Simple Heuristic Based Genetic Algorithm, HGA）、DLS-MC算法等。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议