- How branch and bound method works?
- Live node, e -node and dead node
- FIFO-BB and LIFO-BB
- Branch and bound solution for 0-1 knapsack problem
- Branch and bound solution for Travelling Sales Person(TSP) problem
- Branch and bound solution for N-Queen problem
- Least cost branch and bound(LC-BB)
- A* algorithm is LC-BB
Solving 0-1 Knapsack using Branch and Bound
Branch and bound for Travelling Sales Person (TSP) problem
The travelling salesperson problem, also known as travelling salesman problem (TSP), asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.
The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP.
Solving 4 queen problem using Branch and Bound
Imagine a game of chess where you’re tasked with placing queens on a chessboard. The catch? You can’t place them where they’ll threaten each other. This puzzle is known as the N Queens problem, where you have to position N queens on an N×N chessboard without any of them being able to attack each other. So, no sharing rows, columns, or diagonals!
Now, let’s talk about two ways to tackle this challenge: backtracking and Branch and Bound.
In the backtracking method, you start by placing queens one by one, column by column. When you place a queen in a column, you check if it clashes with any previously placed queens. If it does, you backtrack and try another spot. Simple, right?
Now, Branch and Bound takes a slightly different approach. It’s like peeking ahead in a maze.
A* algorithm is a LC-BB
