“Travelling salesman” notes and video

The travelling salesman problem (TSP) is: find the shortest tour, returning to your start, which visits each vertex at least once.

CLASSICAL AND PRACTICAL

Anyway, that’s what the book calls the “practical travelling salesman problem”. The book calls the problem of finding a shortest tour visiting each vertex exactly once the “classical travelling salesman problem”.

All you need to know for now about the “classical travelling salesman problem” is how to answer the question: what is the difference between the “classical travelling salesman problem” and the “practical travelling salesman problem”. All our algorithms deal with the practical TSP.

Complete Table of Least Distances

Because we’re dealing with the practical TSP, we’re interested only in the shortest route between any two vertices, and we aren’t bothered if that route means going through a vertex we may already have visited.

Instead of working with the original graph, we work with a complete table of least distances, which shows the shortest distances between vertices (even if they’re indirect, and even if that means ignoring direct routes which are longer).

Upper bounds and lower bounds

As with Bin-Packing, no algorithm guarantees you an exact answer for the TSP (except a checking-every-route one which is impossibly long-winded for even a moderate number of vertices, e.g. for just 20 vertices it means checking 1.2×1018 possibilities, several years’ computing time on a fast modern computer).

The algorithms give you upper bounds and lower bounds. The best upper bound is the smallest one. The best lower bound is the biggest one.

Nearest neighbour

Nearest neighbour says: 1. Pick a vertex to start. (For A level, the question will tell you which one to pick). 2. Work from there, step by step, at each step adding the “nearest neighbour” vertex to your last vertex. 3. Finally, connect back to start.

It’s like Prim, except that at each stage you choose the “nearest neighbour” route from your last vertex, rather than from any vertex you’ve reached so far.

Problem with nearest neighbour is that it may give you a really long distance to connect back from the last vertex to the start. Still, it gives you an upper bound.

MST×2

MST×2 gives you, not a better upper bound necessarily, but a quicker-to-calculate upper bound.

Find a minimum spanning tree (MST), using Kruskal or Prim. Then going out along that MST, and getting back to the start by retracing your steps from each “branch”, is a tour and reaches all vertices.

So MST×2 gives an upper bound.

MST×2 with shortcuts

MST×2 gives an upper bound, but maybe a rubbish one. Often you can improve on it just by a bit of human intelligence. For example, choose a start point on your MST and look at the most distant branches. There may be “shortcuts”, routes back to the start from the ends of those most distant branches, which are quicker than retracing your step through the whole MST.

MST and RMST

Just MST gives you a lower bound, because the MST tells you the shortest total distance to visit all vertices. Pretty much always the MST won’t be a tour, but any tour visiting all vertices must be at least as long.

That is a lower bound. But it is so rubbish that the textbook doesn’t even mention it.

Instead it mentions RMST, Residual Minimum Spanning Tree, which is the MST method improved by a bit of human intelligence.

Take out any vertex. (For A level, the question will tell you which one to take out). Find an MST for all the remaining vertices. Then find the two shortest routes which connect that taken-out vertex back in with the MST for those remaining vertices.

That is a lower bound.

If the route you get by doing RMST is a Hamiltonian cycle (meaning: it’s a tour which goes through each vertex exactly once), then that route is not just a lower bound. It’s an exact answer. But usually the route you get by doing RMST is not a Hamiltonian cycle. It gives you not an exact answer but a lower bound.

The video is good but concentrates much more on the “classical” TSP. Also, it’s not quite right about trial-and-improvement. Unintelligent trial-and-improvement, trying absolutely every possibility, becomes unworkable even with six vertices, but intelligent trial-and-improvement is really quite good for fairly small numbers of vertices.