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)
--
Meng,Yunsong
Teaching Assistant
Subscribe to:
Post Comments (Atom)
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).
ReplyDeleteArc 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.