Re: FindShortestTour Function- Error
- To: mathgroup at smc.vnet.net
- Subject: [mg123320] Re: FindShortestTour Function- Error
- From: Dana DeLouis <dana01 at me.com>
- Date: Thu, 1 Dec 2011 05:52:50 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
Hi. Not quite what you are looking for, but you may find it interesting.
Although you data can not be joined in a true Traveling Salesmen fashion,
it appears your data can be joined as a Minimum Spanning Tree.
In this way, a few points act as hubs.
It allows travel from any point to any other point using the least amount of length to connect all the points.
It didn't look like it was possible from your data, but it can be connected with 4940 units.
Needs["Combinatorica`"]//Quiet
rules={{1,4}->290,{1,12}->1600,{2,3}->130,... etc (your data)
d=SparseArray[rules,{20,20},\[Infinity]]//Normal;
h=MinimumSpanningTree[FromAdjacencyMatrix[d,EdgeWeight]]
The total length used:
Edges[h]/.rules //Total
4940
ShowGraph[
RadialEmbedding[h],
VertexLabel->True
]
And for fun... a government project (ie road building, etc) to connect the points...
h=MaximumSpanningTree[FromAdjacencyMatrix[d,EdgeWeight]]
Edges[h]/.rules //Total
14310
A quick table of the data:
TableForm[d,TableHeadings->Automatic]
I'm not familiar with any Combinatorica enhancements made with ver 8
= = = = = = = = = = =
HTH
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