Q2 — TSP Branch-and-Bound: Refine Order and the 282 Tour
Queue simulation: b1, c2, d1, b2 — then leaf e1 pops at 282 and the five-city tour falls out of the degree constraints.
The Question
TSP BnB snapshot when the optimal tour is discovered.
| # | Question | Official answer |
|---|---|---|
| 2.1 | 2nd–5th nodes refined | b1,c2,d1,b2 |
| 2.2 | Optimal tour node + cost | e1,282 |
| 2.3 | Number of cities | 5 |
| 2.4 | Tour from A | A,B,D,E,C |
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,b2
Pop the minimum bound each round; refining replaces the popped node by its two children.
| Pop | Queue before (bound) | Refine | Children added |
|---|---|---|---|
| 1 | a1 : 254 | a1 | b1 : 254, b2 : 279 |
| 2 | b1 : 254, b2 : 279 | b1 | c1 : 302, c2 : 271 |
| 3 | c2 : 271, b2 : 279, c1 : 302 | c2 | d1 : 271, d2 : 342 |
| 4 | d1 : 271, b2 : 279, c1 : 302, d2 : 342 | d1 | e1 : 282, e2 : 286 |
| 5 | b2 : 279, e1 : 282, e2 : 286, c1 : 302, d2 : 342 | b2 | c3 : 279, c4 : 308 |
2.2 — Optimal tour → e1, cost 282
Pop c3(279) → adds d3(300), d4(305). Queue sorted: {e1 : 282, e2 : 286, d3 : 300, c1 : 302, d4 : 305, c4 : 308, d2 : 342}.
The minimum e1 : 282 has no children in the snapshot — it is a complete tour — and every other open bound is ≥ 286 > 282. Nothing cheaper can ever appear → e1 = optimal, 282 ✓
2.3 — Cities → 5
Chain root→e1: AC in → ~AD excluded → BD in → AB in. Fixed edges: A–C, B–D, A–B.
Degrees: A = 2 (C, B) full · B = 2 (D, A) full · C = 1 (A) · D = 1 (B) · E = 0.
AD is excluded, so D's missing partner cannot be A → forced D–E; then C's missing partner is E too → C–E. One closed cycle:
2.4 — Tour from A → A,B,D,E,C
The forced cycle above read from A ✓ (the reverse A,C,E,D,B is the same tour).
Amber = refined in order b1 → c2 → d1 → b2. Green = e1, the 282 tour.
Tricks & Tips
Answers: 2.1 b1,c2,d1,b2 · 2.2 e1,282 · 2.3 5 · 2.4 A,B,D,E,C