Back to Search
Start Over
Random backtracking in backtrack search algorithms for satisfiability
- Source :
- Discrete Applied Mathematics. 155:1604-1612
- Publication Year :
- 2007
- Publisher :
- Elsevier BV, 2007.
-
Abstract
- This paper proposes the utilization of randomized backtracking within complete backtrack search algorithms for propositional satisfiability (SAT). In recent years, randomization has become pervasive in SAT algorithms. Incomplete algorithms for SAT, for example the ones based on local search, often resort to randomization. Complete algorithms also resort to randomization. These include state-of-the-art backtrack search SAT algorithms that often randomize variable selection heuristics. Moreover, it is plain that the introduction of randomization in other components of backtrack search SAT algorithms can potentially yield new competitive search strategies. As a result, we propose a stochastic backtrack search algorithm for SAT, that randomizes both the variable selection and the backtrack steps of the algorithm. In addition, we relate randomized backtracking with a more general form of backtracking, referred to as unrestricted backtracking. Finally, experimental results for different organizations of randomized backtracking are described and compared, providing empirical evidence that the new search algorithm for SAT is a very competitive approach for solving hard real-world instances.
- Subjects :
- Propositional satisfiability
Backtracking
business.industry
Applied Mathematics
Feature selection
Randomization
Satisfiability
Random search
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Search algorithm
Beam stack search
Discrete Mathematics and Combinatorics
Local search (optimization)
Backtrack search algorithms
business
Heuristics
Algorithm
Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 155
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi.dedup.....6a50e61faa53ccfe8b44dbcc531641d9