MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: FindShortestTour Function- Roundtrip & Constructive

  • To: mathgroup at smc.vnet.net
  • Subject: [mg123367] Re: FindShortestTour Function- Roundtrip & Constructive
  • From: Virgil Stokes <vs at it.uu.se>
  • Date: Sun, 4 Dec 2011 02:50:40 -0500 (EST)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • References: <201112011053.FAA15051@smc.vnet.net>

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.



  • Prev by Date: Re: How to simplify ArcSin formula
  • Next by Date: The orde of product
  • Previous by thread: FindShortestTour Function- Roundtrip & Constructive Heuristic
  • Next by thread: Re: FindShortestTour Function- Roundtrip & Constructive Heuristic