# Branch and Bound

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.


## Steps of Branch and Bound Approach
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.

## Applications of Branch and Bound Approach

- 0/1 knapsack problem
- Job Assignment Problem
- Traveling Salesman Problem
- Nearest Neighbor search
- N-Queens Problem


## Popular Dynamic Programming Algorithms
* [0/1 knapsack problem](Knapsack%20Problem/README.md)
* [Job Assignment Problem](Job%20Assignment%20Problem/README.md)
* [Traveling Salesman Problem](../Traveling%20Salesman%20Problem/readme.md)
* Nearest Neighbor search
* [N-Queens](../Backtracking/N%20Queen%20Problem/README.md)
