The travelling salesman problem is an optimization
problem. Therefore it is not sufficient to find an arbitrary solution.
Instead, one is interested in the best (or at least a very good) solution.
The travelling salesman problem is quite simple: a travelling salesman has
to visit customers in several towns, exactly one customer in each town. Since
he is interested in not being too long on the road, he wants to take the
shortest tour. He knows the distance between each two towns he wants to visit.
The picture shows two possible tours for an example with five cities. For such
a small example the problem is easy to solve. But examples with 100 or 1000
cities show that a systematic search for a solution is very expensive.
So far, nobody was able to come up with an algorithm for solving the traveling
salesman problem that does not show an exponential growth of run time with
a growing number of cities. There is a strong belief that there is no
algorithm that will not show this behaviour, but no one was able to prove this
(yet). But one was able to prove that the traveling salesman problem is a kind
of prototypical problem for a big class of problems (the famous class NP)
that show this exponential behaviour. This is the reason why many reasearch
groups are interested in the traveling salesman problem, since techniques
developed for this problem can be transfered to other problems of this class.
Follow the links to
