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?
If the cities lie in a straight line or in a ring then the answer is obvious – go in a straight line or go around the ring. But often the cities are located such that there is no obvious answer.
Then there is only one way to find the shortest path and that is to write down every possible ordering of the cities, calculate the distance for each of those orderings, and pick the shortest one.
Another word for ordering is permutation. How many orderings of the cities or permutations are there? They can be counted this way:
- 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
These numbers must be multiplied together to give the total number of orderings:
= 2,432,902,008,176,640,000 possible orderings
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.
Factorial
The type of multiplication described above occurs so often in counting permutations that we give it a name – factorial.
Definition: the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.
Thus the above multiplication is written as 20! and is spoken as "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
- 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3628800
- 69! = 1.71x1098 (the biggest number my calculator can display)
The reason that the number n is a non-negative integer is that we use it for
counting permutations or arrangements of whole objects.
And since we could have zero objects (e.g. no cities to visit) we also define 0! It doesn't fit the pattern
but it makes sense to define it to equal 1.
If you would like to leave a comment or ask a question please send me an email!