Algorithm Design: Branch-and-Bound Algorithms

Branch-and-bound algorithms

We discover that we can omit many other alternatives while exploring the various choices in a brute force algorithm. The technique is often called branch-and-bound.

Suppose you were exhaustively searching the first floor and heard the phone ringing above your head.

We could immediately rule out the need to search the basement or the first floor. What might have taken three hours might now only take one, depending on how much space we can rule out.