You have to backtrack if, after a value has been assigned to a variable, X, the recursion returns at X without a solution. Concretely, this means that for a single variable with d values remaining, it is possible to backtrack up to d times. For each of the following constraint graphs, if each variable has a domain of size d, how many times would you have to backtrack in the worst case for each of the specified orderings?
This is was a question by CS188 Spring Artificial Intelligence
Here is the graph
A->B->C->D->E
Problem: C-B-D-E-A
No. of Backtracks: 0
How come this is still considered as linear ordering? I dont understand why E-A is still not considered to have a backtrack after all to get from E to A, you will be forced to back and will pass through 3 variables. Please help. Thank you....
Looking at the problem, I think I can illustrate how you might arrive at the answers in here.
To redefine, suppose I illustrate this problem as a coloring problem with 5 nodes, A, B, C, D, E.
And each node can have this set of domains. (Blue, Green) and my constraint, no node can have the same color as the node to the its right.
Then, suppose I begin assigning values for this CSP in this order C->B->D->E->A,
That means, I choose an x in (Blue, Green) for C. so I choose Blue, then, I can eliminate from B, Blue from its domain, so B must have the value Green. Then, when I look at D, since C was assigned Blue, I know D must therefore be assigned value Green as well and in this process so on and so forth.
This means that by assigning C, I have actually pretty much solved the problem moving forward with this ordering which means that the worst case scenario is that there will never be any backtracking since by assigning C, I have constrained all the domains on all of my other nodes, and in fact, this will be true for any sized domain (if it works for 2, it will obviously work for 2+ elements in my domain).
However, you might be wondering, why the order A->E->B->D->C will have 2D backtracking.
Well, here's an example. Suppose I assigned the value Blue for A, then Green for E, Green for B, Blue for D, and since I assigned Green for B, I have forced C to have blue, but C CANNOT have blue since D now has Blue. Therefore, C has no valid elements in its domain so I need to backtrack.
How many times do I need to backtrack? well I would have to unassign Blue from D, but now D has no valid domains, so I have to unassign Green from B, however, B has no domains, so now I have to unassign green from E. Now, I can continue by assigning Blue to E. I think after I've done this, there's now been 4 backtracks (C->D->B->E backtrack order) so it seems like for this simple example with a size 2 domain works (this part I'm a little bit fuzzy on proving how there's 2d solutions, it looks to me like the worst case is when your assignment to E doesn't match your assignment to A, and you have to do 2*d due to having to go through both halves?)
Anyways, I'm fuzzy on CS188, haven't taken that class in years and the only times I've ever had to go back to algorithms was to study for interviews lol. It's funny because I was class of 2014, but I think I took this class in the fall.
Hope this helps.