Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
C
Embedded C
Java
SEO
HR
CS Subjects
CS Basics
O.S.
Networks
DBMS
Embedded Systems
Cloud Computing
Machine learning
CS Organizations
Linux
DOS
More...
Articles
Puzzles
News/Updates

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:
    1. Sorting the array of integers in a {1:n}.
    2. 8 - Queens problem.
    3. 4 - Queens problem, or in generalized way n queen’s problem.
    4. Sum of subsets problem.

Types of backtracking algorithms

There are two types of backtracking algorithms:

  1. Recursive backtracking algorithm
  2. 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.






Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com (2015-2018), Some rights reserved.