Re: FindShortestTour Function- Roundtrip & Constructive Heuristic
- To: mathgroup at smc.vnet.net
- Subject: [mg123420] Re: FindShortestTour Function- Roundtrip & Constructive Heuristic
- From: Dana DeLouis <dana01 at me.com>
- Date: Tue, 6 Dec 2011 03:14:32 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
Hi. I may not understand your question, but you can add a "Method" to the calculation. Here are some x,y points: pts=Tuples[Prime[Range@10],2]; And the distance is: FindShortestTour[pts] //First 249.954 A few extra seconds might come up with a better choice: {len1, tour1} = FindShortestTour[pts, Method -> "SimulatedAnnealing"]; {N[len1], len1} {241.8011097365331, 223 + 2*Sqrt[5] + 2*Sqrt[17] + Sqrt[37]} ListLinePlot[pts[[tour1]], Mesh -> All, PlotLabel -> N[len1]] About 1-2 minutes of calculation might find something even better. {len2, tour2} = FindShortestTour[pts, Method -> "IntegerLinearProgramming"]; {N[len2], len2} {240.77995987511002, 231 + 4*Sqrt[2] + Sqrt[17]} ListLinePlot[pts[[tour2]], Mesh -> All, PlotLabel -> N[len2]] Just for fun. The first graph started in the middle, and the second graph started from point 1. If you would like to see the first graph start from 1 also, here is one idea: We'll start from the same point as tour2. start = tour2[[1]] 1 t = RotateLeft[tour1, Position[tour1, start] [[1,1] ] - 1]; ListLinePlot[pts[[t]], Mesh -> All, PlotLabel -> N[len1]] = = = = = = = = = = HTH Dana DeLouis Mac, Ver 8 = = = = = = = = = = On Dec 1, 6:02 am, Chrissi87 <c.cur... at googlemail.com> wrote: > Dear readers, > I have two different questions, both belonging the "FindShortestTour" > Funktion: > > 1. I refer to an example if the "FindShortesTour" Funktion,http://reference.wolfram.com/mathematica/ref/FindShortestTour.html, > you can find it under "Method". > The example: > > d = SparseArray[{{1, 2} -> 1, {2, 1} -> 1, {6, 1} -> 1, {6, 2} -> 1, > {5, 1} -> 1, {1, 5} -> 1, {2, 6} -> 1, {2, 3} -> 10, {3, 2} ->10, {3, > 5} -> 1, {5, 3} -> 1, {3, 4} -> 1, {4, 3} -> 1, {4, 5} -> 15, {4, 1} -> 1, {5, 4} -> 15, {5, 2} -> 1, {1, 4} -> 1, {2, 5} -> 1, {1, 6} -> > > 1}, {6, 6}, Infinity]; > > In: {len, tour} = FindShortestTour[{1, 2, 3, 4, 5, 6}, > DistanceFunction -> (d[[#1, #2]] &)] > > Out: {6,{1,5,3,4,2,6}} > > I would like to know now, if it is possible to change the calculation > in that way, that at the end of the tour the last point will also be > the first point.Lets say I have to start at knot 1 and at the end of > my tasks I have to return to knot 1. So it would be a travelling > salesman problem, but with the shortest tour to visit all knot. I know > there is a travelling salesman function but for me it does not work, > because I want to use the different Algoriths (Or Opt, Creedy...) > which one can use with the "FindShortestTour" Funktion. > > 2. My second question refers to the different Heuristics to calculate > the Shortest Tour. > There is a group (CCA, Creedy...) which is known in the literature as > a Constructive Heruristic and there is a second group (Or Opt, Two > Opt..) which are improvement algorithtms. > When one calculates by hand a problem like this, one has to construct > a tour with a constructive heuristic (most not very good) and then > make it better with an Improvement heuristic. > I guess Mathematika is doing the same. Still, it is possible calculate > the problem tight from the beginning with an Improvement algorithm. > My question is now, What is the constructive algorithm mathematika > uses? I really would like to know this. > > Thank u in advace for all your help.