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


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

Re: FindShortestTour Function - Roundtrip & Constructive Heuristic

From DrMajorBob <btreat1@austin.rr.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: FindShortestTour Function - Roundtrip & Constructive Heuristic
Date 2011-12-02 12:22 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <jbafts$1sh$1@smc.vnet.net> (permalink)

Show all headers | View raw


Part 1:

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];

{len, ordering} =
  FindShortestTour[nodes = {1, 2, 3, 4, 5, 6},
   DistanceFunction -> (d[[#1, #2]] &)]
tour = nodes[[ordering]]
cycle = Append[#, First@#] &@tour

{6, {1, 4, 3, 5, 2, 6}}

{1, 4, 3, 5, 2, 6}

{1, 4, 3, 5, 2, 6, 1}

Bobby

On Thu, 01 Dec 2011 04:53:48 -0600, Chrissi87 <c.curtaz@googlemail.com>  
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.
>


-- 
DrMajorBob@yahoo.com

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


Thread

Re: FindShortestTour Function - Roundtrip & Constructive Heuristic DrMajorBob <btreat1@austin.rr.com> - 2011-12-02 12:22 +0000

csiph-web