Backtracking Notes 🥊
- Wikipedia - Backtracking
- GeeksforGeeks - Backtracking
- What’s the difference between backtracking and depth first search?
- difference between back tracking and Dynamic programming
Wiki: 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.
GeeksforGeeks: Backtracking is an algorithmic-technique for solving problems recursively 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 (by time, here, is referred to the time elapsed till reaching any level of the search tree).
Notice the difference between “backtracking” and “backtracks”. The latter one is more like
remove a candidate or a selection.
Backtrackingis a more general purpose algorithm. It iterates through a problem space. It can be used on any type of structure where portions of the domain can be eliminated, that is, you can look at a specific move and eliminate it.
Depth-First searchis a specific form of backtracking related to searching tree or graph structures. It iterates through an actual tree/graph structure. DFS is described in Wikipedia as follows:
One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.
If we extend DFS to general problems, we can call it
backtracking. If we use backtracking to tree/graph related problems, we can call it
According to Donald Knuth, it is the same.
Backtracking, also called depth-first search. — His paper about Dancing Links algorithm
Note: I think they should not be compared since they are very different algorithmic approaches.
Dynamic programming problems usually rely on the
principle of optimality. The principle of optimality states that an optimal sequence of decision or choices each sub sequence must also be optimal. Also, DP breaks down the problem into many smaller overlapped subproblems.
Backtracking problems are usually not optimal on their way. They can only be applied to problems which admit the concept of
partial candidate solution. It does not include any “break down” step, but builds the solution incrementally.