图顶点染色问题中隐含约束关系研究与应用
| 摘要 | 第4-6页 |
| Abstract | 第6-7页 |
| 1 引言 | 第11-18页 |
| 1.1 本课题的来源及研究目的 | 第11-12页 |
| 1.2 选题的背景、依据及研究意义 | 第12-15页 |
| 1.3 论文主要工作及其结构 | 第15-17页 |
| 1.4 论文主要创新点 | 第17-18页 |
| 2 图染色问题的研究及应用现状 | 第18-36页 |
| 2.1 常见的整数规划模型 | 第19-21页 |
| 2.2 近似染色算法现状 | 第21-26页 |
| 2.3 精确染色算法现状 | 第26-31页 |
| 2.4 基于SAT的染色方法 | 第31-32页 |
| 2.5 图顶点染色问题的应用现状 | 第32-35页 |
| 2.6 小结 | 第35-36页 |
| 3 SAT问题的完备求解方法 | 第36-49页 |
| 3.1 分支选择策略 | 第37-41页 |
| 3.2 单值传播的实现技术 | 第41-42页 |
| 3.3 冲突驱动子句学习技术 | 第42-44页 |
| 3.4 智能回跳技术 | 第44-46页 |
| 3.5 重启动策略 | 第46-47页 |
| 3.6 子句管理策略 | 第47-48页 |
| 3.7 小结 | 第48-49页 |
| 4 一个基于回溯搜索的图染色算法 | 第49-61页 |
| 4.1 算法BACKGCP的基本思想及结构 | 第49-51页 |
| 4.2 算法BACKGCP的重要组成部分 | 第51-56页 |
| 4.3 算法BACKGCP的实验分析 | 第56-60页 |
| 4.4 算法BACKGCP的不足 | 第60页 |
| 4.5 小结 | 第60-61页 |
| 5 图顶点染色问题中的隐含约束关系 | 第61-77页 |
| 5.1 约束满足问题概述 | 第61-63页 |
| 5.2 K染色问题的CSP描述 | 第63-65页 |
| 5.3 图顶点染色问题的显性约束关系 | 第65-67页 |
| 5.4 图顶点染色问题的隐含约束关系 | 第67-76页 |
| 5.5 小结 | 第76-77页 |
| 6 利用隐含约束改进图染色算法 | 第77-95页 |
| 6.1 CDCLGCP的基本结构 | 第78-80页 |
| 6.2 改进的单值传播过程 | 第80-84页 |
| 6.3 隐含约束关系的发掘利用及算法的智能回跳 | 第84-91页 |
| 6.4 隐含约束关系的管理技术 | 第91-93页 |
| 6.5 染色初始化技术 | 第93-94页 |
| 6.6 小结 | 第94-95页 |
| 7 实验分析 | 第95-120页 |
| 7.1 实验设置 | 第95-96页 |
| 7.2 隐含约束管理中参数取值的影响 | 第96-99页 |
| 7.3 隐含约束的分布规律 | 第99-101页 |
| 7.4 隐含约束关系的有效性 | 第101-109页 |
| 7.5 与其它高效染色算法的对比分析 | 第109-119页 |
| 7.6 小结 | 第119-120页 |
| 8 总结与展望 | 第120-122页 |
| 8.1 全文总结 | 第120-121页 |
| 8.2 研究展望 | 第121-122页 |
| 致谢 | 第122-123页 |
| 参考文献 | 第123-134页 |
| 附录1 攻读博士学位期间完成的学术论文 | 第134-135页 |
| 附录2 攻读博士学位期间参与的课题目录 | 第135页 |
