Pruning Duplicate Nodes in Depth-First Search

Best-first search algorithms require exponential memory, while depth-first algorithms require only linear memory. On graphs with cycles, however, depth-first searches do not detect duplicate nodes, and hence may generate asymptotically more nodes than best-first searches. We present a technique for reducing the asymptotic complexity of depth-first search by eliminating the generation of duplicate nodes. The automatic discovery and application of a finite state machine (FSM) that enforces pruning rules in a depth-first search, has significantly extended the power of search in several domains. We have implemented and tested the technique on a grid, the Fifteen Puzzle, the Twenty-Four Puzzle, and two versions of Rubik’ s Cube. In each case, the effective branching factor of the depth-first search is reduced, reducing the asymptotic time complexity.

Authors

• Larry A. Taylor Richard E. Korf

Keywords

No keywords are indexed for this paper.