search and backtracking (slides5)

Question 1

CSP Standard Incremental Search Formulation (SISF)

Answer 1

• Initial state
• Successor function
• State
• Goal test

same for all CSP’s
every soln appears at depth n with n variables
-depth first search used
path is irrelevant, so complete state formulation is used
for CSP with n variables of domain size d:
b=(n-l)d at depth l, hence n! * d leaves

Question 2

SISF initial state

Answer 2

the empty assignment{}

Question 3

SISF successor function

Answer 3

assign a value to an unassigned variable that does not conflict with the current assignment
-fail if no legal assignments

Question 4

SISF state

Answer 4

partial assignment

Question 5

SISF goal test

Answer 5

the current assignment is complete

Question 6

Backtracking search

Answer 6

• variable assignments are commutative
• 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 approx. 25

Question 7

commutative

Answer 7

ex:

[WA = red then NT = green] same as [NT = green then WA = red]

Question 8

Backtracking search implementation

Answer 8

function Backtracking search(csp) returns a solution or failure
return Recursive-Backtracking(assignments, csp) 
Function Recursive-backtracking returns a solution or failure
-if assignment is complete then return assignment
-var<-- Recursive-Backtracking(assignment, csp)
---if result != failure then return result
---remove {var = value} from assignment
--return failure

Question 9

minimum remaining values (MRV) heuristic

Answer 9

improves backtracking efficiency
general purpose
Most constrained variable: FIRST FAIL
Choose the variable with the fewest legal values (i.e. the variable with the least number of successors)
-for tiebreakers, choose the variable with the most constraints on remaining variables
-combining with choosing of the least constraining

Question 10

Least constraining value

Answer 10

given a variable, choose the least constraining value to SUCCEED FIRST
-choose the one that rules out the fewest values in the remaining

Question 11

cons of backtracking

Answer 11

thrashing
redundant work
late detection of conflict

Question 12

backtracking thrashing

Answer 12

throws away the reason of conflict
Ex: A,B,C,D.E:: 1..10 A>E
-BT tries all the assignments for BCD before finding that A != 1
-soln: backjumping (jump to the source of failure)

Question 13

backtracking redundant work

Answer 13

unnecessary constraint checks are repeated

ex: A,B,C,D,E:: 1..10, B+8<D, C=5*E
- when assigning C,E the values 1,…,9 are repeatedly checked for D
- Soln: rememember (no-)good assignments

Question 14

backtracking late detection of conflict

Answer 14

• constraint violation is discovered only when values for all variables in constraints are known
• Example: A,B,C,D,E::1..10, A=3*E
• -the fact that A>2 is discovered when labeling E
• -Soln: forward checking(forward check of constraints)