On Selection Strategies for the DPLL Algorithm

This paper discusses selection strategies for constructive search algorithms. Existing selection strategies have been based on a belief that it is better to search where solutions are more likely to be, or that it is better to search where the search space is smallest. While we give evidence for both strategies, we also show that they are likely to give modest results. We introduce the utility strategy, show that utility heuristics are superior, and that there is an optimal utility balance. We have focused this work on how the Davis-Putnam-Logeman-Loveland algorithm (“DPLL”) uses heuristics in solving satisfiability problems. Empirical results are given to justify our conclusions.