关于最大团问题的分支搜索算法的优化

摘要

最大团问题是图论中的经典组合优化问题，虽然描述简单，但是非常复杂难解，属于一类NP-完全问题。最大团问题与图论中许多经典问题有十分密切的关系，可以在多项式时间内转换成最大独立集问题、最小顶点覆盖问题、最小着色问题、背包问题以及货郎担问题等经典问题。最大团问题的研究对于解决图论中的众多问题有着重要意义。作为图论中经典的组合优化问题，最大团问题与人们的现实生活关系十分密切，在实践生活中广泛应用于人员活动的安排、市场分析方案的选择，机器故障的诊断以及信号传输等许多应用领域。因此，最大团问题的研究有着巨大的实际应用价值。最大团的问题的算法分为确定性算法和非确定性算法两类。确定性算法要求程序在有效的时间内给出最大团问题的最优解，而非确定性的算法并不保证最终程序给出的是最优解。最大团问题是NP-完全问题，当无向图规模较大时在有效时间内可能无法计算出最优解，非确定性算法可以在有限时间内给出无向图的最大团问题最优解的一个近似解。
　　本文首先对最大团问题的应用背景进行了简单的介绍。描述了当前对于无向图中查找最大团问题的研究成果，并对当前关于最大团问题的主流解法进行了论述。对最大团问题确定性算法中的分支搜索算法做了详细的分析和研究。关于分支搜索算法求解最大团问题的关键在于对无向图的划分和对划分后生成的子图中存在的团上界以及下界的估计。无向图划分目的是将规模大的无向图划分成尽可能小的子图，最大化的降低最大团问题的规模。对于划分子图的上界估计可以提高剪枝效率，缩小在无向图中查找最大团时的搜索空间，从而提高搜索的速率。本文对无向图进行了仔细的分析，根据无向图本身结构特性及图论中 MaxSAT问题的求解技巧对最大团问题的上界估计函数进行了优化，改进了关于最大团问题的分支搜索算法，并对优化后的关于最大团问题的分支搜索算法进行了对比测试，测试结果表明算法速率得了很大的提高。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 最大团问题的意义

1.2 最大团问题的由来

1.3 最大团问题及其算法的研究现状

1.4 主要研究内容

1.5 论文结构

第二章 关于最大团问题的学习和分析

2.1 最大团问题的基础理论

2.2 关于最大团问题的非确定性算法

2.3 关于最大团问题的确定性算法

2.4 本章小结

第三章 关于最大团问题的无向图的分析

3.1 关于最大团问题的无向图

3.2 最大团问题的分支策略

3.3 最大团无向图的benchmark转换为矩阵表示

3.4 关于最大团问题的顶点的K-means聚类分析

3.5 最大团问题的无向图构造特点

3.6 本章小结

第四章 最大团问题的分支搜索算法的实现与优化

4.1 引言

4.2 最大团问题的基本分支限界算法

4.3 最大团问题的分支搜索算法一般的上界估计

4.4 将最大团问题无向图转换为MaxSAT问题输入实例

4.5 最大团问题分支搜索算法的数据结构的设计

4.6 MaxSAT结合无向图结构特点优化上界估计

4.7 本章小结

第五章 实验及结果分析

5.1 最大团问题的测试用例

5.2 实验中对比算法介绍

5.3 最大团的分支搜索算法的测试

5.4 本章小结

第六章 总结和展望

6.1本文总结

6.2 展望

致谢

参考文献

个人简历及硕士期间研究成果