Re: FindShortestTour Function- Roundtrip & Constructive
- To: mathgroup at smc.vnet.net
- Subject: [mg123378] Re: FindShortestTour Function- Roundtrip & Constructive
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Mon, 5 Dec 2011 05:13:30 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
----- Original Message ----- > From: "Virgil Stokes" <vs at it.uu.se> > To: mathgroup at smc.vnet.net > Sent: Sunday, December 4, 2011 1:50:40 AM > Subject: Re: FindShortestTour Function- Roundtrip & Constructive > > On 01-Dec-2011 11:53, Chrissi87 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. > > > Here is something that I took from the documentation on > FindShortestTour, > > Case A. Find the minimum length path for visiting only once the > following 19 > cities with a > fixed starting point (1,1) using FindShortestTour with default > options. > > In[14]:= pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, > 3}, {2, 5}, > {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 1}, {5, > 2}, {5, 3}, > {5, 4}}; > > In[15]:= {len, tour} = FindShortestTour[%] > > Out[15]= {14 + 5 Sqrt[2], {1, 2, 7, 3, 4, 5, 8, 12, 11, 15, 19, 14, > 18, 17, 16, > 13, 9, 10, 6}} > > In[16]:= ListLinePlot[pts[[tour]], Mesh -> All, PlotLabel -> N[len]] > > Case B. Now we visit the same cities but let's return to our starting > point (at > least within an epsilon distance of it) ---a simple but IMHO a > practical answer > to your question 1. > > In[17]:= epsilon = 1.0*10^-15; > pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, > 5}, {3,1}, > {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 1}, {5, 2}, {5, > 3}, {5, 4}, > {1.0 + epsilon, 1.0 + epsilon}}; > > In[18]:= {len, tour} = FindShortestTour[%] > > Out[18]= {21.0711, {1, 6, 9, 10, 13, 16, 17, 14, 18, 19, 15, 12, 11, > 8, 5, 4, 3, > 7, 2, 20}} > > In[19]:= ListLinePlot[pts[[tour]], Mesh -> All, PlotLabel -> N[len]] > > Note, 1) the routes taken are quite different (although some > interesting > "symmetry" is present), and 2) 14 + 5 Sqrt[2] = 21.0711 and thus the > distance > traveled is the same for both cases (at least to 4 decimal places), > which means > that Case A (no return to the start) did not give the shortest route! > > I suggest that you try this code (looking at the graphical outputs) > and then > further investigate FindShortestTour and its documentation. > > These results were obtained using Mathematica 8.0.4.0. To clarify, FindShortestTour gives a result that reflects the distance of the final leg connecting last point to first. It (clearly) does not list the starting point again at the end of the tour. I do not know the reason for this design. I have no particular objection to it, although for some purposes I believe having that point explicitly listed at the end could be useful. I filed a suggestion to the effect that it be documented clearly that the distance returned reflects the contribution of that connecting last leg. To see that it is really used, I borrow from a documentation example. pts = {{1, 4, 3}, {1, 2, 3}, {2, 3, 1}, {3, -5, 1}, {2, -1, 2}}; {len, order} = FindShortestTour[pts] Out[25]= {2 + 3 Sqrt[2] + Sqrt[6] + Sqrt[11] + Sqrt[65], {1, 3, 4, 5, 2}} Now we sum the leg distances explicitly, add ing in the final leg connecting last point to first. In[36]:= p2 = pts[[order]]; p3 = Join[p2, {p2[[1]]}] len2 = Total[Norm[#[[2]] - #[[1]]] & /@ Partition[p3, 2, 1]] Out[37]= {{1, 4, 3}, {2, 3, 1}, {3, -5, 1}, {2, -1, 2}, {1, 2, 3}, {1, 4, 3}} Out[38]= 2 + 3 Sqrt[2] + Sqrt[6] + Sqrt[11] + Sqrt[65] In[43]:= len2 === len Out[43]= True Daniel Lichtblau Wolfram Research