The Travelling Salesman Problem
You are a salesman and you must visit 20 cities spread across North America. You must visit
each city once and only once. The question is this: In what order should you visit them
to minimize the total distance that you have to travel?
The answer is that there is no simple answer. Reasonable people will make a reasonable
choice and accept a reasonably short path.
However there is only one way to find the absolute shortest path, and that is to write
down every possible ordering of cities, compute the distance for each of those orderings,
and pick the shortest one.
How many orderings are there? They can be counted this way:
These numbers must be multiplied together to give the total number of orderings:
- For the first city to visit you have 20 choices.
- For the second city to visit you then have only 19 choices (because you can't visit the first city again).
- For the third city you have 18 choices,
- and so on . . .
- For the last city you have 1 choice
This number is so big that if your computer could check 1 million orderings every second
it would still take 77,000 years to check them all! Thus even though we know how to solve
the Travelling Salesman Problem we still can't do it.
= 2,432,902,008,176,640,000 possible orderings
The Factorial (!) Notation:
To write down a positive integer like 20 followed by an exclamation mark means to multiply
all the numbers from 1 to 20 together.
We say it like this: "twenty factorial".
Look for the factorial function on your calculator. Here are more examples:
- 2! = (2)(1) = 2
- 5! = (5)(4)(3)(2)(1) = 120
- 69!=1.71x1098 (the biggest number my calculator can display)
Click here to return to the Math Entertainment page.