摘录自:

 

当前SAT主要关键技术及其相关文献——参见下面这段叙述。

The annual SAT competitions have become an essential event for the distribution of SAT benchmarks and the development of new SAT-solving methods [5]. Sequential SAT solvers compete mainly in three categories: industrial, crafted, and random tracks. The SAT competitions have demonstrated how difficult it is for SAT solvers to perform well across all categories. Results show that conflict-driven clause-learning (CDCL) SAT solvers were most performant for solving industrial and crafted SAT benchmarks, whereas look-ahead and Stochastic Local Search (SLS)-based SAT solvers have dominated the random category [5]. Modern implementations of CDCL SAT solvers employ a lot of heuristics. Some of them can be considered baseline, such as the Variable State Independent Decaying Sum (VSIDS) [6], restarts [7], and Literal Block Distance (LBD) [8]. Several others were incorporated recently, including: Learnt Clause Minimization (LCM) [9], Distance (Dist) heuristic [10], Chronological Backtracking (ChronoBT) [11], duplicate learnts heuristic [12], Conflict History-Based (CHB) heuristic [13], Learning Rate-based Branching (LRB) heuristic [14], and the SLS component [15].

 

 

 

 

[5] SAT Competitions. 2002. Available online: http://www.satcompetition.org (accessed on 19 November 2019).

[6] Moskewicz, M.W.; Madigan, C.F.; Zhao, Y.; Zhang, L.; Malik, S. Chaff: Engineering an efficient SAT solver. In Proceedings of the 38th Design Automation Conference (IEEE Cat. No.01CH37232), Las Vegas, NV, USA, 22 June 2001; pp. 530–535. [Google Scholar] [CrossRef]

[7] Luby, M.; Sinclair, A.; Zuckerman, D. Optimal speedup of Las Vegas algorithms. Inf. Process. Lett. 1993, 47, 173–180. [Google Scholar] [CrossRef]

[8] Audemard, G.; Simon, L. Predicting Learnt Clauses Quality in Modern SAT Solvers. In Proceedings of the 21st International Jont Conference on Artifical Intelligence, Pasadena, CA, USA, 11–17 July 2009; IJCAI’09. pp. 399–404. [Google Scholar]

[9] Luo, M.; Li, C.M.; Xiao, F.; Manyà, F.; Lü, Z. An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, Melbourne, Australia 19–25 August 2017; pp. 703–711. [Google Scholar] [CrossRef]

[10] Xiao, F.; Luo, M.; Li, C.M.; Manyà, F.; Lü, Z. MapleLRB LCM, Maple LCM, Maple LCM Dist, MapleLRB LCMoccRestart and Glucose-3.0+width in SAT Competition 2017. In Proceedings of the SAT Competition 2017: Solver and Benchmark Descriptions, Melbourne, Australia, 28 August–1 September 2017; Volume B-2017-1, pp. 25–26. [Google Scholar]

[11] Nadel, A.; Ryvchin, V. Chronological Backtracking. In Proceedings of the Theory and Applications of Satisfiability Testing—SAT 2018, Oxford, UK, 9–12 July 2018; Beyersdorff, O., Wintersteiger, C.M., Eds.; Springer International Publishing: Cham, Switzerland, 2018; pp. 111–121. [Google Scholar]

[12] Kochemazov, S.; Zaikin, O.; Semenov, A.A.; Kondratiev, V. Speeding Up CDCL Inference with Duplicate Learnt Clauses. In Proceedings of the ECAI 2020—24th European Conference on Artificial Intelligence, Santiago de Compostela, Spain, 29 August–8 September 2020; Giacomo, G.D., Catalá, A., Dilkina, B., Milano, M., Barro, S., Bugarín, A., Lang, J., Eds.; IOS Press: Shepherdsville, KY, USA, 2020; Volume 325, pp. 339–346. [Google Scholar] [CrossRef]

[13] Liang, J.H.; Ganesh, V.; Poupart, P.; Czarnecki, K. Exponential Recency Weighted Average Branching Heuristic for SAT Solvers. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA, 12–17 February 2016; AAAI’16. pp. 3434–3440. [Google Scholar]

[14] Liang, J.H.; Ganesh, V.; Poupart, P.; Czarnecki, K. Learning Rate Based Branching Heuristic for SAT Solvers. In Proceedings of the Theory and Applications of Satisfiability Testing—SAT 2016—19th International Conference, Bordeaux, France, 5–8 July 2016; Creignou, N., Berre, D.L., Eds.; Springer: Berlin/Heidelberg, Germany, 2016; Volume 9710, pp. 123–140. [Google Scholar] [CrossRef]

[15] Zhang, X.; Cai, S. Relaxed Backtracking with Rephasing. In Proceedings of the SAT Competition 2020, Alghero, Italy, 3–10 July 2020; Solver and Benchmark Descriptions. University of Helsinki, Department of Computer Science: Helsinki, Finland, 2020; Volume B-2020-1, pp. 15–16. [Google Scholar]

 

   

原文地址:http://www.cnblogs.com/yuweng1689/p/16846843.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性