Reputation: 1527

branch and bound

Can someone explain the branch and bound search technique for me? I need to find a path with the smallest cost from any start node to an end node of any random graph using branch and bound search algorithm.

Upvotes: 4

Answers (4)

Tom Swifty

Reputation: 2952

Fantastic answer @j_random_hacker !!!!

See pg 439 (example 18.2) in Papadimitriou and Steiglitz, Combinatorial Optimization.

This book is a classic, and it discusses your exact problem.

Upvotes: 0

j_random_hacker

Reputation: 51226

The basic idea of B & B is:

When solving an optimisation problem ("Find an X satisfying criteria Y so as to minimise the cost f(X)"), you build a solution piece by piece -- at any point in time, you have a partial solution, which has a cost.
If the nature of the problem is such that the cost of a partial solution can only stay the same or go up as you continue adding pieces to it, then you know that there's no point continuing to add pieces to a partial solution if there's already a full solution with lower cost. In this case, you can abandon (or "prune", or "fathom") further processing of this partial solution.

Many problems have the latter property, making B & B a widely applicable algorithm technique.

The process of searching for solutions can be represented by a search tree, where the root node represents the starting point where no decisions have been made, and each edge leading from a node represents a decision about something to be included in a partial solution. Each node is a partial solution comprising the decisions made (edges) from the root to that node.

Example: if we want to solve a Sudoku puzzle, the root node would represent the board with just the originally supplied numbers filled in; there might be 9 edges from this root, each representing the decision to assign a number 1-9 to the top-left cell. Each of those 9 partial solution nodes could have 8 branches, representing the valid assignments to the cell at position (1, 2), and so on. Usually, each edge represents a recursion step in a program.

With B & B, in the best case a good solution is found early, meaning that unpromising areas of the search tree can be pruned near the root; but in the worst case, the entire tree of valid solutions will be generated. For this reason B & B is usually only used to solve problems for which no faster algorithm is known (such as NP-hard problems).

Upvotes: 7