Author: Ed Panek
Date: 22:18:02 05/18/01
Go up one level in this thread
On May 18, 2001 at 19:03:12, Dann Corbit wrote:
>On May 18, 2001 at 15:56:29, Ed Panek wrote:
>[snip]
>>>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.
>
>The computer might never get it right, and it might solve it in a microsecond.
>TSP is solved _approximately_ without much trouble by computers. In fact, you
>have probably used trip planning software that does so. One solution is to
>subdivide the area into bands, solve the bands, and connect the solutions. Then
>you can use simulated annealing or something of that nature to polish it a bit.
>
>But to find the optimal solution with a tangled web of cities is a very
>difficult problem in combinatorics. It seems to me that it has been *proven* NP
>hard, (IIRC). At any rate, there is no solution in P right now for TSP.
>
>It is (of course) possible for a TSP problem to be solved quickly and correctly.
> But there is no way to know if that will happen by accident or not.
>
>Lots of algorithms are like that. We know how to get a pretty good answer
>quickly most of the time. But once in a while, a real stinker comes along that
>make the O(f(n)) important. [Interesting Example: Jon Bentley's articles in
>UNIX Review on "Enginerring a Sort Function" {or something like that, I don't
>recall the exact title...}, where qsort() had been behaving nicely for ages --
>solving large problems in a jiffy, and suddenly it just failed to produce
>results, despite running for as long as could possibly be allowed.]
>
>Quick sort is the algorith that was used for that qsort() interface {not
>required, by the way -- in fact, Plauger's implementation uses Introspective
>Sort instead} and the average case f(n*log(n)) gave way to the O(n^2) behavior
>that happens when qsort goes perverse. An excellent bit of writing and highly
>recommended, along with everything else he writes.
Wow,Speak of the Devil .. I remember Doc Bentley when I was at to West Point.
He came in as a visiting faculty member and gave several excellent talks. They
also had a picture of him in G hall at Carnegie Mellon University in Pittsburgh
if I recall. Really sharp guy.
Cheers,
Ed
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.