一种求解SAT问题的动态重启策略

摘要：

为降低冲突驱动子句学习SAT求解器的运行计算成本,从“何时重启”和“何处重启”两个角度入手,提出一种动态启发式重启策略2WSAT.该策略将冲突决策层次和变量重启次数作为反映求解状态的重要参数,及时摆脱错误的求解分支,通过重启后选择更优的决策变量提高求解性能.采用实际应用的基准测试集,与两个流行的求解器进行了对比实验.结果表明,所提出的策略对求解速度、内存占用、冲突发生数、传播次数等关键指标有显著改善.

关键词：可满足性问题、重启策略、启发式、冲突决策层次、变量重启次数

所属期刊栏目：35

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61073062,61100090;中央高校基本科研业务费专项资金资助项目N11024006;宁夏回族自治区自然科学基金资助项目NZ13265

在线出版日期：2015-07-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：935-938