loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06)
Finding Crucial Subproblems to Focus Global Search
Arlington, Virginia
November 13-November 15
ISBN: 0-7695-2728-0
Susan L. Epstein, The City University of New York, USA
Richard J. Wallace, University College Cork
Traditional global search heuristics to solve constraint satisfaction problems focus on properties of an individual variable that mandate early search attention. If, however, one could predict crucial subproblems (the portions of a constraint satisfaction problem likely to cause each other particular difficulty) in advance, search could address them first. This paper postulates several types of crucial subproblems, and shows how local search can be harnessed to identify them before global search for a solution. A variety of heuristics and metrics are then used to guide traditional constraint heuristics with those crucial subproblems. On certain classes of structured problems, such search outperforms traditional heuristics by at least an order of magnitude in both time and space.
Citation:
Susan L. Epstein, Richard J. Wallace, "Finding Crucial Subproblems to Focus Global Search," ictai, pp.151-162, 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.