[EM] Traveling Salesman

[Eric Gorr]

At 7:10 PM -0400 8/22/03, John B. Hodges wrote:
>I am not a computer-science major, but I have heard of the 
>"traveling salesman" problem and how it is computationally very 
>expensive to guarantee finding the ideal solution, to the point of 
>being practically impossible for large numbers of cities.

Off-topic, but an interesting one nonetheless.

This class of problem in computer science is what is known as NP 
Complete (NP = non-polynomial) - the traveling salesman problem is 
the most common example of a type of problem in this area.

It is, in fact, trivial to write a program to solve the traveling 
salesman problem. The word 'impossible' generally gets improperly 
applied because it will take several billion years to come up with 
the correct answer for a large enough number of cities. 
'Unreasonable' would be a better word.

>But, I have also heard, there are simple algorithms that will 
>reliably get you "close" to the ideal solution: for example, start 
>where you are, and go to the nearest city you have not yet visited; 
>repeat until you have visited all cities.

Reliably, yes...guarantee no...could the answer still be quite 
wrong...certainly possible.

-- 
== Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 ===
"Therefore the considerations of the intelligent always include both
benefit and harm." - Sun Tzu
== Insults, like violence, are the last refuge of the incompetent... ===