AN EFFICIENT LOCAL SEARCH ALGORITHM FOR STRUCTURED SAT PROBLEMS
D. Liang · Chinese Journal of Computers · 1998
Satisfiability (SAT) problem is the first problem that was proved to be NP--complete. Itis fundamental to solving many problems in artificial intelligence and computational complexitytheory. Recently, it was shown that local search methods can outperform many traditional algorithmson some large classes of SAT problems. This paper proposes two modifications to GSAT+walk, atypical local search method. First, sideways moves from the GSAT part of GSAT+walk areremoved; second, each clause is associated with a weight, and the weights are dynamically updatedduring the entire course of the search. Experimental results indicate that the new local searchalgorithm is very efficient in solving many structured SAT problems.