sat问题的随机算法的转移矩阵模型

《sat问题的随机算法的转移矩阵模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文SAT问题的随机算法的转移矩阵模型姓名：曾卫玲申请学位级别：硕士专业：计算机软件与理论指导教师：黄刘生;周智20050501中匿科学歉米矢擎硕士学位论文SAT问题的随机算法的转移矩阵模型摘要合取范式CNF(ConjunctiveNormalForm)的可满足性SAT(Satisfiability)问题是人工智能、计算理论和理论计算机科学中的最瞩目问题之一。SAT问题的描述是简单的，但它是第一个被证明的NP完全问题。同时该问题在自动推理、计算机辅助设计和制造、机器视觉、数据库、机器

2、人、集成电路、计算机体系结构设计和计算机网格设计等许多实际问题中得到了广泛的应用。一些求解SAT问题的最成功的有效算法。如随机爬山法、禁忌搜索法、模拟退火法都是基于随机算法的思想。随机化方法已是求解SAT问题的非常有效的方法。特别是近十年来，SAT问题的随机局部搜索算法取得了突破性进展，同时用统计物理学的方法研究相变现象也取得了相当的进展。新的瓶颈问题在于对搜索空间缺乏了解，使得人们只能评澳4算法却不能解释它。为此，本文对SAT问题的随机局部搜索算法的执行轨迹进行Markov建模，并推导出算法的转移矩阵模型

3、。本文韵主要工作如下：’(1)分析随机局部搜索算法的通用框架，及三种算法变种：GSAT、RandomWalk、WalkSA=r在选取子句和翻转原子上的不同策略。(2)在分析比较搜索空间上实验研究的特点和不足的基础上，选用Markov建模方法来建立我们的转移矩阵的理论模型。(3)通过概率方法抽象和定义，给出RandomWalk算法的基本转移矩阵模型。然后进一步推导出其他策略上的转移概率模型，包括GSAT、GCWSAT、WalkSAT等策略。(4)对搜索空间的某些属性进行实验统计分析，得出其概率分布，并代入上述

4、模型中，得到模型上的转移矩阵概率。(5)通过大量随机SAT实例上的实验统计，得到实例规模上的转移矩阵概率。通过和上述理论模型上概率之间的比较，实验结果进一步验证我们的转移矩阵模型的正确性。本文的研究得到国家973重点基础研究发展规划项目“难解问题的高效实用算法及其应用”(No．G1998030403)的资助。关键词：SAT问题、随机算法、搜索空间、转移矩阵模型!里型兰垫查查堂婴圭堂堡垒兰!坚塑墅塑堕垫簦鲨塑生堡塑壁塑型AbstractTheSAT(satisfiability)problemforpropo

5、sitionalformulasinC_Ⅲ(conjunctivenormalform)isoneofthemostprominentproblemsinartificialintelligence、computingtheoryandtheoreticalcomputerscience．AlthoughthedescriptionofSATproblemisverysimple，itisthefirstproblemshowntobeNP—completeandplaysanimportantrolein

6、solvingmanyproblemsinautomatedreasoning、computer-aideddesign、computer-aidedmanufacturing、machinevision，database、robotic、integratedcircuitdesign、computerarchitecturedesignetc。SomeofthemostsuccessfulandpowerfulalgorithmsforSATproblem，suchasrandomizedhill·cli

7、mbing、tabusearch、andsimulatedamaealing，arebasedonrandomizedalgorithms．RandomizationhasprovedtobeaveryusefultechniqueinsolvingSATproblem．Inrecentyears，SATrandomizedalgorithmshavemadeagreatbreakthrough．Thestudyofphasetransitionbystatisticalphysicalscientists

8、hasalsomaderapiddlyprogress．Thenewbottleneckliesinlittleunderstandingofthesearchspaceofrandomizedalgorithms，whichresultswecarlonlyevaluatealgorithmsbutCannotexptmnthem．Sowefirstmodelthetrackofrandomizedalgori