Pruning Duplicate Nodes in Depth-First Search
Larry A. Taylor, Richard E. Korf · 1993
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. Introduction---The Problem Search techniques are fundamental to artificial intelligence. Best-first search algorithms such as breadthfirst se...