Do you have a question? Post it now! No Registration Necessary. Now with pictures!
- Posted on
- Perl program for neighbourhood walk
January 2, 2005, 5:33 pm
rate this thread
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:
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 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 to contain
(0,0,0,0,1,0,0,0,1,0), @node 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
Any suggestions would be greatly appreciated.
Re: Perl program for neighbourhood walk
: 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.
The problem you describe is well known in graph theory. Devising a
solution is more an exercise in algorithms than one of actual programming.
As far as Perl-centric assistance goes, the Graph module would be useful to
Google for "postman problem" or "traveling salesman problem" for some lucid
discussion of solution techniques.