THE TYPICALITY OF PHASE TRANSITIONS IN SEARCH
- 1 August 1993
- journal article
- Published by Wiley in Computational Intelligence
- Vol. 9 (3) , 221-238
- https://doi.org/10.1111/j.1467-8640.1993.tb00307.x
Abstract
Search is fundamental to artificial intelligence (AI) 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
This publication has 9 references indexed in Scilit:
- Almost all k-colorable graphs are easy to colorJournal of Algorithms, 1988
- Phase transitions in artificial intelligence systemsArtificial Intelligence, 1987
- Observation of Phase Transitions in Spreading Activation NetworksScience, 1987
- The average complexity of depth-first search with backtracking and cutoffIBM Journal of Research and Development, 1986
- Search rearrangement backtracking and polynomial average timeArtificial Intelligence, 1983
- Searching for an optimal path in a tree with random costsArtificial Intelligence, 1983
- Solving combinatorial search problems by intelligent backtrackingInformation Processing Letters, 1981
- Estimating the Efficiency of Backtrack ProgramsMathematics of Computation, 1975
- Poor Man’s Monte CarloJournal of the Royal Statistical Society Series B: Statistical Methodology, 1954