Exploiting Problem Structure as a Search Heuristic

@ARTICLE {,
 AUTHOR = "Tad Hogg",
 TITLE = "Exploiting Problem Structure as a Search Heuristic",
 JOURNAL = "Intl. J. of Modern Physics C",
 VOLUME = "9",
 PAGES = "13--29",
 YEAR = "1998"}

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.
pdf (575K)