带随机步的可满足性算法

摘要

满足性问题是研究如何判定一个任意给定的逻辑表达式是否存在可满足真值指派，它是人工智能、计算理论和理论计算机科学中的最瞩目问题之一，它是第一个被证明的NP完全问题，在计算复杂性理论中起着很重要的作用。求解SAT问题一般分为完全算法和非完全算法两类。如果一个SAT实例有可满足解，完全算法能够找到可满足解，如果这个SAT实例无解，完全算法能给出所有解都是不可满足的证明，但需要花指数级时间；对于一个可满足的SAT实例，非完全算法一般都能以很高的概率找到其可满足解，虽然对一些满足解很少的SAT实例不能找到其满足解，但是非完全算法能在多项式时间内结束算法，所以非完全算法在实际应用中得到了广泛的应用。 随机算法是求解SAT问题的一种重要的非完全算法，就是在算法中引入随机化，算法中根据随机数选择下一步的操作。随机算法的一般框架是随机地选取一个给定SAT实例的解，验证其是否满足，如果满足，算法结束；否则，就根据随机源所产生的随机数选择下一个解，直到找到一个满足解或者到t个解后算法结束。在随机算法中由随机源产生随机数，但真正的随机源很难得到，一般用伪随机数发生器来代替，这也是随机算法的一个致命弱点。改进的办法有两种：一种是改进伪随机数发生器；另一种是在不改变算法的性能的情况下，尽量减少伪随机数的产生，从而减少算法对随机位的依赖。 本文研究的是后一种方法，在随机算法中引入膨胀图，利用膨胀图的性质去诱导算法中的随机步，减少算法中伪随机数的产生，进而减少算法对随机数的依赖和伪随机数对算法的影响。一般的随机算法中如果搜索t个解，随机搜索一个解需要n位伪随机码(n为给定SAT实例中的变元个数)，总共需要tn位伪随机码；而在本文中的算法只需要n+((t-1)log2n位伪随机码，减少了算法中伪随机码的产生，降低了伪随机码对算法的影响。

目录

文摘

英文文摘

声明

第一章绪论

1.1 SAT问题的研究背景

1.2研究动机

1.3研究的问题

1.4本文的主要工作及内容安排

第二章SAT问题及相关知识

2.1引言

2.2 SAT问题的基本符号和定义

2.3难解性问题

2.4P与NP

2.5 Cook定理

2.6求解SAT问题的算法

第三章随机算法

3.1引言

3.2随机算法及相关概念

3.3随机算法的分类

3.4随机算法的复杂度类

3.5随机算法的相关概率及求解框架

3.5.1相关概率

3.5.2随机算法的求解框架

3.6对随机算法研究的意义

第四章膨胀图及相关概率

4.1引言

4.1膨胀图的基本知识

4.2膨胀图上的随机步概率上界估计

第五章带随机步的可满足性算法

5.1引言

5.2膨胀图上随机步在算法设计中的应用

5.3利用膨胀图求解SAT问题的随机算法

5.4对本算法进行分析

5.5结论和进一步的工作

致谢

参考文献

附录