Branch-and-bound & reasoning as search

Pruning without losing optimality

For a type-2 (path-cost) goal like the travelling-salesperson problem, exhaustive search over $(N-1)!$ tours is hopeless for large $N$. Branch-and-bound prunes the search while *still guaranteeing the optimal answer* — it is an *exact* method, unlike a heuristic. The idea:

1. Keep the cost of the best complete solution found so far as a *bound* (the *incumbent*).
2. As you extend a partial path, track its cost so far.
3. The moment a partial path's cost reaches or exceeds the incumbent bound, prune it — no extension can ever beat a tour that already costs more.

For TSP this drops the practical cost from $N!$ toward roughly $1.26^N$ — still exponential, but enormously smaller. Branch-and-bound is depth-first search plus a cost cutoff, and it previews the admissible-cost pruning of A\* in Module 4.

The greedy alternative: nearest neighbour

When even branch-and-bound is too slow, you drop the optimality guarantee for speed. The nearest-neighbour heuristic builds a tour by always stepping to the closest unvisited city — one path, no backtracking, very fast. But greedily minimising each step can force an expensive *closing* arc at the end: Luger's Figure 3.11 has nearest-neighbour cost 550 against the optimal 375. This is the central lesson that opens Module 4: heuristics trade the optimality guarantee for tractability, and must be evaluated empirically — not assumed good because they feel intuitive.

Reasoning IS search

The chapter's deepest idea closes the loop with Module 1's logic. Logical inference is *itself* a state-space search:

- a state is a *set of known true propositions* (facts/assertions); - an arc is the application of an inference rule (e.g. modus ponens), which transforms one fact-set into another by adding a newly derived fact; - proving that a proposition follows from axioms becomes a path-finding problem: is there a sequence of rule applications from the given facts to the target proposition?

Everything from this module transfers directly: data-driven search = forward chaining (apply rules to known facts), goal-driven search = backward chaining (work back from the goal). The soundness and completeness of the inference rules guarantee the search returns correct results. This is *exactly* the production-system view of Module 5 — every rule-firing is one arc in a reasoning state space.

Worked example — branch-and-bound on a 4-city tour

Four cities A, B, C, D with symmetric costs: AB 10, AC 15, AD 20, BC 35, BD 25, CD 30. Fix the start at A (a tour is a cycle, so the start is arbitrary) and extend partial tours depth-first, closing the loop back to A at the end. Each time a partial tour's running cost reaches the best *complete* tour found so far, prune it. The optimal tour is A → B → D → C → A at total cost 80, and along the way the bound lets the search prune 2 partial tours it never needed to finish. The runnable cell reproduces this.