Skip to content

Latest commit

 

History

History
22 lines (21 loc) · 958 Bytes

Backtracking_VS_BranchBound.md

File metadata and controls

22 lines (21 loc) · 958 Bytes

Backtracking

1) Backtracking is used to find all possible solutions available to a problem. 
    When it realises that it has made a bad choice, 
    it undoes the last choice by backing it up. 
    It searches the state space tree until it has found a solution for the problem. 
2) Backtracking traverses the state space tree by DFS(Depth First Search) manner.
3) Backtracking is used for solving Decision Problem.
4) Backtracking is more efficient.

Branch & Bound

1) Branch-and-Bound is used to solve optimisation problems. 
   When it realises that it already has a better optimal solution that the pre-solution leads to, 
   it abandons that pre-solution. 
   It completely searches the state space tree to get optimal solution.

2) Branch-and-Bound traverse the tree in any manner, DFS or BFS.
3) Branch-and-Bound is used for solving Optimisation Problem.
4) Branch-and-Bound is less efficient.