Q2 — TSP Branch-and-Bound: Refine Order and the 434 Tour
Queue simulation gives the refine order b1,c2,b2,c3 — then d3 pops as the 434 tour over five forced cities.
The Question
TSP BnB snapshot at the moment the optimal tour is discovered. XY = include, ~XY = exclude; numbers = lower bounds; reference numbers break ties.
| # | Question | Official answer |
|---|---|---|
| 2.1 | 2nd–5th nodes refined | b1,c2,b2,c3 |
| 2.2 | Optimal tour node | d3 |
| 2.3 | Optimal cost | 434 |
| 2.4 | Number of cities | 5 |
| 2.5 | 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,b2,c3
| Pop | Queue (min first) | Action |
|---|---|---|
| 1 | a1 : 375 | refine → b1(375), b2(414) |
| 2 | b1 : 375, b2 : 414 | refine b1 → c1(418), c2(410) |
| 3 | c2 : 410, b2 : 414, c1 : 418 | refine c2 → d3(434), d4(468) |
| 4 | b2 : 414, c1 : 418, d3 : 434, d4 : 468 | refine b2 → c3(414), c4(452) |
| 5 | c3 : 414, c1 : 418, d3 : 434, c4 : 452, d4 : 468 | refine c3 → d5(414), d6(572) |
2.2 & 2.3 — Optimal tour → d3, 434
Queue continues: pop d5(414) → e1(436), e2(472); pop c1(418) → d1(456), d2(548). Now d3 : 434 is the minimum and a leaf — a tour. Everything else ≥ 436 → d3 = optimal, 434 ✓
2.4 — Cities → 5
Path root→d3: BD in, ~CD, AB in. Degrees: A–1, B–2 (full), C–0, D–1. D can't use CD → D–E. C needs two: C–A and C–E. Forced tour: A–B–D–E–C–A → 5 cities ✓
2.5 — Tour from A → A,B,D,E,C
The forced cycle above ✓ (reverse A,C,E,D,B equivalent).
Interactive queue simulation — gray = already refined, blue = waiting in OPEN, green = the winning tour:
The last step also traces the winning decisions BD in · ~CD · AB in: B is full (AB + BD), so D's second edge cannot be CD — it must be D–E; C then closes the cycle via C–A and C–E. Forced tour: A–B–D–E–C–A, 5 cities, cost 434.
Tricks & Tips
Answers: 2.1 b1,c2,b2,c3 · 2.2 d3 · 2.3 434 · 2.4 5 · 2.5 A,B,D,E,C