view release on metacpan or  search on metacpan

lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm  view on Meta::CPAN

	return $self_eval - $arg_obj_eval;
    }
}



sub compare_by_depth
{
    my ($self, $arg_obj) = @_;
    
    my $self_depth = $self->{_depth};
    my $argobj_depth = $arg_obj->{_depth};
    
    my $result = $self_depth - $argobj_depth;
    
    return $result;    
}



# compare_phrase_word_strings
#
# usage:  $phrase_obj->compare_phrase_word_strings($other_word_obj)
#
# Accepts another Phrase object as an argument.
# Returns 1 if greater than argument, 0 if equal, and -1 if 
# less than argument
sub compare_phrase_word_strings
{
    my ($self, $arg_obj) = @_;
   
    my $arg_phrase_plus_word = $arg_obj->{_phrase} . $arg_obj->{_word};          
    my $phrase_plus_word = $self->{_phrase} . $self->{_word};
    
    if($arg_phrase_plus_word gt $phrase_plus_word){
	return -1;
    }
    elsif($arg_phrase_plus_word eq $phrase_plus_word){
	return 0;
    }
    return 1;   
}



#----------------------------------------------------------------------------
# evaluation function f(n) = g(n) + h(n) where 
#
# g(n) = cost of path through this node
# h(n) = distance from this node to goal (optimistic)
#
# used for A* search.
#
sub evaluate
{    
    my ($min_num_letters) = @_;
    return sub{
		
	my ($self) = @_;

	# if fcost has already been calculated (or reassigned during a backup)
	# then return it.   otherwise calculate it
	my $fcost = $self->{_f_cost};
	if(defined($fcost)){	    
	    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;
	#my $total_cost = 0;  # greedy search (best-first search)	
	#my $distance_from_goal = 0; # branch and bound search.  optimistic/admissible.
        
        my $distance_from_goal = $min_num_letters - ($num_chars_so_far + $num_new_chars);  #1 optimistic/admissible

	my $evaluation = $total_cost + $distance_from_goal;	
	$self->{_f_cost} = $evaluation;

	return $evaluation;
    }
}

#-----------------------------------------------------------------------------
sub phrase_is_palindrome_min_num_chars
{
    my ($min_num_chars) = @_;
    
    return sub{
	my ($self) = @_;
	
	my $phrase = $self->{_phrase};
	
	if(AI::Pathfinding::SMAstar::Examples::PalUtils::is_palindrome($phrase) && 
	   (AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_pal($phrase) >= $min_num_chars)){
	    return 1;
	}
	else{ 
	    return 0; 
	}
    }
}

    
    
#----------------------------------------------------------------------------
sub letters_seen_so_far