Branch & Bound — exact search with pruning

B&B explores the tree of partial tours. At every node the lower bound(partial cost + MST(start ∪ remaining)) is compared with the best complete tour found so far — any branch whose bound cannot beat it is pruned. The bound is valid, so the surviving leaf is the exact optimum.