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


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

FindShortestTour Function- Roundtrip & Constructive Heuristic

From Chrissi87 <c.curtaz@googlemail.com>
Newsgroups comp.soft-sys.math.mathematica
Subject FindShortestTour Function- Roundtrip & Constructive Heuristic
Date 2011-12-01 11:02 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <jb7mt0$gl2$1@smc.vnet.net> (permalink)

Show all headers | View raw


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.

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread


Thread

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

csiph-web