Author: Robert Hyatt
Date: 06:41:14 05/18/01
Go up one level in this thread
On May 18, 2001 at 04:17:59, Graham Laight wrote: >On May 17, 2001 at 22:22:48, Robert Hyatt wrote: > >>The traveling salesman problem is well-known. Route a salesman through N >>cities with the shortest total travel time possible. Since the number of >>cities on Earth are limited, and since the number of cities that a traveling >>salesman would actually need to visit is even more limited, it is a finite >>problem. As I said before, I don't care about visiting the moons of >>Jupiter or Mars, nor planets around alpha-centauri, etc. >> >>To the traveling salesman, the problem is finite. Yet the complexity makes it >>intractable even for reasonable numbers of cities. Just try the county seats >>of government for every county or parish in the US. Not with today's computers. >>Not with next year's either. Or next century's. Yet that is smaller than >>chess. > >One thing that fascinates me about the travelling salesman problem is this: why >is it that it is so difficult to calculate with simple programs, and yet... if >you draw a two dimensional map and put the towns on as points, it's easy to draw >out an efficient route between the towns. > >This is an excellent example of an instance where the computers are >uncompetitive because the humans are doing something that seems simple to them - >but they don't actually know what they're doing, so they can't program computers >to do it. > >-g I think you will find it harder to do with that 2D map than you realize. Remember, you are trying to find the _shortest_ path. not one of several thousand "almost shortest"...
This page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.