3-SAT問題的局部搜索算法.pdf

1、在近半個世紀(jì)以來，算法研究始終是計算機(jī)科學(xué)研究的核心內(nèi)容之一。 作為算法中的經(jīng)典問題之一，可滿足性問題(SAT)是人們證明的最早的NPC問題，它在算法學(xué)中的地位非常重要。3-SAT是SAT問題的一個最重要的子問題，3-SAT(3-SATisfiability)問題可以描述為： 給定n個布爾變量和m個合取范式，每一個合取范式中都只含有上述n個布爾變量中的三個變量，問題是我們該怎么樣給這，n個布爾變量賦值，使得所有的合取范式

2、的取值都是真?若不能，怎么樣賦值才能使盡可能多的合取范式的取值為真? 用計算機(jī)算法語言可以描述為： 實例：布爾變量集合U={u1，u2，...，un}，U上的項集合C={c1，c2，...cm}，滿足︱ci︱=3(1≤i≤n)，即每一個項ci恰好有三個字母組成。 詢問：是否存在UU上的真值指派使C被滿足，或者使C中項盡可能多的滿足。 對這個問題的研究，到目前為止，最好的精確算法的時間復(fù)雜度仍然是O(2n)

3、，最好的近似算法的近似度為1.29。本文對這個問題展開了深入的研究，提出了對這個問題的局部搜索算法。 本文簡要介紹了以往關(guān)于SAT和3-SAT問題的研究結(jié)果，并做出如下結(jié)果： 1．提出了兩個簡單的局部搜索算法，并且巧妙的證明了算法近似度分別是1.25和1.25-ε，比過去最好的理論結(jié)果(近似度是1.29)還要好，并且比它容易簡單的多。 2．采用了簡單的數(shù)據(jù)結(jié)構(gòu)，降低了算法的時間復(fù)雜度，算法的時間復(fù)雜度分別是O(n