计算机算法设计与分析.docx
《计算机算法设计与分析.docx》由会员分享，可在线阅读，更多相关《计算机算法设计与分析.docx（28页珍藏版）》请在冰点文库上搜索。
计算机算法设计与分析
计算机算法设计与分析
最大团问题研究报告
目录
1.MCP问题描述1
1.1MCP问题基本概念1
1.2MCP问题数学描述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改进蚁群算法-AntMCP4
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
最大团问题及其求解算法研究
最大团问题（MaximumCliqueProblem,MCP）是图论中一个经典的组合优化问题，也是一类NP完全问题，在国际上已有广泛的研究，而国内对MCP问题的研究则还处于起步阶段，因此，研究最大团问题具有较高的理论价值和现实意义。
最大团问题又称为最大独立集问题（MaximumIndependentSetProblem），在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。
目前，求解MCP问题的算法主要分为两类：
确定性算法和启发式算法。
确定性算法有回溯法、分支限界法等，启发式算法蚁群算法、顺序贪婪算法、DLS-MC算法和智能搜索算法等。
不管哪种算法，都要求在多项式时间内求得MCP问题的最优解或近似解。
图分为有向图和无向图，本文主要研究确定性算法求解无向图最大团问题。
1.MCP问题描述
1.1MCP问题基本概念
给定无向图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.2MCP问题数学描述
最大团问题作为一个整数规划问题有许多等价的描述，整数规划问题描述如下：
设t:
（0,1）n→2v，t（x）={i
V:
xi=1}，
x
{0,1}n，
S
2v，则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年代末，研究者们开始尝试采用启发式算法求解最大团问题，提出了各种各样的启发式算法，如顺序贪婪启发式算法、遗传算法、模拟退火算法、禁忌搜索算法、神经网络算法等，并且取得了令人满意的效果。
在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、边密度的增加而变得越来越小。
唯一的缺点就是不一定能找到最优值，有时只能找到近优值。
近年来研究表明，单独使用一种启发式算法求解最大团问题，算法性能往往并不是很好，因此，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题。
当前求解该问题最好的启发式算法有反作用禁忌搜索（ReactiveTabuSearch,RTS）算法、基于遗传算法的简单启发式算法（SimpleHeuristicBasedGeneticAlgorithm,HGA）、DLS-MC算法等。
3.求解MCP问题的常用算法
本节首先对求解最大团问题的常用算法进行简要的阐述，然后重点对回溯法和分支限界法求解最大团问题进行着重分析，并用C++语言在VisualStudio2008环境下编程实现。
3.1顺序贪婪启发式算法
顺序贪婪启发式算法是最早的求解最大团的启发式算法。
这类算法通过给一个团重复进行加点操作得到一个极大团或者对一组并不是团的子图重复进行删除顶点操作以得到一个团。
1987年，Kopf和Ruhe把这类型算法分为Bestin和Worstout两类。
（1）Bestin方法的基本思路：
由一个团出发，和这个团中顶点相连的顶点组成候选集；然后以一定的启发式信息，从中选择顶点加入团中，以后反复进行，直到最后得到一个极大团。
（2）Worstout方法的基本思路：
从整个顶点集开始，然后按一定的启发式信息，从中反复进行删除顶点操作，直到最后得到一个团。
顺序贪婪启发式算法有很大不足，该算法一旦找见一个极大团，搜索就停止，因此找到最大团的概率相对较低。
3.2局部搜索启发式算法
假设SG为图的所有极大团的集合，由于顺序贪婪启发式算法仅能找见
SG中的一个极大团，因此，为了提高解的质量，应当扩大在
SG的搜索区域，比如，可以在极大团S的邻居中继续进行搜索，以扩大搜索区域，进而提高解的质量。
在局部搜索启发式算法中，如果搜索S的邻居越多，提高解的质量的机会就越大。
依赖不同的邻居定义，局部搜索启发式算法可以得到不同的解。
在局部搜索启发式算法中，比较有名的算法是K-interchange启发式算法，它是一种基于K-neighbor邻居实现的，在解集S的K邻居中进行局部搜索的方法。
分析可知，局部搜索启发式算法存在一个问题，即仅能够找见一个局部最优值。
所以为了提高求解的质量，常把该算法和其它算法相混合，从而得到求解MCP问题的新的算法。
WaynePullan和HolgerH．Hoos基于这一思想提出了求解最大团问题的DLS-MC算法，该算法是plateausearch局部搜索启发式和算法迭代改善法相混合得到的，算法性能非常好，在该方法中引入了顶点惩罚函数，该函数在算法的求解过程中能够动态改变；在算法执行过程中迭代改善法和plateausearch算法轮流执行来提高解的质量。
在基准图上对该算法进行了测试，性能非常好。
3.3智能搜索启发式算法
智能搜索算法主要有遗传算法、禁忌算法、模拟退火算法、神经网络等。
3.3.1遗传算法
遗传算法（GeneticAlgorithm,GA）是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和自然遗传过程中发生的复制、交叉和变异现象。
1993年，Carter和Park首次提出使用遗传算法求解最大团问题，但由于所求解的质量差，计算复杂度高，因此，他们认为遗传算法并不适合求解最大团问题。
与此同时，Bäck和Khuri致力于最大独立集问题的求解，却得到了完全相反的结论，通过选用合适的适应度函数，取得了很好的效果。
因此在使用GA来解决最大团问题时，适应度函数起着非常关键的作用。
此后，基于遗传算法求解最大团问题的方法逐渐增多，但在提高解的质量，降低算法复杂度上方面却没有大幅度的提高。
l998年，Marchiori提出了一种基于遗传算法的简单启发式算法（simpleheuristicbasedgeneticalgorithm,HGA）。
算法由两部分组成：
简单遗传算法（simplegeneticalgorithm,SGA）和简单的贪婪启发式局部搜索算法（simplegreedyheuristiclocalsearchalgorithm,SGHLSA）。
在基准图上对算法HGA的性能进行测试，证明了该算法在解的质量和计算速度方面都优于基于遗传算法的其它算法。
因此，单纯使用遗传算法（改动变异、杂交、选择等算子）求解最大团问题时，算法的性能是比较差；要提高算法性能，遗传算法最好能和局部搜索算法相结合。
3.3.2模拟退火算法
模拟退火（SimulatedAnnealing,SA）算法是N.Metropolis在1953年提出的一种基于物质退火过程的随机搜索算法，是一种迭代求解的启发式随机搜索算法。
首先在高温下较快地进行搜索，使系统进入“热平衡”状态，大致地找到系统的低能区域。
随着温度的逐渐降低，搜索精度不断提高，可逐渐准确地找到最低能量的基态。
作为局部搜索算法的扩展，当邻域的一次操作使当前解的质量提高时，接受这个改进解作为新的当前解；反之，以一定的概率接受相对质量比较差的解作为新的当前解。
Aarts和Korst提出使用模拟退火算法来解决独立集问题，建议在算法设计时引入惩罚函数，但却没有提供任何的实验结果。
问题的解空间S是图G的全部可能的子图，并不要求是独立集，对于任一子图G*，成本函数为f（V'）=|V'|-λ|E'|，其中V'是图G*的顶点集，E'是图G*的边集，λ是权因子（λ>1）。
选择邻居时，费用值大的将被选中，因此求解最大独立集问题也就是最大化成本函数问题。
Homer和Peinado把模拟退火算法和Johnson的贪婪启发式算法、Boppan的随机化算法、Halldorsson的子图排除法3种启发式算法进行比较，结果比这3种算法要好很多。
总之，模拟退火算法在处理最大团问题上是一个非常好的算法。
3.3.3禁忌算法
禁忌算法（TabuAlgorithm）是一种改进的局部搜索算法。
该算法为了避免在搜索过程中出现死循环和开发新的搜索区域，采用了一种基于禁止的策略。
1989年，Friden提出了基于禁忌搜索的求解最大独立集的启发式算法，独立集的大小固定，该算法的目标是最小化当前子集（解）顶点之间的边数。
使用3个禁忌表：
其中，一个禁忌表用来存放上一代的解，另外两个分别存放刚进入解顶点和刚被删去的顶点。
基于禁忌算法求解最大团问题具有代表性的是Batti和Protasi提出的反作用局部搜索（ReactionLocalSearch,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
蚁群算法是由DorigoM.等人依据模仿真实的蚁群行为而提出的一种模拟进化算法。
蚂蚁之间是通过一种称为信息素（Pheromone）的物质传递信息的，蚂蚁能够在经过的路径上留下该种物质，而且能够感知这种物质的存在及其强度，并以此来指导自己的运动方向。
因此，由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象：
某一条路径上走过的蚂蚁越多，该路径上留下的信息素就越多，则后来者选择该路径的概率就越大。
蚂蚁之间就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的最短路径。
2003年，Fenet和Solnon提出了求解最大团问题的蚁群算法AntClique，该算法仍然将信息素留在边上，信息素τij是指把结点i和结点j分配到同一个团中的期望。
由于没有使用局部启发信息，这使得迭代初期各候选顶点的选择概率几乎相等，这样算法在迭代初期有一定的盲目性，往往需要更多的迭代次数才能得到最优解。
针对这些不足及最大团问题的特点，曾艳于2010年提出了改进的蚁群算法-AntMCP。
算法伪代码描述如下：
ProcedureVertex_AntClique
Initialize//初始化信息素和局部启发信息
Repeat
Forkin1...nbAntsdo:
Chooserandomlyafirstvertexvf
V
Ck←{vf}
Candidate←{vi|（vf,vi）
E}
WhileCandidate≠0do
Chooseavertexvi
Candidatewithprobabilityp（vi）;
Ck←Ck∪{vi}
Candidate←Candidate∩{vj|（vi,vj）
E}
Endofwhile
Endoffor
Updatepheromonew.r.t{C1,…,CnbAnts}
Untilmaxcyclesreachedoroptimalsolutionfound
Endofprocedure
在AntMCP中，增加了局部启发信息；信息素τ和启发信息η不是留在边上，而是留在顶点上。
这样，变量τ和η由二维降为一维，既可节省存储空间，又可提高运行速度，大量实验表明，该算法运算速度更快，效率更高。
3.5其它启发式算法
除上述几种启发式算法外，目前研究者们还提出了一些新的算法。
当图的顶点数不大于阈值M时，称此图为低度图，求解低度图的最大团问题的时间复杂度为O（d），基于这一思想，王青松和范铁生提出了一种求解低度图的最大团的确定性算法。
在该算法中，通过对图按顶点逐步分解实现分别计算，较好地解决了低度图的最大团问题，算法的时间复杂度为O（d*n3）。
针对遗传算法在最大团求解中保持群体多样性能力不足、早熟、耗时长、成功率高等缺陷，依据均匀设计抽样理论对交叉操作进行重新设计，结合免疫机理定义染色体浓度设计克隆选择策略，周本达、岳芹等提出了一种求解最大团问题的均价设计抽样免疫遗传算法。
仿真算例表明，该算法在解的质量、收敛速度等各项指标上均有提高，与DLS-MC、QUALEX等经典搜索算法相比，对部分算例能得到更好解。
吴冬辉和马良提出了基于遗传算法的最大团问题求解算法，通过引入概率模型指导变异产生新的个体，并结合启发式局部算法搜索最大团。
实例结果验证了该算法的有效性。
针对求解最大团问题的分层的边权网络（HierarchicalEdge-WeightNetwork,HEWN）算法，郭长庚和潘晓伟设计了一个实现HEWN算法的数据结构，指出在HEWN算法中HEWN算法的存储宜采用邻接多重表和二叉表相结合的链表表示法，并进行了时间复杂度分析，得出HEWN算法的时间复杂度是指数级而不是O（n8.5）。
针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题，张雁、党群等提出了一种新的基于匹配教程的Memetic算法。
算法中提出交叉匹配度的概念，用来估计两个体交叉所能获得的最佳适应值。
通过匹配度的计算对交叉方向的选择进行控制，保证了交叉操作以较大的概率生成新的优良模式。
测试结果表明，该算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法。
DNA计算是应用分子生物技术进行计算的新方法，具有高度并行性、大容量、低能耗等特点。
针对这一特点，李涛提出了用DNA算法求解最大团问题，开创了以生物技术为工具解决复杂问题的新纪元，为解决NP完全问题开辟了一条新途径。
基于对粘贴模型的组成、基本实验及其生化实现过程的分析，根据最大团问题的需求，周康、刘朔等在粘贴模型中，提出了基于电泳技术和分离实验的DNA序列检测方法。
基于分离实验提出了一种求解最大团问题的DNA算法，并给出了其生化实现过程。
为了提高交叉熵算法求解最大团问题的性能，吕强、柏战华等提出了一种领导者-跟随者协作求解的并行策略来实现交叉熵算法，从而达到减少计算时间和保障解的质量两者的平衡。
算法中领导者活跃在并行处理器之间采集数据，并根据当前获得信息对跟随者作出决策；受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间，完成各自的集团产生任务。
实验结果表明该算法较基于种群的启发式算法有一定的性能改善。
3.6回溯法
3.6.1算法基本思想
回溯法（BacktrackingAlgorithm,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-i3.6.3实例分析
如图1所示，给定无向图G={V,E}，其中V={1,2,3,4,5}，E={（1,2）,（1,4）,（1,5）,（2,3）,（2,5）,（3,5）,（4,5）}。
根据MCP定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。
{1,2,5}是G的一个最大团。
{1,4,5}和{2,3,5}也是G的最大团。
图2是无向图G的补图G'。
根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集。
虽然{1,2}也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图{1,2,5}中。
{1,2,5}是G'的最大独立集。
{1,4,5}和{2,3,5}也是G'的最大独立集。
图1无向图G图2无向图G的补图G'
以图1为例，利用回溯法搜索其空间树，具体搜索过程（见图3所示）如下：
假设我们按照1→2→3→4→5的顺序深度搜索。
开始时，根结点R是唯一活结点，也是当前扩展结点，位于第1层，此时当前团的顶点数cn=0，最大团的顶点数bestn=0。
在这个扩展结点处，我们假定R和第二层的顶点1之间有边相连，则沿纵深方向移至顶点1处。
此时结点R和顶点1都是活结点，顶点1成为当前的扩展结点。
此时当前团的顶点数cn=1，最大团的顶点数bestn=0。
继续深度搜索至第3层顶点2处，此时顶点1和2有边相连，都是活结点，顶点2成为当前扩展结点。
此时当前团的顶点数cn=2，最大团的顶点数bestn=0。
再深度搜索至第4层顶点3处，由于顶点3和2有边相连但与顶点1无边相连，则利用剪枝函数剪去该枝，此时由于cn+n-i=2+5-4=3>bestn=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处。
由于此时c
升级会员 