Week 6 (Chapter 7) - Constraint Satisfaction Problem

Question 1

What’s the difference between tree and graph structured CSP?

Answer 1

Tree = no loops
Graph = loops

If no loops, CSP can be solved in O(nd^2) time = linear

If loops, CSP solved in O(d^n) = exponential

Question 2

What to do when CSP is nearly tree structured?

Answer 2

Cutset - instantiate a variable, prune its neighbours domains

cutset = set of variables that can be deleted so constraint graph forms a tree

Question 3

What is the complexity of arc consistency?

Answer 3

O(n^2d^3) -> can be reduced to O(n^2d^2)