Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #6871 > unrolled thread

FindShortestTour Function- Roundtrip & Constructive Heuristic

Started byChrissi87 <c.curtaz@googlemail.com>
First post2011-12-01 11:02 +0000
Last post2011-12-01 11:02 +0000
Articles 1 — 1 participant

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  FindShortestTour Function- Roundtrip & Constructive Heuristic Chrissi87 <c.curtaz@googlemail.com> - 2011-12-01 11:02 +0000

#6871 — FindShortestTour Function- Roundtrip & Constructive Heuristic

FromChrissi87 <c.curtaz@googlemail.com>
Date2011-12-01 11:02 +0000
SubjectFindShortestTour Function- Roundtrip & Constructive Heuristic
Message-ID<jb7mt0$gl2$1@smc.vnet.net>
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.

[toc] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web