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:
- If we use other tree traversals than DFS (e.g. BFS), can it still be Backtracking?
- If we use other tree traversals than BFS (e.g. DFS), can it still be B&B?
- If we have a constraint satisfaction problem (CSP) and not a constraint optimization problem (COP), can it still be B&B?
- If we have a COP and not a CSP, can it still be Backtracking?
- 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.