 Constrainedness of Search
Prof. Toby Walsh
(NICTA and University of New South Wales)
http://www.cse.unsw.edu.au/~tw/
Will a problem be satisfiable or unsatisfiable? Will it be hard or easy? How can we develop heuristics for new problem domains? A discuss a general method which helps to answer such questions that is applicable to a wide range of combinatorial problems.
My starting point is a definition of the constrainedness of a combinatorial problem.
Measuring the constrainedness of problems during search also provides insight into why some problems are harder to solve than others. I show that hard problems are often on a constrainedness "knife-edge", critically constrained between easy, under-constrained instances and obviously over-constrained instances. Heuristics that try to get off this knife-edge as quickly as possible by, for example, minimizing the constrainedness are often therefore very effective.
Joint work with Patrick Prosser, Ian Gent and others. =
For more info, please visit: http://www.cse.unsw.edu.au/~tw/foga13.ppt
|
