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