论文部分内容阅读
已有研究表明,在SAT求解器中引入重启可以极大地提高求解性能,并已出现了许多不同重启策略.目前还缺少全面的对比分析研究.为了避免重启策略选择的随意性,同时启发设计更好的重启策略,本文选择了具有代表性的7种重启策略,以目前广泛采用的Minisat为基本求解器,在国际SAT2011竞赛中实际应用类基准测试集之上进行了实验对比分析.结果表明:(1)不同重启策略对SAT求解器的求解过程和求解性能影响巨大;(2)在应用类测试集上,几何序列调度策略的平均综合性能优于其他策略;(3)在限定范围内,重启频率越大,求解器综合性能越好;(4)增量变化的重启频率可以克服固定重启频率导致不完备搜索的问题.
Studies have shown that the introduction of restart in the SAT solver can greatly improve the performance of the solution, and many different restart strategies have emerged.At present, there is still a lack of comprehensive comparative analysis.In order to avoid the randomness of restart strategy selection, A good restart strategy, this paper chose a representative of the seven kinds of restart strategy, the widely used Minisat as the basic solver in the international SAT2011 competition practical application benchmark test set on the experimental comparative analysis results show that: (1) Different restart strategies have a great influence on the solving process and solving performance of the SAT solver; (2) On the application test set, the average synthesis performance of the geometric sequence scheduling strategy is superior to other strategies; (3) Within the limited range, The higher the restart frequency, the better the overall performance of the solver; (4) The incremental restart frequency can overcome the problem of incomplete search caused by the fixed restart frequency.