Re: FindShortestTour Function- Roundtrip & Constructive
- To: mathgroup at smc.vnet.net
- Subject: [mg123383] Re: FindShortestTour Function- Roundtrip & Constructive
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Mon, 5 Dec 2011 05:14:24 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
Part 1:
FindShortestTour ALREADY includes a return to the first node in its
distance computation, as you can see from:
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}};
{len, order} = FindShortestTour[pts];
{len, tour = pts[[order]]};
cycle = Append[tour, First@tour];
{len,
EuclideanDistance @@@ Partition[cycle, 2, 1] // Total}
{14 + 5 Sqrt[2], 14 + 5 Sqrt[2]}
Part 2:
FindShortestTour finds A shortest tour in both cases. Adding a second
near-copy of the first node happens to cause a different ordering to be
chosen, but it doesn't change the tour length (except for what's
necessary, due to the new node).
Here's the second tour computation and a comparison of the two tours:
pts2 = Append[pts, 10^-10 + First@pts];
{len2, order2} = FindShortestTour[pts2];
{len2, tour2 = pts2[[order2]]};
{Range@20, order, order2} // Grid
(* output suppressed *)
N[{len, len2}, 13]
{21.07106781187, 21.07106781191}
Partition[
ListLinePlot[#, Mesh -> All, ImageSize -> 250] & /@ {tour, tour2,
tour[[{19, 1, 2, 3, 4}]], tour2[[{17, 18, 19, 20, 1, 2}]]},
2] // Grid
The tours on the top row look different, but a little study shows the
total length is exactly the same. The bottom row shows a portion close to
the initial node on each tour. The added node and initial node hide one
another, so that a tour through 6 nodes looks like a tour through 5.
If we change the added node so that it is on the line from last to first
for the original tour, we get equal tour lengths, despite YET ANOTHER
alternative optimum path.
pts2 = Append[pts, {10^-2, 0} + First@pts];
{len2, order2} = FindShortestTour[pts2];
{len2, tour2 = pts2[[order2]]};
len - len2
0
(same distance)
{Range@20, order, order2} // Grid
(different paths)
Bobby
On Sun, 04 Dec 2011 01:50:40 -0600, Virgil Stokes <vs at it.uu.se> wrote:
> 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.
>
--
DrMajorBob at yahoo.com