学位论文 > 优秀研究生学位论文题录展示

可满足性问题和图染色的一些研究

作　者: 李韶华
导　师: 张健
学　校: 中国科学院研究生院（软件研究所）
专　业: 计算机软件与理论
关键词: 约束求解 可满足性问题 纵览传播 半定规划 图染色
分类号: TP301.6
类　型: 硕士论文
年　份: 2005年
下　载: 173次
引　用: 1次
阅　读: 论文下载
 

内容摘要


约束求解(CSP)是计算机理论界历史悠久的问题,有着广泛的应用。本论文集中讨论了两种CSP问题:SAT和图染色问题,介绍了比较新的SAT算法Survey Propagation(SP)和自己在SP算法上的改进;介绍了自己提出的图染色分割算法Part及两种打破同构的图染色SAT算法X-Zchaff。并给出了相应的实验结果。

全文目录


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

相似论文

  1. 基于约束图的服装参数化制板技术,TS941.2
  2. 交替投影法的应用,O224
  3. 开源软件依赖可满足性识别方法研究与实现,TP311.52
  4. 非线性半定规划参数型FB系统的非奇异性研究,O221.2
  5. 半定规划的灵敏度分析,O221.2
  6. DNA自组装计算模型的应用研究,O242.1
  7. 一全局收敛的求解不等式约整非线性半定规划的内点算法,O221.2
  8. 基于图染色理论的信息隐藏模式,TP309
  9. 图的临界群和染色唯一性的研究,O157.5
  10. 铝酸钠溶液成分浓度软测量数模研究与软件开发,TF821
  11. 飞机装配型架设计约束求解技术研究与实现,V262.4
  12. 基于进化非选择算法的可满足性问题求解,TP18
  13. 张量积B-样条凸函数拟合方法及其在电路建模中的应用,TN47
  14. 半定规划问题的两种数值解法,O221
  15. 基于遗传模拟退火算法的约束求解研究,TP391.72
  16. 关于图的邻点可区别全染色的研究,O157.5
  17. 纵览传播算法求解随机3-SAT问题,TP18
  18. 求解非凸半定规划的一个非线性Lagrange方法,O221.2
  19. 语义特征造型及约束求解的研究,TP391.72
  20. 自由曲面特征的约束求解及其有效性维护的研究,TP391.72
  21. 基于交互式特征造型的约束求解研究,TP391.72

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com