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

命题逻辑的可满足性问题：复杂性和算法

作　者: 卜东波
导　师: 白硕
学　校: 中国科学院研究生院（计算技术研究所）
专　业: 计算机科学理论
关键词: 约束满足问题可满足性问题 NP-Complete问题局部搜索算法分枝回溯算法难度相变现象
分类号: TP18
类　型: 硕士论文
年　份: 1997年
下　载: 297次
引　用: 0次
阅　读: 论文下载

内容摘要

可满足性问题(Satisfiablity问题)在数理逻辑、人工智能、机器学习、约束满足问题、VLSI集成电路设计与检测以及计算机科学理论等等领域具有广阔的应用背景。可满足性问题是第一个NP-Complete问题，并且是一大类NP-Complete问题的核心。大量的实践表明，许多NP-Complete问题无论是对于计算机科学理论还是工程应用都有着至关重要的意义。可满足性问题的重要性以及它的一些奇妙的性质促使我们从问题和算法两个角度来研究它。我们主要从问题本身的固有性质和快速求解算法两个角度来研究可满足性问题。值得注意的是：这两方面的研究工作是相辅相成、互相促进、互相启发的。从问题的角度，我们着重研究可满足性问题的相变现象以及问题实例的难度。这方面的工作更加清晰地刻划出问题本身的固有属性，从而有助于对问题的完整认识和合理分类，并且针对于各个不同的问题子类可以开发出更有效的算法。从算法的角度，我们分析了完备性算法和不完备性算法的复杂性，比较了两者的优缺点和适用范围，进而提出了将以上两种算法更加完美的结合的思想。我们提出的算法CCSAT和USAT，即分别针对于利用不完备性算法为完备性算法提供更强的启发式信息和利用完备性算法帮助不完备性算法处理局部极值点两个方向的结合。通过重新认识2SAT∈P这一结论证明的实质，也给算法的设计提供了新的思路。问题的复杂性是问题的一个固有属性。我们试图用难度这个概念来描述和刻划它，并且给出了难度的一个新的、形式化定义的猜想。自然界中的物质皆有其物态和相，以及随系统序参数而发生的物质从一个相到另一个相的相变现象。作为一个复杂的计算系统，可满足性问题也有一个奇妙的相变现象，即问题实例的可满足概率随着实例的特定序参量的变化而发生的突变现象。我们提出了一种布尔筛模型，更加清晰地描述出相变现象。我们主要做了以下8项工作，分为问题性质剖析类(标记为“P”)和

全文目录

摘要  4-7
Abstract  7-12
第一章引言  12-16
  1.1 NP-Complete问题和可满足性问题  12-13
  1.2 算法的优劣：收敛性和复杂性  13-14
  1.3 论文概要  14-16
第二章可满足性问题综述  16-32
  2.1 可满足问题的表示  16-17
  2.2 求解SAT问题的算法  17-27
    2.2.1 完备性算法  18-23
    2.2.2 局部搜索算法(Local Search)  23-27
  2.3 相变现象  27-32
    2.3.1 物理学中的相变现象  27-30
    2.3.2 可满足性问题中的相变现象  30-32
第三章相变现象和难度  32-48
  3.1 3-SAT问题可满足概率的布尔筛模型  32-37
  3.2 2-3-SAT问题的可满足概率  37-39
  3.3 相变现象的统计描述  39-45
    3.3.1 可能解的个数的期望值  39-44
    3.3.2 相变点上界的估计  44-45
  3.4.总结  45
  3.5 进一步的讨论  45-48
第四章可满足性问题的求解算法  48-67
  4.1 完备性算法和不完备性算法的比较  48-49
  4.2 求解SAT问题的完备性算法—CCSAT(Conflicted Cycle SAT)  49-55
    4.2.1 Crawford方案的剖析和CCSAT算法的提出  49-52
    4.2.2 mom策略的缺陷  52-53
    4.2.3 无级重排  53-54
    4.2.4.实验数据  54-55
  4.3 求解SAT问题算法的统一模型USAT(Uniform SAT)  55-60
    4.3.1 GSAT算法的特点及子空间旋转策略的引入  55-56
    4.3.2 统一的算法模型USAT  56-58
    4.3.3 实验数据  58-59
    4.3.4 总结  59-60
  4.4 求解SAT问题的第三类算法—概率性算法  60-62
  4.5 完备性算法APTSAT(Avoid Phase Transition SAT)  62-64
    4.5.1 子问题的又一种分类方法  63
    4.5.2 完备性算法APTSAT  63-64
  4.6 新的剪枝规则：Subset-Prune剪枝  64-67
    4.6.1 求解2-SAT问题的P算法  64-66
    4.6.2 Subset-Prune剪枝规则  66-67
第五章结束语  67-68
参考文献  68-71
硕士期间发表的论文  71-72
作者简历  72

命题逻辑的可满足性问题：复杂性和算法

内容摘要

全文目录

相似论文