State-Space Search, Problem Reduction, and Iterative Deepening: A Comparative Analysis

Abstract

In previous work, Korf showed that by introducing one problem- reduction step into a state- space search, one could reduce the number of node generations from 0 ((2b)2d ) to 0 (bd ), where b and d are the branching factor and search depth. My results are as follows: 1. The 0(bd) bound is tight, but the 0((bd)2d ) bound is not: the A* procedure does only Q(b2d ) node generations. Thus, the improvement produced by one problem- reduction step is not always as great as the previous results might suggest.2. In an AND/OR tree where multiple problem- reduction steps are possible, problem reduction produces a much more dramatic improvement: both the time complexity and the space complexity decrease from doubly exponential to singly exponential.3. For iterative-deepening procedures like IDA* that only remember the nodes on the current path, the space complexity decreases but the time complexity increases - by exponential amounts in Korf's model, and doubly exponential amounts in the AND/OR-tree model. This is true even for IDAO*, a new procedure that improves IDA*'s performance by combining it with problem reduction.These results lead to the following conclusions: In general, problem reduction can save huge amounts of both time and space. Whether to use a procedure that remembers every node it has visited, or instead use a limited-memory iterative-deepening procedure, depends on whether the primary objective is to save space or save time.