【作者】 周阳；

【导师】 许如初；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2015， 硕士

【摘要】 现实世界中的很多问题如信号传输,投资方案选择,编码错误诊断等都可以抽象为最大团问题（MCP,Maximum Clique Problem）,此外,最大团问题在模式识别,计算机视觉等领域均有应用。最大团问题是组合优化问题领域中一个非常经典的NP-完全问题,研究最大团问题具有很高的实践意义和理论意义。最大团问题的求解目标是在一个给定的无向图中寻找一个规模最大的完全子图,其求解算法可以分为两类:精确算法和启发式算法。启发式算法是一种非确定性的算法,能够在较短的时间内找出问题的一个近似解,但是这个近似解不一定是最优解。精确算法则没有这个缺陷,理论上,在时间足够长的前提下,精确算法可以解决任意难度的最大团问题。其中,最大团问题的精确算法是本文的主要研究对象。本文仔细分析了目前主流的精确算法,如C&P,MCQ,MaxCliqueDyn等。分析结果指出,最大团的精确算法的具有改进潜力的方向有三个:1,改变分支顶点的选择顺序;2,改进算法的初始下界;3,改进划分后子图中的上界估值。本文在这三个方面分别做了实验和分析,并且相应地提出了一种新的精确算法MMC。MMC算法借鉴了其他算法的优势,引入ICE策略改进初始LB,并且使用LRSP策略执行顶点的重排序。测试DIMACS标准算例表明,算法MMC对于部分算例如gen400_p0.9₅5,gen400_p0.9₆5,gen400_p0.9₇5其效率有显著提升,同时,MMC算法的平均效率也优于目前大部分最大团精确算法。因此,可以认为本文提出的MMC算法是一个高效且有潜力的算法。更多还原

【Abstract】 Many real-world problems such as signal transmission, investment scheme selection, coding error diagnosis and so on can be converted to the maximum clique problem（MCP, Maximum Clique Problem）, and it also can be applied into the fields of pattern recognition and computer vision. The MCP is a very classic NP- complete problem in the field of combinatorial optimization problem, and it has a high practical significance and theoretical value.The object of MCP is to find a complete subgraph with maximum size in a undirected graph, and the algorithm for this problem can be divided into two categories: exact algorithms and heuristic algorithms. Heuristic algorithm is a non-deterministic algorithm and an approximate solution can be found by a litter time, but the solution is not guaranteed as the optimal one. However, exact algorithms does not have this defect, in theory, exact algorithm can kill any MCP in unlimited time theoretic. The paper is focused on the exact algorithm of the maximum clique problem.In this paper, details of the current major precise algorithms were analyzed, such as C&P, MCQ, MaxCliqueDyn and so on. The results pointed out the direction of potential improvement of exact algorithm being three: first, to change the selection order of the vertices when branch; second, to improve the algorithm to compute the initial lower bound; third and to improve the algorithm to get more precise upper bound after branch. In this paper, experiment and analysis are conducted and a new exact algorithm for MCP named MMC is proposed.Test result of DIMACS benchmarks show that MMC works very well than other algorithms in some graph like gen400_p0.9₅5, gen400_p0.9₆5 and gen400_p0.9₇5. Meanwhile the average efficiency of MMC algorithm is also better than most of other exact algorithm for MCP. Therefore, MMC is considered to be an efficient and promising algorithm.更多还原