基于变量混合特征的分支启发式策略

• 作者: 宋振明 沈雪 艾森阳
• 来源期刊: 计算机系统应用
• 关键词: SAT问题 CDCL算法 分支启发式 冲突分析 学习子句
• 年，卷（期）: 2020,（3）
• 所属期刊栏目: 软件技术·算法
• 页码范围: 200-205
• 页数: 6页
• 字数: 4675字
• 语种: 中文
• DOI: 10.15888/j.cnki.csa.007288

摘要

先进的SAT求解器能够通过有效的分支启发式策略解决大型应用实例.目前VSIDS策略是最具有代表性的基于冲突分析的分支策略,它因其稳健性而被广泛使用,但在每次冲突分析中其判定变量活性的增量方式过于单一.针对此问题,本文提出了一种基于变量混合特征的分支启发式算法,目的是充分地利用参与冲突分析的变量所携带的不同信息特征来区分变量,来进一步指导变量活性增长.并将所提出的分支策略算法嵌入到Glucose4.1中形成求解器Glucose4.1+MFBS,通过对比测试,实验结果表明改进的分支算法比原本的VSIDS策略,具有一定的优势,求解明显个数增加.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宋振明	西南交通大学系统可信性自动验证国家地方联合工程实验室	35	160	7.0	11.0
2	沈雪	西南交通大学数学学院	2	0	0.0	0.0
3	艾森阳	西南交通大学数学学院	2	0	0.0	0.0