problem. Exact methods have been given which apply to 5000 cities or less and
one has even successfully dealt with a particular problem of 33,810 cities, though
the computer power required in this case was colossal. Non-exact methods
produce routes which are within range of the optimum with a specified
probability. Methods of this type have the advantage of being able to handle
problems with millions of cities.
Computational complexity
Looking at the problem from a computer’s point of view, let’s just think about
the time it might take to find a solution. Simply listing all possible routes is a
worst case scenario. James has discovered that this brute force method for 13
cities would take almost a century to complete. If we threw in an extra 2 cities
the time would go up to over 20,000 years!
Of course these estimates will depend on the actual computer used, but for n
cities the time taken rises in line with n factorial (the number you get by
multiplying together all whole numbers from 1 to n). We calculated 3.1 × 10^9
routes for 13 cities. Deciding whether each route is the shortest yet found
becomes a problem of factorial time – and it will be a long time.
Other methods are available for attacking the problem in which the time for n
cities rises with 2n (2 multiplied by itself n times) so for 13 cities this would
involve the order of 8192 decisions (8 times more than for 10 cities). A method
with this complexity is called an exponential time algorithm. The holy grail of
these ‘combinatorial optimization problems’ is to find an algorithm which
depends not on the nth power of 2, but on a fixed power of n. The smaller the
power the better; for example, if the algorithm varied according to n2 then, in
the case of 13 cities, this would amount to only 169 decisions – less than twice
the time taken for 10 cities. A method of this ‘complexity’ is said to be conducted
in polynomial time – problems solved this way are ‘quick problems’ and could
take 3 minutes, rather than centuries.
The class of problems that can be solved by a computer in polynomial time is
denoted by P. We don’t know if the travelling salesperson problem is one of
these. No one has come up with a polynomial time algorithm for it but nor have
they been able to show that none exists.
A wider class denoted by NP consists of problems whose solutions can be