基于增量式的#SAT求解算法研究

发布时间：2017-09-11 19:22

  本文关键词：基于增量式的#SAT求解算法研究

  更多相关文章： 增量式 #SAT 更新子句 加权算法

【摘要】：可满足(SAT)问题是判定一个合取范式真假的决策性问题,计算复杂度为NP完全。人工智能领域的许多问题如约束模型检测、电路延迟故障测试等都可以转化为SAT问题进行求解,其中不乏相似的问题。早期的SAT求解器不能利用实例间的相似性,每个问题都要从头开始求解。近年来,随着增量式SAT算法的出现和广泛应用,求解这一系列实例的效率有了非常明显的改善。作为SAT问题的扩展,模型计数(#SAT)问题需要计算合取范式所有可满足赋值的个数,计算复杂度为#P完全。该问题在一致性规划、概率推理等领域有着广泛的应用,其中也包含很多相似问题。由于该问题求解较为困难,因此在#SAT求解器中实现信息的重用显得尤为重要。为了更有效的将求解实际生活中相似的#SAT问题,本文在精确的cachet算法基础上加以改进,提出了增量式模型计数算法。首先对多个实例相互比较,找出需要更新的子句,并按照规定的格式放入输入文件中。然后对初始公式进行求解,并在求解过程中对可重用信息及时加以缓存。紧接着,再次读取输入文件,并根据缓存信息对更新子句的可满足性进行相应的分析和处理。如此循环读取并求解,直至整个输入文件处理完毕。此外,本文还用类似的方法对加权#SAT算法进行了增量式的改进,为处理多个相似的加权#SAT问题提供了新思路。为了测试本文算法的求解效率,我们首先选用随机和图着色领域的实例将本文算法与cachet算法进行对比实验,随后又选用求解困难的概率推理领域的实例,将本文增量式权重#SAT算法与普通权重算法进行比较。实验结果证实了本文算法在上述领域的有效性。
【关键词】：增量式 #SAT 更新子句 加权算法
【学位授予单位】：东北师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要4-5
• Abstract5-7
• 第一章 绪论7-10
• 1.1 研究背景与意义7
• 1.2 国内外研究现状7-9
• 1.3 研究内容及论文组织架构9-10
• 第二章 准备知识10-18
• 2.1 SAT 问题和#SAT 问题10-11
• 2.2 cachet算法11-15
• 2.3 概率推理相关定义15-18
• 第三章 基于增量式的#SAT 求解算法18-27
• 3.1 增量式SAT算法18-20
• 3.2 增量式模型计数算法20-27
• 3.2.1 初步求解20-21
• 3.2.2 增量式求解21-24
• 3.2.3 增量式加权模型计数算法24-25
• 3.2.4 算法整体框架及设计25-27
• 第四章 实验结果与分析27-34
• 4.1 实验环境设置及输入文件格式处理27-28
• 4.2 实验测试用例及结果分析28-34
• 第五章 总结与展望34-35
• 参考文献35-38
• 致谢38

【相似文献】

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

1 王秀,叶东毅;基于分布约简的获取规则的增量式方法[J];福州大学学报(自然科学版);2005年01期

2 林俊伟;叶东毅;;基于邻域辨识矩阵的属性约简增量式算法[J];计算机应用;2009年S1期

3 李斌,马戈,孙志挥;项目集发生变化的关联规则增量式更新算法[J];计算机应用;2004年12期

4 刘韶涛;余金山;王宁生;;一种迭代增量式的程序构建方法[J];辽宁工程技术大学学报;2005年06期

5 王军琴;;基于三菱FX_(2N)的增量式PID控制器设计[J];现代电子技术;2010年12期

6 董学勤;刘希璐;;基于增量式PID的改进算法[J];浙江工商职业技术学院学报;2012年03期

7 黄文芝 ,倪国元;基于模糊相似系数的增量式聚类算法[J];微型机与应用;2004年10期

8 罗维;;词语对齐的快速增量式训练方法研究[J];北京大学学报(自然科学版);2013年01期

9 宋和平;胡成全;王力风;侯二娜;;新型双温度反馈增量式PID控制器的设计[J];自动化与仪表;2012年04期

10 刘宗田;属性最小约简的增量式算法[J];电子学报;1999年11期

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

1 单莘;;一种网络告警的增量式情景规则挖掘方法[A];中国通信学会第五届学术年会论文集[C];2008年

2 王鑫;袁晓洁;李楠;;Native XML数据库的增量式验证[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

3 程建军;陈晓云;马志新;;程序设计语言课程的增量式教学法改革与实践[A];2005全国计算机程序设计类课程教学研讨会论文集[C];2005年

4 陈恩红;张振亚;王煦法;;基于神经网络的增量式数据索引机制研究[A];2001年中国智能自动化会议论文集（上册）[C];2001年

5 栾江;唐常杰;黄晓冬;阴小雄;廖勇;;一种增量式支持向量机文本分类模型[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

6 董云云;王中华;冯志全;程金;;吊车-双摆系统的增量式滑模控制[A];第二十七届中国控制会议论文集[C];2008年

中国重要报纸全文数据库 前1条

1 中国社会科学院金融研究所研究员 易宪容;地方增量式金融改革亟待有序规范[N];上海证券报;2012年

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

1 顾斌杰;精确增量式在线v-支持向量回归机的研究[D];江南大学;2015年

2 朱真峰;快速增量式分类算法研究[D];复旦大学;2010年

3 王毅;注塑模改模知识的增量式发现研究[D];广东工业大学;2014年

4 陈春雷;面向GPGPU的并行增量式聚类算法研究[D];西北工业大学;2014年

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

1 王惠贤;基于增量式的#SAT求解算法研究[D];东北师范大学;2016年

2 倪国元;基于模糊聚类的增量式挖掘算法研究[D];华中科技大学;2004年

3 张晶;增量式关联规则挖掘算法研究及其在飞行品质监控中的应用[D];中国民航大学;2008年

4 陈楠;基于粗集理论的增量式属性约简研究[D];长春理工大学;2005年

5 张长城;基于增量式低秩学习的视频目标跟踪[D];大连理工大学;2014年

6 何志刚;多约束增量式布局[D];武汉理工大学;2011年

7 陈飞龙;基于偏序关系的快速增量式概念格构建算法[D];西安电子科技大学;2011年

8 孙岩;增量式贝叶斯网络结构学习研究[D];杭州电子科技大学;2011年

9 郝允允;增量式数据竞争检测[D];中国科学技术大学;2009年

10 赖桃桃;增量式属性约简更新算法研究[D];厦门大学;2009年

，

本文编号：832599