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 Vs Branch and Bound

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

You may also like...

Leave a Reply

Your email address will not be published.