view release on metacpan or  search on metacpan

README  view on Meta::CPAN

It can be shown that of the memory-bounded variations of A* search, such MA*, 
IDA*, Iterative Expansion, etc., SMA* search expands the least number of nodes 
on average. However, for certain classes of problems, guaranteeing optimality 
can be costly. This is particularly true in solution spaces where:

    * the branching factor of the search space is large
    * there are multiple equivalent optimal solutions (or shortest paths)

For solution spaces with these characteristics, stochastic methods or 
approximation algorithms such as Simulated Annealing can provide a massive 
reduction in time and space requirements, while introducing a tunable 
probability of producing a sub-optimal solution.



METHODS

new()

Creates a new SMA* search object.

start_search()

Initiates a memory-bounded search. You must pass a log_function for recording 
current status, a function that returns a *unique* string representing a node in 
the search-space, a maximum number of expanded states to store in the queue, and a 
maximum cost value, beyond which the search will cease.

state_eval_func()

Sets/gets the function that returns the cost of this node in the 
search space.

state_goal_p_func()

Sets/gets the function that returns 1 if the node is a goal node, or 
0 otherwise.

state_num_successors_func()

Sets/gets the function that returns the number of successors of 
this node.

state_successors_iterator()

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

Chakrabarti, P. P., Ghose, S., Acharya, A., and de Sarkar, S. C. (1989) "Heuristic 
search in restricted memory" Artificial Intelligence Journal, 41, pp. 197-221.

AUTHOR

Matthias Beebe, <mbeebe@cpan.org>


INSTALLATION

To install this module type the following:

   perl Makefile.PL
   make
   make test
   make install

DEPENDENCIES

This module requires these other modules and libraries:

  Tree::AVL
  Test::More

COPYRIGHT AND LICENCE

Copyright (C) 2010 by Matthias Beebe

This library is free software; you can redistribute it and/or modify it 
under the same terms as Perl itself, either Perl version 5.10.0 or, at 
your option, any later version of Perl 5 you may have available.