Standard search formulation (incremental) Let's start with the straightforward,dumb approach,then fix it States are defined by the values assigned so far Initial state:the empty assignment,{} Successor function:assign a value to an unassigned variable that does not conflict with current assignment. fail if no legal assignments (not fixable!) Goal test:the current assignment is complete 1)This is the same for all CSPs! 2)Every solution appears at depth n with n variables use depth-first search 3)Path is irrelevant,so can also use complete-state formulation 4)6=(n-ed at depth e,hence n!d"leaves!!!! Chapter 5 11
Standard search formulation (incremental) Let’s start with the straightforward, dumb approach, then fix it States are defined by the values assigned so far ♦ Initial state: the empty assignment, { } ♦ Successor function: assign a value to an unassigned variable that does not conflict with current assignment. ⇒ fail if no legal assignments (not fixable!) ♦ Goal test: the current assignment is complete 1) This is the same for all CSPs! 2) Every solution appears at depth n with n variables ⇒ use depth-first search 3) Path is irrelevant, so can also use complete-state formulation 4) b = (n − `)d at depth `, hence n!dn leaves!!!! Chapter 5 11
Backtracking search Variable assignments are commutative,i.e., [WA=red then NT=green]same as [NT=green then WA=red] Only need to consider assignments to a single variable at each node b=d and there are d"leaves Depth-first search for CSPs with single-variable assignments is called backtracking search Backtracking search is the basic uninformed algorithm for CSPs Can solve n-queens for n25 Chapter 5 12
Backtracking search Variable assignments are commutative, i.e., [WA = red then NT = green] same as [NT = green then WA = red] Only need to consider assignments to a single variable at each node ⇒ b = d and there are dn leaves Depth-first search for CSPs with single-variable assignments is called backtracking search Backtracking search is the basic uninformed algorithm for CSPs Can solve n-queens for n ≈ 25 Chapter 5 12
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 failure then return result remove {var value from assignment return failure Chapter 5 13
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 14