Q2 — TSP Branch-and-Bound: a Small Tree, Fully Resolved
Only four refinements deep — b1, c2, d1 and the leaf d1 pops at 162 with the five-city tour A,D,B,C,E.
The Question
TSP BnB snapshot when the optimal tour is discovered.
| # | Question | Official answer |
|---|---|---|
| 2.1 | 2nd–4th nodes refined | b1,c2,d1 |
| 2.2 | Optimal tour node + cost | d1,162 |
| 2.3 | Number of cities | 5 |
| 2.4 | Tour from A | A,D,B,C,E |
The Topic in 60 Seconds
Refine = pop the cheapest open node, insert its two children. Childless snapshot nodes are tours. Stop when a tour pops with no cheaper open node.
Deep-dive: Reading BnB Trees, Branch and Bound.
2.1 — Refine order → b1,c2,d1
Simulate the priority queue:
| Pop | Queue (min first) | Action |
|---|---|---|
| 1 | a1 : 131 | process a1 → insert b1(131), b2(167) |
| 2 | b1 : 131, b2 : 167 | process b1 → insert c1(176), c2(162) |
| 3 | c2 : 162, b2 : 167, c1 : 176 | process c2 → insert d1(162), d2(198) |
| 4 | d1 : 162, b2 : 167, c1 : 176, d2 : 198 | process d1 — it is a leaf → tour discovered, stop |
The 2nd–4th nodes processed are b1, c2, d1 ✓ (d1 is the tour pop itself; the paper counts it among the processed nodes).
2.2 — Optimal tour → d1, cost 162
At pop 4, d1 (bound 162) is childless in the snapshot — a complete tour — and every other open bound is ≥ 167. Nothing cheaper can exist anywhere in the tree → d1 = optimal tour at cost 162 ✓.
c2's bound (162) ties d1's, but c2 has children — it was refined, so it is a set of candidate tours, not a tour. Only childless nodes can be tours.
2.3 — Cities → 5
Reconstruct the cycle d1's decisions force. Path root→d1: BC included (b1), AC excluded (c2), BD included (d1):
| City | Degree so far | Forced partner(s) |
|---|---|---|
| B | C, D — full | done |
| C | B — needs 1 more | AC excluded → E |
| D | B — needs 1 more | A (E already taken by C) |
| A | — needs 2 | D and E |
Cycle: A–D–B–C–E–A → 5 distinct cities ✓
2.4 — Tour from A → A,D,B,C,E
The forced cycle above rotated to start at A: A, D, B, C, E (reverse A,E,C,B,D equivalent) ✓
Step through the queue — amber marks each pop in order, green is the winning tour:
Tricks & Tips
Answers: 2.1 b1,c2,d1 · 2.2 d1,162 · 2.3 5 · 2.4 A,D,B,C,E