Q2 — TSP Branch-and-Bound: Refine Order and the 230 Tour
b1, b2, c3 — an unusual refine order where the ~BC side outranks BD's children — then d1 pops at 230.
The Question
TSP BnB snapshot when the optimal tour is discovered.
| # | Question | Official answer |
|---|---|---|
| 2.1 | 2nd–4th nodes refined | b1,b2,c3 |
| 2.2 | Optimal tour node + cost | d1,230 |
| 2.3 | Number of cities | 5 |
| 2.4 | Tour from A | A,C,E,B,D |
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,b2,c3
Simulate the priority queue:
| Pop | Queue (min first) | Action |
|---|---|---|
| 1 | a1 : 196 | refine a1 → insert b1(196), b2(230) |
| 2 | b1 : 196, b2 : 230 | refine b1 → insert c1(232), c2(236) |
| 3 | b2 : 230, c1 : 232, c2 : 236 | refine b2 → insert c3(230), c4(310) |
| 4 | c3 : 230, c1 : 232, c2 : 236, c4 : 310 | refine c3 → insert d1(230), d2(271) |
| 5 | d1 : 230, c1 : 232, … | d1 is a leaf → tour discovered, stop |
The 2nd–4th refinements are b1, b2, c3 ✓ — note the rare pattern where b2 (~BC side, bound 230) legitimately outranks b1's children (232, 236), so the exclude-branch is refined before BD's descendants.
2.2 — Optimal tour → d1, cost 230
Queue after pop 4: {d1 : 230, c1 : 232, c2 : 236, c4 : 310, d2 : 271}. The minimum, d1, is childless in the snapshot — a complete tour — and everything else is ≥ 232 → d1 = optimal tour at cost 230 ✓
c3's bound ties d1's at 230, but c3 has children — it was refined, so it represents a set of candidate tours, not a tour itself. Only childless nodes can be tours.
2.3 — Cities → 5
Reconstruct the cycle d1's decisions force. Path root→d1: ~BC excluded (b2), BD included (c3), AD included (d1):
| City | Degree so far | Forced partner(s) |
|---|---|---|
| D | B, A — full | done |
| B | D — needs 1 more | BC excluded → E |
| A | D — needs 1 more | C (E already taken by B) |
| C | — needs 2 | A and E |
Cycle: A–C–E–B–D–A → 5 distinct cities ✓
2.4 — Tour from A → A,C,E,B,D
The forced cycle above rotated to start at A: A, C, E, B, D (reverse A,D,B,E,C equivalent) ✓
Step through the queue — amber marks each refinement in order, green is the winning tour:
Tricks & Tips
Answers: 2.1 b1,b2,c3 · 2.2 d1,230 · 2.3 5 · 2.4 A,C,E,B,D