Backtracking
Backtracking is an algorithmic technique for recursively solving problems by trying to build a solution incrementally, one piece at a time, removing the solutions that fail to meet the constraints of the problem at any time (for example, time, here it is referred to the time elapsed until reaching any level of the search tree).
According to the wikipedia definition,
Backtracking can be defined as a general algorithmic technique that considers the search for all possible combinations in order to solve a computational problem.
There are three types of backtracking problems –
Decision problem – In Decision problem we are looking for a feasible solution.(What is feasible solutions among all solutions possible).
Optimization problem – In Optimization problem we are looking for the best solution(What is best solution among all possible solutions possible).
Problem of enumeration – In Problem of enumeration we find all the feasible solutions(What is feasible solutions among all solutions possible).
Search space and optimization problem techniques Backtracking
General method
Two versions of backtracking algorithms
Solution needs only to be feasible (satisfy problem’s constraints) sum of subsets
Solution needs also to be optimal knapsack problem
The backtracking method
- A given problem has a set of constraints and possibly an objective function
- The solution optimizes an objective function, and/or is feasible.
- We can represent the solution space for the problem by using a state space tree
The root of the tree represents 0 choices,
Nodes at depth 1 represent the first choice
Nodes at depth 2 represent the second choice, etc.
In this tree a path from a root to a leaf represents a candidate solution - Problem space consists of states (nodes) and actions (paths that lead to new states).
- If a node leads to failure go back to its “parent” node.
- Characteristics of Brute Force and Backtracking
Brute force algorithms are slow
They don’t employ a lot of logic
But, brute force algorithms are fairly easy to implement as a first pass solution Backtracking is a form of a brute force algorithm
Goals of Backtracking Possible goals
- Find a path to success
- Find all paths to success
- Find the best path to success
Not all problems are exactly alike, and finding one success node may not be the end of the search
Pseudo code for recursive backtracking algorithms
- If at a solution, report success
- for ( every possible choice from current state / node)
Make that choice and take one step along path
Use recursion to solve the problem for the new node / state
If the recursive call succeeds, report the success to the next high level
Back out of the current choice to restore the state at the beginning of the loop. - Report failure
Algorithm for Backtracking
void checknode(node v)
{
node u;
if promising(v) then
if (there is a solution at v) then
write the solution ;
else
for (each child u of v) do
checknode(u);
}
Topic : Backtracking | Algorithm for Backtracking