3
$\begingroup$

I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound.

What confuses me:

  • Stack Overflow: Difference between 'backtracking' and 'branch and bound', Abhishek Dey: "Backtracking is [always] used to find all possible solutions" and "[Branch and Bound] traverse[s] the tree in any manner, DFS or BFS".
  • zhaoyan.website: Branch-and-Bound uses DFS or BFS, but usually BFS. At the same time, they say that B&B uses a queue which would mean that BFS is done. So this source seems to be inconsistent with itself.
  • Constrained optimization: "Constraint optimization can be solved by branch and bound algorithms. These are backtracking algorithms [...]"
  • *

Here is what I think they are. As it is a question about terminology where I already have an idea what the answer could be, I expect sources.

Concrete and a bit smaller questions:

  1. If we use other tree traversals than DFS (e.g. BFS), can it still be Backtracking?
  2. If we use other tree traversals than BFS (e.g. DFS), can it still be B&B?
  3. If we have a constraint satisfaction problem (CSP) and not a constraint optimization problem (COP), can it still be B&B?
  4. If we have a COP and not a CSP, can it still be Backtracking?
  5. Is B&B a special Backtracking algorithm (or vice versa)?

Depth-First Search

Depth-First-Search (DFS) is a way to traverse a graph:

def dfs(node):
    yield node
    for child in node.children:
        yield from dfs(child)

Example:

The following graph would be traversed in the order A, B, D, H, E, C, F, I, G

    A
   / \
  B   C
 / \  /\
D  E F  G
|    |
H    I

Breadth-First Search

BFS is another way to traverse a graph. For the example graph, the BFS traversal is [A, B, C, D, E, F, G, H, I]

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.

$\endgroup$
  • 2
    $\begingroup$ Your sources are confusing you; in particular, StackOverflow isn't particularly reliable when it comes to algorithmics. The point of branch and bound (beyond the BFS vs DFS question) is that you are pruning some of the search tree. This doesn't happen if you're just doing backtracking (without any pruning). You can think of branch and bound as a particular implementation of backtracking with pruning. $\endgroup$ – Yuval Filmus Mar 30 '20 at 21:18
  • 1
    $\begingroup$ Backtracking and branch and bound are both somewhat informal terms. What counts as backtracking or branch and bound really depends on the context, and ultimately on the person. This is similar to terms such as greedy algorithms, dynamic programming, and divide and conquer. $\endgroup$ – Yuval Filmus Mar 30 '20 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.