How are FindShortestTour and the algorithms therewithin implemented internally?
Also: Can I access some form of incremental, in-progress result during evaluation? (e.g.: PCB autorouting)
$\begingroup$
$\endgroup$
1
-
$\begingroup$ here you can see some references mathworld.wolfram.com/TravelingSalesmanProblem.html and you can find a lot of demos demonstrations.wolfram.com/… $\endgroup$– s.s.oCommented Apr 21, 2013 at 21:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
There are many unrelated methods that FindShortestTour can use. Check the documentation undr Details please:
Possible settings for the Method option include "AllTours", "CCA", "Greedy", "GreedyCycle", "IntegerLinearProgramming", "OrOpt", "OrZweig", "RemoveCrossings", "SpaceFillingCurve", "SimulatedAnnealing", and "TwoOpt".
For small numbers of points in the Euclidean space, an "IntegerLinearProgramming" method is used, which is guaranteed to give the shortest tour.
There's more information for some of these under the Options section.
I'd suggest to Google a bit more for the methods that you are interested in to learn how they work, and asking about one specific method. Some of these methods are completely unrelated.
The reason why so many methods exist is that no fast (polynomial time) method is known that is guaranteed to give the shortest tour. For this reason there was a lot of research on coming up with good approximations to the solutions: finding "short enough" tours, if not the shortest one.
If you need the specific details of one of the methods listed here, WRI support is usually pretty good in supplying the appropriate references.
Unfortunately I don't believe you can access a partial solution and continue the computation from there.
Here are my guesses on what the various methods do:
AllTours This one probably enumerates all possible tours and is going to be unusably slow except for only a handful of points.
SpaceFillingCurve This is quite interesting and I'm told it's used in practice. It's supposed to be fast but it'll only give an approximation. See the details.
Greedy Start with a point and take the closest one as the next.
SimulatedAnnealing is a general method for discrete optimization problems. You'll find a lot of accessible literature and tutorials on it (check Wikipedia for a start)
"CCA" According to the docs, this is "Convex hull, Cheapest insertion and Angle selection". The name gives hints, but I'm not familiar with it.
answered Apr 21, 2013 at 21:23
-
2$\begingroup$ Strangely, the method part isn't there any more in 10.0's doc... $\endgroup$– SilviaCommented Nov 22, 2014 at 19:06
-
$\begingroup$ @Silvia Here's the link to the old docs. I wonder if the algorithms used by FindShortestTour have changed in v10. $\endgroup$– SzabolcsCommented Nov 22, 2014 at 19:18
-
$\begingroup$ Ah thank you! I just found that in v10.0 some of the methods are prompted in auto-completion. I should keep my v9.0 longer... $\endgroup$– SilviaCommented Nov 22, 2014 at 19:31
-
$\begingroup$ @Silvia: You can also use an invalid method and the error message will list the available methods. But yes, the documentation should describe them as did previously... maybe is not complete yet. $\endgroup$ Commented Mar 4, 2015 at 20:14
