Further Maths - Travelling Salesperson Problem

Summary

The Travelling Salesperson Problem, or TSP, is a pretty famous NP-complete problem about visiting each vertex of a graph and returning to the start in the shortest distance possible. Because it’s NP-complete, there isn’t a known polynomial-time algorithm (such as there is in [[Further Maths - Prim’s Algorithm]]^A and [[Further Maths - Kruskal’s Algorithm]]^A for minimum spanning trees).

There are two variants of the TSP considered at A-level decision maths:

• The classical problem, where you must visit every vertex exactly once.
• The practical problem, where you must visit every vertex at least once.

The names “classical” and “practical” make sense here – in the real, practical world, you’re going to be able to visit verticies (e.g. towns) that you’ve already been to.

Because there is isn’t a fast algorithm for the optimal solution, A-level decision maths chooses to describe three algorithms for upper and lower bounds:

• Finding a minimum spanning tree and doubling it for an upper bound (practical version only).
• Using the nearest neighbour algorithm for an upper bound (practical or classical version).
• Finding a “residual minimum spanning tree” and including the two shortest verticies for a lower bound (classical version only).

A mnemonic to remember in which situations you use which is that “residual” has connotations of removing and lowering, and so is for the lower bound, whereas the other two don’t.

Upper bound using a minimum spanning tree

• Find a minimum spanning tree for the network.
• Double the minimum spanning tree.
• Find shortcuts by drawing the graph and seeing which unused arcs will let you skip parts of the doubled minimum spanning tree.

This method only works on the practical travelling salesman problem.

In summary: You can use the minimum spanning tree method to find an upper bound for the practical version of the TSP. If you need to find an upper bound for the classical version of the TSP, then you should use the nearest neighbour algorithm.

Upper bound using the nearest neighbour algorithm

• Select a vertex as a starting point.
• Repeatedly pick the closest vertex to the current vertex until all verticies have been selected.
• Once at the final vertex, pick the shortest route back to the start vertex.

You can run this algorithm on each vertex on the graph and pick the one with the smallest length. There’s a nice way of doing this directly on a distance matrix in a way that is the same as [[Further Maths - Prim’s Algorithm]]^A but where you only consider values in the most recently labelled column.

What is the advantage of this over finding an upper bound using a minimum spanning tree? For large networks, it can be time-consuming to find the minimum spanning tree and then identifying shortcuts. This method also works for both the practical and classical problems, whereas the minimum spanning tree method only works for the practical problem.

In summary: You can use the nearest neighbour algorithm to find an upper bound for the classical or practical TSP. This is the method where you need to add on the shortest route back to the start vertex.

Lower bound using a residual minimum spanning tree

• Remove a vertex from the network.
• Find a residual minimum spanning tree by applying [[Further Maths - Prim’s Algorithm]]^A or [[Further Maths - Kruskal’s Algorithm]]^A to the modified network.
• Reinclude the deleted vertex by adding the two shortest distinct arcs.

Again, you can run this algorithm on each vertex in the network and pick the one with the greatest length for the best lower bound. You can also do this directly on a distance matrix by crossing out the row and column of the vertex you’re deleting.

This algorithm is only applicable to the classical travelling salesperson problem (where you must visit each vertex exactly once). If you’re solving the practical problem, then you must apply the algorithm to a table of least distances.

If this technique gives a Hamiltonian cycle, then it is the optimal solution. Why? Who knows. That’s just what the textbook says. But it doesn’t give a Hamiltonian cycle in general, and so to adapt it into an actual solution, it is necessary to repeat arcs.

In summary: You can use the residual minimum spanning tree method to find a lower bound for the classical version of the TSP. If you need to find a lower bound for the practical version, you have to construct a table of least distances. This is the method where you need to add the two shortest arcs back on.

Mnemonic

I was really struggling to remember this so I wrote a very stupid poem that I could memorise.

If you're being practical, up and MST
Then double and find shortcuts
And bounded you will be

But to up a classical network
--or a practical; it will suit
Nearest neighbour, then find the shortest route

Finally, low and behold
Classical only: residually patrolled
Though ensure two tiny arcs are told

Flashcards

2021-11-26

2021-11-27

2012-12-07

2022-03-07

2022-03-14

2022-03-16

2022-04-14