Q2 — Reading a TSP Branch-and-Bound Search Tree
Simulate one priority queue over the snapshot tree: refine order, the 366 tour, and why the hidden city E is forced.
The Question
The TSP BnB snapshot when the optimal tour is discovered. XY = include edge, ¬XY = exclude. Numbers = lower bounds. Reference numbers break ties.
| # | Question | Official answer |
|---|---|---|
| 2.1 | 2nd–5th nodes refined | b1,c1,d2,b2 |
| 2.2 | Node of the optimal tour | d5 |
| 2.3 | Cost of the optimal tour | 366 |
| 2.4 | Number of cities | 5 |
| 2.5 | Optimal tour from A | A,B,D,C,E (also A,E,C,D,B) |
The Topic in 60 Seconds
- A node = a set of tours sharing its include/exclude decisions; its number = a lower bound for that set.
- Refine = pop the cheapest open node, insert its two children. Bounds rise monotonically toward leaves.
- Childless nodes in the snapshot are finished branches — tours.
- Stop when a tour is popped and no open node is cheaper.
Deep-dive: Reading BnB Trees, Branch and Bound.
2.1 — Refine order → b1,c1,d2,b2
| Pop | Queue (min first) | Action |
|---|---|---|
| 1 | a1 : 305 | refine → b1(305), b2(342) |
| 2 | b1 : 305, b2 : 342 | refine b1 → c1(305), c2(350) |
| 3 | c1 : 305, b2 : 342, c2 : 350 | refine c1 → d1(382), d2(327) |
| 4 | d2 : 327, b2 : 342, c2 : 350, d1 : 382 | refine d2 → e1(378), e2(403) |
| 5 | b2 : 342, c2 : 350, e1 : 378, d1 : 382, e2 : 403 | refine b2 → c3(342), c4(387) |
2nd–5th refined: b1, c1, d2, b2 ✓
2.2 & 2.3 — Optimal tour → d5, cost 366
Continue the queue: after b2 the OPEN set is c3 : 342, c2 : 350, e1 : 378, d1 : 382, c4 : 387, e2 : 403. Pop c3(342) → d5(366), d6(382). Pop c2(350) → d3(500), d4(516). Now the minimum is d5 : 366 — a leaf (tour), and every open node ≥ 378. d5 is the optimal tour, cost 366 ✓
2.4 — Number of cities → 5
Reconstruct the tour d5 forces. Path root→d5: ¬AC, BD, CD (exclude A–C; include B–D, C–D).
- Degrees: B–1, C–1, D–2 (full), A–0, E–0.
- D is done. A needs 2 edges from AB and AE (AC excluded) — so AB and AE. E then takes the remaining slot: E–C.
- Forced tour: A–B–D–C–E–A → 5 distinct cities ✓ (a 4-city attempt strands C once CD and AC are gone).
2.5 — Tour from A → A,B,D,C,E
The forced cycle above, rotated to start at A: A, B, D, C, E (reverse rotation A,E,C,D,B also accepted).
Interactive tree — amber = refined (in pop order), green = the winning leaf:
Interactive queue simulation — gray = already refined, blue = waiting in OPEN, green = the winning tour:
The last step also traces the winning decisions ¬AC · BD · CD: D is full (BD + CD); A cannot use AC, so A takes AB and AE; C then closes the cycle via C–E. Forced tour: A–B–D–C–E–A, 5 cities, cost 366.
Tricks & Tips
Answers: 2.1 b1,c1,d2,b2 · 2.2 d5 · 2.3 366 · 2.4 5 · 2.5 A,B,D,C,E