Colin P. Williams and Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@ARTICLE {
AUTHOR = "Colin P. Williams and Tad Hogg",
TITLE = "The Typicality of Phase Transitions in Search",
JOURNAL = "Computational Intelligence",
VOLUME = "9",
NUMBER = "3",
PAGES = "221-238",
YEAR = "1993"}
Search is fundamental to Artificial Intelligence, and numerous
sophisticated search methods have been developed. We present a general,
simple model of search processes and use it to analytically determine
some typical behavior when applied to large problems. In particular,
this identifies abrupt changes in overall search cost as small
improvements are made in the underlying method. We also examine the
robustness of this model's predictions in a range of more realistic
cases. More generally, we introduce a criterion for determining when
average case results reflect typical behavior which allows the method
developed here to be used for investigating other large-scale behaviors
of complex AI systems.
keywords: search, complexity, typicality, phase transitions
postcript (582K, available on-line only within Xerox)
A longer version of this paper, with more detailed derivations, is available as a Xerox PARC technical report (760K).