Re: FindShortestTour Function- Error
- To: mathgroup at smc.vnet.net
- Subject: [mg123156] Re: FindShortestTour Function- Error
- From: Jaebum Jung <jaebum at wolfram.com>
- Date: Thu, 24 Nov 2011 07:00:54 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
FindShortestTour find a tour that visit all given element only once.
In your example,
FindShortestTour[{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},DistanceFunction->(d[[#1,#2]]&)]
will try to find tour that visit all {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}.
But by your given distance matrix, it's not possible.
In[107]:= g = WeightedAdjacencyGraph[d];
In[108]:= HamiltonianGraphQ[g]
Out[108]= False
- Jaebum
----- Original Message -----
From: "Chrissi87" <c.curtaz at googlemail.com>
To: mathgroup at smc.vnet.net
Sent: Wednesday, November 23, 2011 6:08:49 AM
Subject: [mg123156] FindShortestTour Function- Error
Dear readers,
I am writing my master thesis about the routing of winter gritting
systems. My problem is a traveling salesman problem and I want to use
the function:
"FindShortestTour" in mathematika.
Under this link one can find a lot of examples
http://reference.wolfram.com/mathematica/ref/FindShortestTour.html,
but for my problem there is only one example and it does not work. My
problem is that my matrix has no euclidian distances, because a
street network can not be euclidian, since a street is never the
direct distance between two points. For this I made a matrix,
measuring the real distances of the streets between the several knots.
And of course there is not a conection between all knots.
So I changed the one example one can find under the link in my
problem.
This is the example out of the link:
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, tour} = FindShortestTour[{1, 2, 3, 4, 5, 6}, DistanceFunction -
> (d[[#1, #2]] &)]
Result: {6, {1, 4, 3, 5, 2, 6}}
Mine looks as follows:
d = SparseArray[{{1, 4} -> 290, {1, 12} -> 1600, {2, 3 } -> 130, {2,
12} -> 1950, {3, 2} -> 130, {3, 4} -> 230, {3, 18} -> 1720, {4, 1} ->
290, {4, 3} -> 230, {4, 5} -> 220, {4, 18} -> 1490,
{5, 4} -> 220, {5, 6} -> 170, {6, 5} -> 170, {6, 7} -> 270, {6, 18} ->
1100, {7, 6} -> 270, {7, 8} -> 100, {7, 17} -> 250, {8, 7} -> 100, {8,
9} -> 120, {8, 16} -> 450, {9, 8} -> 120, {9, 10} -> 250, {10, 9} ->
250, {10, 11} -> 210, {10, 15} -> 280, {10,
16} -> 290, {10, 20} -> 750, {11, 10} -> 210, {11, 12} -> 250, {12, 1}
-> 1600, {12, 2} -> 1950, {12, 11} -> 250, {12, 13} -> 280, {13, 12} -
> 280, {13, 14} -> 850, {14, 13} -> 850, {14, 15} -> 90, {15, 10} ->
280, {15, 14} -> 90, {15, 20} -> 1000, {16, 8} -> 450, {16, 10} ->
290, {16, 17} -> 250, {17, 7} -> 250, {17, 16} -> 250, {17, 18} ->
700, {18, 3} -> 1720, {18, 4} -> 1490, {18, 6} -> 1100, {18, 17} ->
700, {18, 19} -> 350, {19, 18} -> 350, {19,
20} -> 500, {20, 10} -> 750, {20, 15} -> 1000, {20, 19} -> 500}, {20,
20} Infinity ];
{len, tour} = FindShortestTour[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16, 17, 18, 19, 20}, DistanceFunction -> (d[[#1, #2]] &)]
Then the Error comes and says:
FindShortestTour::dist: The distance function d[[#1,#2]]& does not
give a numerical result when applied to two points. >>
Set::shape: Lists {len,tour} and
FindShortestTour[{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},DistanceFunction-
>(d[[#1,#2]]&)] are not the same shape. >>
I just do not know what it means and where my mistake ist. I just
bought this program some weeks ago, so the synatax is hart for me.
I would really appreciate it if somebody could help me. Thanks!
Chrissi