SMA*
SMA*
- SMA* or Simplified Memory Bounded A*** is a shortest path algorithm based on the [[a*-search-algorithm|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*.
Process ## Properties 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
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: <syntaxhighlight 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 </syntaxhighlight>