Improving Stochastic Local Search for SAT with a New Probability Distribution

被引：0

作者：

Balint, Adrian ^{[1
]}

Froehlich, Andreas ^{[1
]}

机构：

[1] Univ Ulm, Inst Theoret Comp Sci, D-89069 Ulm, Germany

来源：

THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2010, PROCEEDINGS | 2010年 / 6175卷

关键词：

SATISFIABILITY;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper introduces a new SLS-solver for the satisfiability problem. It is based on the solver gNovelty+. In contrast to gNovelty+, when our solver reaches a local minimum, it computes a probability distribution on the variables from an unsatisfied clause. It then flips a variable picked according to this distribution. Compared with other state-of-the-art SLS-solvers this distribution needs neither noise nor a random walk to escape efficiently from cycles. We compared this algorithm which we called Sparrow to the winners of the SAT 2009 competition on a broad range of 3-SAT instances. Our results show that Sparrow is significantly outperforming all of its competitors on the random 3-SAT problem.

引用

页码：10 / 15

页数：6