Breadth first recursion
In computer programming, Breadth first recursion is one of design patterns.
Problem: Find routes to everything, or find the shortest route there.
Solution: Maintain a queue of items to examine. When you find something you need to
recurse into, put it on the end of the queue. Keep a list of things you've already
done so you know what you do and don't need to recurse into.
Concepts of depth first and breadth first are confusing. First attempts at writing
code to traverse a map, directory structure, and so forth, mix elements of both
unsuccessfully.
sub solve_maze {
my $me = $_[0];
my $dest = $_[1];
return ($me) if $me eq $dest;
my @queue = ($me);
my %route = ($me => [$me]);
while(my $ob = shift @queue) {
foreach my $i (@{$ob->neighbors()}) {
if(!$route{$i}) {
$route{$i} = [@{$route{$ob}}, $i];
return \$route{$i} if($i eq $dest);
push @queue, $i;
}
}
}
}
Objects represent blocks on a map. Each object returns a list of neighbors when
the //->neighbors()// method is called.
//@queue// is the list of directions we haven't taken yet, and need to get back to.
We do them in the order found. When going through a directory structure on a filesystem,
that would do the top level directories first, then the 2nd level ones, then the 3rd level,
and so forth.
//%route// keeps track of what we've found, and how we've found it.
Every node we find, we know the path to: the path to the current node plus the
current neighbor we're examining. Initially, the current node is the root node,
and all of its neighbors will have a two hop path: the root node, then the current
neighbor. This pattern repeats for all of their neighbors.
For our purposes, we want to know the route used to get from one place to another:
we return a list of steps taken to get there.
We want the first match. There may be several paths. Removing the //return \$route...//
line will find all of the routes, shortist routes first, without duplicates.
Before the //if(!$route...// line, instead put:
push @routes_to_dest, [@{$route{$ob}}, $i] if($i eq $dest);
That will log all routes we find, not merely the first.
Since BreadthFirst recurssion starts at the root and expands outward
in all directions at the same rate, it is optimal for cases where the target
and destination are near by.
DepthFirst recurssion is even easier to implement, and is optimal for
cases where every node must be visited. It goes as far as it can in any
one direction, then goes back until it finds another route. Since
new tangets are taken as soon as they are found, there is no need to remember
what has been done or what needs to be done - only where you were on previous
routes when you took a tangent.
External Links
- http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466
The article is originally from Perl Design Patterns Book.
See also
Referenced By
Container pattern | Design pattern (computer science) | Design pattern (computing) | Software design pattern | Software desisgn pattern | Software pattern
|
