Forward checking

constrain satisfection problem of forword checking

1. CSP-F orward Checking Presented by , Sourav Kairy ID:171-115-128 Md. Juwel Ahmad ID:171-115-152

2. Constraint satisfaction problems An assignment is complete when every value is mentioned. A solution to a CSP is a complete assignment that satisfies all constraints. Applications: Scheduling the time of observations on the Hubble Space Telescope, Floor planning, Map coloring, Cryptography

3. CSP example: Map-Coloring Variables WA, NT, Q, NSW, V, SA, T Domains D i = {red,green,blue} Constraints : adjacent regions must have different colors e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}

4. Goal Solutions are complete and consistent assignments, e.g., WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = green

5. Introduction Constraints between the current variable and the future variables. That it detects also the conflicts between future variables and therefore allows branches of the search tree. Forward checking is a type of filtering used in backtracking search. Useful for detecting inevitable failures early. Forward checking:

6. Degree heuristic Use degree heuristic Rule: select variable that is involved in the largest number of constraints on other unassigned variables. Degree heuristic is very useful as a tie breaker. In what order should its values be tried?

7. Minimum remaining values(variable ordering) A.k.a. most constrained variable heuristic. Rule: choose variable with the fewest legal moves . Which variable shall we try first?

8. Least constraining domain value(value ordering) Remaining 1 value for SA Remaining 0 value for SA Least constraining value heuristic. Rule: given a variable choose the least constraining value i.e. the one that leaves the max imum flexibility for subsequent variable assignments.

9. Forward Checking Example • Idea : – Keep track of remaining legal values for unassigned variables – Terminate search when any variable has no legal values

10. Forward Checking WA NT SA Q NSW V T

11. Forward Checking WA NT SA Q NSW V T

12. Forward Checking WA NT SA Q NSW V T

13. Forward Checking WA NT SA Q NSW V T

14. WA NT SA Q NSW V T Forward Checking

15. WA NT SA Q NSW V T Forward Checking

16. WA NT SA Q NSW V T Forward Checking

17. Advantages Forward checking allows us to see when problems arise as we assign a new variable and to exit early to avoid doing unnecessary work Disadvantages Forward checking does not provide early detection for all failures. Particularly, it does not detect failures between two unassigned variables.