浅论3-sat问题的局部搜索算法

《浅论3-sat问题的局部搜索算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文3-SAT问题的局部搜索算法姓名：张平平申请学位级别：硕士专业：计算机软件与理论指导教师：朱大铭20080405山东大学硕士学位论文摘要在近半个世纪以来，算法研究始终是计算机科学研究的核心内容之一。作为算法中的经典问题之一，可满足性问题(SAT)是人们证明的最早的NPC问题，它在算法学中的地位非常重要。3．SAT是SAT问题的一个最重要的子问题，3-SAT(3一SATisfiability)问题可以描述为：给定刀个布尔变量和m个合取范式，每一个合取范式中都只含有上述刀个布尔变量中的三个变量，问题是

2、我们该怎么样给这以个布尔变量赋值，使得所有的合取范式的取值都是真?若不能，怎么样赋值才能使尽可能多的合取范式的取值为真?用计算机算法语言可以描述为：实例：布尔变量集合u={"1，”2，．．．，％}，U上的项集合C={c1，c2，．．．c。}，满足IC，l-3(1≤f≤拧)，即每一个项C，恰好有三个字母组成。询问：是否存在UU上的真值指派使C被满足，或者使C中项尽可能多的满足。对这个问题的研究，到目前为止，最好的精确算法的时间复杂度仍然是0(2”)，最好的近似算法的近似度为1．29。本文对这个问题展开了深入的研究，提出

3、了对这个问题的局部搜索算法。本文简要介绍了以往关于SAT和3．SAT问题的研究结果，并做出如下结果：1．提出了两个简单的局部搜索算法，并且巧妙的证明了算法近似度分别是1．25和1．25一s，比过去最好的理论结果(近似度是1．29)还要好，并且比它容易简单的多。2．采用了简单的数据结构，降低了算法的时间复杂度，算法的时间复杂度分别是O(nm)和O(nm2)。3．对这一问题的局部搜索算法进行了展望，认为这个局部搜索算法随着所用的时间复杂度的提高，它的近似度会不断的降低，直到时间复杂度提高到D沏22”)，它的近似度也等于1

4、。山东大学硕士学位论文关键字：3-SAT；布尔变量；合取范式II山东大学硕士学位论文ABSTRACTCOmputerAfgOrithmtheoryisanewtheoryafterthebornofthecomputer，anditistakenintotheconsiderationofthehumans’mindgoingwiththecomputerwidelyusedinmanyareas。ThestudyoftheComputerAlgorithmtheoryisthehotpointofthecomput

5、erscienceduringthepasthalfcentury。Gradually，peoplefindthatthestudyofcomputeralgonthmisjustonejobthatisrichinchallengeanditisalsoanimportantjobthatishelpfultothestudyofthecomputerscience。3-SATisfiabilityproblem(3-SAT)，asReoftheclassicalquestionsincomputeralgorit

6、hm，isoneoftheearliestquestionsthatareprovedtobeNPC(NP．Complete)。Itisimportantinthecomputeralgorithm。PeoplecouldstudytherelationshipbetweenPproblemsandNPproblemsbystudy3．SAT。Wecoulddepictthe3一SATproblemby：Given／11BooleanVariablesandtnClauses。Eeahclausecontains3o

7、fthe力variables。Thenthequestionis：Inordertomakealloftheclausesistrue，howtodecidethevalueofeachvariable?Andinordertogetmoreclausesthatistrue，howtodecideeveryvariable’Svalue?Wealsocoulddepictitbyexpertisecomputerlanguage：Instance：AsetofBooleanvariablesU={HI)”2，．．．

8、，材。)andasetofclausesonvadablesC={c1，C2，⋯c。)，ICfI=3(1≤f≤刀)，thatis，everyclauseisjustcomprisedof3variables。Ask：IsthereatruevalueassignedthattheclausesinsetCarealltrue?Orfindatr