Is there any (kind of) (well-known) problem which can be expressed as a CSP in which the least constrained variable heuristic seems to give the best results, when employing backtracking with constraint propagation as the search method?

I am aware of the most constrained variable heuristic, and the intuition behind it, but I was wondering when one would prefer to use the opposite approach.

  • 1
    $\begingroup$ Least constrainED or least constrainING? Least constrained looks like a dumb heuristic, because it starts by taking a variable about which we have very little information and chooses a value for it without knowing what the consequences might be. Does anybody use that? Least constraining, on the other hand, starts by choosing values for the variables that don't seem to have many consequences. $\endgroup$ – David Richerby Feb 2 '17 at 14:31
  • $\begingroup$ @DavidRicherby That's precisely why I'm asking, and that was my intuition too. I don't know of anyone using it, nor have I seen it mentioned in any AI (or similar) course. $\endgroup$ – Călin Feb 2 '17 at 15:09
  • $\begingroup$ OK. I was just confused by your question. Google doesn't seem to return any useful hits for least constrainED, so I wanted to check that you'd not misread least constrainING. $\endgroup$ – David Richerby Feb 2 '17 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.