| 【中文题名】 | 最大团问题及其分支定界法研究 |
| 【英文题名】 | Study on Maximum Clique Problem and Its Branch and Bound Alecrithms |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2003-9-3 |
| 【中关键词】 | 最大团,着色,最大加权团,启发式算法,分支定界法, |
| 【英关键词】 | Maximum clique,Coloring,Maximum weight clique,Heuristics,Branch and bound algorithm., |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
本文首先对当前国际上最大团问题的理论研究成果及算法研究中的启发式算法进行了介绍，然后对精确算法中的分支定界法作了较为详细的讨论，最后作者在现有算法的基础上，给出了最大加权团问题的一种新的分支定界算法。该算法用团的简单启发式算法提供下界；用加权着色的启发式算法提供上界；在分支阶段，每次只产生一个新的子问题，并利用着色信息来选择分支顶点；最后利用回溯法来检验整体最优性。该算法从理论上提供了减小搜索树的规模及运行时间的可能性。 |
| 【论文题纲】 |
|
摘要 |
2-3 |
|
ABSTRACT |
3-5 |
|
第一章 绪论 |
5-12 |
|
1.1 最大团问题的意义 |
5-6 |
|
1.2 国内外研究现状 |
6-7 |
|
1.3 一些基本概念 |
7-12 |
|
第二章 最大(加权)团问题的理论研究 |
12-17 |
|
2.1 特殊图类 |
12-14 |
|
2.2 界的估计 |
14-17 |
|
2.2.1 上界 |
14-15 |
|
2.2.2 下界 |
15-17 |
|
第三章 最大(加权)团问题的启发式算法 |
17-22 |
|
3.1 一般启发式算法 |
17 |
|
3.2 现代优化算法 |
17-22 |
|
3.2.1 模拟退火算法 |
18-19 |
|
3.2.2 遗传算法 |
19-20 |
|
3.2.3 禁忌搜索算法 |
20-21 |
|
3.2.4 人工神经网络方法 |
21-22 |
|
第四章 最大(加权)团问题的分支定界法 |
22-29 |
|
4.1 最大团问题的分支定界法 |
22-26 |
|
4.2 最大加权团问题的分支定界法 |
26-29 |
|
第五章 最大加权团问题的一种新算法 |
29-46 |
|
5.1 引言 |
29-30 |
|
5.2 下界 |
30-31 |
|
5.3 上界 |
31-36 |
|
5.4 分支方案及搜索策略 |
36-37 |
|
5.5 最大加权团问题的算法 |
37-39 |
|
5.6 举例 |
39-44 |
|
5.7 本章小结 |
44-46 |
|
进一步工作 |
46-47 |
|
参考文献 |
47-52 |
|
发表论文情况 |
52-53 |
|
致谢 |
53 |
|
| 【DOI】 | LunWen.ID:2.2008.11390 |
