回溯与深度优先搜索的比较

1. Introduction

In this tutorial, we’ll explore the difference between backtracking and depth-first search. We’ll also look at an example algorithm using the backtracking technique.

2. Depth-First Search

Depth-first search (DFS) is the algorithm used to traverse a graph. It starts on the root node and travels as deep as possible along each branch.

The tree below presents the order in which nodes will be visited when applying depth-first search:

We can use the depth-first search to solve puzzles with only one solution or to find connected components. It’s also a default algorithm for finding cycles in a graph. Moreover, it’s a more useful general graph search than the breadth-first search because it’s more space-efficient.

3. Backtracking

Backtracking is an algorithm used to iterate over all possible solutions in the search space. Therefore, it’s commonly used to solve problems with constraints. In this sense, backtracking limits the search space, thus saving compute time.

The process of constructing partial solutions from the base case corresponds to performing a depth search traversal of the tree.

3.1. An Example

Let’s write a straightforward algorithm to generate all subsets from elements in the given array. For each input element, we will add it to the candidate list and recursively invoke the Subsets() function. After this step, we backtrack by removing this element from our candidate list. Finally, we call Subsets() function again.

The ultimate result is a sum of both recursive calls.

algorithm findAllSubsets(Q, k, candidateSubset):
    // INPUT
    //    Q = An array of n unique elements
    //    k = Current index in the array Q
    //    candidateSubset = Current subset being constructed
    // OUTPUT
    //    A list of all possible subsets of the array Q without duplicates
    
    if k = length(Q):
        result <- create an empty list
        add candidateSubset to result
        return result
    else:
        include the current element in candidateSubset
        subresultWithElement <- findAllSubsets(Q, k + 1, candidateSubset)
        
        exclude the current element from candidateSubset
        subresultWithoutElement <- findAllSubsets(Q, k + 1, candidateSubset)
        
        combine both subresults
        result <- subresultWithElement + subresultWithoutElement
        return result

The recursive execution tree of the above algorithm will look as follows:

We can find the final solution at the bottom of the execution tree. It’s a set of eight elements:

   

The subsets order shows that to construct them, we used depth-first search following the left tree branch.

3.2. Applications of Backtracking

Backtracking is widely used to solve crosswords, Sudoku, chess, tic-tac-toe, and other puzzles. It’s also useful when generating all the combinations of elements from a given set. Additionally, it’s the basis of programming languages such as Icon, Planner, and Prolog.

4. Comparison

Interestingly, we can see that the solution space over which the backtracking algorithm iterates usually has a form of a graph. As such, the implementation of both algorithms is very similar:

Backtracking

Depth-first Search

Can be applied to any data structure

Restricted to graphs

General technique for dealing with constraint problems

Algorithm used to iterate over a graph

Can stop searching the tree if the constraint isn’t met

Has to reach the leaf node before returning

5. Conclusion

In this article, we discussed the similarities and differences between backtracking and DFS. We also wrote a simple algorithm using backtracking.

Finally, we learned that because backtracking uses DFS to traverse the solution space, they can both be represented as recursive algorithms.