The Travelling Salesman Problem

What is it?

Let's say you want to visit all the cities in England, what is the shortest way of travelling to all the cities?

The Graph Theory Definition

TSP (The Travelling Salesman Problem): An algorithm used to find the shortest cycle that visits every vertex in a network before returning to the starting node.

It is important to note that this is different from the Route Inspection / Chinese Postman problem, because route inspection is used to find the shortest way of visiting all the arcs/edges, not the nodes (like in the TSP).

The two types of problem

There are two types of problem: The Classical & The Practical.

• Classical: Each vertex must be visited exactly once before returning to the starting node.
• Practical: Each vertex must be visited at least once before returning to the starting node.

In order to make both of these problems the same, we need to construct a complete network of least distances.

A complete network of least distances: A graph, often represented as a table, that shows the shortest distance between every node¹

You will do this by inspection, so there is no need to use Floyd's Algorithm to solve this in your exam.

The Algorithm

Something that it is key to understand, is that there is no perfect algorithm that'll solve this problem.

Instead, what we are going to do, is find a Lower Bound and an Upper Bound. You should remember these terms from GCSE and your frequency tables. You would have a class like: 13 ≤ x < 25. That would have a lower bound of 13, and an upper bound of 25. So we know that the value of x could be anything in between these two numbers.

Upper Bound: The biggest number a variable could take

Lower Bound: The smallest number a variable could take

What we need to find is the Lowest Upper Bound and the highest Lower Bound. You might be confused by this, but what we are trying to do is close in on the smallest number of possible values. Let's say for 13 ≤ x < 25. There are 12 values it could take. So, if we wanted to guess what value x was, it would be a "1 in 12" chance. But if we were to have the bounds: 20 ≤ x < 22, we only have 2 values it could be, so we have a "1 in 2" chance of guessing it.

The Upper Bound

There are two methods to find an upper bound:

• The Minimum Spanning Tree Method
• The Nearest Neighbour Algorithm

MST (Minimum Spanning Tree): A subgraph that has no cycles and contains every vertex

The MST Method

1. Use Krushkal's or Prim's Algorithm to find the MST
2. Double the arcs
3. Seek shortcuts

The Nearest Neighbour Algorithm²

1. Select a starting node
2. Choose the smallest arc that is connected to a node that hasn't been visited yet
3. From that node, and only that node, select an arc

This algorithm is virtually the same as Prim's algorithm, but in Prim's you always look back at every Arc you have visited in the past, whereas in NN you only focus on the node you are currently visiting.

The Lowest Bound

There is one algorithm for the Lowest Bound and it has a very fancy name:

• The Lowest Bound Algorithm

This algorithm is all about finding a Residual Minimum Spanning Tree

RMST (Residual Minimum Spanning Tree): An MST of a subgraph with one vertex missing

The Lowest Bound Algorithm

1. Choose a starting node, note down its two smallest arcs
2. Delete said node from the graph and all its arcs
3. Find the MST from this new subgraph
4. Add back the starting node, with only the two shortest nodes

Extra notes

1. Questions relating to this can be found on Page 103 / Exercise 5A in the Edexcel D1 Textbook
2. An implementation of the NN Algorithm can be found here

Further Reading

• A good link for some questions + ans: PMT

A quick note: This is not intended to teach you, it is instead intended to be a quick refresher to make sure you understand what you are doing. I needed to write these so that I had a database of ways to differentiate between the different types of problem.