命题逻辑中随机3-SAT问题算法研究

发布时间：2017-06-22 17:19

  本文关键词：命题逻辑中随机3-SAT问题算法研究，由笔耕文化传播整理发布。

【摘要】：命题逻辑公式的可满足性问题(SAT)是计算机科学和人工智能中一个重要问题。它是第一个被证明了的NP完全问题,由Stephen Cook于1971年提出。SAT问题在人工智能、软件工程、VLSI集成电路设计等领域具有广泛的应用。3-SAT问题是每个子句的文字个数固定为3的SAT问题。作为SAT问题的子问题之一,3-SAT问题也是NP完全问题。3-SAT问题有来自工业问题转化的实际问题,也有机器自动生成的。来自工业问题转化的3-SAT问题在数目和结构上都有很大的限制,根本不能满足各类SAT算法的测试需求,所以目前大部分的3-SAT问题来自机器自动生成,这类问题又称为随机3-SAT问题。当变元的数目达到1000乃至1兆的规模时,3-SAT问题的求解变得异常困难,所以对大规模随机3-SAT的求解是一个比较有前景的研究领域。自从20世纪80年代随机3-SAT问题被提出以来,很多学者在这方面做了大量的工作,提出了各种各样的算法。当前较为高效的算法有Sparrow2011算法、ProbSAT算法、CCMC算法等。然而这些算法,在求解较大规模的随机3-SAT问题上的效率仍不够理想。本文在综合分析以往SAT问题算法的基础上,在提高随机3-SAT问题的求解效率方面主要做了如下工作：1、基于SAT问题的自身结构,研究各个文字在子句集中出现的频率,挖掘出文字与子句集可满足性判定的关系。给出文字的关键度和关键文字的概念,利用关键文字规则和DPLL规则设计出了对子句集初始真值指派的优化策略。2、给出了基于优化后的初始真值指派的新的WASAT算法,算法先是运用真值指派综合评估函数来寻求更优的赋值,然后运用子句权重重置的策略,跳出局部最优解开辟新的搜索区域。3、运用来自SAT竞赛网站的不同规模的随机3-SAT实例设计实验并得出结果。通过对比Sparrow2011算法、ProbSAT算法、CCMC算法,评估并分析了新的权重分析算法的效率。
【关键词】：子句 子句集 随机3-SAT 可满足性 关键文字 子句权重 真值指派 权重重置 权值评估函数
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O141
【目录】：

• 摘要6-8
• Abstract8-12
• 第1章 绪论12-17
• 1.1 研究背景和和研究意义12-13
• 1.2 国内外研究现状13-15
• 1.3 本文研究的内容和结构安排15-17
• 第2章 基础知识17-21
• 2.1 基本概念17-19
• 2.2 符号说明19-20
• 2.3 本章小结20-21
• 第3章 4种SAT问题的算法介绍21-29
• 3.1 SDF算法21-23
• 3.2 Sparrow2011算法23-25
• 3.3 ProbSAT算法25-26
• 3.4 CCMC算法26-27
• 3.5 本章小结27-29
• 第4章 随机3-SAT问题新算法29-46
• 4.1 初始赋值的优化29-37
• 4.2 随机3-SAT问题新算法37-40
• 4.3 子句权重重置函数40-45
• 4.4 本章小结45-46
• 第5章 算法评估46-51
• 5.1 理论评估46-47
• 5.2 测试标准47-48
• 5.3 测试结果比较48-50
• 5.4 本章小结50-51
• 第6章 总结与展望51-53
• 6.1 论文总结51
• 6.2 展望51-53
• 致谢53-54
• 参考文献54-60
• 附录：WASAT算法源代码60-78
• 攻读硕士学位期间发表的论文及参与的科研工作78

【相似文献】

中国期刊全文数据库 前10条

1 邹汪平;;一种基于网络安全控制的蜂群算法应用研究[J];吉林师范大学学报(自然科学版);2013年04期

2 郭毅可;韩锐;;云计算中的弹性算法:概要和展望[J];上海大学学报(自然科学版);2013年01期

3 刘江华;戴新喜;白似雪;;基于模式矩阵的P_Matrix算法[J];南昌大学学报(理科版);2007年05期

4 胡俊鹏;;基于双向选择的蚁群相遇算法的优化[J];湖北民族学院学报(自然科学版);2013年01期

5 张丽;;关联规则挖掘算法的研究[J];赤峰学院学报(自然科学版);2013年02期

6 吴秋峰;尹海东;孟翔燕;;基于和积和最大积的信念传播算法的收敛性分析[J];数学的实践与认识;2011年09期

7 赵吉东;;蚁群算法的改进策略研究[J];中国科技信息;2012年12期

8 胡森森;周贤善;;一种改进蚁群算法的研究[J];长江大学学报(自科版);2006年10期

9 王恒娜;赵晓静;;基于属性覆盖的关联规则挖掘算法[J];安庆师范学院学报(自然科学版);2007年03期

10 曹建军;刁兴春;李凯齐;邵衍振;;基于进化强度的蚁群算法过程性能评价[J];解放军理工大学学报(自然科学版);2013年01期

中国重要会议论文全文数据库 前10条

1 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会——2004年学术年会论文集[C];2004年

2 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会2004年学术年会论文集[C];2004年

3 符丽锦;覃华;邓海;孙欣;;一种改进的Apriori算法的研究[A];广西计算机学会2012年学术年会论文集[C];2012年

4 王东锋;王军民;陈英武;;模糊定性仿真理论研究与算法实现[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年

5 赵唯;;晶粒度评级的改进算法[A];中国图象图形科学技术新进展——第九届全国图象图形科技大会论文集[C];1998年

6 刘启文;;可扩展的图形学算法演示系统的研究[A];’2004计算机应用技术交流会议论文集[C];2004年

7 佘智;蒋泰;朱延生;;基于Type C协议的防冲突改进算法[A];广西计算机学会25周年纪念会暨2011年学术年会论文集[C];2011年

8 朱绍文;赵培;朱秋云;;基于pSPADE并行挖掘序列算法的研究[A];2003年中国智能自动化会议论文集（下册）[C];2003年

9 杨霞;;新的基于启发式蚁群算法的QoS路由算法[A];广西计算机学会2009年年会论文集[C];2009年

10 陈黎飞;姜青山;董槐林;;基于图形轮廓的快速聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

中国博士学位论文全文数据库 前10条

1 钟永腾;基于近场MUSIC算法的复合材料结构健康监测研究[D];南京航空航天大学;2014年

2 单美静;求解非线性实代数系统的混合算法研究[D];华东师范大学;2008年

3 邱剑锋;人工蜂群算法的改进方法与收敛性理论的研究[D];安徽大学;2014年

4 潘磊;若干社区发现算法研究[D];南京大学;2014年

5 陈俊波;频繁闭合项集挖掘算法及应用研究[D];浙江大学;2009年

6 陆楠;关联规则的挖掘及其算法的研究[D];吉林大学;2007年

7 范洪博;快速精确字符串匹配算法研究[D];哈尔滨工程大学;2011年

8 寇晓丽;群智能算法及其应用研究[D];西安电子科技大学;2009年

9 刘维;生物序列模式挖掘与识别算法的研究[D];南京航空航天大学;2010年

10 吴擎;基于模式搜索的类电磁机制算法研究与应用[D];华中科技大学;2013年

中国硕士学位论文全文数据库 前10条

1 安世勇;命题逻辑中随机3-SAT问题算法研究[D];西南交通大学;2015年

2 毕晓庆;油气探矿权竞争性出让系统设计与实现[D];中国地质大学(北京);2015年

3 王明明;铁路大机与线路固定设施间距检测算法研究[D];西南交通大学;2015年

4 李静;基于视频图像序列的运动目标检测与跟踪算法研究[D];宁夏大学;2015年

5 刘贝玲;基于天地图的租房平台开发及其关键技术研究[D];西南交通大学;2015年

6 曹海锋;IDS中串匹配臭算法并行优化研究[D];西安建筑科技大学;2015年

7 周攀;基于蚁群算法的山区高速铁路隧道火灾应急疏散最优路径研究[D];西南交通大学;2015年

8 张路奇;基于改进蚁群算法的WSN路由协议的研究[D];中国地质大学(北京);2015年

9 王晓晨;入侵杂草优化算法的应用与改进[D];长安大学;2015年

10 信琴琴;手势控制和识别算法研究[D];闽南师范大学;2015年

  本文关键词：命题逻辑中随机3-SAT问题算法研究，由笔耕文化传播整理发布。

，

本文编号：472569