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... === ---- Election-methods mailing list - see http://electorama.com/em for list info
