Backtracking search Backtracking example VE-BACKTRACKIN f,cp)returns soln/failur 嗡的的 Backtracking example Backtracking example 倒 嗡嗡鈴 给给 Backtracking example Improving backtracking efficiency 哈 General-purpo methods ca ive huge gains in speed: 1.Which ariable soud be assigned next 哈哟玲 3.Can we detect inevitable falure erly? 4.Can we take advantage of problem structure? Backtracking search function Backtracking-Search(csp) returns solution/failure return Recursive-Backtracking({ }, csp) function Recursive-Backtracking(assignment, csp) returns soln/failure if assignment is complete then return assignment var ← Select-Unassigned-Variable(Variables[csp], assignment, csp) for each value in Order-Domain-Values(var, assignment, csp) do if value is consistent with assignment given Constraints[csp] then add {var = value} to assignment result ← Recursive-Backtracking(assignment, csp) if result 6= failure then return result remove {var = value} from assignment return failure Chapter 5 13 Backtracking example Chapter 5 14 Backtracking example Chapter 5 15 Backtracking example Chapter 5 16 Backtracking example Chapter 5 17 Improving backtracking efficiency General-purpose methods can give huge gains in speed: 1. Which variable should be assigned next? 2. In what order should its values be tried? 3. Can we detect inevitable failure early? 4. Can we take advantage of problem structure? Chapter 5 18