|
Listing 5-3. Recursive Tree-Traversal
def tree_walk(T, r): # Traverse T from root r
for u in T[r]: # For each child. . .
tree_walk(T, u) # ... traverse its subtree
In terms of the maze metaphor, if you’re standing at an intersection and you can go left or right, you first traverse
the part of the maze to the left and then the one to the right. And that’s it. It should be obvious (perhaps with the aid
of a little induction) that this strategy will traverse the entire maze. Note that only the act of walking forward through
each passage is explicitly described here. When you walk the subtree rooted at node u, you walk forward to u and start
working on the new passages out from there. Eventually, you will return to the root, r. Going backward like this, over
your own tracks, is called backtracking and is implicit in the recursive algorithm. Each time a recursive call returns,
you automatically backtrack to the node where the call originated. (Do you see how this backtracking behavior is
consistent with the left-hand rule?)
6
Tracing your tour from a, you should end up with the node sequence a, b, c, d, e, f, g, h, d, c, i, j, i, k, i, c, b, l, b, a.
7
This recursive version would be harder to use if you were actually faced with a real-life maze, of course.
Chapter 5
■
traversal: the skeleton key of algorithmiCs
101
Imagine that someone poked a hole through one of the walls in the maze so that the corresponding graph
suddenly had a cycle. Perhaps they busted through the wall just north of the dead end at node e. If you started your
walk at e, walking north, you could keep left all you wanted, but you’d never traverse the entire maze—you’d keep
walking in circles.
8
This is a problem we face when traversing general graphs.
9
The general idea in Listing 5-1 gives us
a way out of this problem, but before I get into that, let’s see what our French telegraphic engineer came up with.
How to Stop Walking in Circles
Édouard Lucas describes Tremaux’s algorithm for traversing mazes in the first volume of his Récréations
Mathématiques in 1891. Lucas writes, in his introduction:
10
To completely traverse all the passages of a labyrinth twice, from any initial point, simply follow
the rules posed by Trémaux, marking each entry to or exit from an intersection. These rules may
be summarized as follows: When possible, avoid passing an intersection you have already visited,
and avoid taking passages you have already traversed. Is this not a prudent approach, which also
applies in everyday life?
Later in the book, he goes on to describe the method in much more detail, but it is really quite simple, and the
previous quote covers the main idea nicely. Instead of marking each entry or exit (say, with a piece of chalk), let’s just
say you have muddy boots, so you can see our own tracks (like in Figure
5-2
). Trémaux would then tell you to start
walking in any direction, backtracking whenever you came to a dead end or an intersection you had already walked
through (to avoid cycles). You can’t traverse a passage more than twice (once forward and once backward), so if you’re
backtracking into an intersection, you walk forward into one of the unexplored passages, if there are any. If there
aren’t any, you keep backtracking (into some other passage with a single set of footprints).
11
And that’s the algorithm. One interesting observation to make is that although you can choose several passages
for forward traversal, there will always be only one available for backtracking. Do you see why that is? The only way
there could be two (or more) would be if you had set off in another direction from an intersection and then come back
to it without backtracking. In this case, though, the rules state that you should not enter the intersection but backtrack
immediately. (This is also the reason why you’ll never end up traversing a passage twice in the same direction.)
The reason I’ve used the “muddy boots” description here is to make the backtracking really clear; it’s exactly
like the one in the recursive tree traversal (which, again, was equivalent to the left-hand rule). In fact, if formulated
recursively, Trémaux’s algorithm is just like the tree walk, with the addition of a bit of memory. We know which
nodes we have already visited and pretend there’s a wall preventing us from entering them, in effect simulating a tree
structure (which becomes our traversal tree).
See Listing 5-4 for a recursive version of Trémaux’s algorithm. In this formulation, it is commonly known as
depth-first search, and it is one of the most fundamental (and fundamentally important) traversal algorithms.
12
8
And just like that, a spelunker can turn troglodyte.
9
People seem to end up walking in circles when wandering in the wild as well. And research by the U.S. Army suggests that people
prefer going south, for some reason (as long as they have their bearings). Neither strategy is particularly helpful if you’re aiming for
a complete traversal, of course.
10
My translation.
11
You can perform the same procedure even if your boots aren’t muddy. Just make sure to clearly mark entries and exits (say,
with a piece of chalk). In this case, it’s important to make two marks when you come to an old intersection and immediately start
backtracking.
12
In fact, in some contexts, the term backtracking is used as a synonym for recursive traversal, or depth-first search.
Chapter 5
■
traversal: the skeleton key of algorithmiCs
102
Do'stlaringiz bilan baham: |
