Author: Graham Laight
Date: 01:17:59 05/18/01
Go up one level in this thread
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
This page took 0 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.