2
$\begingroup$

I'm a complete beginner. Please forgive my ignorance.Trying to learn about CSP online, I noticed a lot of the focus on search methods and heuristics which tell you which variable to expand next (e.g. most constrained variable) and those that tell you which value to try first (e.g. least constraining value) but I've yet to see heuristics that relate to constraint checks. Since I'm doing everything by hand, I notice a lot of redundancy when eliminating values from variable domains. How do you go about checking for violated constraints in a way that is efficient? Say constraint A will have me eliminate odd numbers 1 to 1000 and constraint B will have me wipe out everything above 250. Intuitively, it feels like order matters as I would waste my time cherry picking even numbers above 250 to only later find out that anything above 250 was not consistent in the first place. I apologize for lacking the proper terminology, my understanding is mostly intuitive. I hope it makes sense. Thanks in advance! I'm mostly looking to acquire a conceptual understanding of selected topics in computer science so if you have book recommendations or any resource that would be appropriate for me as an interested layman, please don't hesitate!

$\endgroup$
3
  • $\begingroup$ Welcome to CS.SE! $\endgroup$ – D.W. Aug 25 '20 at 5:07
  • $\begingroup$ A solid intro is the Russell & Norvig book. Welcome to the site! $\endgroup$ – Juho Aug 25 '20 at 6:19
  • $\begingroup$ Thank you @Juho, I'm already set on that front. A comprehensive introduction indeed! $\endgroup$ – Matthieu Aug 25 '20 at 20:13
1
$\begingroup$

These are known as variable ordering heuristics. One standard one is "fail first". See the "dom" heuristic, i.e., try first the variable with the fewest number of possible values, or "dom+deg", where ties are broken by choosing the variable that participates in the smallest number of constraints. That would handle the case you list as desired.

$\endgroup$
3
  • $\begingroup$ Thank you for your warm welcome. I'm already familiar with these kinds of heuristics (value and variable ordering) as general-purpose search methods. I find it interesting that you would suggest going for the variable that participates in the SMALLEST number of constraints. I've read about the tie-breaker as the variable that has the highest degree (involved in most constraints). Anyways, what I'm actually looking for are heuristics to help check for consistency. Please refer back to the example I gave with the numbers. How do I avoid falling into a redundant removal of inconsistent values. $\endgroup$ – Matthieu Aug 25 '20 at 20:11
  • $\begingroup$ @Matthieu, ok. Did I misunderstand your question? I'll delete my answer if it wasn't what you were hoping for - my apologies. $\endgroup$ – D.W. Aug 26 '20 at 3:04
  • $\begingroup$ No worries! It helped to see that that there are different ways to go about heuristics. I guess I will just be creative and try stuff out on my own. I was hoping to learn something about the way an algorithm will scan the values for constraint violation. $\endgroup$ – Matthieu Aug 26 '20 at 3:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.