Author: Dann Corbit
Date: 16:03:12 05/18/01
Go up one level in this thread
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.
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.