SMA*
# SMA*

SMA* o o simplificado de memoria acotada A * es un algoritmo del camino más corto basada en el algoritmo A*. La principal ventaja de SMA * es que utiliza una memoria limitada, mientras que el algoritmo A * puede ser que necesite memoria exponencial. Todas las demás características de SMA * son heredados de A *.

## Proceso

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 $f$ para cada nodo. El nodo $x$ almacena un valor de $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 $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 $f$ por lo menos tan alta como la de sus sucesores. Además, el nodo almacena el valor $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 $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.

## Propiedades

SMA * tiene las siguientes propiedades

* Funciona con una heurística, al igual que A *
* Es completo si la memoria permitido es lo suficientemente alta para almacenar la solución menos profunda
* Es óptimo si la memoria permitido es lo suficientemente alta como para almacenar la solución óptima menos profunda, de lo contrario volverá la mejor solución que se ajusta en la memoria permitido
* Evita estados repite mientras la memoria unida permite
* Se utilizará toda la memoria disponible
* La ampliación de la memoria ligada del algoritmo sólo acelerará el cálculo
* Cuando hay suficiente memoria disponible para contener todo el árbol de búsqueda, a continuación, el cálculo tiene una velocidad óptima

## Implementación

La aplicación de SMA * es muy similar a la de A *,la única diferencia es que cuando no hay ningún espacio a la izquierda, los nodos con el más alto f costo se podan de la cola. Debido a que se eliminan los nodos, la SMA * también tiene que recordar el f - coste del niño mejor olvidado con el nodo padre.

Pseudo código:

