Enumerate assignments Dumb Exponential time d But complete can we be clever about exponential time algorithms? 口卡4三4色进分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Enumerate assignments Dumb Exponential time d n But complete can we be clever about exponential time algorithms?
Table of Contents CSP examples Backtracking search for CSPs Problem structure and problem decomposition Local search for CSPs 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents CSP examples Backtracking search for CSPs Problem structure and problem decomposition Local search for CSPs
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,0 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-Nd at depth I,hence n!.d leaves! d is the maximum size of the domain 口卡4三4色进分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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! d is the maximum size of the domain
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 口◆4日1三1，是90C
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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
Backtracking search function BACKTRACKING-SEARCH(csp)returns solution/failure return RECURSIVE-BACKTRACKING({}.esp) 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 le is consistent with assigent given CONSTRAINTS[esp]then add {var valuet to assignment result-RECURSIVE-BACKTRACKING(assignment,csp) if result foilure then return result remove {var=value from assignment return failure 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Backtracking search