SAT问题求解器重启策略对比分析

• 作者: 张斌 张长胜 郭莹
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 可满足性问题 求解器 冲突驱动子句学习 重启策略
• 年，卷（期）: 2013,（12）
• 所属期刊栏目: 计算机软件与数据库
• 页码范围: 2729-2733
• 页数: 5页
• 分类号: TP18
• 字数: 4767字
• 语种: 中文

摘要

已有研究表明,在SAT求解器中引入重启可以极大地提高求解性能,并已出现了许多不同重启策略.目前还缺少全面的对比分析研究.为了避免重启策略选择的随意性,同时启发设计更好的重启策略,本文选择了具有代表性的7种重启策略,以目前广泛采用的Minisat为基本求解器,在国际SAT2011竞赛中实际应用类基准测试集之上进行了实验对比分析.结果表明:(1)不同重启策略对SAT求解器的求解过程和求解性能影响巨大;(2)在应用类测试集上,几何序列调度策略的平均综合性能优于其他策略;(3)在限定范围内,重启频率越大,求解器综合性能越好;(4)增量变化的重启频率可以克服固定重启频率导致不完备搜索的问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张斌	东北大学信息科学与工程学院	203	1801	20.0	33.0
2	郭莹	东北大学信息科学与工程学院	8	60	4.0	7.0
6	张长胜	东北大学信息科学与工程学院	23	161	6.0	12.0