MathOnWeb.com


The Travelling Salesman Problem

North America

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:

These numbers must be multiplied together to give the total number of orderings:

20 factorial

= 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:

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!