Sunday, June 18, 2017

Difference between backtracking & Branch and Bound

Backtracking:
* It is used to find all posible solution available to the problem
*It traverse tree by DFS(Depth first Search)
*It realizes that it has made a bad choice & ubndoes the last choice by tracking up.
*It search the state space tree until it found a solution
*It involves feasibility function

Branch-and-Bound(BB):
*It is used to solve optimization problem
*It may traverse the tree in any manner, DFS or BFS
*It realizes that is already has a better optional solution that the pre-solution leads to so it abandons that pre-solution.
*It completely search the state space tree to get optional solution.
*It involves bounding function.