General-purpose methods can give huge gains in speed:
Which variable should be assigned next?
Idea 1: Min. remaining values
Idea 2: Degree heuristic
In what order should its values be tried?
Idea 3: Least constraining value
Can we detect inevitable failure early?
Idea 4: Forward checking / AC-3 Algorithm
Can we take advantage of problem structure?
Idea 5: Tree-structured CSPs
Minimum Remaining Values
Choose the variable with the fewest legal values, i.e., the most constrained variable
We choose the variable with the least remaining legal value, which means most likely to fail. If it fails early, we will ignore the entire branch and avoid wasting time.
What happens when multiple variables have the same MRV?
Degree Heuristic: Choose the variable with the most constraints on remaining variables (i.e. choose the variable that has the most impact on the domains of the other variables)
In the example above, using the principle of least constraining value, we will go with coloring the state red instead of blue, since it has more values left available for SA as opposed to 0.
Forward Checking
Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
Identifiable as connected components of constraint graph
Suppose each subproblem has c variables out of total n variables
Worst-case solution cost is , linear in n
e.g. n=80, d=2,c=20
= 4 billion years at 10m nodes/sec
broken down to 4 independent subproblems: = 0.4 seconds at 10 million nodes/sec
Tree-structured CSPs
Theorem: if the constraint graph has no loops, the CSP can be solved in time
Compared to general CSPs, where worst-case time is
Algorithm
Choose a variable as root, order variables from root to leaves such that every node's parent precedes it in the ordering (this step is to order the graph as a tree)
For j from n down to 2, apply RemoveInconsistent(Parent(Xj),Xj)
For j from 1 to n, assign Xj consistently with Parent(Xj)