Tutorialspoint.dev

Introduction To

Branch and Bound Algorithm

Branch-and-bound is a general technique for improving the searching process by systematically enumerating all candidate solutions and disposing of obviously impossible solutions.

Branch-and-bound usually applies to those problems that have finite solutions, in which the solutions can be represented as a sequence of options. The first part of branch-and-bound branching requires several choices to be made so that the choices will branch out into the solution space. In these methods, the solution space is organized as a treelike structure. Branching out to all possible choices guarantees that no potential solutions will be left uncovered. But because the target problem is usually NP-complete or even NP-hard, the solution space is often too vast to traverse.

An important advantage of branch-and-bound algorithms is that we can control the quality of the solution to be expected, even if it is not yet found.

 

Course Structure

Subscribe to Our Newsletter