Algorithm::Search - Module for traversing an object.
use Algorithm::Search; my $as = new Algorithm::Search(); $as->search({ # Example parameters here are the default parameters search_this => $object_to_search, #no default search_type => 'dfs', # dfs, bfs, cost, or rdfs max_steps => 20000, # number of moves to look at maximum_depth => 0, # longest allowable path length if > 0 solutions_to_find => 0, # search stops when number reached, 0 finds all do_not_repeat_values => 0, # only traverse position with value once cost_cannot_increase => 0, # whether or not moves can increase cost initial_cost => undef, # for cost based search return_search_trace => 0, # does $as->search_trace return array ref of moves }); if (!$as->completed) { $as->continue_search({additional_steps => 300}); } if ($as->solution_found) { @solutions = $as->solutions; @paths_to_solution = $as->paths; } $steps_taken = $search->steps_taken;
A user provided traversable object starts in an initial position. The traversable object must have certain methods, such as 'move', described below. This is passed into the search method via the 'search_this' parameter.
At any position, the object has a list of moves to new positions, the list may be empty.
A position is a solution if the "is_solution" function returns true.
A traversal does not require that a solution be found or even looked for. A search is a traversal that looks for a solution.
A path corresponds to a list of valid moves from the initial position. The path values correspond to the list of values by the positions the object moves along the path.
A move is valid if the move function returns a value. The number of steps, is the number of calls to the move function.
A queue based traversal stores positions and paths on a queue, copying the object before performing each move.
In depth first search (dfs), the next position to search is the most recently placed on the queue.
In breadth first search (bfs), the next item to search is the least recently placed on the queue.
In cost based search (cost) , the next item to search is the lowest cost item on the queued, ties go to the most recently placed on the queue. Cost based search with all the same costs behaves as depth first search.
A reversible depth first search (rdfs) traversal uses reverse move to traverse paths with the search object. A reversible traversal does not use a queue resulting in less memory usage. A reversible traversal is more complicated to set up and only allows depth first search.
sub move ($move, $cost) #required, return undef if illegal move else return cost
If the parameter cost_cannot_increase is set, any move which would decrease the cost is disallowed. The cost is the value returned from the move method.
The search parameter initial_cost corresponds to where in the queue the moves from the initial position belong.
sub value #optional - used to pare down search, a value cannot #repeat on a search path, prevents loops in paths
If the parameter do_not_repeat_values is set, a value cannot repeat any time in the search. Presumably this would be done to find a single solution and not be concerned about the paths.
sub stop_search #optional - after every step, this procedure #is passed the current position, the number of steps, #and the path to the current position. If it returns #a true value, the search stops. Useful for tracing the search.
sub next_moves #required, list of moves from given object sub copy #required sub commit_level #optional - returns number, used to pare down search # if the commit level decreases, all moves in the queue are emptied # except for the current position sub move #return numeric value, the lower the value, the earlier the #moves from the position will be traversed.
sub move_after_given($previous_move) #required #if $previous_move is null, first move to try from position #else the next move after $previous move is returned, undef if no move sub reverse_move #required sub copy # If provided, will copy solutions to an array. sub commit_level #optional - returns number, used to pare down search # cannot reverse a move to a position with a higher commit level
There is a directory example included in the package.
package traveller; $destination = ''; %roads = ( 'Minneapolis' => ['St. Paul', 'Duluth'], 'St. Paul' => ['Minneapolis', 'Madison'], 'Madison' => ['Rockford', 'St. Paul', 'Chicago'], 'Rockford' => ['Bloomington', 'Madison'], 'Bloomington' => ['Champaign'], 'Champaign' => ['Urbana', 'Chicago'], 'Chicago' => ['Minneapolis', 'Urbana'], 'Urbana' => [], 'Duluth' => [], ); sub new {return bless {}} sub next_moves {my $self = shift; return @{$roads{$self->{position}}}} sub move {my $self = shift; $self->{position} = shift; return 0;} sub value {my $self = shift; return $self->{position}} sub copy {my $self = shift; my $copy = $self->new; $copy->move($self->{position}); return $copy;}; sub is_solution {my $self = shift; return $self->{position} eq $destination;} sub set_destination {my $self = shift; $destination = shift;} package main; use Algorithm::Search; my $driver = new traveller; my $travel_search = new Algorithm::Search(); $driver->move('Minneapolis'); #start out in Minneapolis $driver->set_destination('Urbana'); $travel_search->search({search_this => $driver, solutions_to_find => 0, }); my $full_path; if ($travel_search->solution_found) { #should be true, path to Urbana foreach my $path ($travel_search->paths) { $full_path .= join("..", @{$path})."\n"; } } #$full_path should contain string: St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana St. Paul..Madison..Rockford..Bloomington..Champaign..Chicago..Urbana St. Paul..Madison..Chicago..Urbana
package traveller; %roads = ( 'Minneapolis' => ['St. Paul', 'Duluth'], 'St. Paul' => ['Minneapolis', 'Madison'], 'Madison' => ['Rockford', 'St. Paul', 'Chicago'], 'Rockford' => ['Bloomington', 'Madison'], 'Bloomington' => ['Champaign'], 'Champaign' => ['Urbana', 'Chicago'], 'Chicago' => ['Minneapolis', 'Urbana'], 'Urbana' => [], 'Duluth' => ['Chicago'], ); %distance_to_urbana = ( 'Minneapolis' => 515, 'St. Paul' => 505, 'Madison' => 252, 'Rockford' => 185, 'Bloomington' => 56, 'Champaign' => 2, 'Chicago' => 140, 'Urbana' => 0, 'Duluth' => 575, ); sub distance_to_urbana { my $self = shift; return $distance_to_urbana{$self->{position}}; } sub new {return bless {}} sub next_moves {my $self = shift; return @{$roads{$self->{position}}}} sub move {my $self = shift; $self->{position} = shift; return $distance_to_urbana{$self->{position}};} sub value {my $self = shift; return $self->{position}} sub copy {my $self = shift; my $copy = $self->new; $copy->move($self->{position}); return $copy;}; sub is_solution {my $self = shift; return $self->{position} eq 'Urbana';} package main; use Algorithm::Search; my $driver = new traveller; my $travel_search = new Algorithm::Search(); $driver->move('Minneapolis'); $travel_search->search({search_this => $driver, solutions_to_find => 0, search_type => 'cost', initial_cost => $driver->distance_to_urbana, maximum_depth => 8, #if 7 then only 3 paths will be returned }); $full_path = ''; foreach my $path ($travel_search->paths) { $full_path .= join("..", @{$path})."\n"; } # $full_path should contain: St. Paul..Madison..Rockford..Bloomington..Champaign..Urbana St. Paul..Madison..Rockford..Bloomington..Champaign..Chicago..Urbana St. Paul..Madison..Chicago..Urbana Duluth..Chicago..Urbana
package r_traveller; %roads = ( 'Minneapolis' => ['St. Paul', 'Duluth'], 'St. Paul' => ['Minneapolis', 'Madison'], 'Madison' => ['Rockford', 'St. Paul', 'Chicago'], 'Rockford' => ['Bloomington', 'Madison'], 'Bloomington' => ['Champaign'], 'Champaign' => ['Urbana', 'Chicago'], 'Chicago' => ['Minneapolis', 'Urbana'], 'Urbana' => [], 'Duluth' => [], ); sub new {return bless {}} sub move_after_given { my $self = shift; my $previous = shift; my $move_count = 0; if ($previous) { $move_count = $previous->[2] + 1; } my $city = $self->{position}; if (scalar(@{$roads{$city}}) > $move_count) { return [$self->{position}, $roads{$city}->[$move_count], $move_count] } else { return undef; } } sub reverse_move {my ($self, $move) = @_; $self->{position} = $move->[0];} sub move {my ($self, $move) = @_; $self->{position} = $move->[1]; return 0} sub value {my $self = shift; return $self->{position}} sub is_solution {my $self = shift; return $self->{position} eq 'Urbana';} package main; use Algorithm::Search; my $r_driver = new r_traveller; $travel_search = new Algorithm::Search(); $r_driver->move([undef, 'Minneapolis']); #start out in Minneapolis $travel_search->search({ search_this => $r_driver, search_type => 'rdfs', solutions_to_find => 0, }); $full_path .= ""; foreach $path ($travel_search->paths) { foreach $move (@$path) { $full_path .= " ".$move->[0]." "; } $full_path .= "\n"; } #$full_path should contain: Minneapolis St. Paul Madison Rockford Bloomington Champaign Minneapolis St. Paul Madison Rockford Bloomington Champaign Chicago Minneapolis St. Paul Madison Chicago
Arthur Goldstein , <arthur@acm.org>
Copyright (C) 2008 by Arthur Goldstein
Please email in bug reports.
Test cases may take too long, can make faster.
Might want a value function for the moves, this might be of use in the trace.
Any reference on depth/first search and searching in general.
To install Algorithm::Search, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::Search
CPAN shell
perl -MCPAN -e shell install Algorithm::Search
For more information on module installation, please visit the detailed CPAN module installation guide.