AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
* n is a state (node) along a path
* g(n) is the total cost of the path leading up to n
* h(n) is the heuristic function, or estimated cost of the path from n
to the goal node.
The to be admissible, the heuristic must never over-estimate the distance
from the node to the goal. If the heuristic is set to zero, A* search reduces
to Branch and Bound search.
For a given heuristic function, it can be shown that A* search is optimally
efficient, meaning that, in its calculation of the shortest path, it expands
fewer nodes in the search space than any other algorithm.
The space complexity of A* search is bounded by an exponential of the
branching factor of the search-space and the length of the longest path
examined during the search. This is can be a problem particularly if the
branching factor is large, as the algorithm may run out of memory.
Sets/gets the function that returns the next successor of
this node.
state_get_data_func()
Sets/gets the function that returns a string representation
of this node.
show_prog_func()
sets/gets the callback function for displaying the progress of the
search. It can be an empty callback if you do not need this output.
EXPORT
None by default.
SEE ALSO
Russell, Stuart. (1992) "Efficient Memory-bounded Search Methods" Proceedings
of the 10th European conference on Artificial intelligence, pp. 1-5
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
return $best;
}
elsif($best->{_f_cost} >= $max_cost){
croak "\n\nSearch unsuccessful. max_cost reached (cost: $max_cost).\n";
}
else{
my $successors_iterator = $best->$successors_func();
my $succ = $successors_iterator->();
if($succ){
# if succ is at max depth and is not a goal node, set succ->fcost to infinity
if($succ->depth() >= $max_depth && !$succ->$goal_p() ){
$succ->{_f_cost} = $max_cost;
}
else{
# calling eval for comparison, and maintaining pathmax property
$succ->{_f_cost} = max($eval_func->($succ), $eval_func->($best));
my $descendant_index = $succ->{_descendant_index};
$best->{_descendant_fcosts}->[$descendant_index] = $succ->{_f_cost};
}
}
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
if($best->need_fval_change()){
$$priority_queue->insert($best);
my $antecedent = $best->{_antecedent};
my $i = 0;
while($antecedent){
if($was_on_queue{$i} && $antecedent->need_fval_change()){
# the antecedent needed fval change too.
$$priority_queue->insert($antecedent);
}
if($antecedent->need_fval_change()){
# set need_fval_change back to 0, so it will not be automatically seen as
# needing changed in the future. This is important, since we do not want
# to remove an element from the queue *unless* we need to change the fcost.
# This is because when we remove it from the queue and re-insert it, it
# loses its seniority in the queue (it becomes the newest node at its cost
# and depth) and will not be removed at the right time when searching for
# deepest_lowest_cost_leafs or shallowest_highest_cost_leafs.
$antecedent->{_need_fcost_change} = 0;
}
$antecedent = $antecedent->{_antecedent};
$i++;
}
# Again, set need_fval_change back to 0, so it will not be automatically
# seen as needing changed in the future.
$best->{_need_fcost_change} = 0;
}
}
#
# If best's descendants are all in memory, mark best as completed.
#
if($best->all_in_memory()) {
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
croak "Error while pruning queue: shallowest-highest-cost-leaf was null\n";
}
$antecedent = $shcl_obj->{_antecedent};
if($antecedent){
my $antecedent_successors = \$antecedent->{_descendants_list};
$antecedent->remember_forgotten_nodes_fcost($shcl_obj);
$antecedent->{_forgotten_nodes_num} = $antecedent->{_forgotten_nodes_num} + 1;
my $descendant_index = $shcl_obj->{_descendant_index};
# record the index of this descendant in the forgotten_nodes list
$antecedent->{_forgotten_nodes_offsets}->{$descendant_index} = 1;
# flag the antecedent as not having this descendant in the queue
$antecedent->{_descendants_produced}->[$descendant_index] = 0;
$antecedent->{_descendant_fcosts}->[$descendant_index] = -1;
# flag the ancestor node as having deleted a descendant
$antecedent->descendants_deleted(1);
# update the number of descendants this node has in memory
$antecedent->{_num_successors_in_mem} = $antecedent->{_num_successors_in_mem} - 1;
# update the total number of nodes in the queue.
$num_states_in_queue--;
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
to the goal node.
=back
For a given admissible heuristic function, it can be shown that A* search
is I<optimally efficient>, meaning that, in its calculation of the shortest
path, it expands fewer nodes in the search space than any other algorithm.
To be admissible, the heuristic I<h(n)> can never over-estimate the distance
from the node to the goal. Note that if the heuristic I<h(n)> is set to
zero, A* search reduces to I<Branch and Bound> search. If the cost-so-far
I<g(n)> is set to zero, A* reduces to I<Greedy Best-first> search (which is
neither complete nor optimal). If both I<g(n)> and I<h(n)> are set to zero,
the search becomes I<Breadth-first>, which is complete and optimal, but not
optimally efficient.
The space complexity of A* search is bounded by an exponential of the
branching factor of the search-space, by the length of the longest path
examined during the search. This is can be a problem particularly if the
branching factor is large, because the algorithm may run out of memory.
=head3 SMA* Search
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
}
return $most_frequent_letter_freq;
}
sub get_letters
{
my ($word) = @_;
my @letter_set = ();
my %letters_hash = ();
my @letters = split('', $word);
foreach my $element (@letters) { $letters_hash{$element}++ }
foreach my $element (keys %letters_hash)
{
push(@letter_set, $element);
}
return @letter_set;
}
{ my %memo_cache;
sub word_collision_memo
{
my ($word,
$sorted_letters_seen) = @_;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
@_, # Override previous attributes
};
return bless $self, $class;
}
##############################################
## methods to access per-object data
##
## With args, they set the value. Without
## any, they only retrieve it/them.
##############################################
sub start_word {
my $self = shift;
if (@_) { $self->{_start_word} = shift }
return $self->{_start_word};
}
sub word {
lib/AI/Pathfinding/SMAstar/Examples/WordObj.pm view on Meta::CPAN
my $self = {
_word => undef,
@_, # Override previous attributes
};
return bless $self, $class;
}
##############################################
## methods to access per-object data ##
## ##
## With args, they set the value. Without ##
## any, they only retrieve it/them. ##
##############################################
sub word {
my $self = shift;
if (@_) { $self->{_word} = shift }
return $self->{_word};
}
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
#
# path stuff
#
###########################################
_antecedent => undef, # pointer to the antecedent of this obj
_f_cost => undef, # g + h where g = cost so far, h = estimated cost to goal.
_forgotten_node_fcosts => [], # array to store fcosts of forgotten nodes
_forgotten_nodes_num => 0,
_forgotten_nodes_offsets => {},
_depth => 0, # depth used for memory-bounded search
_descendants_produced => [],
_descendant_index => undef,
_descendant_fcosts => [],
_descendants_on_queue => 0,
_descendands_deleted => 0,
_is_completed => 0,
_num_successors => undef,
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
my $fcost = $self->{_f_cost};
my $least_fcost2 = 99;
my $min = sub {
my ($n1, $n2) = @_;
return ($n1 < $n2 ? $n1 : $n2);
};
if($self->{_forgotten_nodes_num} != 0){
foreach my $ind (keys %{$self->{_forgotten_nodes_offsets}}){
my $cost = $self->{_forgotten_node_fcosts}->[$ind];
if($cost != -1 && $cost < $least_fcost2){
$least_fcost2 = $cost;
}
}
}
my $j = 0;
foreach my $fc (@{$self->{_descendant_fcosts}}){
if(defined($descendant_ind) && $j != $descendant_ind){
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
}
}
elsif($fc != -1 && $fc < $least_fcost2){
$least_fcost2 = $fc;
}
}
$j++;
}
# if no successors, this node cannot lead to
# goal, so set fcost to infinity.
if($self->{_num_successors} == 0){
$least_fcost2 = 99;
}
if($least_fcost2 != $fcost){
# setting need_fcost_change to 1
$self->need_fval_change(1);
my $antecedent = $self->{_antecedent};
# recurse on the antecedent
if($antecedent){
$antecedent->check_need_fval_change($least_fcost2, $descendant_index);
}
}
}
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
my $fcost = $self->{_f_cost};
my $least_fcost = 99;
my $min = sub {
my ($n1, $n2) = @_;
return ($n1 < $n2 ? $n1 : $n2);
};
if($self->{_forgotten_nodes_num} != 0){
foreach my $ind (keys %{$self->{_forgotten_nodes_offsets}}){
my $cost = $self->{_forgotten_node_fcosts}->[$ind];
if($cost != -1 && $cost < $least_fcost){
$least_fcost = $cost;
}
}
}
foreach my $fc (@{$self->{_descendant_fcosts}}){
if($fc != -1 && $fc < $least_fcost){
$least_fcost = $fc;
}
}
# if no successors, this node cannot lead to
# goal, so set fcost to infinity.
if($self->{_num_successors} == 0){
$least_fcost = 99;
}
if($least_fcost != $fcost){
# changing fcost from $self->{_f_cost} to $least_fcost
$self->{_f_cost} = $least_fcost;
my $antecedent = $self->{_antecedent};
if($antecedent){
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
my $already_produced_p = $self->{_descendants_produced}->[$i] || ($self->{_descendant_fcosts}->[$i] != -1);
if($already_produced_p){
# have already produced this descendant
$descendants_found++;
# found descendant in tree\n";
if($i == $num_successors - 1 && $descendants_deleted){
# !!! resetting iterator index. descendants have been deleted. clearing forgotten_fcosts on next expansion.
$iterator = $self->get_successors_iterator();
$self->{_iterator_index} = 0;
$i = 0;
# setting completed to 1 (true)
$self->is_completed(1);
next;
}
else{
$i++;
}
if($descendants_found == $num_successors){
# setting completed to 1.
$self->is_completed(1);
}
$next_descendant = undef; # found this one in list, so undef next descendant.
}
else{
# did not find descendant in descendant's list
if($i < $self->{_iterator_index} && $self->{_forgotten_nodes_num} != 0){
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
$self->{_iterator_index} = $i + 1;
if($self->{_iterator_index} == $self->{_num_successors}){
$iterator = $self->get_successors_iterator();
$self->{_iterator_index} = 0;
$i = 0;
# node is completed, setting completed to 1\n";
$self->is_completed(1);
}
# break out of while() loop
last;
}
}
if($i >= $num_successors - 1 && $descendants_deleted && $self->depth() == 0){
# root node. going to reset iterator index. descendants have been deleted. Also, will be
# clearing out forgotten_descendants fcost list, since those descendants will be re-generated anyway.
$iterator = $self->get_successors_iterator();
$self->{_iterator_index} = 0;
$i = 0;
# setting completed to 1
$self->is_completed(1);
}
if($next_descendant){
if($self->{_forgotten_node_fcosts}->[$next_descendant->{_descendant_index}] != -1){
# erase the index of this node in the forgotten_nodes list
$self->{_forgotten_node_fcosts}->[$next_descendant->{_descendant_index}] = -1;
# decrement the number of forgotten nodes
$self->{_forgotten_nodes_num} = $self->{_forgotten_nodes_num} - 1;
delete $self->{_forgotten_nodes_offsets}->{$next_descendant->{_descendant_index}};
}
}
else{
# no next successor found
$self->is_completed(1);
}
return $next_descendant;
}
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
print STDERR "-" x 80 . "\n";
print STDERR "-" x 80 . "\n";
diag("reading dictionary '$dictionary_file'");
eval{
($num_words, @words) = AI::Pathfinding::SMAstar::Examples::PalUtils::read_dictionary_filter_by_density($dictionary_file, $sparsity);
};
is( $@, '', '$@ is not set after object insert' );
diag("loaded words: '$num_words'");
isnt( $num_words, undef, 'num_words is $num_words');
%letter_freq = AI::Pathfinding::SMAstar::Examples::PalUtils::find_letter_frequencies(@words);
foreach my $w (@words){
( run in 1.476 second using v1.01-cache-2.11-cpan-49f99fa48dc )