Journal of Artificial Intelligence Research, 7 (1997)
Submitted 10/96; published 9/97
© 1997 AI Access Foundation and Morgan Kaufmann Publishers.
All rights reserved.
A New Look at the Easy-Hard-Easy Pattern of Combinatorial
Dorothy L. Mammen,
Computer Science Department
Amherst, MA 01003, U.S.A.
Xerox Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, CA 94304, U.S.A.
The easy-hard-easy pattern in the difficulty of combinatorial search
problems as constraints are added has been explained as due to a
competition between the decrease in number of solutions and increased
pruning. We test the generality of this explanation by examining one
of its predictions: if the number of solutions is held fixed by the
choice of problems, then increased pruning should lead to a monotonic
decrease in search cost. Instead, we find the easy-hard-easy pattern
in median search cost even when the number of solutions is held
constant, for some search methods. This generalizes previous
observations of this pattern and shows that the existing theory does
not explain the full range of the peak in search cost. In these cases
the pattern appears to be due to changes in the size of the minimal
unsolvable subproblems, rather than changing numbers of solutions.
- 1. Introduction
- 2. Some Classes of Search Problems
- 2.1 Random CSPs
- 2.2 Graph Coloring
- 3. The Easy-Hard-Easy Pattern
- 3.1 An Example
- 3.2 An Explanation
- 4. Search Difficulty and Solvability
- 4.1 Search Behavior
- 4.2 Solvable Problems
- 4.3 Problems With a Fixed Number of Solutions
- 5. Minimal Unsolvable Subproblems
- 6. Conclusions
- 7. Acknowledgements
Return to Contents
Send comments to firstname.lastname@example.org
Fri Aug 29 12:21:02 EDT 1997