Author: David Blackman
Date: 03:09:56 05/19/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. With this particular instance, there are programs that would find the optimal solution (and prove it optimal) in milliseconds using plain old fashioned branch and bound. This kind of setup makes branch and bound really fast because most of the bad lines can be cut off almost immediately. >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 has been proven NP complete. (Which means it is NP hard, among other things.) It is not clear if some of the current best algorithms are in P or not. It certainly hasn't been proven that they are in P, and it would surprise most theoreticians if they are, but it really isn't clear either way. >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.
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.