SMA* or Simplified Memory Bounded A* is a shortest path algorithm based on the A* algorithm. The main advantage of SMA* is that it uses a bounded memory, while the A* algorithm might need exponential memory. All other characteristics of SMA* are inherited from A*.
Properties.
SMA* has the following properties
Implementation.
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.
Pseudo code:
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) &amp;&amp; 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
References.
 ;templatestyles src="Reflist/styles.css" / ;