From Enumeration to Backtracking
Backtracking
Branch on every possibility
Must maintain the current partial solution being developed
Might print or maintain all complete solutions
Check every partial solution for validity
If a partial solution violates some constraint, it makes no sense to extend it (so drop it), i.e., backtrack
M-Coloring Algorithm
Input: n (number of nodes),
m (number of colors),
W[0..n)[0..n) (adjacency matrix)
( W[i][j] is true if there is an edge
from node i to node j, and false otherwise)
Output: all possible colorings of graph
represented by int vcolor[0..n), where
vcolor[i] is the color associated with
node i
Algorithm m_coloring(index i = 0)
if (i == n)
print vcolor(0) thru vcolor(n - 1)
return
for (color = 0; color < m; color++)
vcolor[i] = color
if (promising(i))
m_coloring(i + 1)
bool promising(index i)
for (index j = 0; j < i; ++j)
if (W[i][j] and vcolor[i] == vcolor[j])
return false
return true
When is Backtracking Efficient?
Backtracking avoids looking at large portions of the search space by pruning, but this does not necessarily improve the asymptotic complexity over brute force.
- e.g. If we prune out 99% of the search space, $0.01 \times b^n$ is still $O(b^n)$
However, backtracking works well for constraint satisfaction problems that are either:
Highly-constrained: Constraint violations are detected early in partial solutions and lead to MASSIVE amounts of pruning.
Under-constrained: Acceptable solutions are densely distributed, so it is quite likely we find one early and can terminate.
