基于变量决策层的启发式变量选择策略

摘要：

启发式分支策略是SAT求解器中不可或缺的一部分,直接影响求解器的效率.早期的启发式分支决策需要遍历整个子句数据库,效率比较低.随着独立变量状态衰减和(Variable State Independent Decaying Sum,VSIDS)分支策略的出现,SAT求解器的效率有所提高,但VSIDS策略以及它的延伸策略中变量的增量都只是与变量的冲突次数有关,没有考虑变量的决策层在分支策略中的影响.因此当发生冲突时,如果与冲突有关的变量的得分相同而决策层不同时,对于变量的选择就具有随机性.基于此,本文在阐述变量的决策层的重要性之后在VSIDS策略的基础上,提出一种基于变量决策层的启发式变量选择策略——HSVDL策略.然后通过实例显示HSVDL策略在变量决策阶段选择决策层低的变量的可能性比选择决策层高的变量的可能性要大,而且得分比较小,减少了内存的占用.最后通过实验表明HSVDL策略能够求解出更多的实例,求解器的效率也有所提高,说明该策略有一定的优势.

关键词：启发式分支策略、SAT求解器、VSIDS策略、HSVDL策略、变量决策

分类号：TP311.1(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61673320;中央高校基本科研业务费专项资金资助项目2682018ZT10

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

页数：共6页

页码：20-24,96