Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@TECHREPORT {,
AUTHOR = "Tad Hogg",
TITLE = "Exploiting Problem Structure as a Search Heuristic",
INSTITUTION = "Xerox PARC",
MONTH = "January",
YEAR = "1995"}
Recent empirical and theoretical studies have shown that simple
parameters characterizing the structure of many constraint satisfaction
problems predict whether they have a solution and the cost to solve
them, on average. This paper examines the effectiveness of using these
predictions as a heuristic for a complete search method solving the
graph coloring problem. Specifically, by adding some global information
on the consequences of various choices, the use of problem structure
parameters can reduce the amount of search required to find a solution.
Current limitations of this approach, due to the high variance
associated with the predictions, are also presented.
postcript (593K)