Standard search formulation (incremental) Let's start with the straightforward 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 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 4Fe (n-)d at depthRence nainseavgn 11
4 Feb 2004 CS 3243 - Constraint Satisfaction 11 Standard search formulation (incremental) Let's start with the straightforward 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 ◼ 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 - l )d at depth l, hence n! ·d n leaves
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 n25 4Feb2004 CS 3243-Constraint Satisfaction 12
4 Feb 2004 CS 3243 - Constraint Satisfaction 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 $d^n$ 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 ◼