Control Abstraction for Backtracking
Control abstraction for backtracking defines the flow of how it solves the given problem in an abstract way.
In backtracking, solution is defined as n-tuple X = (x1, x2, …, xn), where xi = 0 or 1. xi is chosen from set of finite components Si. If component xi is selected then set xi = 1 else set it to 0. Backtracking approach tries to find the vector X such that it maximize or minimize certain criterion function P(x1, x2, …, xn).
Control abstraction for the backtracking approach is shown below :
Control Abstraction for Recursive Backtracking:
- Backtracking is rather a typical recursive algorithm. Problems solved using backtracking are often solved using recursion. General algorithm discussed below finds all answer nodes, not just one. Let (x1, x2, …, xk) be the path from the root to the ith node. Let
T(x1, x2, …, xk) be the set all of all possible values for next node xk+1 such that (x1, x2, …., xk+1) is also a path from the root to a problem state.
- Recursive approach for backtracking is stated below.
REC_BACKTRACK(k) // X[1…k – 1] is the solution vector // T(x, x,…, x[K - 1]) is the state space tree // Bk( ) is the bounding function
each x[k] ∈ T[x, x, …, x[k – 1]]
(Bk(x, x, …, x[k – 1])) == TRUE
// (Feasible solution)
(x, x, …, x[k]) is path to answer node
print (x, x, …, x[k])
k < n
REC_BACKTRACK(k + 1)
Control Abstractyion for Iterative Backtracking:
The iterative approach for backtracking method is described below:
ITERATIVE_BACKTRACK(n) // X[1…k – 1] is the solution vector // T(x, x,…, x[K - 1]) is the state space tree // Bk( ) is the bounding function k ← 1
k ≠ 0
(untried x[k] ∈ T[x, x, …x[k – 1]]) AND (Bk(x, x, …, x[k]) is path to answer node)
print x, x,…x[k] // Solution k ← k + 1 // Consider next candidate in set
k ← k – 1 // Backtrack to recent node
- The performance of backtracking algorithm depends on four parameters:
1. Time to compute the tuple x[k]
2. Number of x[k] which satisfy the explicit constraint
3. Time taken by bounding function Bk to generate a feasible sequence
4. A number of x[k] which satisfies the bounding function Bk for all k.
- First three factors are independent and they can be computed in polynomial time. Whereas the last factor is problem dependent. In the worst case, checking of x[k] can be done in factorial time because the tree might have n! nodes. Time complexity of backtracking method is given as,
Popular problems solved using backtracking:
Backtracking is useful in solving the following problems:
- N-Queen problem
- Sum of subset problem
- Graph coloring problem
- Knapsack problem
- Hamiltonian cycle problem
Additional Reading: Read more on IEEE