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.

Answer 2

Backtracking

Backtracking is a general concept to solve discrete constraint satisfaction problems (CSPs). It uses DFS. Once it's at a point where it's clear that the solution cannot be constructed, it goes back to the last point where there was a choice. This way it iterates all potential solutions, maybe aborting sometimes a bit earlier.

Branch-and-Bound

Branch-and-Bound (B&B) is a concept to solve discrete constrained optimization problems (COPs). They are similar to CSPs, but besides having the constraints they have an optimization criterion. In contrast to backtracking, B&B uses Breadth-First Search.

One part of the name, the bound, refers to the way B&B prunes the space of possible solutions: It gets a heuristic which gets an upper bound. If this cannot be improved, a sup-tree can be discarded.

Besides that, I don't see a difference to Backtracking.

Other Sources

There are other answers on the web which make very different statements:

• Branch-and-Bound is backtracking with pruning (source)