A Heuristic Complete Algorithm for SAT Problem by Approximation Solution

The advantages of complete algorithm and incomplete algorithm of the SAT problem are integrated into an algorithm.First,an approximation solution is obtained by an incomplete algorithm,as an initial input of the complete algorithm,which is used to phase decision of branched variable.The algorithm guides the complete algorithm first search the subspace that the approximation solutions lie in,which accelerates the process that the solver find the satisfied solution and provides a new approach for SAT problem. Experimental results show that proposed algorithm improves the decision precision and the efficiency of solver and performs well in many instances.