Branch and Bound
BnB is not always bed and breakfast
Branch and bound is similarly inspired to A*
Unlike A* may not guarantee optimal solution first
As in A*, look for a bound which is guaranteed lower than the true cost
Search the branching tree in any way you like
- e.g. depth first (no guarantee), best first
Cut off search if cost + bound > best solution found
If heuristic is cost + bound, search = best first