21

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?

thepurpleowl
  • 147
  • 4
  • 15
Varun Teja
  • 503
  • 2
  • 6
  • 16

4 Answers4

14

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.
Shirish Kadam
  • 689
  • 1
  • 9
  • 21
Abhishek Dey
  • 1,601
  • 1
  • 15
  • 38
  • does backtracking find optimal solution always? – Varun Teja May 04 '15 at 10:17
  • Yep, always give the best solution. – Abhishek Dey May 04 '15 at 10:25
  • @AbhishekDey Actually, backtracking will give *a* solution, not necessarily the most optimal solution. Backtracking works best for constraint satisfaction problems and branch-and-bound is best for optimization problems. – Cameron Gagnon Nov 02 '16 at 06:36
  • 5
    @CameronGagnon To be clear, backtracking guarantees optimality *in theory*, because it will explore *all* solutions, only pruning those that it knows for sure they can't possibly be optimal. In practice, of course, this algorithm can take forever on medium to large size instances if the number of combinations is exponential and if no smart pruning is possible. – Patrice Gahide Nov 09 '16 at 20:04
3

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)
Martin Thoma
  • 124,992
  • 159
  • 614
  • 958
1

Backtracking

  • Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.
  • It enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.
  • Conceptually, the partial candidates are represented as the nodes of a tree structure, the potential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step, the leaves of the tree are the partial candidates that cannot be extended any further.
  • It traverses this search tree recursively, from the root down, in depth-first order (DFS). It realizes that it has made a bad choice & undoes the last choice by backing up.
  • For more details: Sanjiv Bhatia's presentation on Backtracking for UMSL.

Branch And Bound

  • A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root.
  • The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
  • It may traverse the tree in any following manner:
    1. BFS (Breath First Search) or (FIFO) Branch and Bound
    2. D-Search or (LIFO) Branch and Bound
    3. Least Count Search or (LC) Branch and Bound
  • For more information: Sanjiv Bhatia's presentation on Branch and Bound for UMSL.
Arjun Ashok
  • 53
  • 1
  • 8
kshitij chaurasiya
  • 177
  • 1
  • 13
0

Backtracking: -optimal solution is selected from solution space. -traversed through DFS. Branch and Bound: -BFS traversal. -here only fruitful solutions are generated rather than generating all possible ones.

user117172
  • 1