I have been looking into the backtracking search for CSPs, and understand that if we just plainly do a typical depth-limited search we have a vast tree with leaves size n!d^n where n is the # of variables and d the domain size. It can also be easily understood that there exists instead only d^n complete assignments. So the reason for the the tree being so large is attributed to the fact that we are ignoring the commutative way of variable assignments in CSP. Can anyone please explain, as to how exactly this commutative property affects?

  • $\begingroup$ I just want to comment on my own understanding of commutative variable selection. So, if I correctly understand that if we select only a single variable at an instance and then select another one (minus the previous one) it is similar to as if we would have done the selection vice versa (commutative). So, isn't DFS following this naturally? $\endgroup$ Dec 21 '19 at 4:43

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.