Backtracking Search Algorithm for Satisfiability Degree Calculation

摘要

Satisfiability degree can compensate for the deficiency of classical logics in representing uncertainty. As the calculation of the satisfiability degree is an NP-complete problem, it is necessary to construct some efficient algorithm. In this paper, an algorithm for computing the satisfiability degree of arbitrary propositional formula is proposed. It refers to and modifies the backtracking search algorithm used in the Boolean satisfiability problem (SAT), making optimizations by using heuristic strategy and intelligent analysis. Experimental results compare the time consumed by the basic enumeration algorithm with this algorithm, indicating that this algorithm is extremely effective for large formulas.