SMA*

Como A *, se expande las ramas más prometedoras de acuerdo con la heurística. Lo que diferencia a SMA * aparte es que poda nodos cuya expansión se ha revelado menos prometedor de lo esperado. El enfoque permite que el algoritmo para explorar ramas y dar marcha atrás para explorar otras ramas.

La expansión y la poda de los nodos es impulsado por mantener dos valores de ${\displaystyle f}$ para cada nodo. El nodo ${\displaystyle x}$ almacena un valor de ${\displaystyle f(x)}$ que estima el costo de llegar a la meta mediante la adopción de un camino a través de ese nodo. Cuanto menor sea el valor, mayor es la prioridad. Al igual que en A * este valor es inicializado para ${\displaystyle h(x)+g(x)}$, pero entonces será actualizado para reflejar los cambios en esta estimación cuando sus hijos se expanden. Un nodo completamente expandido tendrá un valor de ${\displaystyle f}$ por lo menos tan alta como la de sus sucesores. Además, el nodo almacena el valor ${\displaystyle f}$ del sucesor mejor olvidado. Este valor se restablece si el sucesor olvidado se revela para ser el sucesor más prometedor.

Comenzando con el primer nodo, mantiene ABIERTO, ordenó lexicográficamente por ${\displaystyle f}$ y profundidad. Al elegir un nodo para expandir, elige la mejor de acuerdo a ese orden. Al seleccionar un nodo de podar, elige el peor.