DB4 - Travelling salesperson bounds
Visiting every location once and returning home is a different task from inspecting every road. You will construct travelling salesperson tours, use nearest neighbours for upper bounds and deleted-vertex minimum spanning trees for lower bounds. Comparing the bounds tells you what has been proved about the best tour and what remains uncertain.
Hamiltonian tours and the optimum
Does always travelling to the nearest unvisited town guarantee the shortest round trip? Consider four towns with symmetric distances AB 4, AC 9, AD 5, BC 7, BD 6, CD 11 kilometres. Starting at A, the nearest unvisited choice gives A–B–D–C–A, of length 30. We will test whether that is really best.
Travelling salesperson problem
A Hamiltonian tour visits every node exactly once before returning to its starting node. The travelling salesperson problem asks for a tour of minimum total weight. Write its optimum as . A tour of weight proves ; a lower bound proves .
Returning to the starting node is the one required repeat. A–B–A–C–D–A is a closed walk, but not a Hamiltonian tour: it visits A in the middle. By contrast, route inspection covers arcs and allows repeated nodes. An MST merely connects nodes and need not form a tour at all.
| From/to | A | B | C | D |
|---|---|---|---|---|
| A | — | 4 | 9 | 5 |
| B | 4 | — | 7 | 6 |
| C | 9 | 7 | — | 11 |
| D | 5 | 6 | 11 | — |
This complete symmetric distance network allows travel between any pair of towns. When a road network lacks a direct arc, you may instead form a complete table of shortest road distances, if travel through intermediate towns is allowed. A tour of that distance table visits each listed town once in its ordering; the actual road walk may pass through some towns again. State which interpretation the problem requires. If intermediate visits are forbidden, replacing missing arcs by shortest paths can change the problem.
For a sparse graph a Hamiltonian tour need not exist. Nearest neighbour may reach an unvisited node from which completion or return is impossible. A partial walk is not an upper bound: only a feasible complete tour is.
Key idea
An upper bound comes from an achievable complete tour. A lower bound comes from a limit that every tour must obey. A bound is not automatically the optimum.
Distinguish the two types of evidence with new values.
Nearest-neighbour upper bounds
Choose a starting node. Travel to a nearest unvisited node, repeating until every node has been visited, then return directly to the start. At each step ignore previously visited nodes even if one is nearer. If several eligible nodes tie, either is allowed; record the choice because the eventual totals can differ. When a question specifies a start or tie rule, follow it.
The method is quick, but its locally cheapest choices can leave an expensive final link. Repeat from different starting nodes and try alternatives at ties when useful. The smallest valid tour total is the strongest upper bound obtained, because it gives the lowest known achievable cost. The algorithm is not supplied in the formula booklet.
[DIAGRAM: asset_name: Two nearest-neighbour tours; asset_slug: aqa7367-tsp-tours; caption: Starting at A gives a tour of 30 kilometres, while starting at B gives 27 kilometres; description: Two panels show tours on towns A B C D with arrows indicating order and edge-distance labels. The first is A to B 4, B to D 6, D to C 11, C to A 9, total 30. The second is B to A 4, A to D 5, D to C 11, C to B 7, total 27. Arrows describe the chosen walk, not one-way roads.]
Worked example 1: nearest neighbour from A
Question. Use nearest neighbour starting at A on AB 4, AC 9, AD 5, BC 7, BD 6, CD 11 kilometres. State an upper bound.
Plan. Choose the least distance to an unvisited town at each step, then include the return.
From A choose B: . From B choose D rather than C: . Only C is unvisited, so go D–C for 11, then return C–A for 9.
Answer. A–B–D–C–A has length , so .
Check. A, B, C and D each occur once before the final A. Summing the reverse tour A–C–D–B–A gives , consistent with symmetry.
Change only the starting node to B. The rule stays the same, but the tour improves.
Worked example 2: nearest neighbour from B
Question. Use nearest neighbour starting at B on AB 4, AC 9, AD 5, BC 7, BD 6, CD 11 kilometres. Compare its bound with 30.
Plan. Rebuild the tour from B, rather than rotating the previously found tour.
From B choose A for 4. From A choose D for 5 rather than C for 9. From D go to the only unvisited town C for 11, then return C–B for 7.
Answer. B–A–D–C–B has length . Hence 27 is a better upper bound: .
Check. Written from A, the same cycle is A–D–C–B–A: . It is different from the 30-kilometre cycle, not just a different starting point on it.
This answers part of the opening puzzle: nearest neighbour from A was not optimal, because a shorter valid tour exists. A different start does not guarantee the optimum either.
Watch out
Wrong: “The bound is .” That omits the return to A. Also, an arc leading back to the start is ineligible until every other node has been visited.
Follow the specified start on a fresh complete network.
Deleted-vertex lower bounds
Delete a node and all its incident arcs. Find an MST on the remaining nodes, then add the weights of the two cheapest distinct arcs incident with in the original network. This gives a lower bound, not generally a tour.
Why? Removing and its two incident arcs from any Hamiltonian tour leaves a path through all the other nodes. That path is a spanning tree, so it weighs at least their MST. The two removed tour arcs cost at least the two cheapest available arcs at . Adding these inequalities proves the bound. The cheapest two arcs need not be compatible with an optimal remaining tree to make an actual tour: relaxing that compatibility is precisely why this is a lower bound.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account