Backtracking Vs Branch and Bound
Backtracking Vs Branch and Bound
Backtracking Vs Branch and Bound are discussed in this blog post. Backtracking is used to solve decision problems, whereas branch and bound is used to solve optimization problems. Decision problems are normally answered with yes or no. Optimization problems are those that seek to get the best possible solution from a given pool of solutions. In that way, the branch and bound methods sit in the category of dynamic programming and greedy algorithms.
Backtracking is a generic technique for solving various computational problems, most notably constraint satisfaction problems, that progressively constructs candidates to the solutions and abandons a candidate whenever it judges that it cannot potentially be completed to a legitimate solution.
Branch and Bound is a method for solving discrete and combinatorial optimization issues as well as mathematical optimization problems. The collection of candidate solutions is viewed as forming a rooted tree with the entire set at the root in a branch-and-bound method, which uses state-space search to systematically enumerate them. The method investigates the tree’s branches, which are subsets of the solution set. Before enumerating a branch’s candidate solutions, it’s tested against upper and lower estimated bounds on the optimal solution, and it’s eliminated if it can’t generate a better solution than the algorithm’s best so far.
| Backtracking | Branch and Bound |
| Backtracking is normally used to solve decision problems | Branch and bound is used to solve optimization problems |
| Nodes in the state-space tree are explored in depth-first order in the backtracking method | Nodes in the tree may be explored in depth-first or breadth-first order in branch and bound method |
| It realizes that it has made a bad choice & undoes the last choice by backing up. | It realizes that it already has a better optimal solution that the pre-solution leads to so it abandons that pre-solution. |
| The feasibility function is used in backtracking. | Branch-and-Bound involves a bounding function. |
| The next move from the current state can lead to a bad choice | The next move is always towards a better solution |
| On successful search of a solution in state-space tree, the search stops | The entire state space tree is searched in order to find the optimal solution |
| Backtracking is more efficient. | Branch-and-Bound is less efficient. |
| Applications: N Queen Problem Knapsack Problem Sum of subsets problem Hamiltonian cycle problem, Graph coloring problem |
Applications: Traveling salesman problem Knapsack problem Job sequencing problem |
Additional Reading: Read More