view release on metacpan or  search on metacpan

README  view on Meta::CPAN

AI-Pathfinding-SMAstar version 0.07
===================================

NAME

AI::Pathfinding::SMAstar - Memory-bounded A* Search

SYNOPSIS

 use AI::Pathfinding::SMAstar;

EXAMPLE

 ##################################################################
 #
 # This example uses a hypothetical object called FrontierObj, and
 # shows the functions that FrontierObj must feature in order to 
 # perform a path search in a solution-space populated by 
 # FrontierObj objects.
 #
 ##################################################################

 my $smastar = AI::Pathfinding::SMAstar->new(
        # evaluates f(n) = g(n) + h(n), returns a number
        _state_eval_func           => \&FrontierObj::evaluate,

        # when called on a node, returns 1 if it is a goal
        _state_goal_p_func         => \&FrontierObj::goal_test,

        # must return the number of successors of a node
        _state_num_successors_func => \&FrontierObj::get_num_successors,

        # must return *one* successor at a time
        _state_successors_iterator => \&FrontierObj::get_successors_iterator,

        # can be any suitable string representation 
        _state_get_data_func       => \&FrontierObj::string_representation,

        # gets called once per iteration, useful for showing algorithm progress
        _show_prog_func            => \&FrontierObj::progress_callback,      
    );

 # you can start the search from multiple start-states
 # Add the initial states to the smastar object before starting the search.
 foreach my $frontierObj (@start_states){
    $smastar->add_start_state($frontierObj);
 }

 # Start the search.  If successful, frontierGoalObj will contain the 
 # goal node.   The optimal path to the goal node will be encoded in the 
 # ancestry of the goal node.   $frontierGoalObj->antecedent() contains
 # the goal object's parent, and so forth back to the start state.
 my $frontierGoalObj = $smastar->start_search(
    \&log_function,       # returns a string used for logging progress
    \&str_function,       # returns a string used to *uniquely* identify a node 
    $max_states_in_queue, # indicate the maximum states allowed in memory
    $MAX_COST,            # indicate the maximum cost allowed in search
    );

Explanation

In the example above, a hypothetical object, FrontierObj, is used to 
represent a node in your search space. To use SMA* search to find a shortest 
path from a starting node to a goal in your search space, you must define what 
a node is, in your search space (or point, or state).

A common example used for informed search methods, and one that is 
used in Russell's original paper, is a N-puzzle, such as an 8-puzzle or 
15-puzzle. If trying to solve such a puzzle, a node in the search space 
could be defined as a particular configuration of that puzzle.    In the 
/t directory of this module's distribution, SMA* is applied to the problem 
of finding the shortest palindrome that contains a minimum number of letters 
specified, over a given lexicon of words.

Once you have a definition and representation of a node in your search space, SMA* 
search requires the following functions to work: