Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Software » comp.soft-sys.math.mathematica

Topic: FindShortestTour Function- Roundtrip & Constructive
Replies: 3   Last Post: Dec 5, 2011 5:54 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Virgil Stokes

Posts: 77
Registered: 3/16/06
Re: FindShortestTour Function- Roundtrip & Constructive
Posted: Dec 4, 2011 2:21 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.