Exploiting Problem Structure as a Search Heuristic

Tad Hogg ()
Additional contact information
Tad Hogg: Xerox Palo Alto Research Center, Palo Alto, CA 94304, USA

International Journal of Modern Physics C (IJMPC), 1998, vol. 09, issue 01, 13-29

Abstract: Recent empirical and theoretical studies have shown that simple parameters characterizing 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 solving the graph coloring problem. Specifically, by adding some global information on the consequences of various choices, the use of these parameters can reduce the search required to find a solution. Current limitations of this approach, due to the high variance associated with the predictions, are also presented. More generally, observations of universal behaviors analogous to physical phase transitions can be applied to improve search methods.

Keywords: Constraint Satisfaction; Phase Transitions in Heuristic Search (search for similar items in EconPapers)
Date: 1998
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183198000030
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:09:y:1998:i:01:n:s0129183198000030

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183198000030

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().