Imagine a salesman must start in Paris, and fly to 4 cities (
London, Berlin, Rome, and
Athens).
What is the shortest route he can take?
This is a famous
problem which cannot be solved efficiently.
The
straightforward method is to
examine all possible route, calculate the length of each trip,
and choose the
smallest. Here is the list of all of the 24 possible trips (he
always starts and
finishes in Paris):
P-L-B-R-A-P P-L-B-A-R-P P-L-R-A-B-P P-L-R-B-A-P P-L-A-R-B-P P-L-A-B-R-P |
P-B-L-R-A-P P-B-L-A-R-P P-B-A-L-R-P P-B-A-R-L-P P-B-R-L-A-P P-B-R-A-L-P |
P-R-A-L-B-P P-R-A-B-L-P P-R-B-L-A-P P-R-B-A-L-P P-R-L-B-A-P P-R-L-A-B-P |
P-A-B-L-R-P P-A-B-R-L-P P-A-R-L-B-P P-A-R-B-L-P P-A-L-R-B-P P-A-L-B-R-P |
Why are there 24 possibilities? There are 4 choices for the
first city, then 3
choices for the next,
then 2 choices for the next, then 1 choice left
for the last city.
(The P's at beginning and end are fixed.)
So the number of possible trips is 4*3*2*1 = 4! (factorial) =
24
If the salesmen must visit 10 cities, there are 10! = 3,628,800 - over 3 million trips to examine.
The number of trips grows very fast as the number of cities grows.
The efficiency of the Travelling Salesman algorithm is O( N ! )
The Travelling Salesman problem is an example of a problem
desperately in need of a
more efficient algorithm.
Although some clever programs have been
written for this
problem, the programs only guarantee
to get a good result, not
necessarily the best
result. This remains an unsolved problem in Computer Science.