命題可滿足性問題（SAT）的局部搜索算法研究與改進.pdf

1、中山大學(xué)碩士學(xué)位論文命題可滿足性問題（SAT）的局部搜索算法研究與改進姓名：龍勝申請學(xué)位級別：碩士專業(yè)：計算機軟件與理論指導(dǎo)教師：蘇開樂20080508中山大學(xué)碩士學(xué)位論文命題可滿足性問題(SAD的局部搜索算法研究與改進ResearchandIInproVememonLocalSearchAlgorit№sforthePropositonalSatisfiabilityProblem(SAT)M萄or：CoInputerSo舢yarea

2、ndTheo巧Name：ShengLongSupervisor：ProfessorKaileSuABSTRACTThePropositonalSatisfiabili夠Problem(SAT)ismetaSktodedde南ra百VenpropositonalfomulainconjullctiVenomalfom(CNF)whetherthereisaIlassig呦enttoitsVadablesthatsatisfiesthefo

3、舯ulaSATisacentralprobl鋤inlo沓c，arti矗calintellige置1ce，meoreticalcomputerscienceandmanya_pplicationsTherefore，it’sVeryimport觚ttoresearchandi珈【proVeSATalgoritllIIlsbomintheoryaIldinpracticeRecently，itwasShownmat10calsearchal

4、gorithnlscalloutperfonnmaIlysystematicsearc_halgorithmsonsonlela疆reclassesofSATproblemsInthist11esis，localsearchalgorithmsforSATarcresearchedfirstlyAjcterresearcmngsomeexistingSAT10calsearChalgorithms，wefindt11atmestrate

5、酉esusedintllesealgoritllInsareLook—AheadonestepandthushaVesomeproblemsInordertostrell垂hellme伊eedyde筍eeof10calsearch，decreasethenumberofnipping向rfindingasolution，aIldimproVesearchings01utionablityofalgori如[Ils，weproposean

6、ewalgoritllmics仃ategycalledLook—Ahead—Twostepstoimprove廿lemethodhowtoselectaVariablet0nipinSAT10calsearchTlleLook—AheadTwices仃ategyprcposedinthjstheSisiscomposedofLook—AheadOnest印strategya11dLookAheadTwostepss仃ategyWegot

7、three目oupsofnewalgoritllInsbaSedonWalkSATbyapplyingthepmposeds仃ateg)，onthreeimportalltcurrentlocalsearChalgorimms，ieWSAT，TSAT，aIldNoVeltyFurth鋤ore，weiInplementsuchimpr0Vedalgorithms111ordertoC0mparemesenewalgorimmswimthe