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

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