branch and bound
- it is similar to backtracking since it uses the state space tree
- Used for solving optimization problems and minimization problems
- If we are given with a maximisation problem then we can convert it using brands and bound technique by simply converting the problem into maximisation problem
- A graph will be given and we need to find the shortest path between the source and the destination
- This method is used when both dynamic programming and greedy algorithms fail
- Branchandbound is much slower than they often leads to exponential time complexity in worst cases
- This method involves tree organisation of solution space
- Use of bounding function to limit the search that is to avoid the generation that do not contain the answer
Branch and bound from ChatGPT
-we use DFS in div and conq, but in bnb we use BFS.
-Used for solving optimization problems it is particularly useful For combinatorial Optimization problems where you want to find the best solution from finite set of possibilities
-The main idea Behind Branchandbound is to divide the problem into sub problems and use bounce to eliminate certain branches of the dream making the algorithm more efficient
the working of branch and bound technique:
1. Branching: It begins with initial solution or a partial solution and divides the problem into sub problems called as branching. Here each Branch represents different choice or decision point in the problem
2. bounding: The algorithm assigns Bounce that is upper bounds and lower bounds to each branch these bounds are used to estimate the quality of the solution that can be obtained by completing a branch
- Branches with bounds worse than the current best solution are pruned meaning they are not explored further
3. Searching: The algorithm systematically explores all the branches prioritises dose with the more promising bounds.
- This process goes on continuing until The optimal solution is found or proves that no better solution can be found within the current search space
- Black tracking: If a branch is proven to be feasible or if the algorithm finds a better solution it backtracks to the previous decision point and continues the search from there
Branch and bound is particularly useful In many number of possible solutions as it reduces the search space by eliminating unpromising branches early in the process it can be used both for maximising and minimising problems
Applications of branch and bound technique
- 0/1 knapsack problem
- Travelling salesperson problem
Search techniques used in branch and bound :
1. BF S
2. Dfs
3. Least cost search
0/1 knapsack problem
Involves systematically exploring different combinations of items to find optimal Solutions while efficiently pruning the branches of the search tree which are guaranteed not to lead to Better solution
- It is a combinatorial optimization problem where you have a set of items each with weight and value you have to determine the most valuable combination of items to include in the knapsack without exceeding its weight capacity
- Initialisation: Start with an empty knapsack. Set the current best solution the upper bound to zero and the current solution to an empty set of items start with the first item
- Branching: Create two child notes for each node in the search till 1 child includes the next item and the other does not
- BoundingCalculate an upper bound on the maximum value for each node if the bound is less than the best solution for funk so for prune the branch that is don’t explore further
- ExplorationExplore all the branches with the highest bounds first
- BacktrackingContinue exploring until you find a solution or prune all the branches if solution is found update the best solution if the current is higher
- Terminationthe algorithm terminates when all the notes are explored and no more notes have higher bound than the current best solution
Travelling salesperson using branch and bound
The goal is to find the shortest possible tour or the path That visits a set of cities exactly once and returns to the starting city
1. You will have a set of cities each with specific location and you need to find the shortest path
2. Start with lower bound of zero create a initial node in a search tree that represents starting city
3. Calculate the lower bound for the initial node using Minimal spanning tree or nearest neighbour
4. Create a priority queue like min-heap To store the notes to be explored initially containing only the initial
branching and bounding starts
5. Pop the node with the lowest lower bound from the priority queue
6. For this note create child notes by adding one unvisited city as the next city in the tour
7. Calculate the lower bound for each child node this can be done using minimum spanning tree or nearest neighbour algorithm
8. Prune the notes where lower bound exceeds the current best solution
9. When the leaf node is reachedthat means all the cities are visited then calculate the cost of the tour for the node
10. If the cost is better than the current best solution update the current best solution
11. Backtrack to the parent nod and continue branching bounding and updating the best solution continue this process until you have explored all the possible paths or pruned enough branches to prove that no better solution exist
12. The current best solution is the optimal tour or the shortest path for the TSP
NP harden NP completes
- Problem that can be solved in polynomial time is called as P problem
- Problem that cannot be solved in polynomial time is called np problem
- The problems which can be Sold in less time or called as polynomial time(Linear search and binary search) and which take more time are called as exponential time(zero1 knapsack problem travelling sales person problem)
N P complete:
A Np complete problem will be completed in polynomial time If and only if all other NP complet problems complete in polynomial time
N P hard:
One NP heart problem can be completed in polynomial time only if and only if all other np complete problems can be solved in polynomial time
- A problem that is in both N P and N P hard are called as N P complete problems
-all N P problems that can be reduced ….en time is known as N P hard problem
