How Long Will It Take?
Ron Musick
Computer Science Division
University of California
Berkeley, California 94720
musick@cs.berkeley.edu
and
Stuart Russell
Computer Science Division
University of California
Berkeley, California 94720
russell@cs.berkeley.edu
Abstract
We present a method for approximating the expected number of steps
required by a heuristic search algorithm to reach a goal from any
initial state in a problem space. The method is based on a mapping
from the original state space to an abstract space in which states are
characterized only by a syntactic ``distance'' from the nearest goal.
Modeling the search algorithm as a Markov process in the abstract
space yields a simple system of equations for the solution time for
each state. We derive some insight into the behavior of search
algorithms by examining some closed form solutions for these
equations; we also show that many problem spaces have a clearly
delineated ``easy zone'', inside which problems are trivial and
outside which problems are impossible. The theory is borne out by
experiments with both Markov and non-Markov search algorithms. Our
results also bear on recent experimental data suggesting that
heuristic repair algorithms can solve large constraint satisfaction
problems easily, given a preprocessor that generates a sufficiently
good initial state.
Appeared in
AAAI 1992