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 = (x₁, x₂, …, x_n), where x_i = 0 or 1. x_i is chosen from set of finite components S_i. If component x_i is selected then set x_i = 1 else set it  to 0. Backtracking approach tries to find the vector X such that it maximize or minimize certain criterion function P(x₁, x₂, …, x_n).

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 (x₁, x₂, …, x_k) be the path from the root to the i^th node. Let
  T(x₁, x₂, …, x_k) be the set all of all possible values for next node x_k+1 such that (x₁, x₂, …., x_k+1) is also a path from the root to a problem state.
• Recursive approach for backtracking is stated below.

Algorithm

 REC_BACKTRACK(k)
// X[1…k – 1] is the solution vector
// T(x[1], x[2],…, x[K - 1]) is the state space tree
// Bk( ) is the bounding function

for

each x[k] ∈ T[x[1], x[2], …, x[k – 1]] 

do

if

(Bk(x[1], x[2], …, x[k – 1])) == TRUE 

then

 // (Feasible solution)
    

if

(x[1], x[2], …, x[k]) is path to answer node 

then

      print (x[1], x[2], …, x[k])
    

end

if

k < n 

then

      REC_BACKTRACK(k + 1)
    

end

end

end

Control Abstractyion for Iterative Backtracking:

The iterative approach for backtracking method is described below:

Algorithm

ITERATIVE_BACKTRACK(n)
// X[1…k – 1] is the solution vector
// T(x[1], x[2],…, x[K - 1]) is the state space tree
// Bk( ) is the bounding function

k ← 1

while

k ≠ 0 

do

if

(untried x[k] ∈ T[x[1], x[2], …x[k – 1]]) AND
    (Bk(x[1], x[2], …, x[k]) is path to answer node)  

then

      print x[1], x[2],…x[k]	// Solution
    k ← k + 1     // Consider next candidate in set
  

else

    k ← k – 1     // Backtrack to recent node
  

end

end

Complexity Analysis

• 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