BACKTRACKING | Introduction to backtracking
BACKTRACKING
WHAT IS BACKTRACKING?
Backtracking is a technique that uses recursive algorithm by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (level of the tree) called as BOUNDATION CONDITIONS
Acc to Wikipedia -
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably
constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate
("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution
WHEN TO USE BACKTRACKING / IDENTIFYING BACKTRACKING PROBLEM
Ans.When we have to get multiple solutions to a problem statement including subset problems, set problems etc. we use backtracking
Types of BackTracking Problems.
- Decision problem used to find a feasible solution of the problem.
- Optimisation problem used to find the best solution that can be applied.
- Enumeration problem used to find the set of all feasible solutions of the problem.
- root(P): return the partial candidate at the root of the search tree.
- reject(P,c): return true only if the partial candidate c is not worth completing.
- accept(P,c): return true if c is a solution of P, and false otherwise.
- first(P,c): generate the first extension of candidate c.
- next(P,s): generate the next alternative extension of a candidate, after the extension s.
- output(P,c): use the solution c of P, as appropriate to the application
CONSTRAINT RELATION SATISFACTION
Some constraints ar provided to get the answer, if the set satisfies the problem then the traversal of the binary tree is continued else the compiler backtracks to another set of problems, in this way we can prevent all the unnecessary traversals of the tree that are not required
At the end we get all the possible subsets of solutions from the given data that satisfies the constraint relation.
Pseudo Code
For example. If we want a subset from the array whose sum is equal to 40.
Algorithm
Step 1.
Take a binary tree with two nodes having the sum of numbers uptill the traversal and next carrying the remaining array element's sum.
Step 2
if the sum of values of Node 1 and 2 is greater than the given sum it continues the traversal else it backtracks.
Step 3
Continues to check if the sum of values at Node 1 and Next element in the array is Less than or Equal to the given sum, else backtracks.
Comments