AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
Revision history for Perl extension AI::Pathfinding::SMAstar.
0.01 Tue Feb 23 12:06:47 2010
- original version; created by h2xs 1.23 with options
-XAn AI::Pathfinding::SMAstar
0.02 Fri Feb 25 11:17:01 2010
- updated pod documentation
0.03 Sun Feb 28 12:26:58 2010
- updated pod documentation
0.04 Tue Mar 2 13:17:53 2010
- updated error handling in add_start_state method
);
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:
** State evaluation function (_state_eval_func above)
DESCRIPTION
Overview
Memory-bounded A* search (or SMA* search) addresses some of the limitations of
conventional A* search, by bounding the amount of space required to perform a
shortest-path search. This module is an implementation of SMA*, which was first
introduced by Stuart Russell in 1992. SMA* is a more efficient variation of the
original MA* search introduced by Chakrabarti et al. in 1989. See references below.
Motivation and Comparison to A* Search
A* search
A* Search is an optimal and complete algorithm for computing a sequence of
operations leading from a system's start-state (node) to a specified goal. In
this context, optimal means that A* search will return the shortest possible
sequence of operations (path) leading to the goal, and complete means that A* will
always find a path to the goal if such a path exists.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
);
In the example above, a hypothetical object, C<FrontierObj>, is used to
represent a state, or I<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 I<node> is, in your search space (or I<point>, or I<state>).
A common example used for informed search methods, and one that is used in Russell's
original paper, is optimal puzzle solving, such as solving an 8 or 15-tile puzzle
in the least number of moves. If trying to solve such a puzzle, a I<node> in the
search space could be defined as a configuration of that puzzle (a paricular
ordering of the tiles).
There is an example provided in the /t directory of this module's distribution,
where SMA* is applied to the problem of finding the shortest palindrome that
contains a minimum number of letters specified, over a given list of words.
Once you have a definition and representation of a node in your search space, SMA*
search requires the following functions to work:
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=head1 DESCRIPTION
=head2 Overview
Simplified Memory-bounded A* search (or SMA* search) addresses some of the
limitations of conventional A* search, by bounding the amount of space required
to perform a shortest-path search. This module is an implementation of
SMA*, which was first introduced by Stuart Russell in 1992. SMA* is a simpler,
more efficient variation of the original MA* search introduced by P. Chakrabarti
et al. in 1989 (see references below).
=head2 Motivation and Comparison to A* Search
=head3 A* search
A* Search is an I<optimal> and I<complete> algorithm for computing a sequence of
( run in 0.249 second using v1.01-cache-2.11-cpan-f985c23238c )