计算机工程与应用2017，Vol.53Issue(14)：56-60,110,6.DOI:10.3778/j.issn.1002-8331.1603-0151
基于加强概率控制策略的SAT局部搜索算法
SAT local search algorithm based on enhanced probability con-trolling strategies
摘要
Abstract
Currently local search algorithms are very effective for solving some SAT problems, and Sattime is a typical local search algorithm which won a silver medal in the 2011 international SAT competition. But, after recording the vari-able flipping event data stream into a database in the solving process of Sattime algorithm, data analysis and pattern min-ing uncover that Sattime sometimes selects the same variable to flip in two successive flipping steps. This search behavior may cause loop back and is known as the loopback phenomenon, which reduces the local search efficiency. To solve the problem, this paper proposes two probability control strategies:the enhanced strategy for choosing clause and the enhanced strategy for choosing variable. Applying these two strategies into Sattime algorithm, the paper develops a new local search algorithm called Sattime-P. Experimental results show that the improved algorithm Sattime-P is more efficient in most cases. Moreover, this method can also be applied to other SAT local search algorithms to improve their efficiency.关键词
SAT问题/局部搜索/概率控制/子句/布尔变元Key words
SAT problem/local search/probability controlled/clause/Bool variable分类
信息技术与安全科学引用本文复制引用
洪剑珂,张峥华,许贵平..基于加强概率控制策略的SAT局部搜索算法[J].计算机工程与应用,2017,53(14):56-60,110,6.基金项目
国家自然科学基金(No.61272014) （No.61272014）
华中科技大学2016年自主创新基金项目. （）
