Backtracking Search Algorithm for Satisfiability Degree Calculation
Chongyuan Yin, Guiming Luo, Pei Hu · International Conference on Fuzzy Systems and Knowledge Discovery (FSKD) · 2009
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.
Cited by 5 works. doi:10.1109/fskd.2009.782
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Fuzzy sets
- Probabilistic logic
- GRASP: a search algorithm for propositional satisfiability
- Improvements to propositional satisfiability search algorithms
- Fuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Recognition
- Reasoning about Uncertainty
- A rearrangement search strategy for determining propositional satisfiability
- Probabilistic logic learning
- Search algorithms for satisfiability problems in combinational switching circuits.