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
How could you formulate the travelling salesperson problem in terms of Hamiltonian cycles?
Finding the shortest Hamiltonian cycle on a graph.
For small graphs, how can you solve the travelling salesperson problem?
Try every Hamiltonian cycle.
What is the nearest neighbour algorithm used for?
Finding a Hamiltonian cycle that can be used as an upper bound for the TSP.
What are the 4 steps of the nearest neighbour algorithm?
- Choose any start vertex
- Go to the nearest vertex that hasn’t been included
- Repeat 2 until all vertices have been included
- Return directly to the start vertex
What would be the first step in using the nearest neighbour algorithm on this distance matrix?
What would be the first step in using the nearest neighbour algorithm on this distance matrix?Crossing out the $A$ row and labelling the $A$ column with a $1$.
What is the next step when trying to use the nearest neighbour algorithm?
What is the next step when trying to use the nearest neighbour algorithm?Crossing out the $E$ row and labelling the $E$ column with a $2$.
How can you use the nearest neighbour algorithm to get an upper bound on a graph?
Use the algorithm starting at each vertex to find a Hamiltonian cycle and pick the lowest one.
What is the key difference between the matrix version of Prim’s algorithm and nearest neighbour algorithm?
In the nearest neighbour algorithm, you only try and find smallest value for the most recently added vertex.
2021-11-27
When using a minimum spanning tree as a lower bound for the TSP, what do you have to do?
Double the minimum spanning tree.
What is the 3 stage technique for finding a lower bound for the TSP?
- Delete one vertex and all edges associated with it.
- Find a minimum spanning tree for this reduced graph.
- Include the two shortest edges that were connected to the deleted vertex.
If the upper and lower bound are the same, what must be true?
The value at the bound is the optimal solution.
2012-12-07
What is triangle inequality for an edge $AB$?
What is the TSP for complete graphs that satisfy the triangle inequality called?
The classical problem.
How can you turn a non-complete graph that doesn’t satisfy the triangle inequality into one that does?
Rewrite it using the shortest distances between all points and jot down which paths you male.
How can you rewrite a graph matrix to show the shortest distances between each point for the TSP?
Draw the graph and do it visually.
2022-03-07
When finding the minimum spanning tree to find a lower bound for the travelling salesperson problem, what two things do you add on at the end?
The two shortest edges from the tree to the node you deleted.
2022-03-14
What is the difference between the classical and practical travelling salesperson problems?
In the classical problem, each vertex must be visited exactly once. In the practical problem, verticies must be visited at least once.
How can you turn the practical travelling salesperson problem into the classical one?
Draw a table of least differences.
You’ve just found an upper bound for the TSP by doubling a minimum spanning tree. How can you use “shortcuts” to improve this lower bound?
Use arcs that you haven’t used yet to reduce the lower bound.
How can you identify shortcuts after finding a lower bound by doubling a minimum spanning tree?
Draw a sketch.
2022-03-16
For which of the classical and practical versions of the TSP are you allowed to use the “double the minimum spanning tree” technique for finding an upper bound?
The practical version.
For which of the classical and practical versions of the TSP are you allowed to use the “find a Hamiltonian cycle using the nearest neighbour algorithm” technique for finding an upper bound?
Either the classical or practical versions.
For which of the classical and practical versions of the TSP are you allowed to use the “find a residual minimum spanning tree and then include the two shortest arcs” technique for finding a lower bound?
The classical version.
Why do you need to complete a table of least distances when finding a lower bound on the practical version of the TSP?
The algorithm for lower bounds using residual spanning trees only works for the classical problem. The table of least distances converts the practical problem into the classical problem.
If the sequence of edges found for the lower bound solution to the classical TSP using the residual spanning tree approach is a Hamiltonian cycle, then what is guaranteed?
It is the optimal solution.
What algorithm do you use for: classical TSP, lower bound?
Residual minimum spanning tree with the two shortest arcs back.
What algorithm do you use for: practical TSP, lower bound?
A table of least distances and then residual minimum spanning tree with the two shortest arcs back.
What algorithm do you use for: practical TSP, upper bound?
Double the minimum spanning tree and find shortcuts, or the nearest neighbour algorithm.
What algorithm do you use for: classical TSP, upper bound?
The nearest neighbour algorithm.
2022-04-14
When giving an interval for the optimal solution to the TSP, how do you know whether to use $>$ or $\ge$?
If the value at the bound corresponds to a Hamiltonian cycle, then use $\ge$.