Home »
Algorithms
Backtracking (Types and Algorithms)
In this article, we will study about the concept of Backtracking and its types with their algorithms.
Submitted by Shivangi Jain, on June 26, 2018
Backtracking
- The name backtrack was first given by D. H. Lehmer in 1950s.
- The general technique to solve any problem that deal with searching for a set of solution or which ask for an optimal solution satisfying some constraints is known as backtracking.
-
Some of the problems that can be solved by backtracking are:
- Sorting the array of integers in a {1:n}.
- 8 - Queens problem.
- 4 - Queens problem, or in generalized way n queen’s problem.
- Sum of subsets problem.
Types of backtracking algorithms
There are two types of backtracking algorithms:
- Recursive backtracking algorithm
- Non - recursive backtracking algorithm
1) Recursive backtracking algorithm
Naturally describing backtracking in this way is essential because it is a postorder traversal of a tree.
Algorithm:
1. Algorithm Backtrack (k)
2. // this scheme describes the backtracking process using
3. // recursion. On entering, the first k-1 values.
4. // x [1], x [2]… x [k-1] of the solution vector.
5. // x [1:n] have been assigned. X [] and n are global.
6. {
7. For (each x [k] £ T (x[1],……,x[k-1])do
8. {
9. If ( Bk (x [1], x[2],……….,x [k] != 0) then
10. {
11. If (x[1], x[2], …… , x[k] is a path to an answer node )
12. Then write (x[1:k]);
13. If(k<n) then backtrack (k+1);
14. }
15. }
16. }
The solution vector (x1, x2... xk) is treated as a global array x [1: n]. All the possible elements for kth position of the tuple that satisfy Bk are generated, one by one and then they are adjoined to the current vector (x1... xk-1). Each time xk is attached, a check is made to find whether a solution has been found. When the for loop of line 7 is completed, no more values for xk exist and the current copy of backtrack ends.
2) Non - Recursive backtracking algorithm
An iterative or non-recursive version of recursive algorithm appears in non-recursive algorithm.
Algorithm:
1. Algorithm backtrack (k)
2. // this scheme describes the backtracking process.
3. // all solution are generated in x [1: n] and printed
4. // as soon as they are determined.
5. {
6. K = 1;
7. While (k != 0) do
8. {
9. If ( there remains are untried x[1] £ T ( x [1], x[2], ….., x [k-1]) and Bk (x[1], ….., x[k]) is true) then
10. {
11. If ( x[1], …., x[k] is a path to an answer node)
12. Then write ( x[1 : k]);
13. K = k+1; // consider the next set
14. }
15. Else k = k-1 ; // backtrack to the previous set
16. }
17. }
T() here yields the set of all possible values that can be placed as the first component x1 of the solution vector. The component x1 will take values for which the bounding function B1 (x1) is true.
Elements are generated here in a depth first manner.