SMA*

The Simplified Memory - Bounded Algorithm ( SMA *) is an algorithm for memory optimized search in trees. It is a special case of the A * algorithm to compute a shortest path.

If the area to be examined tree is searched with a greedy algorithm and not enough memory is available to hold the complete tree in memory, then uneven nodes or subtrees are initially ignored. In the predecessor node information on the cost of the subtree are stored. If no better result is achieved in the remaining part of trees, the calculation of the low- forgotten node can be resumed. The savings effect on memory consumption due to the fact that very promising solution variants are not initially kept in memory.

  • Algorithm