利用近似解加速求解SAT问题的启发式完全算法

荆明娥; 周电; 唐璞山; 周晓方

首页> 中文期刊> 《计算机辅助设计与图形学学报》 >利用近似解加速求解SAT问题的启发式完全算法

利用近似解加速求解SAT问题的启发式完全算法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.

著录项

来源
《计算机辅助设计与图形学学报》 |2007年第9期|1184-1189|共6页
作者
荆明娥; 周电; 唐璞山; 周晓方;
展开▼
作者单位

复旦大学专用集成电路国家重点实验室,上海,201203;

复旦大学专用集成电路国家重点实验室,上海,201203;

Electronic Engineering Department, The University of Texas at Dallas, Dallas, TX75083 USA;

复旦大学专用集成电路国家重点实验室,上海,201203;

复旦大学专用集成电路国家重点实验室,上海,201203;

展开▼
原文格式 PDF
正文语种 chi
中图分类测试和检验;
关键词
SAT问题; 完全算法; 局部搜索; 变量决策;

相似文献

中文文献
外文文献
专利

1. 利用逻辑演绎求解SAT问题的启发式完全算法 [J] . 陈青山 ,徐扬 ,何星星 . 西南交通大学学报 . 2017,第006期
2. 求解连续平衡网络设计问题近似解的启发式算法 [J] . 宋一凡 ,高自友 . 北京交通大学学报 . 1998,第006期
3. 基于关键文字的求解SAT问题的启发式算法 [J] . 秦永彬 ,张秋菊 . 计算机与数字工程 . 2010,第010期
4. 结合启发式算子的单变量边缘分布算法求解SAT问题 [J] . 武燕 ,王宇平 ,刘小雄 . 计算机科学 . 2008,第005期
5. 利用改进的HBDE算法求解MAX-k-SAT问题 [J] . 宋建民 ,苟海燕 . 河北省科学院学报 . 2014,第001期
6. 利用基于MILP的启发式算法求解钢管合同组批问题 [C] . 林侃 ,杜斌 ,朱俊 . 中国计量协会冶金分会2013年会暨全国第十八届自动化应用技术学术交流会 . 2013
7. 基于警示传播的启发式极性决策算法求解SAT问题 [A] . 王晓峰 . 2010

利用近似解加速求解SAT问题的启发式完全算法

摘要

著录项

相似文献

相关主题

期刊订阅