| 致谢 | 第1-3页 |
| 摘要 | 第3-5页 |
| ABSTRACT | 第5-11页 |
| 第一章 引言 | 第11-16页 |
| §1.1 约束满足问题(CSPs)及其难解性 | 第11-12页 |
| §1.2 算法复杂性与问题复杂性 | 第12-14页 |
| §1.3 本文的主要工作 | 第14页 |
| §1.4 论文概要 | 第14-16页 |
| 第二章 约束满足问题 | 第16-29页 |
| §2.1 引言 | 第16页 |
| §2.2 约束满足问题的表示 | 第16-17页 |
| §2.3 求解CSP问题的各类算法 | 第17-29页 |
| §2.3.1 回溯搜索算法 | 第17-25页 |
| §2.3.2 局部搜索算法(Local Search) | 第25-29页 |
| 第三章 分级重排搜索算法(MSRA) | 第29-57页 |
| §3.1 分级重排搜索算法的一般性描述 | 第29-30页 |
| §3.2 一个特例—N-皇后问题 | 第30-34页 |
| §3.3 可满足性(SAT)问题的求解算法 | 第34-47页 |
| §3.3.1 SAT问题的几种表示方式 | 第34-35页 |
| §3.3.2 “弱”约束情况下的局部搜索算法 | 第35-39页 |
| §3.3.3 “强”约束情况下求解小规模SAT问题的回溯算法 | 第39-41页 |
| §3.3.4 “强”约束情况下求解大规模SAT问题的分级重排搜索算法 | 第41-46页 |
| §3.3.5 算法性能比较 | 第46-47页 |
| §3.4 图着色问题的快速算法 | 第47-54页 |
| §3.4.1 K-着色问题的表示形式及其某些特性 | 第47-49页 |
| §3.4.2 求解K-着色问题的局部搜索法 | 第49-51页 |
| §3.4.3 求解小规模图的K-着色问题的回溯算法 | 第51页 |
| §3.4.4 求解大规模K-着色问题的分级重排算法 | 第51-54页 |
| §3.5 Hamilton圈及其他CSP问题的求解算法 | 第54-57页 |
| §3.5.1 Hamilton圈问题及其特点 | 第54-56页 |
| §3.5.2 求解其他NP-Complete问题时的情况 | 第56-57页 |
| 第四章 分级重排搜索算法的复杂性分析 | 第57-76页 |
| §4.1 求解SAT问题的局部搜索算法复杂性分析 | 第57-66页 |
| §4.2 求解SAT问题的回溯算法复杂性分析 | 第66-76页 |
| §4.2.1 模型和定义 | 第66-68页 |
| §4.2.2 搜索树大小分析 | 第68-76页 |
| 第五章 相变与难解性 | 第76-100页 |
| §5.1 从有序到混沌(Chaos) | 第76-78页 |
| §5.2 相变与问题难解性之间的关系 | 第78-82页 |
| §5.3 SAT问题的相变现象及其分析 | 第82-91页 |
| §5.4 其他CSP问题的相变现象 | 第91-100页 |
| 第六章 总结 | 第100-102页 |
| §8.1 结论 | 第100-101页 |
| §8.2 存在的问题和进一步的工作 | 第101-102页 |
| 参考文献 | 第102-108页 |
| 作者简历 | 第108页 |
