Next: Constructing All Subsets Up: Combinatorial Search and Heuristic Previous: Combinatorial Search and Heuristic

# Backtracking

Backtracking is a systematic way to go through all the possible configurations of a space. These configurations may be all possible arrangements of objects (permutations) or all possible ways of building a collection of them (subsets). Other applications may demand enumerating all spanning trees of a graph, all paths between two vertices, or all possible ways to partition the vertices into color classes.

What these problems have in common is that we must generate each one of the possible configurations exactly once. Avoiding both repetitions and missing configurations means that we must define a systematic generation order among the possible configurations. In combinatorial search, we represent our configurations by a vector , where each element is selected from an ordered set of possible candidates for position i. As shown below, this representation is general enough to encode most any type of combinatorial object naturally.

The search procedure works by growing solutions one element at a time. At each step in the search, we will have constructed a partial solution with elements fixed for the first k elements of the vector, where . From this partial solution , we will construct the set of possible candidates for the (k+1)st position. We will then try to extend the partial solution by adding the next element from . So long as the extension yields a longer partial solution, we continue to try to extend it.

However, at some point, might be empty, meaning that there is no legal way to extend the current partial solution. If so, we must backtrack, and replace , the last item in the solution value, with the next candidate in . It is this backtracking step that gives the procedure its name:

```

Backtrack(A)

Compute   , the set of candidate first elements of solution A.

k = 1

while k > 0 do

= the next element from

if    is a solution, report it.

k = k + 1

compute   , the set of candidate kth elements of solution A.

k = k - 1  (*backtrack*)

```

Backtracking constructs a tree of partial solutions, where each vertex is a partial solution. There is an edge from x to y if node y was created by advancing from x. This tree of partial solutions provides an alternative way to think about backtracking, for the process of constructing the solutions corresponds exactly to doing a depth-first traversal of the backtrack tree. Viewing backtracking as depth-first search yields a natural recursive implementation of the basic algorithm:

```

Backtrack-DFS(A,k)

if    is a solution, report it.

else

k = k +1

compute

while    do

= an element in

=

Backtrack(a,k)

```

Although a breadth-first search could also be used to enumerate all solutions, depth-first search is greatly preferred because of the amount of storage required. In depth-first search, the current state of the search is completely represented by the path from the root to the current search node, which requires space proportional to the height of the tree. In breadth-first search, the queue stores all the nodes at the current level, which is proportional to the width of the search tree. For most interesting problems, the width of the tree will grow exponentially in its height.

To really understand how backtracking works, you must see how such objects as permutations and subsets can be constructed by defining the right state spaces. Examples of several state spaces are described below.

Next: Constructing All Subsets Up: Combinatorial Search and Heuristic Previous: Combinatorial Search and Heuristic

Algorithms
Mon Jun 2 23:33:50 EDT 1997