Compare Three Backtracking Algortihms 1. Chronological Backtracking 2 ) Conflict-Directed Backjumping 3 ) Dynamic Backtracking
Compare Three Backtracking Algortihms 1.) Chronological Backtracking 2.) Conflict-Directed Backjumping 3.) Dynamic Backtracking
Sneak preview of the solution Solve map example using D 1 ) Chronological Backtracking A 2 )Conflict-Directed Backjumping 3. Dynamic Backtracking E 1)A This is what the solution will look 2)B like each time We will compare the of nodes 3)C●0●●0●00 expanded (i.e. regions colored) 4)D until the first solution is found E点
Sneak Preview of the Solution Solve map example using: 1.) Chronological Backtracking 2.) Conflict-Directed Backjumping 3.) Dynamic Backtracking Note: This is what the solution will look like each time. We will compare the # of nodes expanded (i.e. regions colored) until the first solution is found A B C D E 1.) 2.) 3.) 4.) 5.)
1 )Chronological Backtracking Chronological_ Backtrack( 1 )Set P=null](P is the partial solution to the CSP) Set Vi=(1(start with first variable in instantiation order) 2. )If P= solution, return Success. If Vi=0 return Failure Else if P= consistent set (Vi) to the next variable in instantiation order and assign it's next domain color(c) Else if P= Inconsistent, remove(c)from domain of(vi) and continue 3. )While domain of (vi) is not empty, choose the next domain color(c)and return to step 2 4. )If domain of (Vi) is empty(i.e. out of colors to try for(vi) Remove) from p,setⅵ=Ⅵ-1, and return to step3 Instantiation Order D C 1)o°A A B 2.)O00 B 3)°oC0●·0 ○e0 ○e 5) E.^
1.) Chronological Backtracking Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Chronological_Backtrack() 1.) Set P = {null} (P is the partial solution to the CSP) Set Vi = {1} (start with first variable in instantiation order) 2.) If P = solution, return Success. If Vi = 0 return Failure Else if P = Consistent, set (Vi) to the next variable in instantiation order and assign it’s next domain color (c). Else if P = Inconsistent, remove (c) from domain of (Vi) and continue 3.) While domain of (Vi) is not empty, choose the next domain color (c) and return to step 2. 4.) If domain of (Vi) is empty (i.e. out of colors to try for (Vi) Remove (Vi) from P, set Vi = Vi – 1, and return to step 3
1 ) Chronological Backtracking D C A B E Instantiation Order Notes 1)( ○⊕ A Helpful notes will go2)0●°B here e○ C ORD of Nodes expanded 5.OO9E
1.) Chronological Backtracking E Instantiation Order : A B C D 1.) 2.) 3.) 4.) 5.) Notes: Helpful notes will go here # of Nodes Expanded 1
1 ) Chronological Backtracking D C A B E Instantiation Order Notes 1)00A Helpful notes will go 2)O●eB here 3)C OOOD of Nodes expanded 5)0e E
Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: Helpful notes will go here # of Nodes Expanded 2