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.

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,
Control Abstraction for Backtracking

Backtracking is useful in solving the following problems:


Additional Reading: Read more on IEEE

You may also like...

Leave a Reply

Your email address will not be published.