D
Dackle
I'm looking for suggestions on how to write a Perl program which will
return the most optimal route through a city neighbhourhood, with the
condition that every inch of every street in that neighbourhood must
be walked on. "Optimal" in this case is less concerned with distance
and more concerned with not walking on the same street more than once,
or if this is impossible, keeping the number of times certain streets
are "rewalked" to a minimum. Just as an example, a particular group of
streets I have in mind are displayed on this map:
http://ca.maps.yahoo.com/maps_resul...iLHTFN0whs8AJ5.IU-&csz=Toronto,+ON&country=ca,
and the area in particular is bound by the railway tracks to the
north, Yonge Street to the west, Bloor Street to the south and Mount
Pleasant Road to the East. All boundaries except for the railway
tracks can be walked on.
I have been thinking about numbering each intersection as a node,
and then the array @node[0] might contain (1,3,4), which would be the
nodes Node 0 is connected to, then running through all combinations
with a for loop. Another option might be for @node[0] to contain
(0,0,0,0,1,0,0,0,1,0), @node[1] would contain (0,0,1,0,0,0,0,1,0)
etc., where the 1s show connections from Node 0 (i.e. 0 connects to 4
and 8, node 1 connects to nodes 2 and 7), and the zeroes show no
connection. The problem though is that while you may have an optimal
route between each node, this still doesn't mean you walked on every
street. If you number the top corners of a square 1, 2, and the bottom
corners 3,4, you could trace through each node of a square with the
route 1 -> 2 -> 4 -> 3 (clockwise beginning from top left) and still
not "walk" the left side of the square between 1 and 3. Specifying the
necessity of "returning home" is not the answer, because more gaps
open up with more complex street structures. I thought about numbering
the segments instead (i.e. top of the square is a, bottom is b, left
and right are c and d), but then the connection rules change depending
on what end of the segment you are standing on. "A" connects to "C" if
you are standing on the left side of A, but not if you are on the
right side.
Any suggestions would be greatly appreciated.
return the most optimal route through a city neighbhourhood, with the
condition that every inch of every street in that neighbourhood must
be walked on. "Optimal" in this case is less concerned with distance
and more concerned with not walking on the same street more than once,
or if this is impossible, keeping the number of times certain streets
are "rewalked" to a minimum. Just as an example, a particular group of
streets I have in mind are displayed on this map:
http://ca.maps.yahoo.com/maps_resul...iLHTFN0whs8AJ5.IU-&csz=Toronto,+ON&country=ca,
and the area in particular is bound by the railway tracks to the
north, Yonge Street to the west, Bloor Street to the south and Mount
Pleasant Road to the East. All boundaries except for the railway
tracks can be walked on.
I have been thinking about numbering each intersection as a node,
and then the array @node[0] might contain (1,3,4), which would be the
nodes Node 0 is connected to, then running through all combinations
with a for loop. Another option might be for @node[0] to contain
(0,0,0,0,1,0,0,0,1,0), @node[1] would contain (0,0,1,0,0,0,0,1,0)
etc., where the 1s show connections from Node 0 (i.e. 0 connects to 4
and 8, node 1 connects to nodes 2 and 7), and the zeroes show no
connection. The problem though is that while you may have an optimal
route between each node, this still doesn't mean you walked on every
street. If you number the top corners of a square 1, 2, and the bottom
corners 3,4, you could trace through each node of a square with the
route 1 -> 2 -> 4 -> 3 (clockwise beginning from top left) and still
not "walk" the left side of the square between 1 and 3. Specifying the
necessity of "returning home" is not the answer, because more gaps
open up with more complex street structures. I thought about numbering
the segments instead (i.e. top of the square is a, bottom is b, left
and right are c and d), but then the connection rules change depending
on what end of the segment you are standing on. "A" connects to "C" if
you are standing on the left side of A, but not if you are on the
right side.
Any suggestions would be greatly appreciated.