Interleaved Depth-First Search

Abstract

In tree search, depth-first search (DFS) often uses ordering successor heuristics. If the heuristic makes a mistake ordering a bad successor (without goals in its subtree) before good ones (with goals in their subtrees), DFS has to unsuccessfully traverse the whole bad subtree before finding a goal. To prevent this useless work, we present a new strategy called interleaved depthfirst search ( ID FS), which searches depth- first several subtrees -c alled active- in parallel. IDFS assumes a single processor on which it interleaves DFS on active subtrees. When IDFS finds a mistake, it traverses partially the bad subtree. IDFS does not reexpand nodes and uses a memory amount linear in search depth (with a bounded number of active subtrees). IDFS outperforms DFS if the heuristic improves from the first to the second tree level. Experimentctl results on hard solvable problems confirm the practical validity of IDFS.