Wednesday, March 18, 2009

Regarding Forward Checking and Arc Consistency

Since so many students asked questions about Forward Checking and Arc Consistency today,
I think it is necessary to make sure everyone are on the same boat. Let me try to clarify, correct me if
I am wrong:

Forward Checking:
Keep a list of all possible values for each unassigned variables, every time before assigning a value to a variable,
check whether that value is the only possible value for neighbor variables (Don't permanently delete that
value from neighbor's possible value), if none of them is the case, make the assignment, and update the possible
values for other variables (Now you can delete the value just assigned). And keep going.

Arc Consistency:
Keep all possible values for unassigned variables, and propagate constraints to each of the variable.
Remove any possible value that has no support from neighbors, and check all variables each round.
End if no value was removed in one round. (For one round, I mean update all variables) 

Teaching Assistant

1 comment:

  1. Actually, I understood forward checking to be as follows: when assigning a value to some position, check all unassigned neighbors of that position. If the neighboring positions have the value we're assigning in their possible values, remove it. (Neighbors being unassigned positions constrained by position we're working with).

    Arc constraints are: for each possible value in a our position, check if neighbors have a value they can use So if we're looking at the value 4, each of our neighbors has to be able to assign a legal value to their position. If not, we remove 4 from our positions' possible values. There's a queue involved and you have to add and delete arcs from it as described on pg 146 of the text.

    That was my interpretation.


Note: Only a member of this blog may post a comment.