一种基于加权决策变量决策层的分支策略

摘要：

为了提高CDCL求解器的求解效率,针对可满足性(SAT)问题算法中决策变量的选择问题,提出了一种基于加权决策变量决策层的分支策略.这个新策略的主要思想是:基于布尔约束传播(BCP)过程中的回溯以及重启机制,首先考虑变量作为决策变量的次数以及所在决策层;其次,由于被选择的次数以及所在决策层不同,即占权重不同,对此进行加权;最后,结合冲突分析过程,对不同的变量给予不同的奖励得分.将不同变量在新策略与VSIDS和EVIDS策略中的得分进行对比,采用SATLIB(SAT Little Information Bank)中的大量例子进行实验测试,结果表明,新策略能够减少冲突次数以及求解时间(cpu),提高了求解器的求解效率.

关键词：决策层、加权、重启、决策变量、冲突

所属期刊栏目：46

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

资助基金：国家自然科学基金项目61673320,61603307,61473239;教育部人文社科项目19YJCZH048

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

页数：共4页

页码：19-22