3-SAT問(wèn)題的局部搜索算法.pdf

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

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

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