Re: FindShortestTour Function- Error
- To: mathgroup at smc.vnet.net
- Subject: [mg123130] Re: FindShortestTour Function- Error
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Thu, 24 Nov 2011 06:56:11 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <201111231208.HAA15040@smc.vnet.net>
- Reply-to: drmajorbob at yahoo.com
Mathematica finds no tour, then BADLY mishandles letting you know it.
There's no reason to throw error messages, when an infinite path-length
suffices.
We can get more information by avoiding Infinity:
rules = {{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};
nodes = Range@20;
bigEnough = 1 + Total@Abs@rules[[All, -1]]
d = SparseArray[rules, {20, 20}, bigEnough];
{len, ordering} =
FindShortestTour[nodes, DistanceFunction -> (d[[#1, #2]] &)]
tour = nodes[[ordering]]
Partition[tour, 2, 1] /. rules
32281
{70532, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 19,
18, 17, 16}}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 19, 18, 17, 16}
{{1, 2}, 130, 230, 220, 170, 270, 100, 120, 250, 210, 250, 280, 850, \
90, 1000, 500, 350, 700, 250}
Mathematica used the non-existent link from 1 to 2.
There is a legal path 1 -> 12 -> 2, but taking it would not allow a tour
visiting every node ONCE.
When I remove 1 and 12, we still don't have a valid tour in the remaining
nodes:
others = Complement[nodes, {1, 12}];
{len, ordering} =
FindShortestTour[others, DistanceFunction -> (d[[#1, #2]] &)]
tour = others[[ordering]]
Partition[tour, 2, 1] /. rules
{70002, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 18, 17, 16, 15,
14}}
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 20, 19, 18, 17, 16}
{130, 230, 220, 170, 270, 100, 120, 250, 210, {11,
13}, 850, 90, 1000, 500, 350, 700, 250}
as we see from use of the nonexistent 11 -> 13 link.
Bottom line: your path matrix is too sparse to allow tours.
Bobby
On Wed, 23 Nov 2011 06:08:49 -0600, Chrissi87 <c.curtaz 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 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
>
--
DrMajorBob at yahoo.com
- References:
- FindShortestTour Function- Error
- From: Chrissi87 <c.curtaz@googlemail.com>
- FindShortestTour Function- Error