Author: Ed Panek
Date: 12:56:29 05/18/01
Go up one level in this thread
On May 18, 2001 at 09:41:14, Robert Hyatt wrote:
>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"...
How long would it take the computer to find one of several thousand "almost
shortest paths"? And _realize_ it found an "almost shortest" route?
what if the map looked like this
Begin- x x x x x End
x x x x x x x x
x x x x xx x x x x
xx xx xxxx x
I bet I could find the only Best path much faster than a computer.
This page took 0.01 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.