What is a backtracking algorithm?

Question

What is an algorithm Backtracking ?

• What are its characteristics ?
• What are its advantages and disadvantages ?

Answer 1

Backtracking is a generic algorithm that searches, by brute force, possible solutions to computational problems (typically problems of satisfaction with restrictions).

• In an incremental way, search for candidates for solutions and abandon each partial candidate C when C cannot result in a solution valid.
• When your search reaches one end of the data structure, as a terminal node of a tree, the algorithm performs a rewind typically implemented through a recursion.

Algorithm Example

bool acabou = FALSE;

backtrack(int a[], int k, int n) {
    int c[MAXCANDIDATOS];  /* Candidatos para a próxima posição */
    int ncandidatos;       /* Número de candidatos para a próxima posição */
    int i;                 /* Contador */

    if (e_uma_solucao(a, k, n)) {
        processar_solucao(a, k, n);
    } else {
        k = k + 1;
        construir_candidatos(a, k, n, c, &ncandidatos);
        for (i=0; i<ncandidatos; i++) {
            a[k] = c[i];
            backtrack(a, k, n);
            if (acabou) return;
        }
    }
}

Basic Characteristics:

• For each recursive call there are several options that can be followed. E.g.: Many vertices may be next.
• Several data from the subset of input data not yet included in the solution are candidates. It may be that all are and there may be a restriction (Constraint) reducing the number of candidates. Ex.: Only neighbouring vertices are candidates to be next.
• The algorithm can attempt a recursive call for each of the candidates (solution for exhaustive search). Ex.: The Traveler Clerk tries all paths.
• The algorithm can choose one or a few data according to any criterion.
• The search process creates a recursive call tree. E.g.: All partial paths of the traveling salesman.
• Leaves of this tree are of two types:
  • They represent a possible solution to the problem.
  • Represent a point where the algorithm could no longer go forward (Failure) without hurting any precondition for the previously generated solution to be valid. Ex.: Path found up to now is very long, although there are still vertices to go.

Positives:

• Fairly easy way to implement a problem that would otherwise be much more complex than resolve.
• Logic Programming Area Languages (PROLOG, KL-ONE, OPS5) usually bring some built-in mechanism that supports backtracking.

Negative Points:

• Backtracking programs, unless you program constraints (constraints) always run an exhaustive search and will tend to the combinatorial explosion.
• Backtracking programs are by nature, combinatorics !
• They need a lot of memory in the stack, since the amount of local variables transported by each recursive call is directly proportional to the problem size.
• This means that the amount of memory required for a backtracking program can grow exponentially with the size of the problem.

Where applicable:

Backtracking is applicable in the solution of several known problems, among which can be highlighted:

• Traveler
• Horseback Ride
• N-Queens
• Find Space for Solutions
• Graham’s exam
• Generation of Permutations
• Maze problems

OBS: The combinatorial explosion should be kept in mind.

Source: Backtracking