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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date最大团问题的各种算法和源代码最大团问题的各种算法和源代码最大团问题目 录1. MCP问题描述11.1 MCP问题基本概念11.2 MCP问题数学描述12. MCP问题应用背景23. 求解MCP问题的常用算法23.1 顺序贪婪启发式算法23.2 局部搜索启发式算法23.3 智能搜索启发式算法33.3.1 遗传算法33.3.2 模拟退火算法33.3.3 禁忌算法43.3.4 神经网络算法43.4 改进蚁群算法-AntMCP43.5 其它启发式算法53.6 回溯法63.6.1 算法基本思想63.6.2 算法设计思想63.6.3 实例分析73.6.4 程序设计及测试83.7 分支限界法113.7.1 算法描述113.7.2 算法求解流程123.7.3 优先队列式分支限界法求解MCP问题123.7.4 实例分析133.7.5 程序设计及测试134. 回溯法与分支限界法比较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中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果UV，且对任意两个顶点u，vU有(u, v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。如果UV且对任意u，vU有(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)n2v，t(x)=iV: xi=1，x0,1n，S2v，则x=t-1(S)=xi: i=1,2,n，其中，n为图的顶点数。 (1)s.t. 。如果x*是式(1)的最优解，则集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。由于xi, xj0,1，xi+xj1，(i, j)当且仅当xixj=0，有，其中为图G的补图G的邻接矩阵。MCP问题等价于下面的全局二次0/1问题： (2)s.t. x0,1n其中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算法等。3. 求解MCP问题的常用算法本节首先对求解最大团问题的常用算法进行简要的阐述，然后重点对回溯法和分支限界法求解最大团问题进行着重分析，并用C+语言在Visual Studio 2008环境下编程实现。3.1 顺序贪婪启发式算法顺序贪婪启发式算法是最早的求解最大团的启发式算法。这类算法通过给一个团重复进行加点操作得到一个极大团或者对一组并不是团的子图重复进行删除顶点操作以得到一个团。1987年，Kopf和Ruhe把这类型算法分为Best in和Worst out两类。(1) Best in方法的基本思路：由一个团出发，和这个团中顶点相连的顶点组成候选集；然后以一定的启发式信息，从中选择顶点加入团中，以后反复进行，直到最后得到一个极大团。(2) Worst out方法的基本思路：从整个顶点集开始，然后按一定的启发式信息，从中反复进行删除顶点操作，直到最后得到一个团。顺序贪婪启发式算法有很大不足，该算法一旦找见一个极大团，搜索就停止，因此找到最大团的概率相对较低。3.2 局部搜索启发式算法假设SG为图的所有极大团的集合，由于顺序贪婪启发式算法仅能找见SG中的一个极大团，因此，为了提高解的质量，应当扩大在SG的搜索区域，比如，可以在极大团S的邻居中继续进行搜索，以扩大搜索区域，进而提高解的质量。在局部搜索启发式算法中，如果搜索S的邻居越多，提高解的质量的机会就越大。依赖不同的邻居定义，局部搜索启发式算法可以得到不同的解。在局部搜索启发式算法中，比较有名的算法是K-interchange启发式算法，它是一种基于K-neighbor邻居实现的，在解集S的K邻居中进行局部搜索的方法。分析可知，局部搜索启发式算法存在一个问题，即仅能够找见一个局部最优值。所以为了提高求解的质量，常把该算法和其它算法相混合，从而得到求解MCP问题的新的算法。Wayne Pullan和Holger HHoos基于这一思想提出了求解最大团问题的DLS-MC算法，该算法是plateau search局部搜索启发式和算法迭代改善法相混合得到的，算法性能非常好，在该方法中引入了顶点惩罚函数，该函数在算法的求解过程中能够动态改变；在算法执行过程中迭代改善法和plateau search算法轮流执行来提高解的质量。在基准图上对该算法进行了测试，性能非常好。3.3 智能搜索启发式算法智能搜索算法主要有遗传算法、禁忌算法、模拟退火算法、神经网络等。3.3.1 遗传算法遗传算法（Genetic Algorithm, GA）是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和自然遗传过程中发生的复制、交叉和变异现象。1993年，Carter和Park首次提出使用遗传算法求解最大团问题，但由于所求解的质量差，计算复杂度高，因此，他们认为遗传算法并不适合求解最大团问题。与此同时，Bck和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年提出的一种基于物质退火过程的随机搜索算法，是一种迭代求解的启发式随机搜索算法。首先在高温下较快地进行搜索，使系统进入“热平衡”状态，大致地找到系统的低能区域。随着温度的逐渐降低，搜索精度不断提高，可逐渐准确地找到最低能量的基态。作为局部搜索算法的扩展，当邻域的一次操作使当前解的质量提高时，接受这个改进解作为新的当前解；反之，以一定的概率接受相对质量比较差的解作为新的当前解。Aarts和Korst提出使用模拟退火算法来解决独立集问题，建议在算法设计时引入惩罚函数，但却没有提供任何的实验结果。问题的解空间S是图G的全部可能的子图，并不要求是独立集，对于任一子图G*，成本函数为f(V)=|V|-l|E|，其中V是图G*的顶点集，E是图G*的边集，l是权因子（l1）。选择邻居时，费用值大的将被选中，因此求解最大独立集问题也就是最大化成本函数问题。Homer和Peinado把模拟退火算法和Johnson的贪婪启发式算法、Boppan的随机化算法、Halldorsson的子图排除法3种启发式算法进行比较，结果比这3种算法要好很多。总之，模拟退火算法在处理最大团问题上是一个非常好的算法。3.3.3 禁忌算法禁忌算法（Tabu Algorithm）是一种改进的局部搜索算法。该算法为了避免在搜索过程中出现死循环和开发新的搜索区域，采用了一种基于禁止的策略。1989年，Friden提出了基于禁忌搜索的求解最大独立集的启发式算法，独立集的大小固定，该算法的目标是最小化当前子集（解）顶点之间的边数。使用3个禁忌表：其中，一个禁忌表用来存放上一代的解，另外两个分别存放刚进入解顶点和刚被删去的顶点。基于禁忌算法求解最大团问题具有代表性的是Batti和Protasi提出的反作用局部搜索（Reaction Local Search, RLS）算法，通过引入局部搜索算法，扩展了禁忌搜索的框架。与一般禁忌搜索算法相比，该算法的特点是：在执行过程中，根据所得到的解的情况形成一种内部反馈机制以控制调整算法的控制参数，所以该算法的控制参数是动态变化的；比如，禁止表长度参数是动态变化的，因此禁忌表长度是动态变化的。他们在DIMACS的基准图上对算法性能进行测试，取得非常好的效果。3.3.4 神经网络算法人工神经网络指为了模拟生物大脑的结构和功能而构成的一种大型的、分布式系统，它有很强的自组织性、自适应性和学习能力。20个世纪80年代末期，Ballard、Godbeerl、Ramanujam和Sadayappan等都尝试对最大团和相关问题按人工神经网络进行编码，进而求解该问题。然而，这些研究只提供了很少的实验结果。Grossman提出一种离散的/确定性的Hopfield模型来求解最大团。这个模型有一个用来决定网络是否处于稳定态的临界值参数。Grossman建议在这个参数上使用退火策略，并且使用自适应机制选择网络的初始状态和临界值。在DIMACS基准图上测试，得到比较好的结果，但与性能好的启发式算法相比，其结果较差，比如结果要差于模拟退火算法。1995年Jagota对Hopfield模型进行了多处修改来近似求解最大团问题，其中有的是离散化的，有的是连续的；虽然有了一定改进，但是性能并没有显著提高。随后，仍然有好多研究者使用Hopfield神经网络来求解最大团问题，但是与其它智能搜索算法相比，效果比较差。研究表明：(1) 前3种智能搜索算法适合求解MCP，而通过神经网络算法求解MCP时的性能比较差；(2) 单独使用智能搜索算法来求解MCP，算法性能并不好，因此，常和局部搜索算法相结合形成新的混合算法，比如：禁忌算法与局部搜索算法相混合形成的反作用禁忌搜索算法，遗传算法与局部搜索算法相混合形成的简单启发式算法等。3.4 改进蚁群算法-AntMCP蚁群算法是由Dorigo M.等人依据模仿真实的蚁群行为而提出的一种模拟进化算法。蚂蚁之间是通过一种称为信息素（Pheromone）的物质传递信息的，蚂蚁能够在经过的路径上留下该种物质，而且能够感知这种物质的存在及其强度，并以此来指导自己的运动方向。因此，由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象：某一条路径上走过的蚂蚁越多，该路径上留下的信息素就越多，则后来者选择该路径的概率就越大。蚂蚁之间就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的最短路径。2003年，Fenet和Solnon提出了求解最大团问题的蚁群算法AntClique，该算法仍然将信息素留在边上，信息素tij是指把结点i和结点j分配到同一个团中的期望。由于没有使用局部启发信息，这使得迭代初期各候选顶点的选择概率几乎相等，这样算法在迭代初期有一定的盲目性，往往需要更多的迭代次数才能得到最优解。针对这些不足及最大团问题的特点，曾艳于2010年提出了改进的蚁群算法-AntMCP。算法伪代码描述如下：Procedure Vertex_AntCliqueInitialize /初始化信息素和局部启发信息RepeatFor k in 1.nbAnts do: Choose randomly a first vertex v f V Ck v f Candidate v i |( v f, v i) E While Candidate0 do Choose a vertex v i Candidate with probability p(v i); Ck Ck v i Candidate Candidate v j |( vi, v j) E End of whileEnd of forUpdate pheromone w.r.t C1,CnbAntsUntil max cycles reached or optimal solution foundEnd of procedure在AntMCP中，增加了局部启发信息；信息素t和启发信息h不是留在边上，而是留在顶点上。这样，变量t和h由二维降为一维，既可节省存储空间，又可提高运行速度，大量实验表明，该算法运算速度更快，效率更高。3.5 其它启发式算法 除上述几种启发式算法外，目前研究者们还提出了一些新的算法。当图的顶点数不大于阈值M时，称此图为低度图，求解低度图的最大团问题的时间复杂度为O(d)，基于这一思想，王青松和范铁生提出了一种求解低度图的最大团的确定性算法。在该算法中，通过对图按顶点逐步分解实现分别计算，较好地解决了低度图的最大团问题，算法的时间复杂度为O(d*n3)。针对遗传算法在最大团求解中保持群体多样性能力不足、早熟、耗时长、成功率高等缺陷，依据均匀设计抽样理论对交叉操作进行重新设计，结合免疫机理定义染色体浓度设计克隆选择策略，周本达、岳芹等提出了一种求解最大团问题的均价设计抽样免疫遗传算法。仿真算例表明，该算法在解的质量、收敛速度等各项指标上均有提高，与DLS-MC、QUALEX等经典搜索算法相比，对部分算例能得到更好解。吴冬辉和马良提出了基于遗传算法的最大团问题求解算法，通过引入概率模型指导变异产生新的个体，并结合启发式局部算法搜索最大团。实例结果验证了该算法的有效性。针对求解最大团问题的分层的边权网络（Hierarchical Edge-Weight Network, HEWN）算法，郭长庚和潘晓伟设计了一个实现HEWN算法的数据结构，指出在HEWN算法中HEWN算法的存储宜采用邻接多重表和二叉表相结合的链表表示法，并进行了时间复杂度分析，得出HEWN算法的时间复杂度是指数级而不是O(n8.5)。针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题，张雁、党群等提出了一种新的基于匹配教程的Memetic算法。算法中提出交叉匹配度的概念，用来估计两个体交叉所能获得的最佳适应值。通过匹配度的计算对交叉方向的选择进行控制，保证了交叉操作以较大的概率生成新的优良模式。测试结果表明，该算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法。DNA计算是应用分子生物技术进行计算的新方法，具有高度并行性、大容量、低能耗等特点。针对这一特点，李涛提出了用DNA算法求解最大团问题，开创了以生物技术为工具解决复杂问题的新纪元，为解决NP完全问题开辟了一条新途径。基于对粘贴模型的组成、基本实验及其生化实现过程的分析，根据最大团问题的需求，周康、刘朔等在粘贴模型中，提出了基于电泳技术和分离实验的DNA序列检测方法。基于分离实验提出了一种求解最大团问题的DNA算法，并给出了其生化实现过程。为了提高交叉熵算法求解最大团问题的性能，吕强、柏战华等提出了一种领导者-跟随者协作求解的并行策略来实现交叉熵算法，从而达到减少计算时间和保障解的质量两者的平衡。算法中领导者活跃在并行处理器之间采集数据，并根据当前获得信息对跟随者作出决策；受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间，完成各自的集团产生任务。实验结果表明该算法较基于种群的启发式算法有一定的性能改善。3.6 回溯法3.6.1 算法基本思想回溯法（Backtracking Algorithm, BA）有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解，是一个既带有系统性又带有跳跃性的搜索算法。在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按照深度优先的策略进行搜索。BA在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而BA在用来求问题的任一解时，只要搜索到问题的一个解即可结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死结点。此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点。回溯法以这种方式递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点为止。3.6.2 算法设计思想搜索：回溯法从根结点出发，按深度优先策略遍历解空间树，搜索满足约束条件的解。剪枝：在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界；也即判断该结点是否包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先的策略搜索。一般来讲，回溯法求解问题的基本步骤如下：(1) 针对所给问题，定义问题的解空间；(2) 确定易于搜索的解空间结构；(3) 以深度优先方式搜索解空间，并在搜索过程中利用Pruning函数剪去无效的搜索。无向图G的最大团问题可以看作是图G的顶点集V的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点Z位于解空间树的第i层。在进入左子树前，必须确认从顶点i到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。用邻接矩阵表示图G，n为G的顶点数，cn存储当前团的顶点数，bestn存储最大团的顶点数。cn+n-i为进入右子树的上界函数，当cn+n-ibestn=0，则回溯到结点2处进入右子树，开始搜索。此时当前团的顶点数cn=2，最大团的顶点数bestn=0。再深度搜索至第5层顶点4处，由于顶点3和4无边相连，剪去该枝，回溯到结点3处进入右子树，此时当前团的顶点数cn=2，最大团的顶点数bestn=0。继续深度搜索至第6层顶点5处，由于顶点5和4有边相连，且与顶点1和2都有边相连，则进入左子树搜索。由于结点5是一个叶结点，故我们得到一个可行解，此时当前团的顶点数cn=3，最大团的顶点数bestn=3。vi的取值由顶点1至顶点5所唯一确定，即v=(1, 2, 5)。此时顶点5已不能再纵深扩展，成为死结点，我们返回到结点4处。由于此时cn+n-i=3+5-6=2bestn=3，不能在右子树中找到更大的团，利用剪枝函数可将结点4的右结点剪去。以此回溯，直至根结点R再次成为当前的扩展结点，沿着右子树的纵深方向移动，直至遍历整个解空间。最后得到图1的按照12345的顺序深度搜索的最大团为U=1,2,5。当然1,4,5和2,3,5也是其最大团。图3 回溯法求解图1的最大团问题3.6.4 程序设计及测试3.6.4.1 程序代码/ MaxClique.cpp : 定义控制台应用程序的入口点。/*回溯法求解最大团问题*/#include stdafx.h#include#include#include#includeusing namespace std;#define MAX_v 50 /定义一个最大顶点个数typedef structint aMAX_vMAX_v; /无向图G的邻接矩阵int v; /无向图G的顶点int e; /无向图G的边int x50; /顶点与当前团的连接，xi=1 表示有连接int bestx50; /当前最优解int cn; /当前团的顶点数目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.txtG.v;for(int i=1;i=G.v;i+)for(int j=1;jG.aij; for(i=1;i=G.v;i+) /初始化 G.bestxi=0; G.xi=0; G.bestn=0;G.cn=0; coutendl;cout回溯法求解最大团问题endl; coutendl; cout输入初始化无向图矩阵为:endl; /初始化 for(i=1;i=G.v;i+) for(j=1;j=G.v;j+) coutG.aij ; coutG.v) for (int j=1; j=G.v; j+) G.bestxj = G.xj; G.bestn =G.cn; return; /检查顶点i与当前团的连接 int OK = 1; for(int j=1; jG.bestn) G.xi = 0;Backtrack(G,i+1); void main()MCP G;Creat(G); Backtrack(G,1);cout最大团包含的顶点数为:G.bestnendl;cout最大团方案为:( ; for(int i=1;i=G.v;i+) if(G.bestxi=1)couti ; cout)bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。(3) 终止条件算法的while循环的终止条件是遇到子集树中的一个叶结点（即n+1层结点）成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。3.7.4 实例分析仍以图1无向图为例，优先队列式分支限界法求解最大团问题思路与回溯法相类似，这里就不再阐述，其搜索解空间流程如下图所示。图8 分支限界法求解MCP3.7.5 程序设计及测试3.7.5.1 程序设计/ MaxClique_BB.cpp : 定义控制台应用程序的入口点。/* 分支限界法求解最大团问题*/#include stdafx.h# include # include # include # include using namespace std;typedef structint v; /无向图G的顶点int e; /无向图G的边int a5050; /定义图G的邻接矩阵int bestx50; /最优解MCP;void Creat(MCP &G) int i,j;ifstream fin(data.txt);if(!fin)cout不能打开文件:data.txtG.v;for(int i=1;i=G.v;i+)for(int j=1;jG.aij; for(i=1;i=G.v;i+) /初始化 G.bestxi=0;coutendl;cout 优先队列式分支限界法求解最大团问题endl; coutendl; cout输入初始化无向图矩阵为:endl; /初始化 for(i=1;i=G.v;i+) for(j=1;j=G.v;j+) coutG.aij ; coutendl; struct BBNode BBNode *parent; /指向父结点的指针 bool LChild; /左儿子结点标志;struct CliqueNode /定义优先队列类型为CliqueNode int cn; /当前团的顶点数 int un; /当前团最大顶点数的上界 int level; /结点在子集空间树种所处的层次 BBNode *p; /指向活结点在子集树中相应结点的指针 bool operator(const CliqueNode& b) const /un) return true; if(b.un=un & cn) return true; else return false; ;void BBMaxClique(MCP &G) BBNode *E=new(BBNode); /定义B代表记录的队列情况 /初始化 int j,i=1; int cn=0,bestn=0; int OK=1; priority_queue Q; /定义优先队列Q E-LChild=false; /初始化 E-parent=NULL; while(i!=G.v+1)/非叶结点 /检查顶点i与当前团中其它顶点之间是否有边相连 OK=1; BBNode *B=E; /把当前点的数据给B，B为中间变量 for(j=i-1;j0;B=B-parent,j-) if(B-LChild & G.aij=0) /如果不满足就停止 OK=0; break; if(OK) /满足条件，即左儿子结点为可行结点 CliqueNode *D=new(CliqueNode); /定义一个节点D D-p=new(BBNode); if(cn+1bestn) bestn=cn+1; D-cn=cn+1; D-level=i+1; D-p-LChild=true; D-p-parent=E; D-un=cn+1+G.v-i; Q.push(*D); /进队列 if(cn+G.v-ibestn ) /不满足条件但是还是可能有最优解 CliqueNode *D=new(CliqueNode); /定义一个节点D D-p=new(BBNode); D-cn=cn; D-level=i+1; D-p-LChild=false; D-p-parent=E; D-un=cn+G.v-i; Q.push(*D); /进队列 CliqueNode N; N=Q.top(); /取队顶元素，最大堆 Q.pop(); /删除队顶元素 E=N.p; /记录当前团的信息 cn=N.cn; /记录当前团的顶点数 i=N.level; /所在的层次 for(j=G.v;j0;j-) /保存最优解 G.bestxj=E-LChild; E=E-parent; bestn=cn; void main() MCP G; Creat(G); BBMaxClique(G);cout0;i-) if(G.bestxi=1) couti ; cout)endl;getch();3.7.5.2 算例测试 图9 测试算例 图10 data结果图11 data2结果4. 回溯法与分支限界法比较表1 回溯法与分支限界法的比较方法内容回溯法分支限界法求解目标找出解空间树中满足约束条件的所有解找出满足约束条件的一个解，或是在满足约束条件的解中找出某种意义下的最优解搜索方式以深度优先的方式搜索解空间树以广度优先货最小耗费优先的方式搜索解空间树算法复杂度O(n2n)O(n2n)访问结点数平均情况下与分支限界法相比较多平均情况下与回溯法相比较少