SMA*

SMA*, short for Simplified Memory Bounded A*, is a shortest path algorithm based on the A* algorithm. Its main advantage is that it uses bounded memory, whereas A* can need exponential memory, and all its other characteristics are inherited from A*. It works with a heuristic, just as A* does. It is complete if the allowed memory is high enough to store the shallowest solution, and optimal if the memory is high enough to store the shallowest optimal solution; otherwise it returns the best solution that fits in the memory it is given. It avoids repeated states as long as the memory bound allows, and it uses all the memory available. Its implementation is very close to that of A*, except that when no space is left the nodes with the highest f-cost are pruned from the queue, and the parent remembers the f-cost of its best forgotten child so a path can be regenerated if every explored path looks worse.