关于布尔可满足性判定的新方法研究
发布时间：2021-01-27 06:54
布尔可满足性（Boolean Satisfiability,SAT）问题是指,给定一组布尔变元X及由X构成的CNF公式,问是否存在一组对X的赋值,使得公式为真。SAT问题是第一个被证明为NP完全的问题,在计算理论中具有重要地位。如果找到能够在多项式时间求解SAT问题的完备方法,则P=NP;反之,如果能够确定所有SAT算法的最坏时间复杂度下界为指数级别,则P≠NP。此外,SAT问题在电路验证、组合优化、自动推理等领域有重要的实践意义。当前,SAT问题的求解算法分为完备算法和不完备算法。完备算法总是能够找到一个满足公式的赋值,或者证明公式的不可满足性。基于DPLL的搜索算法是目前主流的一类完备算法,这类算法用回溯的方法,对赋值空间进行系统的搜索。在对DPLL算法的各种改进中,CDCL算法利用子句学习和非逐字回溯大大减少了回溯次数。目前已知的完备算法最坏时间复杂度为指数级别。而不完备算法针对实际的SAT问题,提高了求解效率。其中,局部搜索算法广泛应用了概率和贪心的策略,只对赋值空间的一部分进行搜索,提高了搜索效率。基于优化的方法将SAT问题转化为优化问题,然后用拉格朗日法、牛顿法等方法解决。...
【文章来源】：中国科学院大学(中国科学院重庆绿色智能技术研究院)重庆市
【文章页数】：79 页
【学位级别】：硕士
【部分图文】：
图３．１?ＤＰＬＬ搜索树图示??元传播化简的公式Ｊｅ
图３．２蕴含图示例??
?关于布尔可满足性判定的新方法研究???ｆ?０?Ｊ——?０⑴??，２＝１０＾０??，＝１?￡）??图３．３?ＣＤＣＬ搜索树图示??（在第／ｅｖｅ／层）与其父节点的边（在第／ｅｖｄ－１层）对应的赋值，记Ｌｅｖｄ（Ｘｕ）?＝??／ｅｖｄ－１。另一种顶点是矛盾顶点，记为Ａ＾，由其他的顶点推出。蕴含图中，有??向边的出发点是赋值（决策赋值或者蕴含赋值），终点是蕴含赋值或者矛盾。有??向边用的标记，表示代入这条边出发点对应的赋值后，Ｍ成为新的单元子句或??者空子句，用单元传播推出终点对应的蕴含赋值或者矛盾。??仍然以〇＾公式７７＝｛０１，〇）２，，．，，叫｝为例，其中，〇；１?＝?｛＾＇１，＆｝，〇）２?＝??｛Ｘ２，Ｘ３｝，的＝卜＆，￣＾４，＾｝’?叫＝｛，Ｘ丨，Ｘ４，Ｘ６｝，吨＝■｛，Ｘ１，，Ｘ５，Ｘ６｝，叫＝??卜Ａ：ｈＸ４，＊ｎＸ６｝，的＝｛－＾，，Ｘ５，，Ｘ６｝，叫＝｛Ｘ３，Ｘ７｝。为了对比ＤＰＬＬ算法与??ＣＤＣＬ算法的搜索过程，将ＣＤＣＬ算法对ＪＴ赋值的搜索过程呈现为图３．３中的搜索??树。在节点“１１１１”发生矛盾之前，搜索流程与ＤＰＬＬ相同，之后的回溯机制??以及节点０Ｗ和的含义将在后文中详述。当在节点“１１１１”发生矛盾??时，生成的蕴含图如图３．２所示。在第０层的边上赋值不：＝１，在第３层的边上??赋值Ｘ４：＝ｌ以后，在第４层的顶点上由叱得出Ｘ５＝ｌ。因此，在蕴含图中有两条??标记为叱的有向边分别从‘％?：＝?１?＼?０”和“＆?：＝?１?＼?３”指向“Ｘ５?＝?１?＼?３”。??矛盾集合用ＣＳ（Ａ／）表示。在求ＣＳ（Ａ〇之前，首先定义集合儿Ｐ（ｇ）。ＡＰＯ）是??一个赋值的集合，元素为在子句＾中
【参考文献】：
期刊论文
[1]CDCLSAT求解器的重启策略分析[J]. 程睿,周彩兰,徐宁,周强. 计算机辅助设计与图形学学报. 2018(06)
[2]调查传播算法收敛的一个充分条件[J]. 王晓峰,许道云,姜久雷,唐延辉. 中国科学:信息科学. 2017(12)
[3]基于加强概率控制策略的SAT局部搜索算法[J]. 洪剑珂,张峥华,许贵平. 计算机工程与应用. 2017(14)
[4]求解SAT问题的算法的研究进展[J]. 郭莹,张长胜,张斌. 计算机科学. 2016(03)
本文编号：3002641
【文章来源】：中国科学院大学(中国科学院重庆绿色智能技术研究院)重庆市
【文章页数】：79 页
【学位级别】：硕士
【部分图文】：
图３．１?ＤＰＬＬ搜索树图示??元传播化简的公式Ｊｅ
图３．２蕴含图示例??
?关于布尔可满足性判定的新方法研究???ｆ?０?Ｊ——?０⑴??，２＝１０＾０??，＝１?￡）??图３．３?ＣＤＣＬ搜索树图示??（在第／ｅｖｅ／层）与其父节点的边（在第／ｅｖｄ－１层）对应的赋值，记Ｌｅｖｄ（Ｘｕ）?＝??／ｅｖｄ－１。另一种顶点是矛盾顶点，记为Ａ＾，由其他的顶点推出。蕴含图中，有??向边的出发点是赋值（决策赋值或者蕴含赋值），终点是蕴含赋值或者矛盾。有??向边用的标记，表示代入这条边出发点对应的赋值后，Ｍ成为新的单元子句或??者空子句，用单元传播推出终点对应的蕴含赋值或者矛盾。??仍然以〇＾公式７７＝｛０１，〇）２，，．，，叫｝为例，其中，〇；１?＝?｛＾＇１，＆｝，〇）２?＝??｛Ｘ２，Ｘ３｝，的＝卜＆，￣＾４，＾｝’?叫＝｛，Ｘ丨，Ｘ４，Ｘ６｝，吨＝■｛，Ｘ１，，Ｘ５，Ｘ６｝，叫＝??卜Ａ：ｈＸ４，＊ｎＸ６｝，的＝｛－＾，，Ｘ５，，Ｘ６｝，叫＝｛Ｘ３，Ｘ７｝。为了对比ＤＰＬＬ算法与??ＣＤＣＬ算法的搜索过程，将ＣＤＣＬ算法对ＪＴ赋值的搜索过程呈现为图３．３中的搜索??树。在节点“１１１１”发生矛盾之前，搜索流程与ＤＰＬＬ相同，之后的回溯机制??以及节点０Ｗ和的含义将在后文中详述。当在节点“１１１１”发生矛盾??时，生成的蕴含图如图３．２所示。在第０层的边上赋值不：＝１，在第３层的边上??赋值Ｘ４：＝ｌ以后，在第４层的顶点上由叱得出Ｘ５＝ｌ。因此，在蕴含图中有两条??标记为叱的有向边分别从‘％?：＝?１?＼?０”和“＆?：＝?１?＼?３”指向“Ｘ５?＝?１?＼?３”。??矛盾集合用ＣＳ（Ａ／）表示。在求ＣＳ（Ａ〇之前，首先定义集合儿Ｐ（ｇ）。ＡＰＯ）是??一个赋值的集合，元素为在子句＾中
【参考文献】：
期刊论文
[1]CDCLSAT求解器的重启策略分析[J]. 程睿,周彩兰,徐宁,周强. 计算机辅助设计与图形学学报. 2018(06)
[2]调查传播算法收敛的一个充分条件[J]. 王晓峰,许道云,姜久雷,唐延辉. 中国科学:信息科学. 2017(12)
[3]基于加强概率控制策略的SAT局部搜索算法[J]. 洪剑珂,张峥华,许贵平. 计算机工程与应用. 2017(14)
[4]求解SAT问题的算法的研究进展[J]. 郭莹,张长胜,张斌. 计算机科学. 2016(03)
本文编号：3002641
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3002641.html
