SearchTree - search a tree of nodes in a variety of ways.
# First define your own MyNode hash reference object
# with the following methods.
{ package MyNode;
sub new { } # the object must be a hash references, i.e. $self={}
sub expand { } # return a reference to list of nodes below given node.
sub isGoal { } # return true if this node is the goal else false.
sub areEqual { } # return true if two nodes represent equivalent states.
sub asText { } # return node as text (for verbose>1 output)
}
my $rootNode = MyNode->new( ); # Create the top node in the tree.
# Return a reference to a list of nodes starting at $rootNode
# ending at $goalNode, such that $goalNode->isGoal() is true.
use SearchTree;
my $nodePath = SearchTree::breadthFirst( root => $rootNode,
depth => 5,
VERBOSE => 1);
# or
my $nodePath = SearchTree::depthFirst( root => $rootNode,
depth => 5, );
print "Here's a path to the goal :\n";
foreach my $node (@$nodePath) { print $node->asText() . "\n" }
This module will search through a tree of node objects.
The logic of the tree itself - how to generate new nodes below a given one, how to detect if the goal as been reached, and so on - must be defined in another package. Moreover, the node objects should be implemented as hash references, so that SearchTree can store various data such as parent and depth within the nodes themselves, in the form $object->{_ST_dataname}.
The calling routine defines a package that implements the logic behind the tree of nodes to be searched, including methods to find the subnode children of a given node (expand), to test if the goal has been reached (isGoal), to return a string representation of a node (asText), and to see if the internals of a given node are equivalent to that of another node (areEqual).
See the SearchTree.pm source code for the sampleNode package which illustrates these methods.
The search algorithms implemented are
* breadthFirst, which looks for the goal in all the nodes at each depth before moving deeper, keeping all unique nodes in memory, and
* depthFirst, which uses less memory but descends quickly to the maximum depth without exploring simpler alternatives.
To see the algorithms run on a simple test tree you can run the package with ``perl SearchTree.pm''.
By default: nothing. By request: breadthFirst, depthFirst.
Perl
Copyright 2003 by Jim Mahoney, <mahoney@marlboro.edu
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.