Further Maths Travelling salesman problem Practice Questions

Start at $A$ and repeatedly go to the nearest unvisited vertex

At each stage the algorithm takes the shortest arc to a vertex that has not yet been visited, and finally returns to $A$.

Add the lengths of the arcs used, including the return to $A$

The tour uses the arcs AB,\;BE,\;ED,\;DC,\;CA.

State the upper bound

The tour A\to B\to E\to D\to C\to A has length $248$, so the optimal tour is no longer than $248$.

List the arcs joined to the deleted vertex $E$

Only the arcs at $E$ matter once the residual minimum spanning tree has been found.

Select the two shortest arcs at $E$

A tour uses exactly two arcs at $E$, so the two shortest arcs give the smallest possible contribution.

Select the pair of arcs that must be added back

These two arcs are added to the weight of the residual minimum spanning tree to give the lower bound.

List the arcs joined to the deleted vertex $D$

Only the arcs at $D$ matter once the residual minimum spanning tree has been found.

Select the two shortest arcs at $D$

A tour uses exactly two arcs at $D$, so the two shortest arcs give the smallest possible contribution.

Note that all the distances in this network are different

With no two arcs of equal length, the nearest unvisited vertex is always unique, so the algorithm has a single well-defined output.

Recall that the nearest-neighbour algorithm gives an UPPER bound

The nearest-neighbour algorithm produces a genuine tour, and the optimal tour cannot be longer than a tour we have actually found.

Recall that deleting a vertex gives a LOWER bound

Removing a vertex from any tour leaves a path through the other vertices, which is a spanning tree of them, so it is at least as long as the minimum spanning tree.

Select the pair of arcs that must be added back

These two arcs are added to the weight of the residual minimum spanning tree to give the lower bound.

Find the least distance from $B$ to $D$

There is no direct arc from $B$ to $D$, so the least distance is the length of the shortest route, B\to A\to D.

Enter the least distance $BD=32$ in the table of least distances

The shortest route B\to A\to D has length $32$.

Find the least distance from $B$ to $E$

There is no direct arc from $B$ to $E$, so the least distance is the length of the shortest route, B\to C\to E.

Enter the least distance $BE=30$ in the table of least distances

The shortest route B\to C\to E has length $30$.

Find the least distance from $C$ to $D$

There is no direct arc from $C$ to $D$, so the least distance is the length of the shortest route, C\to A\to D.

Enter the least distance $CD=39$ in the table of least distances

The shortest route C\to A\to D has length $39$.

Find the least distance from $D$ to $F$

There is no direct arc from $D$ to $F$, so the least distance is the length of the shortest route, D\to A\to F.

Enter the least distance $DF=59$ in the table of least distances

The shortest route D\to A\to F has length $59$.

Note why the table of least distances is needed

In the practical problem the salesman may pass through a vertex more than once, so the relevant distance is the shortest route.

State the least distance from $B$ to $D$

The shortest route from $B$ to $D$ is B\to A\to D, of length $32$, and this is the entry that goes in the table of least distances.

Find the least distance from $A$ to $E$

There is no direct arc from $A$ to $E$, so the least distance is the length of the shortest route, A\to B\to E.

Enter the least distance $AE=37$ in the table of least distances

The shortest route A\to B\to E has length $37$.

Find the least distance from $B$ to $D$

There is no direct arc from $B$ to $D$, so the least distance is the length of the shortest route, B\to C\to D.

Enter the least distance $BD=52$ in the table of least distances

The shortest route B\to C\to D has length $52$.

Find the least distance from $C$ to $E$

There is no direct arc from $C$ to $E$, so the least distance is the length of the shortest route, C\to B\to E.

Enter the least distance $CE=32$ in the table of least distances

The shortest route C\to B\to E has length $32$.

Delete vertex $E$ and every arc joined to it

The lower bound is built from the network on the other $5$ vertices.

List the arcs of the remaining network in ascending order

A minimum spanning tree for these $5$ vertices is now needed.

Build the minimum spanning tree of the remaining network

Each arc chosen is the shortest arc joining the tree built so far to a vertex not yet in it.

Add the lengths of the arcs of the residual tree

The residual minimum spanning tree has total weight $122$.

Add back the two shortest arcs from $E$

In any tour, vertex $E$ is joined to exactly two other vertices, so at least the two shortest arcs at $E$ must be used.

Note that all the distances in this network are different

With no two arcs of equal length, the nearest unvisited vertex is always unique, so the algorithm has a single well-defined output.

Recall that the nearest-neighbour algorithm gives an UPPER bound

The nearest-neighbour algorithm produces a genuine tour, and the optimal tour cannot be longer than a tour we have actually found.

Recall that deleting a vertex gives a LOWER bound

Removing a vertex from any tour leaves a path through the other vertices, which is a spanning tree of them, so it is at least as long as the minimum spanning tree.

Add the two shortest arcs to the weight of the residual tree

Deleting $E$ gives a lower bound of $172$ for the length of the optimal tour.