论文部分内容阅读
在近半个世纪以来，算法研究始终是计算机科学研究的核心内容之一。
作为算法中的经典问题之一，可满足性问题(SAT)是人们证明的最早的NPC问题，它在算法学中的地位非常重要。3-SAT是SAT问题的一个最重要的子问题，3-SAT(3-SATisfiability)问题可以描述为：
给定n个布尔变量和m个合取范式，每一个合取范式中都只含有上述n个布尔变量中的三个变量，问题是我们该怎么样给这，n个布尔变量赋值，使得所有的合取范式的取值都是真?若不能，怎么样赋值才能使尽可能多的合取范式的取值为真?
用计算机算法语言可以描述为：
实例：布尔变量集合U={u1，u2，...，un}，U上的项集合C={c1，c2，...cm}，满足︱ci︱=3(1≤i≤n)，即每一个项ci恰好有三个字母组成。
询问：是否存在UU上的真值指派使C被满足，或者使C中项尽可能多的满足。
对这个问题的研究，到目前为止，最好的精确算法的时间复杂度仍然是O(2n)，最好的近似算法的近似度为1.29。本文对这个问题展开了深入的研究，提出了对这个问题的局部搜索算法。
本文简要介绍了以往关于SAT和3-SAT问题的研究结果，并做出如下结果：
1．提出了两个简单的局部搜索算法，并且巧妙的证明了算法近似度分别是1.25和1.25-ε，比过去最好的理论结果(近似度是1.29)还要好，并且比它容易简单的多。
2．采用了简单的数据结构，降低了算法的时间复杂度，算法的时间复杂度分别是O(nm)和O(nm2)。
3．对这一问题的局部搜索算法进行了展望，认为这个局部搜索算法随着所用的时间复杂度的提高，它的近似度会不断的降低，直到时间复杂度提高到O(m22n)，它的近似度也等于1。