Overview Definition of a csp Simple Map Coloring EXample Representing a CSP as a Search Tree Introduce the Example Problem Compare Three Backtracking Algorithms Chronological Backtracking Conflict-Directed Backjumping Dynamic Backtracking Summary ot Dynamic Backtracking Pros and cons Apm5,2004
Overview • Definition of a CSP • Simple Map Coloring Example – Representing a CSP as a Search Tree – Introduce the Example Problem • Compare Three Backtracking Algorithms – Chronological Backtracking – Conflict-Directed Backjumping – Dynamic Backtracking • Summary of Dynamic Backtracking – Pros and Cons April 5, 2004
Quick definition of a csP Constraint Satisfaction Problem(I,V,C) I a set of variables Vi, a set of possible values for each variable in C, a set of Ci] constraints, each a binary relation C={Cl,1….C,nC2,1..C2,n…,Cn,n a Solution is found when each variable i is assigned a value from it,'s domain Vi and the set of all Constraints C) is satisfied D C I=A, B,C D,E A B Vi=red, yellow, blue) Cij=(no neighbor can be the same color E
Quick Definition of a CSP Constraint Satisfaction Problem ( I,V,C ) - I , a set of variables , a set of variables - Vi, a set of possible values for each variable in a set of possible values for each variable in I. - C, a set of , a set of Cij constraints, each a binary relation constraints, each a binary relation C = {C1,1 … C1,n C2,1 … C2,n … Cn,n} A Solution is found when each variable I is assigned a value from it’s domain Vi and the set of all Constraints {C} is satisfied. I = {A,B,C,D,E} Vi = {red,yellow,blue} Cij = (no neighbor can be the same color)
Simple Example Problem
Simple Example Problem
Search Tree Representation of a cSP Simple Map Coloring Example Variables are assigned values according to an instantiation order The search tree grows downward as A B until each variable is assigned a value from it's domain Dynamic Backtracking allows a E dynamic instantiation order Instantiation Search tree Order 000 A 2)⊙oB 3)°oC→·8·60060·6060606 4)⊙06D 4。。 5)oeE-●O
Search Tree Representation of a CSP A B C D E Instantiation Order • Variables are assigned values according to an instantiation order • The search tree grows downward as until each variable is assigned a value from it’s domain. • Dynamic Backtracking allows a dynamic instantiation order 1.) 2.) 3.) 4.) 5.) Search Tree Simple Map Coloring Example
Changing the Color Ordering to Create an Interesting example problem Pushes the first feasible solution further into the search tree A B Still covers all possible permutations of value assignments to variables · Still a valid csp E Search tree Instantiation Order OO A ○eB 3)·°C→●·●0●90·0··●0···0●·0 6朵。。 .eo 's E AAAA
Changing the Color Ordering to Create an Interesting Example Problem A B C D E • Pushes the first feasible solution further into the search tree • Still covers all possible permutations of value assignments to variables • Still a valid CSP Search Tree Instantiation Order 1.) 2.) 3.) 4.) 5.)