Quote Originally Posted by Moderator Bob
FredBow,
MS Streets and Trips has an "optimizing" feature -- given enough time (it's a laborious process, seemingly), it will attempt to find the shortest, most efficient route.
Your parenthetical comment there may be more significant than you know. This is actually a famous problem in computer science known as the "travelling salesman problem." It turns out that many problems can be reduced to this one, or problems very similar to it, so an algorithm for solving it has many applications beyond simply finding the shortest route covering a number of cities.

It is widely believed--but not proven--that any program which finds an exact solution to the traveling salesman problem requires what computer scientists call "exponential time."

(That is, the time required to find the solution doubles each time you add some fixed number of cities. If you have a program that takes twice as long to find a solution for 40 cities as it does for 30 (say, 10 minutes compared to 5 minutes), and twice again as long to find a solution for 50 (20 minutes) as it does for 40, and still twice more to find a solution for 60 (40 minutes) as it does for 50, that is a program that takes exponential time. If you had a different program that let you add more cities before you doubled the running time, but was still a fixed number you had to add to double the time--say, 30 cities takes 5 minutes, 50 cities takes 10 minutes, 70 cities takes 20 minutes, 90 cities takes 40 minutes--that's a better program, but it's still one which takes exponential time.)

If any algorithm is found which could solve the travelling salesman problem in less than exponential time, it would have wide-ranging implications in computer science, because it would mean that a large number of problems which are also widely thought to require exponential time would not.

A brute-force approach--calculate the length of every possible route among the cities, and see which is the shortest--becomes impractical even around 20 or so cities. There are better algorithms out there, but all known algorithms which find the exact solution still take exponential time. One case of a 15112-city problem, solved in 2001, required 22.6 years worth of processor time.

Alternately, algorithms are known which give approximate solutions (that is, they can't guarantee that the route produced is the shortest route, but can guarantee that the route produced is no more than, say, 2% longer than the shortest route) in polynomial time (i.e., better than exponential time). The Wikipedia article on the problem notes that these approximation algorithms can find solutions for millions of cities in "a reasonable time."

So yes, finding the shortest route among a number of cities is a seemingly laborious process--and not just seemingly so to you and me, but to the brightest minds in computer science right now. If anyone discovered a process which was less laborious (took less than exponential time), it would be a very significant result in computer science. A proof that any process for finding the solution requires exponential time would also be quite significant.

Sorry for the digression into computer science, but I couldn't resist the opportunity to talk about what I find a fascinating problem!