Author: Steffen Jakob
Date: 04:12:19 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. It´s also easy to find "an efficient" route with a program e.g. with a genetic algorithm. The problem is to find "the best" route because thats the goal of the travelling salesman problem. Greetings, Steffen. >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.
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.