Difference between 'backtracking' and 'branch and bound'

Question

In backtracking we use both bfs and dfs. Even in branch and bound we use both bfs and dfs in additional to least cost search.

so when do we use backtracking and when do we use branch and bound

Does using branch and bound decreases time complexity?

What is Least cost search in Branch and Bound?

Answer 1

Backtracking

1. It is used to find all possible solutions available to a problem.
2. It traverses the state space tree by DFS(Depth First Search) manner.
3. It realizes that it has made a bad choice & undoes the last choice by backing up.
4. It searches the state space tree until it has found a solution.
5. It involves feasibility function.

Branch-and-Bound

1. It is used to solve optimization problem.
2. It may traverse the tree in any manner, DFS or BFS.
3. It realizes that it already has a better optimal solution that the pre-solution leads to so it abandons that pre-solution.
4. It completely searches the state space tree to get optimal solution.
5. It involves a bounding function.