To Solve csPs we combine arc consistency and search 1. Arc consistency( Constraint propagation) eliminates values that are shown locally to not be a part of any solution explores consequences of committing to particular assignments Methods Incorporating Search Standard search Back Track search (BD BT with Forward Checking(FC) Dynamic Variable Ordering(DV Iterative Repair Backjumping(BJ) Solving CSPs with Standard Search · State Variables assigned thus far · Initial state · No assignments Operator Assign value to any unassigned variable ·Goa|Test All variables assigned All constraints satisfied · Branching factor? 2 Sum of domain size of all variables O(v*d) Performance? 9 exponential in branching factor R. G5 To Solve CSPs we combine arc consistency and search 1. Arc consistency (Constraint propagation), • eliminates values that are shown locally to not be a part of any solution. 2. Search • explores consequences of committing to particular assignments. Methods Incorporating Search: • Standard Search • Back Track search (BT) • BT with Forward Checking (FC) • Dynamic Variable Ordering (DV) • Iterative Repair • Backjumping (BJ) 6 Solving CSPs with Standard Search • State • Initial State • Operator • Goal Test • Variables assigned thus far • No assignments • Assign value to any unassigned variable • All variables assigned • All constraints satisfied • Branching factor? Î Sum of domain size of all variables O(v*d) • Performance? Î exponential in branching factor R, G R, G R, G, B V1 V3 V2