Exploiting Problem Structure as a Search Heuristic

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"}

Abstract

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)