Constraint Satisfaction Problems
-
Constraints
-
Unary: involving 1 variable only
-
n-ary: involving at most n variables
-
Backtracking Search
-
Assign 1 variable at a time
-
Check constraints as you go
-
Return result if all constraints are satisfied, otherwise un-assign value
-
Fix an ordering for variables since assignments are commutative \(X_0: 1, X_1: 2 \equiv X_0: 2, X_1:
1\)
-
Assign the current variable to a value that doesn't conflict with the previous values, if none
exists, backtrack
-
Filtering
-
Forward Checking:
Cross off values that violate a constraint when added to the existing assignment
i.e. enforce constraints on future values / propagates information from assigned to unassigned
-
Forward Checking cont.
When a variable is assigned, all constraints related to it are checked
Does not propagate information from variable to variable
Example
-
Arc Consistency:
Check consistency for all arcs between variables
If a variable loses a value in its domain, all its neighbors need to be checked
-
Arc Consistency cont.
Arc Consistency always removes more values than Forward Checking since it checks other arcs on top
of checking the forward arc
Still runs inside a backtracking search
-
Arc consistency removes more values by checking more relationships between variables: AC checks
consistency between every pair of variables, and re-checks after domain pruning, while FC only
checks between
assigned and unassigned variables.
-
AC-3 complexity: \(O\left(e d^{3}\right)\)
-
Ordering
-
MRV (Minimum Remaining Values): Choose most constrained variable to assign
Fail-Fast
-
LCV (Least Constraining Value): Choose the value that rules out the fewest neighboring variables
Succeed-Fast
-
Structure
-
A Graph of \(n\) variables with domain \(d\):
Worst case \(O(d^n)\)
-
Break into \(c\) sub-graphs with \(n/c\) variables each:
Worst case \(O(c \cdot (d^{n/c}))\)
-
Tree Structured CSP:
Choose variables in topological ordering
Can be solved in \(O(nd^2)\)
No backtracking w/ AC.
-
Cut-Sets can be identified s.t. after removing the cut-set, the remaining graph is a tree
Instantiate a case for each of the assignments for the cut-set, then solve the remaining graph in
linear time.
-
With a cut-set of size \(c\), the complexity is now \(O\left(d^{c}(n-c) d^{2}\right)\)
-
Iterative Improvement
-
Min-conflicts: any variable violating a constraint can be reassigned to another value that minimizes
violations given that other variables are unchanged
