The optimal route for Santa Claus: an extremely hard problem

Suppose Santa Claus asked you to plan
his route so that the sleigh will travel
the shortest possible distance while
visiting every home. This is an example
of an extremely hard problem known in
general as the travelling salesman
problem. You need to know the distance
between each pair of locations, and you
can solve the problem if you can check
every possible route. If there are
10 locations, there are
10*9*8*7*6*5*4*3*2*1=3,628,800
possible routes. (The product of
all the numbers from 1 up to n
is known as n-factorial, written
as n!. This number determines the
number of different orderings of
n objects, which is the same sa
the number of different routes between
the locations.)
The problem is that n! is very large.
The number of locations for Santa
to visit is itself a large number,
so the factorial of that number
is unimaginably large.
Checking every possible route
would take too long — “that’s
impossible, even for a computer”
(in the words of the skeptical
rebel pilot in the original “Star
Wars.”)
See more about this problem at

https://www.wired.com/2013/01/traveling-salesman-problem/

……………..
–Douglas Downing
You are welcome to write your comments on the facebook page at

https://www.facebook.com/DouglasADowningSPU/?ref=profile
This blog is part of the

Seattle Pacific University Political Economy blog group
(click here for index).

Click here for the index of topics for the blog
Twitter:
https://twitter.com/douglasdowning
New items are posted about twice per week.