c++最大团问题分支限界法
C++最大团问题分支限界法
最大团问题是一类典型的计算机视觉算法，是一种经典的NP难问题。
它的出处可以追溯到1960年代的军事合作活动，它是一个试图确定由一系列正交关系中的最大团的问题。
为了解决该问题，具有一组称为“分支限界法”（Branch and Bound）的方法已经开发出来，它是一种基于回溯的搜索算法。
分支限界法主要是通过组合所有可能的顶点组合来求解最大团问题。
该算法从一个指定顶点顺序表开始，依次检查每个顶点，组合每个子团，直到它找到最大的团为止。
算法步骤如下：
（1）将所有顶点按照一定的顺序排序，然后将它们放入一个队列中。
（2）移除队列中的第一个顶点并将其加入当前团中。
（3）继续循环，检查剩余顶点是否需要加入当前团，如果确定它们满足条件，则将它们加入当前团。
（4）检查团大小是否达到最大值。
（5）如果当前团的大小小于最大值，则回到步骤2，继续检查剩余顶点是否可以加入团中。
（6）重复步骤2到5，直到找到最大团为止。
该算法通过在搜索空间中枚举所有可能的节点组合，来求解最大团问题。
尽管该算法可以有效地解决最大团问题，但它也存在一些弊端，例如，该算法的时间复杂度非常高（O（n^2）），因为它需要搜索所有可能的节点组合。
这就是该算法的局限性。
回溯法解决最⼤团问题问题描述 团是两两相邻顶点组成的集合。
最⼤团是指⼀个图中所含顶点数最多的那个团。
上图中顶点⼦集{v1,v2,v3,v4}就构成⼀个最⼤团。
独⽴集是两两不相邻顶点组成的集合。
图G的团与图G补图/G的独⽴集之间存在⼀⼀对应的关系。
U是G的最⼤团当且仅当U是/G的最⼤独⽴集。
算法设计 ⽆向图的最⼤图和最⼤独⽴⼦集问题都可以⽤回溯法在O（n2n）时间内解决。
图G的最⼤团和最⼤独⽴集问题都可以看成是图G顶点集V的⼦集选取问题。
因此，可以⽤⼦集数表⽰问题的解空间。
设当前要扩展的节点Z位于解空间的第i层。
在进⼊左⼦树前，必须确认从顶点i 到已选⼊的顶点集中每⼀个顶点都有边相连。
在进⼊右⼦树之前，必须确认还有⾜够多的可选择顶点使得算法可能⼦右⼦树中找到更⼤团。
具体实现# -*- coding: utf-8 -*-"""Created on Sun Oct 22 10:14:22 2017@author: zhuhan"""import numpy as npN = 5a = np.random.randint(0, 2, (N, N)) #generate 0-1 random matrix as adjacent matrixa = np.triu(a)a += a.T - np.diag(a.diagonal())for i in range(N):a[i][i] = 1print(a)cn = 0 #current number of vertexbestn = 0 #current maximal number of vertexx = np.zeros((N,)) #currrent solutionbestx = np.zeros((N,)) #best solutiondef backtrace( i ):global cnglobal bestnif(i >= N):for j in range(N):bestx[j] = x[j]bestn = cnreturnOk = True #检查顶点i与当前团的连接for j in range(i-1):if x[j] == 1 and (not a[i][j]):Ok = Falsebreakif Ok: #进⼊左⼦树x[i] = 1cn = cn + 1backtrace(i+1)cn = cn -1if cn + N-i-1 > bestn:x[i] = 0backtrace(i+1)def main():backtrace(0)for i, j in enumerate(bestx):print(i,':',j)if__name__ == '__main__':main()运⾏结果。
计算机算法设计与分析最大团问题研究报告目录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 问题的最优解或近似解。
图分为有向图和无向图，本文主要研究确定性算法求解无向图最大团问题。
