7.04c, 7.04d - Bounds for the travelling salesperson | OCR A-Level Further Mathematics A

Construct a tour quickly, then judge how much shorter the best tour might be. You will find upper bounds by nearest neighbour, improve feasible routes, calculate lower bounds from reduced minimum spanning trees, and recognise when an incomplete network changes the argument.

Nearest neighbour upper bounds

A greedy tour of five stops costs $30$ . Can you find a better tour and put a limit on how much further improvement is possible, without checking every ordering?

You already know

A Hamiltonian cycle visits every vertex once and returns to the start. A minimum spanning tree connects every vertex without a cycle. Its weight is a minimum connector cost, not the length of a tour.

For this lesson's main example, direct travel costs are given by the complete symmetric table below. Every pair is connected; costs need not be geometric distances.

	$A$	$B$	$C$	$D$	$E$
$A$	–	$5$	$2$	$15$	$9$
$B$	$5$	–	$7$	$5$	$6$
$C$	$2$	$7$	–	$4$	$2$
$D$	$15$	$5$	$4$	–	$15$
$E$	$9$	$6$	$2$	$15$	–

A feasible tour of weight $U$ proves that the minimum tour weight $L$ satisfies $L\le U$ . This is an upper bound: there is an actual tour costing that much. It need not be optimal.

Travelling salesperson problem

On a weighted complete graph, the travelling salesperson problem asks for a least weight cycle through all vertices. Each vertex is visited once before returning to the start. In practical road problems, read whether repeated visits are permitted.

Nearest neighbour makes a local choice at each step. The final return to the starting vertex is compulsory, even if that last arc is expensive.

Nearest neighbour method

Start at the specified vertex. Repeatedly take a least weight arc to an unvisited vertex. After every vertex has been visited, return to the start. If several eligible choices tie, any is allowed unless a tie rule is specified.
In the formula booklet.

The route order is evidence of the method. A final sum on its own hides whether visited vertices were incorrectly reused.

Worked example 1: the greedy tour from A

Question. Apply nearest neighbour to the table, starting at $A$ , to find an upper bound.

Plan. At each current vertex compare only arcs to unvisited vertices, then close the tour.

\begin{aligned} A\to C&:\ 2 &&\text{least from }A\\ C\to E&:\ 2 &&\text{least to an unvisited vertex}\\ E\to B&:\ 6 &&\text{compare }B\text{ and }D\\ B\to D&:\ 5 &&\text{last unvisited vertex}\\ D\to A&:\ 15 &&\text{return to the start}\\ U&=2+2+6+5+15=30 &&\text{sum the closed tour} \end{aligned}

Why this step? From $E$ , the cheap arc back to $C$ is ineligible: $C$ has already been visited.

Answer. $A-C-E-B-D-A$ , giving upper bound $30$ .

Check. All five vertices occur once before the final $A$ , and every arc is available.

Change only the starting vertex. Nearest neighbour is a heuristic, so the bound can change.

Worked example 2: the greedy tour from D

Question. Apply nearest neighbour to the same table, starting at $D$ . Break ties alphabetically.

Plan. Restart with every vertex unvisited except $D$ , and make the same local choices.

\begin{aligned} D\to C&:\ 4 &&\text{least available arc}\\ C\to A&:\ 2 &&\text{tie with }E\text{ broken alphabetically}\\ A\to B&:\ 5 &&\text{least eligible arc}\\ B\to E&:\ 6 &&\text{last unvisited vertex}\\ E\to D&:\ 15 &&\text{close the cycle}\\ U&=4+2+5+6+15=32 &&\text{total cost} \end{aligned}

Why this step? The tie rule determines which valid nearest-neighbour output is requested; it does not guarantee the best tour.

Answer. $D-C-A-B-E-D$ , giving upper bound $32$ . Between $30$ and $32$ , the better upper bound is $30$ .

Check. Changing the start does not change the underlying optimisation problem; either closed tour is feasible.

For a minimisation problem, a smaller feasible cost gives stronger information.

Watch out

Wrong: omit the final return arc, giving $15$ in example 1. Right: include $DA=15$ , so the closed tour costs $30$ . An open path is not a tour.

Test the method on a different complete network.

Improving feasible tours

Nearest neighbour is a starting point: any valid shorter tour improves its upper bound.

One useful check replaces two edges of a tour by two others, reversing the segment between them if necessary. Keep a single cycle through every vertex; two separate cycles are not a tour. Compare the removed and added costs before claiming an improvement.

[DIAGRAM: asset_name: A shorter feasible tour; asset_slug: h245_7_04_tsp_tours; caption: Replacing CE and DA by CD and EA shortens the nearest-neighbour tour from 30 to 26; description: Two panels show the five vertices A B C D E. Left cycle A C E B D A has weights 2 2 6 5 15, total 30. Right cycle A C D B E A has weights 2 4 5 6 9, total 26. Removed edges are dashed clay and replacement edges are solid sage, with the saving 17 minus 13 equals 4.]
Replacing CE and DA by CD and EA shortens the nearest-neighbour tour from 30 to 26

Worked example 3: replacing two expensive connections

Question. Improve the tour $A-C-E-B-D-A$ by replacing $CE$ and $DA$ with $CD$ and $EA$ .

Plan. Check that the replacement gives one tour, then subtract the saving from the old weight.

\begin{aligned} \text{removed cost}&=2+15=17 &&\text{edges }CE,DA\\ \text{added cost}&=4+9=13 &&\text{edges }CD,EA\\ \text{saving}&=17-13=4 &&\text{positive means improvement}\\ U&=30-4=26 &&\text{new feasible cost} \end{aligned}

Why this step? Reversing the old $E-B-D$ section gives $D-B-E$ , which is permitted because the network is undirected.

Answer. $A-C-D-B-E-A$ , giving improved upper bound $26$ .

Check. $2+4+5+6+9=26$ , with every vertex visited once.

Change only the pair of edges being replaced, now using the improved tour. A small further saving still strengthens the bound.

Worked example 4: a second improvement

Question. In $A-C-D-B-E-A$ , replace $AC$ and $BE$ with $AB$ and $CE$ . Find the new tour and cost.

Plan. Reconnect the two open sections into one cycle and compare costs.

\begin{aligned} \text{removed cost}&=2+6=8 &&\text{edges }AC,BE\\ \text{added cost}&=5+2=7 &&\text{edges }AB,CE\\ U&=26-8+7=25 &&\text{reduce by }1 \end{aligned}

Why this step? Reversing $C-D-B$ gives the valid order $B-D-C$ , rather than leaving two disconnected circuits.

Answer. $A-B-D-C-E-A$ , cost $25$ .

Check. $5+5+4+2+9=25$ . This proves $L\le25$ , without yet proving $L=25$ .

A short-cut can also remove a repeated visit from a feasible closed walk. In this table, replacing $C-B-D$ , of cost $7+5=12$ , by $CD=4$ shortens the walk $A-B-C-B-D-E-A$ from $48$ to the tour $A-B-C-D-E-A$ , of cost $40$ . Check that the skipped vertex is still visited elsewhere. A short-cut is guaranteed not to increase distance when the direct distances satisfy the triangle inequality; arbitrary weights need not do so. Here $ED=15$ is greater than $EC+CD=6$ , so replacing $E-C-D$ by $ED$ would increase the cost.

Problem-solving

Compare complete feasible routes. The best upper bound is their least cost; improving a route does not certify optimality.

The next question gives a complete four-vertex network, so every replacement edge exists.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.04c, 7.04d - Bounds for the travelling salesperson

Nearest neighbour upper bounds

Improving feasible tours

Continue this lesson.

Learn faster with Nova