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 11Standard 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