| 摘要 | 第1-6页 |
| Some study on SAT and Graph Coloring algorithms | 第6-8页 |
| 目录 | 第8-12页 |
| 第一章 引言 | 第12-14页 |
| 第二章 可满足性问题 | 第14-40页 |
| ·预定义 | 第15-16页 |
| ·典的SAT求解算法 | 第16-19页 |
| ·Zchaff | 第16-17页 |
| ·Walksat | 第17-19页 |
| ·自旋玻璃、SAT问题及其相变现象 | 第19-22页 |
| ·自旋玻璃简介 | 第19-20页 |
| ·相变和骨干 | 第20-21页 |
| ·SAT问题的因子图(Factor Graph)表示 | 第21-22页 |
| ·统计物理和SAT | 第22-24页 |
| ·BP算法简介 | 第24-28页 |
| ·空腔偏量(cavity bias)和空腔场(cavity field) | 第24-25页 |
| ·迭代动态过程(Iteration Dynamics) | 第25-26页 |
| ·BP算法流程 | 第26-28页 |
| ·SP算法简介 | 第28-35页 |
| ·纵览(survey)的定义 | 第28-29页 |
| ·纵览迭代方程 | 第29-31页 |
| ·SP算法流程 | 第31-32页 |
| ·SP启发的消解过程(Survey Inspired Decimation，SID) | 第32-35页 |
| ·SP算法的不完备性 | 第35页 |
| ·不收敛情况分析和回溯 | 第35-36页 |
| ·实验结果 | 第36-37页 |
| ·结论及其他 | 第37页 |
| ·SAT实例生成的一些方法 | 第37-40页 |
| 第三章 图染色问题 | 第40-54页 |
| ·简介 | 第40-41页 |
| ·一些简单的数学结论 | 第41-42页 |
| ·κ-COL问题的相变现象 | 第42-43页 |
| ·图的最大切问题 | 第43-45页 |
| ·简介 | 第43页 |
| ·半定规划简介 | 第43-44页 |
| ·最大切的Goemans-Williamson算法 | 第44-45页 |
| ·基于最大切的图分割染色算法Part | 第45-47页 |
| ·图的分割 | 第45-46页 |
| ·颜色重用 | 第46页 |
| ·顶点削去 | 第46-47页 |
| ·Part实验结果 | 第47-49页 |
| ·图染色的SAT解法 | 第47页 |
| ·实验结果对比 | 第47-49页 |
| ·几种利用打破同构的图染色算法的比较 | 第49-52页 |
| ·对Zchaff的修改 | 第52页 |
| ·X-Zchaff实验结果 | 第52-53页 |
| ·总结 | 第53-54页 |
| 第四章 结语 | 第54-56页 |
| 参考文献 | 第56-64页 |
