/ Data Structure and Algorithms  

Backtracking Algorithm

Concept

The backtracking algorithm is actually an enumeration-like search attempt process, which is mainly to find a solution to the problem during the search attempt. When it is found that the solution conditions have not been met, it “backtracks” and try another path.

The backtracking method is a search method for optimal selection. It searches forward according to the optimal conditions to achieve the goal. However, when exploring a certain step, if it is found that the original choice is not good or does not reach the goal, it goes back one step and chooses again, which is called “backtrack point”.

Many complex and large-scale problems can use the backtracking method. So it is known as the “universal problem solving method”.

Basic idea

In the solution space which contains all the solutions to the problem, the solution space is explored from the root node according to the depth-first search strategy. When a node is explored, first determine whether the node contains a solution to the problem. If it does, continue to explore from that node. If the node does not contain a solution to the problem, go back to its ancestor layers. (in fact, the backtracking method is a depth-first search algorithm for implicit graphs).

If using the backtracking method to find all the solutions to the problem, you must backtrack to the root, and all feasible subtrees of the root node must have been searched through before ending.

If you use the backtracking method to find any solution, you can end as long as you find a solution to the problem.

General steps to solve a problem using backtracking

  1. Determine the solution space for the given problem. The solution space of the problem should be clearly defined. The solution space of the problem should contain at least one (optimal) solution of the problem.

  2. Determine search rules for nodes

  3. Search the solution space in a depth-first manner, and use pruning functions to avoid invalid searches during the search.

Algorithm framework

  1. Problem framework
1
Suppose the solution of the problem is an n-dimensional vector(a1, a2, ...... an), and the constraint condition is that ai(i = 1,2,3, ....., n) satisfies a certain condition and is denoted as f(ai).
  1. Non-recursive backtracking framework
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int a[n],i;
initialize a[];
i = 1;

// haven't backtrack to the root
while (i > 0 (still have path to go) and (haven't reach target)) { 
    // search leaf node
    if(i > n) {                                             
        find a solution, output
    // process i-th element
    } else {                                                 
        a[i] the first possible value；
        
        while(a[i] not satisfy constraint condition, but still within search space) {
            a[i] next possible value；
        }

        if(a[i] within search space) {
            mark occupied resource;

            // extend to next node
            i = i+1;  
        } else {
            clear occupied resource;

            // backtrack
            i = i –1; 
        }
    }
}
  1. Recursive backtracking framework
    The backtracking method is a depth-first search of the solution space. In general, it is relatively simple to use a recursive function to implement the backtracking method, where i is the depth of the search, and the framework is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a[n];
try(int i) {
    if(i>n)
        output result;
    else {
        // iterate all possible path for i
        for(j = lower bound; j <= upper bound; j=j+1) {
            // satisfy boundary and constraint condition
            if(fun(j)) {                 
                a[i] = j;
                // other operations
                ...
                try(i+1);
                    cleaning tasks before backtracking (e.g set a[i] to empty etc);
            }
        }
    }
}