
Re: FindShortestTour Function Roundtrip & Constructive
Posted:
Dec 4, 2011 2:21 AM


On 01Dec2011 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.

