Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. The Branch and Bound Algorithm technique solves these problems relatively quickly.
The general idea of Branch and Bound algorithm is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.
- 0/1 knapsack problem
- Job Assignment Problem
- Traveling Salesman Problem
- Nearest Neighbor search
- N-Queens Problem
- 0/1 knapsack problem
- Job Assignment Problem
- Traveling Salesman Problem
- Nearest Neighbor search
- N-Queens