How to Search Efficiently

Abstract

The only technique available for solving many important problems is searching. Since searching can be extremely costly, it is important to identify features that improve the efficiency of search algorithms. We compute the efficiency of simple backtracking, of an algorithm similar to backtracking except that it notices when the predicate is empty instead of noticing when it is unsatisfiable (the empty predicate method), of the combination of simple backtracking with the empty predicate method, and of search rearrangement backtracking (the unit clause rule combined with backtracking). The analysis is done over two sets of random problems. We also consider the algorithm based on the pure literal rule that was analyzed by Goldberg and the results he obtained. All these algorithms are simplifications of the complete Putham-David procedure, which has not been analyzed as yet (although most of its components have been analyzed). The performances of the algorithms are compared and features that lead to efficient algorithms are identified.