Q2 — Reading a TSP Branch-and-Bound Search Tree
The search tree is the answer sheet: refine order, optimal tour, number of cities — all extracted by simulating one priority queue.
The Question
A TSP Branch-and-Bound run stops the moment it discovers the optimal tour. The tree below is that snapshot. Each node shows an edge decision (BD = include edge B–D, ~BD = exclude it), a lower-bound cost, and a reference number (used for ties).
| # | Question | Official answer |
|---|---|---|
| 2.1 | How many nodes were refined to discover the optimal tour? | 7 |
| 2.2 | Node of the optimal tour + its cost | d3,434 |
| 2.3 | Number of cities | 5 |
| 2.4 | Optimal tour from city A | A,B,D,E,C |
The Topic in 60 Seconds
- Every tree node = a set of candidate tours sharing the include/exclude decisions on the path from the root. Its number = a lower bound on any tour in that set.
- Refining a node = removing it from the open list and inserting its two children (include / exclude one more edge). Bounds only ever increase going down.
- A node with no children in the snapshot = a finished branch — either a complete tour (leaf) or a dead end.
- The algorithm always refines the cheapest open node (ties → reference number). The run ends when a tour is popped and no open node has a smaller bound.
Deep-dive: Reading BnB Trees, Branch and Bound, TSP.
2.1 — Nodes refined → 7
Simulate the priority queue. Internal nodes get refined (children added); leaves of the snapshot are tours — they are selected, not refined.
| Pop # | Queue (min first) | Action |
|---|---|---|
| 1 | a1 : 375 | refine → add b1(375), b2(414) |
| 2 | b1 : 375, b2 : 414 | refine b1 → add c1(418), c2(410) |
| 3 | c2 : 410, b2 : 414, c1 : 418 | refine c2 → add d3(434), d4(468) |
| 4 | b2 : 414, c1 : 418, d3 : 434, d4 : 468 | refine b2 → add c3(414), c4(452) |
| 5 | c3 : 414, c1 : 418, d3 : 434, d4 : 468, c4 : 452 | refine c3 → add d5(414), d6(572) |
| 6 | d5 : 414, c1 : 418, d3 : 434, e1 : 436, d4 : 468, c4 : 452, e2 : 472, d6 : 572 | refine d5 → add e1(436), e2(472) |
| 7 | c1 : 418, d3 : 434, e1 : 436, c4 : 452, d4 : 468, e2 : 472, d6 : 572, d1 : 456, d2 : 548 | refine c1 → add d1(456), d2(548) |
| 8 | d3 : 434 is the minimum and a leaf | tour discovered — stop |
Refined (internal) nodes: a1, b1, c2, b2, c3, d5, c1 = 7 ✓ (the 8th pop, d3, is the tour itself — selected, not refined).
2.2 — Optimal tour node and cost → d3,434
At pop #8, d3 (bound 434) is a leaf, and every other open node is ≥ 436. No tour cheaper than 434 can exist anywhere else, so d3 = optimal tour, cost 434.
d5 (414) looks cheaper than d3 (434), but d5 has children in the snapshot — it was refined, so it is not a tour. Only childless nodes can be tours. This is exactly how the paper separates the two.
2.3 — Number of cities → 5
Reconstruct the tour that d3's decisions force. Along the root→d3 path: BD included, CD excluded, AB included.
- Degrees so far: A–1, B–2 (full), C–0, D–1.
- B is done. C can't use CD, so C must connect to A and E; D must connect to E.
- The completion is forced: A–B–D–E–C–A.
That tour visits 5 distinct cities — and a 4-city attempt is impossible (C would be left with degree < 2 once CD is excluded). So the instance has 5 cities.
2.4 — Optimal tour from A → A,B,D,E,C
The forced completion above is the tour: A, B, D, E, C (back to A implied). The paper also accepted the reverse rotation A,C,E,D,B — same cycle, opposite direction.
Interactive view of the tree — step through the seven refinements and the final tour pop:
Amber marks each pop in order (a1, b1, c2, b2, c3, d5, c1); green = d3, the optimal tour at 434.
Tricks & Tips for This Question Family
Answers: 2.1 7 · 2.2 d3,434 · 2.3 5 · 2.4 A,B,D,E,C