The Constraint Propagation scheme is to embed a consistency algorithm inside a backtracking algorithm. Determining how the constraints and the possible values of one variable affect the possible values of other variables.
Backtracking
Even simple backtracking (BT) performs some kind of consistency technique and it can be seen as a combination of pure generate & test and a fraction of arc consistency.
The BT algorithm detects the inconsistency as soon as it appears and, therefore, it is far away efficient than the simple generate & test approach. But it has still to perform too much search.
Forward Checking (Restricted Arc Consistency)
Forward checking is the easiest way to prevent future conflicts.Instead of performing arc consistency to the instantiated variables, it performs restricted form of arc consistency to the not yet instantiated variables. We speak about restricted arc consistency because forward checking checks only the constraints between the current variable and the future variables.
When a value is assigned to the current variable, any value in the domain of a "future" variable which conflicts with this assignment is (temporarily) removed from the domain. Forward checking is almost always a much better choice than simple backtracking. But it should be noted that forward checking does more work when each assignment is added to the current partial solution.
Look Ahead (Maintaining Arc Consistency, MAC)
Forward checking checks only the constraints between the current variable and the future variables. So why not to perform full arc consistency that will further reduces the domains and removes possible conflicts? This approach is called (full) look ahead or maintaining arc consistency (MAC).
The advantage of look ahead is that it detects also the conflicts between future variables and therefore allows branches of the search tree that will lead to failure to be pruned earlier than with forward checking. Also as with forward checking, whenever a new variable is considered, all its remaining values are guaranteed to be consistent with the past variables, so the checking an assignment against the past assignments is no necessary.
Look ahead prunes the search tree further more than forward checking but, again, it should be noted that look ahead does even more work when each assignment is added to the current partial solution than forward checking.
Summary
More constraint propagation at each node will result in the search tree containing fewer nodes, but the overall cost may be higher, as the processing at each node will be more expensive. In one extreme, obtaining strong n-consistency for the original problem would completely eliminate the need for search, but as mentioned before, this is usually more expensive than simple backtracking. Actually, in some cases even the full look ahead may be more expensive than simple backtracking. That is the reason why forward checking and simple backtracking are still used in applications.
Reference
Look-ahead (backtracking)
cs121
Guide to Constraint Programming
發表文章
沒有留言:
張貼留言