SMA*

SMA* has the following properties

• It works with a heuristic, just as A*
• It is complete if the allowed memory is high enough to store the shallowest solution
• It is optimal if the allowed memory is high enough to store the shallowest optimal solution, otherwise it will return the best solution that fits in the allowed memory
• It avoids repeated states as long as the memory bound allows it
• It will use all memory available
• Enlarging the memory bound of the algorithm will only speed up the calculation
• When enough memory is available to contain the entire search tree, then calculation has an optimal speed

The implementation of Simple memory bounded A* is very similar to that of A*; the only difference is that nodes with the highest f-cost are pruned from the queue when there isn't any space left. Because those nodes are deleted, simple memory bounded A* has to remember the f-cost of the best forgotten child of the parent node. When it seems that all explored paths are worse than such a forgotten path, the path is regenerated.[1]

Pseudo code: <syntax highlight lang="pascal"> function simple memory bounded A*-star(problem): path

 queue: set of nodes, ordered by f-cost;

begin

 queue.insert(problem.root-node);

 while True do begin
   if queue.empty() then return failure; //there is no solution that fits in the given memory
   node := queue.begin(); // min-f-cost-node
   if problem.is-goal(node) then return success;
   
   s := next-successor(node)
   if !problem.is-goal(s) && depth(s) == max_depth then
       f(s) := inf; 
       // there is no memory left to go past s, so the entire path is useless
   else
       f(s) := max(f(node), g(s) + h(s));
       // f-value of the successor is the maximum of
       //      f-value of the parent and 
       //      heuristic of the successor + path length to the successor
   end if
   if no more successors then
      update f-cost of node and those of its ancestors if needed
   
   if node.successors ⊆ queue then queue.remove(node); 
   // all children have already been added to the queue via a shorter way
   if memory is full then begin
     bad Node := shallowest node with highest f-cost;
     for parent in bad Node.parents do begin
       parent.successors.remove(bad Node);
       if needed then queue.insert(parent); 
     end for
   end if

   queue.insert(s);
 end while

end </syntax highlight>