The travelling salesman

Marianne Freiberger

On 20th November 2012 Plus hosted the first UK screening of Travelling Salesman, an intellectual thriller imagining the consequences of solving the P vs NP problem, at the Centre for Mathematical Sciences in Cambridge. Here you can find out what this problem is all about.

Travelling Salesman poster

We're hosting another screening of the film on 14 March 2013, Pi Day, as part of the Cambridge Science Festival

Get cash from the cash point, go to the supermarket, pick up kids from school and prescription from doctor. In what order should you do these things so that the distance you've got to drive is as short as possible? Not a particularly exciting problem, you might think, but it's one that fascinates mathematicians. That's because in general it's very hard to solve and opens the door on one of the trickiest unanswered questions in mathematics.

The problem is called the travelling salesman problem and the general form goes like this: you've got a number of places to visit, you're given the distances between them, and you have to work out the shortest route that visits every place exactly once and returns to where you started. If it's a small number of places, you can find the answer quite easily simply by looking at all the possible routes. As the number of places grows, this becomes incredibly tedious. Is there a better method for doing this, an algorithm, that can give you an answer in a reasonable amount of time even if the number of places is huge?

Of course the answer depends on what you mean by reasonable. The time it takes an algorithm to conclude its task is proportional to the number of steps it has to execute. Perhaps you can find an algorithm that takes $n^2$ steps to solve the problem for $n$ places. That would mean 100 steps if the problem involves visiting ten places and 400 steps if it involves 20 places. That may seem bad but imagine the algorithm takes $2^ n$ steps to solve the problem for $n$ places. Then ten places would require 1,024 steps and 20 places more than a million. This is rapidly exploding exponential growth.


The functions 2n (black), n3 (red) and n2 plotted against n. You can see that 2n grows fastest for larger n.

Mathematicians have a clear idea of what they mean by a "reasonable" amount of time in this context. Expressions involving powers of $n$, such as $n^2$, $n^3$ or $n^4$ are called polynomials in $n$. An algorithm is deemed efficient if the number of steps it requires grows with the number $n$ in the same way, proportionally, as some polynomial in $n$ grows with $n$. That can still give you pretty rapid growth, especially if the power of $n$ in the polynomial is large, but at least it’s not exponential. An algorithm which fits this bill is called a polynomial-time algorithm.

So is there a polynomial-time algorithm for solving the travelling salesman problem? The answer is that nobody knows. Nobody has managed to find one yet, and nobody has been able to prove that there isn’t one either. So let’s make the problem a little easier: rather than asking for the shortest route, let’s ask if there is a route visiting all the places on your list that’s shorter than some number $D$ we’ve previously specified. This is called the decision version of the travelling salesman problem because it’s got a yes/no answer. Unfortunately it’s not known if there’s a polynomial-time algorithm to solve the decision version either, but at least there’s one bit of good news. If someone were to give you an answer to the problem, a route they claim is shorter than $D$, then it’s really easy to check whether it’s true.

The collection of all decision problems for which a possible answer can be verified easily (in the sense that there’s a polynomial-time algorithms for checking the answer) has a name: it’s called the NP class. Another problem in that class is how to factorise large numbers into primes, for example working out that

  \[ 44,926,453 = 11^2 \times 13^5. \]    

Once you know the prime factors of a number it’s easy to check that they are correct, you only need to multiply, but nobody knows of any polynomial-time algorithms to find these factors in the first place.

This leads us to the big question: are there any polynomial-time algorithms for problems in the NP class that simply haven't been discovered yet? The question is known as the P versus NP problem because the class of problems that can be solved in polynomial time is called P. P versus NP is one of the hardest open problems in maths. Anyone who manages to answer it will win $1 million from the Clay Mathematics Institute (see How maths can make you rich and famous). Not everyone agrees, but most mathematicians seem to think that P is not equal to NP: this would mean that NP problems really are very difficult, they cannot be solved in polynomial time.

Lock and key

Answers to NP problems can be used as the key to encrypted messages.

And there's another twist to the story: any problem in the NP class can actually be reduced to the decision version of the travelling salesman problem. This means that any algorithm that solves the decision travelling salesman problem can be translated into one that solves all other problems in the NP class. So imagine you find a polynomial-time algorithm for the decision travelling salesman problem. This would then mean that every problem in NP could be solved in polynomial time, you would have proved that P=NP and could go and collect your $1 million. (And the same would be true if you found such an algorithm for the harder, general version of the travelling salesman problem.)

But there are other implications too. Problems from the NP class are often used in cryptography, for example in the RSA system that's used to make internet transactions secure. Essentially, the answer to an NP problem (say the prime factors of a large number) is used as the key you need to decode a message. The fact that there are no known algorithms to solve NP problems quickly means that the key is very hard to crack. (See Safety in numbers for more.)

So imagine you did manage to find an efficient algorithm to solve the travelling salesman problem. You'd get your million dollars, a key to the world's most secret codes and your life would probably no longer be safe. Someone should make a movie about this...


A new 'Shrink' algorythm resolves the TSP problem at a rate of n^3*7E-5 secs. 100 nodes take 2 seconds on a 1.8Ghz PC running on a QPC2 emulator with a procedural basic. Timings were done by a Professor of mathematics at Delaware State university. The code can surely be optimised, and produces a 94% accurate result as things stand, but this will be improved on. The maths are very simple, but the logic is quite complex. The program was published by the English 'Quanta' QL users group, and is available for programmers to work on.

TSP solved? I am not sure!
I believe tha I have found the effective algoritm for the shortest route to take.
I have contacted The Clay Mathematics Institute for how to present my solution.
Dr Lars Hellström, Uppsala, Sweden

Real world gets more complicated than the salesman pitch.

In the real world, the factors influencing the optimal outcome:
* is it faster to do tasks without kids (or persons cared for),
* how much time do you have to complete all tasks,
* is it cheaper to be quick, or take shortest route?

I have no algorithm but these factors affect my decision-making every day to maximise my 24 hours.

1. "Mum" has scientifically reduced the problem to its essence. Never take the kids to the grocery store if efficiency is your first concern. So go there first.
2. Solve as much of the problem once and for all in advance as possible. Never go to an ATM (if that's what a pay point is). Get a Paypal account, move cash into it online, and use the Paypal card instead of cash. Easier, more secure, eliminates one stop on the trip, and gives you a record of what you spent and where, making budgeting simpler (thus reducing another set of math and tracking problems).
3. Change your prescriptions to three-month refills or better, delivered by mail. There -- two trips out of three to the pharmacy, or all of them, eliminated.
4. The Law of Scientific Parsimony absolutely dictates: Never give a problem to a mathematician if a Mum can solve it. This approach has been proven by experience to work for up to whatever number of children are in your family.

And if you really need to pretend this is a math/geography problem: It is not. It's a management question. The first parameter to plug in is the likelihood of the traveling salesman closing a deal, and how big, at each destination. Send him to the likeliest big deals first and hit the marginal ones up with a phone call. Be very wary of trying to apply math to social-interaction questions with small sample sizes.

Glad to be of assistance.