next up previous contents index CD CD Algorithms
Next: Constructing All Subsets Up: Combinatorial Search and Heuristic Previous: Combinatorial Search and Heuristic



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 tex2html_wrap_inline25600 , where each element tex2html_wrap_inline25602 is selected from an ordered set of possible candidates tex2html_wrap_inline25604 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 tex2html_wrap_inline25606 . From this partial solution tex2html_wrap_inline25608 , we will construct the set of possible candidates tex2html_wrap_inline25610 for the (k+1)st position. We will then try to extend the partial solution by adding the next element from tex2html_wrap_inline25614 . So long as the extension yields a longer partial solution, we continue to try to extend it.

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


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

k = 1

while k > 0 do

while tex2html_wrap_inline25628 do (*advance*)

tex2html_wrap_inline25630 = the next element from tex2html_wrap_inline25632


if tex2html_wrap_inline25636 is a solution, report it.

k = k + 1

compute tex2html_wrap_inline25640 , 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:  


if tex2html_wrap_inline25644 is a solution, report it.


k = k +1

compute tex2html_wrap_inline25648

while tex2html_wrap_inline25650 do

tex2html_wrap_inline25652 = an element in tex2html_wrap_inline25654

tex2html_wrap_inline25656 = tex2html_wrap_inline25658


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 up previous contents index CD CD Algorithms
Next: Constructing All Subsets Up: Combinatorial Search and Heuristic Previous: Combinatorial Search and Heuristic

Mon Jun 2 23:33:50 EDT 1997