| 【中文题名】 | 最大团问题的二元熵函数法及同伦方法 |
| 【英文题名】 | Bivariate Entropy Function Method and Homotopy Method for Maximum Clique Problem |
| 【学科专业】 | 计算数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-1-17 |
| 【中关键词】 | 最大团,二元熵函数法,复制子等式,同伦方法,, |
| 【英关键词】 | Maximum Clique Problem,Bivariate Entropy Function Method,Replicator Dynamics,Homotopy Method, |
| 【分类导航】 | 数理科学和化学>数学>计算数学>数值分析>> |
| 【论文摘要】 | 最大团问题是组合优化中的一个经典的NP-Complete问题。此问题自被人们发现之后，广为研究和应用。但是因为问题本身的复杂性，所以人们将研究的重点放在问题的近似计算上，并且取得了一系列的研究成果。这篇文章的主要内容也是研究该问题的近似算法，结构安排如下：
在第一章，介绍了最大团问题的有关定义和优化模型。概述了问题的特点和研究意义所在。给出了最大团问题的相关研究工作。
在第二章，给出了求解最大团问题的一种方法，二元熵函数内点法。该算法基于一个超方体约束的二次规划模型。在用二元熵函数构造的辅助项后，可得到一个新的模型。通过求解这个新的模型来逼近原模型的解。在求解过程中，先是得到一个下降方向，并证明了沿此方向进行一维搜索且步长不超过1可以保证迭代点始终在可行域内部。在这一章最后，给出算法收敛性证明。
在第三章，给出了求解最大团问题的一种同伦方法，基于复制子等式的同伦方法。首先，介绍了复制子等式一些性质以及在求解最大团问题上的作用。其后，在求解的二次规划模型上以同伦形式添上正则项得到同伦形式的正则化模型。然后通过调节同伦参数，对每个不同的参数用复制子等式进行求解，从而... |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-8 |
|
1 绪论 |
8-22 |
|
1.1 最大团问题的定义 |
8-9 |
|
1.2 最大团问题的数学描述 |
9-12 |
|
1.2.1 离散模型描述 |
9-10 |
|
1.2.2 连续模型描述 |
10-12 |
|
1.3 最大团问题的实际应用和理论意义 |
12 |
|
1.4 最大团问题的相关研究 |
12-20 |
|
1.4.1 确定性算法 |
12-14 |
|
1.4.2 启发式算法 |
14-18 |
|
1.4.3 半定规划和半定松弛方法 |
18-19 |
|
1.4.4 其他相关的一些研究方法 |
19-20 |
|
1.5 本文主要工作及内容安排 |
20-21 |
|
1.6 本章小结 |
21-22 |
|
2 二元熵函数法 |
22-32 |
|
2.1 熵函数的介绍 |
22-23 |
|
2.2 模型的建立 |
23-25 |
|
2.3 模型分析 |
25-29 |
|
2.4 算法构造和算法收敛性 |
29-31 |
|
2.4.1 算法的构造 |
29 |
|
2.4.2 算法的收敛性 |
29-31 |
|
2.5 本章小结 |
31-32 |
|
3 基于复制子等式的同伦方法 |
32-40 |
|
3.1 复制子等式基础知识介绍 |
32-35 |
|
3.2 复制子等式在最大团问题中的应用 |
35-36 |
|
3.3 同伦方法基础及其模型建立 |
36-39 |
|
3.3.1 同伦方法基础 |
36-38 |
|
3.3.2 模型建立及算法构造 |
38-39 |
|
3.4 本章小结 |
39-40 |
|
4 数值试验 |
40-44 |
|
4.1 二元熵函数法 |
40-41 |
|
4.2 基于复制子等式的同伦方法 |
41-43 |
|
4.3 本章小结 |
43-44 |
|
结论 |
44-45 |
|
参考文献 |
45-51 |
|
攻读硕士学位期间发表学术论文情况 |
51-52 |
|
致谢 |
52-53 |
|
大连理工大学学位论文版权使用授权书 |
53 |
|
| 【DOI】 | LunWen.ID:2.2008.15585 |
