Problem Detail: Can somebody explain me how can I join forward checking with conflict directed backjumping in my CSP solver? I understand that when the consistency fails when I add a value to a variable, I should save all the instantiated variables of the restriction that fails, on the conflict set of the variable to which I gave a value. But what happens when there’s no consistency failure but when I’m doing the inferences of the forward checking I found a contradiction? Do I need to know which restrictions failed and add the variables to the current variable conflict set? My current approach: My function that solves the CSP is recursive. So right now I’m doing the following, for each the current variable (the one I’m in the recursive step) I’m checking if the value that I give to her is consistent, if not, I add all the attributed variables of the restriction that fails to the conflict set of this variable. When I’m backjumping in the recursivity, I return this conflict set, and if any variable is contained in this set, it will try to change his value. (this implements the basic backjumping and with some other small changes I put my algorithm using conflict directed backjumping). I tested this part and it’s working. Now, when I add the forward checking, I need to get from the forward checking some informations when it finds contradictions (and this is the problem). Right now, I’m getting the variable where the contradiction occurs and all the attributed variables related to restrictions that failed. Is this all the infromation I need from the backjumping?
Asked By : Luis Alves
Answered By : Kyle Jones
If forward checking detects that the potential assignment of a variable $x_1$ leaves no valid assignments for the variable $x_2$, one simple strategy is to just make the assignment to $x_1$ and then queue $x_2$ as the next variable to be assigned. When the assignment of $x_2$ inevitably fails, your backjumping machinery will do what it always does and you need not code any special information gathering related to forward checking. In the meantime, you’ve saved all the time that would have been wasted doing (and undoing) a potentially exponential number of unrelated assignments that do nothing to resolve the inevitable conflict between $x_1$ and $x_2$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33594 Ask a Question Download Related Notes/Documents
