An image of the front cover The figure in the middle shows a phase transition of state-space search, from exponential to polynomial in the maximum search depth.  The horizontal axis of the figure is the branching factor of a state space, and the vertical axis is the probability that a node has the same cost as its parent.  The curve in the middle of the figure represents the average number of children of a node which have the same cost as their parent.  The shaded area to the upper right of the figure is the polynomial region, the unshaded area to the lower left is the exponential region, and the curve in the middle is the transition boundary.  The large (vague) background figure describes a novel approach to solve a difficult combinatorial problem which exploits this phase transition.

Synopsis on the back cover of the book

This book examines state-space search, a general problem-solving paradigm, for combinatorial optimization, which is one of the fundamental problems of computer science and operations research.  In particular, it focuses on heuristic state-space search algorithms, including best-first search, depth-first branch-and-bound, iterative deepening, recursive best-first search, and space-bounded best-first search.

The book has two central themes.  The first is the average-case complexity of these search algorithms based on an analytic model of a state space.  It studies the expected number of states that need to be explored by a search algorithm in terms of the parameters of a state-space model, such as the depth of a goal and branching factor, and the precision of a heuristic function.  The results reveal the existence of phase transitions of average-case complexity, from exponential to polynomial, of all these search algorithms.  The second theme is the application of the analytical results to developing new search algorithms.  Two successful applications are presented in depth, one is a state-space transformation method and the other a forward pruning method for single agent combinatorial optimization and two-agent game playing. These methods can be used to find approximate solutions quickly and to make tradeoffs between the expected solution quality and the required computation cost.

This book is primarily written for students and researchers in computer science and operations research.  It contains theoretical and experimental algorithm analyses.  The author presupposes a familiarity with complexity and the basic concepts of random variables and recursive functions.

Weixiong Zhang was Research Assistant Professor of Computer Science at University of Southern California (USC) and Senior Scientist at USC Information Sciences Institute.  He is currently Associate Professor of Computer Science and Genetics at Washington University in St. Louis.