Pruning Duplicate Nodes in Depth-First Search

Larry A. Taylor, Richard E. Korf

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.