1
$\begingroup$

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 number 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?

$\endgroup$
1
  • $\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, 2019 at 4:43

1 Answer 1

0
$\begingroup$

(Assuming we don't consider some objective function) a CSP has a finite depth that corresponds with its goal state. Think of Sudoku - every solution necessarily fills up the whole board. That is, anytime we reach a depth equal to $n$, where $n$ is the total variables, then we have a reached a goal. Therefore, we don't care about the path that gets us to the goal. In other types of problems where we care about finding the shortest path, assigning the wrong variable might lead us to a goal with an inefficient path. In CSP though, we're happy to end up at any goal so any path we take will not affect the outcome. If we reach a dead end we can always backtrack and try a different branch.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .