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

约束满足问题：算法和复杂性

作　者: 刘涛
导　师: 夏培肃；李国杰
学　校: 中国科学院研究生院（计算技术研究所）
专　业: 计算机组织与结构
关键词: 约束满足问题 复杂性理论 算法 NP-Completeness 局部搜索算法 回溯搜索算法 D-P算法 N-皇后问题 “难度”(Hardness) 相变现象
分类号: TP301.6
类　型: 博士论文
年　份: 1994年
下　载: 533次
引　用: 1次
阅　读: 论文下载
 

内容摘要


约束满足问题(CSPs)在数据库检索(Database Retrieval)、集成电路设计、计算机视觉、定理证明、机器人规划、机器学习等诸多研究领域具有广泛的应用背景。正是因为CSP问题是一类十分普遍的问题以及近年来引人注目的复杂性理论研究促使我们从算法和复杂性两个角度来研究它。 本文工作的重点是针对那些属于NP-Complete的CSP问题(如SAT、K-着色和Hamilton圈问题等)。我们除提出了求解此类型问题的一系列目前最有效算法之外，还讨论了此类问题的难易分布和相变规律。 局部搜索算法和基于回溯的搜索算法是求解CSP问题的两种基本算法。本文结合CSP问题的特点并借助于分治策略将它们有机地结合起来而形成一种快速、完备的求解算法—多级重排搜索算法(MSRA)。MSRA算法在与一般D-P算法的性能比较中所表现出的优势是十分明显的。此外，我们找到了N-皇后问题一个特殊解(或构造解，它区别于历史上所出现的其他解)，并且分析了该问题的特殊性。 之后，本文详尽分析了MSRA算法的平均时间复杂性并且用实验结果进一步证实了所得结论。 考虑到NP-Complete理论通常只关心问题在最坏情况下的复杂性而极少为具体的问题求解算法提供有价值的指导，本文主要从实验分析的角度来研究CSP问题的难解性。由于算法要面对的是一个个具体的问题例，而我们又可将这些具体的问题例以某种方式将其划归若干问题子类，这样，我们就可以通过分析所谓问题例的“难度”(Hardness)及其分布情况来研究CSP的内在规律。在这里，问题例的“难度”指的是该问题例所属问题子类的平均复杂性最小上界。已有研究结果表明CSP问题确实存在“相变”现象，即问题例的“难度”相对于特定序参量(通常指约束条件个数与变量个数之比值)而言分布上的突变现象。这在本文中不仅得到了进一步证实而且更准确地确定了各种CSP问

全文目录


致谢  2-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

相似论文

  1. 基于差分进化算法的JSP环境下成套订单研究,F273
  2. 基于图的标志SNP位点选择算法研究,Q78
  3. 高灵敏度GNSS软件接收机的同步技术研究与实现,P228.4
  4. 天然气脱酸性气体过程中物性研究及数据处理,TE644
  5. 基于Thermo-Calc三元共晶合金凝固路径的耦合计算,TG111.4
  6. 压气机优化平台建立与跨音速压气机气动优化设计,TH45
  7. 多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
  8. 基于感性负载的车身网络控制系统,U463.6
  9. 基于蚁群算法的电梯群优化控制研究,TU857
  10. 高精度激光跟踪装置闭环控制若干关键问题研究,TN249
  11. 半导体激光器热电控制技术研究,TN248.4
  12. AES算法及其DSP实现,TN918.1
  13. 基于UWB脉冲信号的测距定位技术,TN929.5
  14. 基于TS101的DFT输出子集算法研究及软件实现,TN911.72
  15. 高光谱图像空—谱协同超分辨处理研究,TN911.73
  16. DBF接收机用于二维测向算法的研究,TN851
  17. 电视制导系统中视频图像压缩优化设计及实现研究,TN919.81
  18. IEEE802.16e信道编译码算法研究,TN911.22
  19. LDPC码译码算法的研究,TN911.22
  20. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  21. 基于人眼检测的驾驶员疲劳状态识别技术,TP391.41

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