最大团问题精确算法研究

摘要

在无向图G=(V，E)中，团（ clique)指图 G的一个完全子图，在这个子图中的任意两个顶点之间都有边连接。最大团问题（Maximum Clique Problem)指在给定的图 G中找出包含顶点个数最多的一个团。最大团问题是经典的N P难度问题，其对应的判定问题：给定无向图G和整数 A;，判断图 G中是否存在大小为A:的团，是 N P完全间题。最大团问题在故障诊断、生物信息学、编码理论、计算机视觉、组合拍卖、经济学分析、社会网络分析等实际问题中存在着广泛的应用，与最大独立集、最小顶点覆盖、图染色等其它经典的NP难度问题也密切相关。研究最大团问题的求解算法具有重要的理论意义和应用价值。
　　当前求解最大团问题的算法主要分为两类：启发式算法和精确算法。启发式算法通常能在较短的时间内给出质量相对较高的解，但无法保证解的最优性。精确算法通过系统搜索问题的整个解空间，从而保证最终得到的解为全局最优解。尽管从理论分析上看，现有的最大团精确算法在最坏情况下的时间复杂度无一例外都是指数级的，但近年来的研究进步使得精确算法的实际求解能力得到显著提升。
　　本文研究基于分支定界方案的最大团精确算法。论文工作紧紧围绕分支与定界这两个决定算法性能的关键策略展开。具体工作体现在以下四个方面：
　　(一）在标准 MaxSAT推理的基础上，提出了更加高效的渐进MaxSAT推理技术用于减少分支顶点数量。对图进行近似顶点染色是估计最大团上界的经典方法。但近似染色数上界与最大团的实际值之间往往存在较大差距。标准 MaxSAT推理将顶点的染色结果编码成MaxSAT公式，利用 MaxSAT推理技术来计算更加精确的上界。尽管标准MaxSAT推理能显著减少搜索树大小，但对搜索树的剪枝作用仍存在“全或无”的显著特征。本文从设计思路上将MaxSAT推理的目标从改进上界估计转变为减少分支顶点数量，提出了渐进MaxSAT推理技术。实验表明，渐进 MaxSAT推理在减少分支数量方面总是能产生积极效果，与传统的MaxSAT推理技术相比效率更高。
　　(二）研究了动态顺序和静态顺序两种分支顺序策略，提出了混合分支顺序策略。结合渐进MaxSAT推理技术，本文设计了基于动态分支顺序的DoMC算法和基于静态分支顺序的 SoMC算法。SoMC算法在保持静态分支顺序的前提下最小化分支顶点集，而 DoMC允许分支顺序动态变化以使分支顶点集最小化。实验表明二者在性能上相互补充。基于动态顺序与静态顺序性能互补的观察，本文提出了混合分支顺序策略，设计了混合分支顺序算法MoMC。实验结果表明， DoMC、 SoMC和 MoMC三个算法的总体性能显著地超越当前国际上最好的精确算法。
　　(三）针对大量存在的真实世界稀疏大图，设计了简单高效的预处理程序。该预处理程序在单一的过程中高效地完成初始顶点顺序计算、初始团寻找、图规模化简等三项预处理任务。结合该预处理程序和渐进MaxSAT推理技术，设计了针对稀疏大图的精确算法LMC。实验表明， LM C能够快速求解顶点规模达到千万级的真实世界大图，其性能明显超越了目前国际上最好的大图精确算法PM C和 BBMCSP。LMC算法的优异表现也驳斥了文献中关于MaxSAT推理等高级技术并不适用于大稀疏图求解的观点。
　　(四）针对最大团问题的变型一加权最大团问题，设计了精确算法WLMC。由于顶点之间存在权重差异，加权图中的顶点关系更加复杂，使得加权最大团问题的求解难度要显著地高于非加权的经典最大团问题。为简化顶点之间的复杂关系，本文提出了由冲突驱动的两个顶点权重切分规则：显式冲突切分和隐式冲突切分，并从图概念的视角直观地阐述了基于冲突独立集探测的上界估计。大量真实世界图集上的实验结果表明， W LMC算法的整体性能表现显著地超越了当前最好的精确算法和启发式算法，有力地驳斥了精确算法对解决大规模图能力不足的主流观点。
　　传统的最大团分支定界算法集中关注如何改进上界估计，本文在算法设计思路上集中关注如何减少分支数量。这一设计思路的转变使得对MaxSAT推理和顶点权重切分等技术的运用效率更高。该设计思路也有望用于改进其它基于分支定界的组合优化问题算法设计。针对稀疏大图设计的LM C和 WLM C算法，显著地提高了最大团精确算法求解真实世界大规模图的实际能力，增强了精确算法的现实可用性。

目录

声明

1 引言

1.1 课题背景及研究意义

1.2 课题来源及研究目标

1.3 国内外研究现状

1.4 NP-hard问题算法评价

1.5 本文的结构

2 最大团问题及分支定界算法基础

2.1 定义与符号

2.2 最大团问题

2.3 分支定界方案

2.4 定界策略

2.5 分支策略

2.6 本章小节

3 渐进MaxSAT推理

3.1 MaxSAT问题

3.2 最大团问题的MaxSAT编码

3.3 标准MaxSAT推理——改进上界估计

3.4 渐进MaxSAT推理——减少分支数量

3.5 一个实际的图例

3.6 本章小节

4 结合渐进MaxSAT推理与动静态分支策略的高效算法

4.1 基本的算法框架MC1及算法DoMC1d0、DoMC1和SoMC1

4.2 邻接矩阵重建和渐进上界

4.3 改进的算法框架MC2及算法DoMC2d0、DoMC2和SoMC2

4.4 混合分支顺序算法MoMC

4.5 实验结果与分析

4.6 本章小节

5 结合高效预处理与渐进MaxSAT推理的大稀疏图算法

5.1 大图中的最大团问题

5.2 基于core的最大团上界

5.3 大稀疏图算法LMC

5.4 实验结果与分析

5.5 本章小节

6 冲突驱动的顶点权重切分与加权最大团算法

6.1 加权最大团问题

6.2 基于冲突独立集探测的上界

6.3 冲突驱动的顶点权重切分

6.4 加权最大团算法WLMC

6.5 实验结果与分析

6.6 本章小节

7 总结与展望

致谢

参考文献

附录1 攻读学位期间发表论文及专利目录

附录2 攻读博士学位期间申请的发明专利和其他成果

附录3 攻读博士学位期间参与的科研项目