AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
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.
SMA* Search
SMA* search addresses the possibility of running out of memory during search by
pruning the portion of the search-space that is being examined. It relies on the
pathmax, or monotonicity constraint on f(n) to remove the shallowest of the
highest-cost nodes from the search queue when there is no memory left to
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
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
Like A* search, SMA* search is an optimal and complete algorithm for finding
a least-cost path. Unlike A*, SMA* will not run out of memory, I<unless the size
of the shortest path exceeds the amount of space in available memory>.
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
use Tree::AVL;
use AI::Pathfinding::SMAstar::Examples::WordObj;
package AI::Pathfinding::SMAstar::Examples::PalUtils;
my $max_nodes_in_mem = 0;
sub length_no_spaces
{
my ($w) = @_;
$w =~ s/\ //g;
return length($w);
}
sub get_word_number_of_letters_that_have_repeats
{
my ($word) = @_;
my @letters = split('', $word);
my %letters_hash = ();
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
foreach my $l (@letters)
{
$letters_freq{$l}++;
}
}
return %letters_freq;
}
sub collisions_per_length
{
my ($w, $phrase) = @_;
if(!$w){ $w = "" }
if(!$phrase){ $phrase = "" }
my $length = length($w);
$phrase =~ s/ //g;
my @letters = split('', $w);
my @letters_seen = split('', $phrase);
my $collisions = 0;
foreach my $l (@letters){
foreach my $ls (@letters_seen){
if($l eq $ls){
$collisions++;
}
}
}
my $val = $collisions/$length;
return $val;
}
sub get_word_sparsity
{
my ($word) = @_;
my $length = length($word);
my $num_letters = num_chars_in_word_memo($word);
my $sparseness = $length - $num_letters;
return $sparseness;
}
{ my %memo_cache;
sub get_word_sparsity_memo
{
my ($word) = @_;
if($memo_cache{$word}){
return $memo_cache{$word};
}
else{
my $length = length($word);
my $num_letters = num_chars_in_word_memo($word);
my $sparseness = $length - $num_letters;
$memo_cache{$word} = $sparseness;
return $sparseness;
}
}
}
# get the highest number of times a letter
# is repeated within a word.
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
}
sub match_remainder
{
my ($word1, $word2) = @_;
$word1 =~ s/\ //g;
$word2 =~ s/\ //g;
my $len1 = length($word1);
my $len2 = length($word2);
if(index($word1, $word2) != 0)
{
return;
}
my $remainder_word = substr($word1, $len2);
return $remainder_word;
}
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
my $cache_key = $word . $dictionary;
my $cached_vals = $memo_hash_ref->{$cache_key};
if($cached_vals1){
#print $spaces . "DING DING DING. cache hit!\n";
return @$cached_vals;
}
else{
for(my $i = 1; $i < length($word); $i++){
push(@words, substr($word, 0, $i));
}
foreach my $substring (@words){
#print "looking for matches on: \"$substring\"\n";
my $cand = AI::Pathfinding::SMAstar::Examples::WordObj->new(
_word => $substring
);
my $match_word = $dictionary->lookup($cand, \&AI::Pathfinding::SMAstar::Examples::WordObj::compare);
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
}
sub get_substrs
{
my ($word, $dictionary) = @_;
my @words;
my @matches;
for(my $i = 1; $i < length($word); $i++){
push(@words, substr($word, 0, $i));
}
foreach my $substring (@words){
#print "looking for matches on: \"$substring\"\n";
my $cand = AI::Pathfinding::SMAstar::Examples::WordObj->new(
_word => $substring
);
my $match_word = $dictionary->lookup($cand, \&AI::Pathfinding::SMAstar::Examples::WordObj::compare);
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
}
{my %memo_cache;
sub num_chars_in_pal
{
my ($pal) = @_;
my $num_keys;
$pal =~ s/\ //g;
my $length = length($pal);
my $first_half = substr($pal, 0, $length/2 + 1);
if($memo_cache{$first_half}){
return $memo_cache{$first_half};
}
else{
my %hash;
@hash{ split '', $first_half } = 1;
$num_keys = keys(%hash);
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
return $fcost;
}
my $word = $self->{_start_word};
my $cost = $self->{_cost};
my $cost_so_far = $self->{_cost_so_far};
my $num_new_chars = $self->{_num_new_chars};
my $num_chars_so_far = $self->{_num_chars_so_far};
my $phrase = defined($self->{_phrase}) ? $self->{_phrase} : "";
my $len_phrase = length($phrase);
my $phrase_num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word($phrase);
my $ratio = 0;
if($phrase_num_chars){
$ratio = $len_phrase/$phrase_num_chars;
}
#my $total_cost = $cost_so_far + $cost;
my $total_cost = $cost_so_far + $cost + $ratio;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $repeated_pal_hash_ref = $phrase_obj->{_repeated_pal_hash_ref};
my $letters_seen = $phrase_obj->{_letters_seen};
my $cost = $phrase_obj->{_cost};
my $cost_so_far = $phrase_obj->{_cost_so_far};
my $num_chars_so_far = $phrase_obj->{_num_chars_so_far};
my $no_match_remainder = $phrase_obj->{_no_match_remainder};
my $depth = $phrase_obj->{_depth};
my $direction = $phrase_obj->{_dir};
my $word = $phrase_obj->{_start_word};
my $whole_word = $phrase_obj->{_cand};
my $len_whole_word = defined($whole_word) ? length($whole_word) : 0;
my $rev_word = reverse($word);
my $len_word = length($word);
my @cands;
my @descendants;
if($direction == 0){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($word, $dictionary, $dictionary_rev);
}
elsif($direction == 1){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_right($word, $dictionary, $dictionary_rev);
}
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
$antecedent_dir = $antecedent->{_dir};
}
}
if($repeated_word_p || $w eq $word){
goto LABEL1;
#next; #skip this word, we are already looking at it
}
#----------------Compute the Cost-------------------------------------------
my $len_w = length($w);
my $collisions_per_length = AI::Pathfinding::SMAstar::Examples::PalUtils::collisions_per_length($w, $phrase_obj->{_phrase});
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity_memo($w);
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word_memo($w);
my ($word_intersect, @differences) = AI::Pathfinding::SMAstar::Examples::PalUtils::word_collision($w,
\@sorted_letters_seen);
my $num_new_chars = $num_chars - $word_intersect;
#my $newcost = $collisions_per_length + $sparsity;
my $newcost = $collisions_per_length + $len_w;
my $new_cost_so_far = $cost + $cost_so_far;
#---------------------------------------------------------------------------
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
#_words_w_cands_list => \@words_to_make_phrases,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
_dictionary_rev => $dictionary_rev,
_start_word => $w,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
}
else{
#flag this candidate as already having been tested (below).
$repeated_pal_hash_ref->{$repeated_pal_hash_key} = $depth;
}
}
#--------------------------------------------------------------------------
#--------------------------------------------------------------------------
my $len_c = length($c);
my $rev_c = reverse($c);
my $word_remainder;
if($len_c < $len_word){
$word_remainder = $c;
}
elsif($len_c > $len_word){
$word_remainder = $word;
}
my $rev_word_remainder = reverse($word);
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
$match_remainder = AI::Pathfinding::SMAstar::Examples::PalUtils::match_remainder($rev_word, $c);
$match_remainder = reverse($match_remainder);
$new_direction = 1;
}
elsif($len_c > $len_word){
$match_remainder = AI::Pathfinding::SMAstar::Examples::PalUtils::match_remainder($c, $rev_word);
$new_direction = 0;
}
}
$len_match_remainder = defined($match_remainder) ? length($match_remainder) : 0;
#----------------Compute the Cost-------------------------------------------
if($len_c < $len_word){
$num_new_chars = 0;
$newcost = 0; # new candidate is a (reversed) substring of word
$new_cost_so_far = $cost + $cost_so_far;
}
elsif($len_c > $len_word){
#if($len_c != $len_word){
my $collisions_per_length = AI::Pathfinding::SMAstar::Examples::PalUtils::collisions_per_length($match_remainder, $phrase_obj->{_phrase});
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word_memo($match_remainder);
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity_memo($match_remainder);
my ($word_intersect, @differences) = AI::Pathfinding::SMAstar::Examples::PalUtils::word_collision_memo($match_remainder,
\@sorted_letters_seen);
$num_new_chars = $num_chars - $word_intersect;
#$newcost = $sparsity + $collisions_per_length;
$newcost = $collisions_per_length + $len_match_remainder;
$new_cost_so_far = $cost + $cost_so_far;
}
#---------------------------------------------------------------------------
if($match_remainder){ # there is a length difference between the candidate and this word.
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
_dictionary_rev => $dictionary_rev,
_start_word => $match_remainder,
_cand => $c,
_word => $whole_word,
_predecessor => $phrase_obj,
_dir => $new_direction,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
$antecedent_dir = $antecedent->{_dir};
}
}
if($repeated_word_p || $w eq $word){
goto LABEL1;
#next; #skip this word, we are already looking at it
}
#----------------Compute the Cost-------------------------------------------
my $len_w = length($w);
my $collisions_per_length = AI::Pathfinding::SMAstar::Examples::PalUtils::collisions_per_length($w, $phrase_obj->{_phrase});
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity_memo($w);
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word_memo($w);
my ($word_intersect, @differences) = AI::Pathfinding::SMAstar::Examples::PalUtils::word_collision_memo($w,
\@sorted_letters_seen);
my $num_new_chars = $num_chars - $word_intersect;
#my $newcost = $collisions_per_length + $sparsity;
my $newcost = $collisions_per_length + $len_w;
my $new_cost_so_far = $cost + $cost_so_far;
#---------------------------------------------------------------------------
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
_dictionary_rev => $dictionary_rev,
_start_word => $w,
_cand => $c,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $letters_seen = $phrase_obj->{_letters_seen};
my $cost = $phrase_obj->{_cost};
my $cost_so_far = $phrase_obj->{_cost_so_far};
my $num_chars_so_far = $phrase_obj->{_num_chars_so_far};
my $no_match_remainder = $phrase_obj->{_no_match_remainder};
my $depth = $phrase_obj->{_depth};
my $direction = $phrase_obj->{_dir};
my $word = $phrase_obj->{_start_word};
my $whole_word = $phrase_obj->{_cand};
my $len_word = length($word);
my @cands;
my @descendants;
if($direction == 0){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($word, $dictionary, $dictionary_rev);
}
elsif($direction == 1){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_right($word, $dictionary, $dictionary_rev);
}
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
}
else{
#flag this candidate as already having been tested (below).
$repeated_pal_hash_ref->{$repeated_pal_hash_key} = $depth;
}
}
#--------------------------------------------------------------------------
#--------------------------------------------------------------------------
my $len_c = length($c);
my $rev_c = reverse($c);
my $word_remainder;
if($len_c < $len_word){
$word_remainder = $c;
}
elsif($len_c > $len_word){
$word_remainder = $word;
}
my $rev_word_remainder = reverse($word);
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $match_remainder;
my $len_match_remainder;
if($len_c != $len_word){
$match_remainder = 1;
}
if($match_remainder){ # there is a length difference between the candidate and this word.
$num_successors++;
}
else{
#
# There is no match_remainder, so this candidate is the reverse
# of $word, or the phrase built so far is an "even" palindrome,
# i.e. it has a word boundary (space) in the middle.
#
#
# This is a special case since there is no match remainder.
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $letters_seen = $phrase_obj->{_letters_seen};
my $cost = $phrase_obj->{_cost};
my $cost_so_far = $phrase_obj->{_cost_so_far};
my $num_chars_so_far = $phrase_obj->{_num_chars_so_far};
my $no_match_remainder = $phrase_obj->{_no_match_remainder};
my $depth = $phrase_obj->{_depth};
my $direction = $phrase_obj->{_dir};
my $word = $phrase_obj->{_start_word};
my $whole_word = $phrase_obj->{_cand};
my $len_word = length($word);
my @cands;
my @descendants;
if($direction == 0){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($word, $dictionary, $dictionary_rev);
}
elsif($direction == 1){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_right($word, $dictionary, $dictionary_rev);
}
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
}
else{
#flag this candidate as already having been tested (below).
$repeated_pal_hash_ref->{$repeated_pal_hash_key} = $depth;
}
}
#--------------------------------------------------------------------------
#--------------------------------------------------------------------------
my $len_c = length($c);
my $rev_c = reverse($c);
my $word_remainder;
if($len_c < $len_word){
$word_remainder = $c;
}
elsif($len_c > $len_word){
$word_remainder = $word;
}
my $rev_word_remainder = reverse($word);
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
my $match_remainder;
my $len_match_remainder;
if($len_c != $len_word){
$match_remainder = 1;
}
if($match_remainder){ # there is a length difference between the candidate and this word.
return 1;
}
else{
#
# There is no match_remainder, so this candidate is the reverse
# of $word, or the phrase built so far is an "even" palindrome,
# i.e. it has a word boundary (space) in the middle.
#
#
# This is a special case since there is no match remainder.
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
my $caching;
my @words;
my @words_w_cands;
my @word_objs;
my $num_word_objs;
my @rev_word_objs;
my $num_words;
my $sparsity;
my $max_states_in_queue;
my %letter_freq;
my $max_word_length = 0;
my $MAX_COST = 99;
#my $collisions_per_length = PalUtils::collisions_per_length("ocid", "abo gad abalones rot abdicators enol aba dagoba");
#print "collisions: $collisions_per_length\n";
#exit;
$dictionary_file = 't/test8.lst';
$min_letters = 4;
$sparsity = 2;
$max_states_in_queue = 4;
diag("\ncreating AVL trees");
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
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){
my $length = length($w);
if($length > $max_word_length){
$max_word_length = $length;
}
}
$num_words_filtered = @words;
diag("$num_words words in the currently loaded dictionary. Minimum letters specified = $min_letters");
diag("$num_words_filtered words that meet the initial sparsity constraint max_sparsity = $sparsity.");
if(!@words){
print STDERR "no words to process. exiting\n";
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
#_show_prog_func => \&AI::Pathfinding::SMAstar::Examples::PalUtils::show_progress_so_far,
),
'created smastar');
diag("smastar object created");
foreach my $word (@words_w_cands){
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity($word);
my $len_word = length($word);
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word($word);
my $cost = $sparsity + $len_word;
my $phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => \@words,
_words_w_cands_list => \@words_w_cands,
_dictionary => $avltree,
_dictionary_rev => $avltree_rev,
_start_word => $word,
_word => $word,
_cost => $cost,
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
$evaluation = AI::Pathfinding::SMAstar::Path::fcost($path_obj);
$depth = $path_obj->{_depth};
$num_chars_so_far = sprintf("%02d", $num_chars_so_far);
$num_new_chars = sprintf("%02d", $num_new_chars);
$cost = sprintf("%02d", $cost);
$cost_so_far = sprintf("%02d", $cost_so_far);
$depth = sprintf("%02d", $depth);
my $specifier = "%" . $max_word_length . "s";
$str = sprintf($specifier, $str);
$evaluation = sprintf("%04f", $evaluation);
$letters_seen_str = sprintf("%26s", $letters_seen_str);
my $log_str = "";
$log_str = $log_str . "depth: $depth, ";
$log_str = $log_str . "eval: $evaluation, ";
$log_str = $log_str . "letters: '$letters_seen_str', ";
( run in 0.562 second using v1.01-cache-2.11-cpan-65fba6d93b7 )