Re: FindShortestTour Function- Error
- To: mathgroup at smc.vnet.net
- Subject: [mg123152] Re: FindShortestTour Function- Error
- From: Dana DeLouis <dana01 at me.com>
- Date: Thu, 24 Nov 2011 07:00:11 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
Hi. If I am not mistaken, here is one additional way to show that your set up has no solution.
data={{1,4}->290,{1,12}->1600,....etc Your data here
However, instead of giving a value of Infinity for paths that are not used, give a value of say 10000.
d=SparseArray[data,{20,20}, 10000]
{len,tour}=FindShortestTour[Range@20,DistanceFunction->(d[[#1,#2]]&)]
{25970,{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,20,19,18,17,16}}
Here are the leg distances:
Partition[tour,2,1]/.data
{{1,2},130,230,220,170,270,100,120,250,210,250,280,850,90,1000,500,350,700,250}
This indicates there is no given value along the leg 1-2, and hence has a value of 10000.
This indicates that your setup is unfeasible.
The other missing 10000 value is not so obvious. It's the value that was applied going from the end (16) back to the beginning.
You are missing a connection from 16 as well.
= = = = = = = = = =
Good Luck :>)
Dana DeLouis
Mac, Ver 8
= = = = = = = = = =
On Nov 23, 7:16 am, Chrissi87 <c.cur... at googlemail.com> wrote:
> 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 exampleshttp://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},Dista nceFunction-
>
> >(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