Types of Branch and Bound Solutions
The solution of the Branch and the bound problem can be represented in two ways:
- Variable size solution: Using this solution, we can find the subset of the given set that gives the optimized solution to the given problem. For example, if we have to select a combination of elements from {A, B, C, D} that optimizes the given problem, and it is found that A and B together give the best solution, then the solution will be {A, B}.
- Fixed-size solution: There are 0s and 1s in this solution, with the digit at the ith position indicating whether the ith element should be included, for the above example, the solution will be given by {1, 1, 0, 0}, here 1 represent that we have select the element which at ith position and 0 represent we don’t select the element at ith position.
Introduction to Branch and Bound – Data Structures and Algorithms Tutorial
Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and general mathematical optimization problems.
A branch and bound algorithm provide an optimal solution to an NP-Hard problem by exploring the entire search space. Through the exploration of the entire search space, a branch and bound algorithm identify possible candidates for solutions step-by-step.
There are many optimization problems in computer science, many of which have a finite number of the feasible shortest path in a graph or minimum spanning tree that can be solved in polynomial time. Typically, these problems require a worst-case scenario of all possible permutations. The branch and bound algorithm create branches and bounds for the best solution.
In this tutorial, we’ll discuss the branch and bound method in detail.
Different search techniques in branch and bound:
The Branch algorithms incorporate different search techniques to traverse a state space tree. Different search techniques used in B&B are listed below:
- LC search
- BFS
- DFS
1. LC search (Least Cost Search):
It uses a heuristic cost function to compute the bound values at each node. Nodes are added to the list of live nodes as soon as they get generated.
The node with the least value of a cost function selected as a next E-node.
2.BFS(Breadth First Search):
It is also known as a FIFO search.
It maintains the list of live nodes in first-in-first-out order i.e, in a queue, The live nodes are searched in the FIFO order to make them next E-nodes.
3. DFS (Depth First Search):
It is also known as a LIFO search.
It maintains the list of live nodes in last-in-first-out order i.e. in a stack.
The live nodes are searched in the LIFO order to make them next E-nodes.
Contact Us