GENERAL METHOD OF BACKTRACKING
Introduction :
Backtracking is a type of technique that is based on a particular algorithm to solve a basic problem. It basically uses the recursive call function to get a particular solution by creating or building a solution stepwise with increasing values and time.
This algorithm is applied to the particular specific types of problems :
1 . Problems that require decision-making and are used to find a good solution for the problem.
2. The problems that can be optimized and are used to find the better solution that can be applied.
3. In the case of enumeration kind of problems, the algorithm is used to find the set of all easy and workable solutions for the given problem.
For Backtracking problems, the algorithm finds a path sequence for the solution of the problem that keeps some checkpoints,i.e, a point from where the given problem can take a backtrack if no workable solution is found out for the problem.
Backtracking – a schematic process of trying out different types of sequences of the various decision until it reaches the conclusion.
Some terms related to backtracking are :
- Live Node: Nodes that can further generate are known live nodes.
- E Node: the nodes whose children are generated and become a successor node.
- Success Node: if the node provides a solution that is feasible.
- Dead Node: A node that cannot be further generated and does not provide a particular solution.
There are many problems that can be solved by the use of a backtracking algorithm, and it can be used over a complex set of variables or constraints, they are basically of two types :
1. Implicit constraint: a particular rule used to check how many each element is in a proper sequence is related to each other.
2. Explicit constraint: the rule that restricts every element to get chosen from the particular set.
Some applications of backtracking include the N-Queen Problem, Sum of subset problem, Graph coloring, Hamilton cycle.
The algorithm is as follows :
Backtrak(n) if n is not the solution return false if n is new solution add the list of soliution to the list backtrack(expdn n)
Backtracking is a vital tool for solving different problems. Though the time complexity of the algorithm is comparatively higher, it is still needed to explore different kinds of algorithms.
The backtracking algorithm is required to solve various problems such as the:
- Hamilton problem
- The knight’s tour problem
- Maze solving problem
- N queen problem
And many more.
Reference