Author: David Blackman
Date: 03:01:36 05/19/01
Go up one level in this thread
On May 18, 2001 at 04:17:59, Graham Laight wrote: >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 really easy for a human to draw a route that is ok. As in maybe within 20% or so of ideal. For a lot of cases that is good enough in practice. But it is even easier for a computer to do this than a human. A few years back i wrote a program that could do the 2D euclidean case for a million points in a few seconds at about this standard. (In fact i suspect it usually got within 10%, but it's hard to be sure because i couldn't get a proveably best solution to compare it to in most of the test cases.) When it gets hard, is when you need the proveably best solution. Humans basically can't do this at all for more than about 50 points, and have extreme difficulty for more than about 15. Computers could do several hundred points when i last looked many years ago. No doubt they are even better now. >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. No it's not. You just haven't seen the best programs in action.
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.