SMA*
SMA* o el algoritmo simplificado de memoria restringida A* es un algoritmo de ruta más corta basado en el algoritmo A* . La principal ventaja de SMA* es que usa memoria limitada, mientras que el algoritmo A* puede requerir memoria exponencial. Todas las demás características de SMA* se heredan de A* .
Propiedades
SMA* tiene las siguientes propiedades:
- SMA* funciona con heurística como A* .
- SMA* está completo si la memoria permitida es lo suficientemente grande para contener la solución más superficial.
- Es óptimo si la memoria permitida es lo suficientemente grande como para almacenar la solución óptima más superficial; de lo contrario, se devolverá la mejor solución que se ajuste a la memoria permitida.
- SMA* evita estados repetidos siempre que lo permita la memoria limitada.
- Se utilizará toda la memoria disponible.
- Aumentar el tamaño de la memoria del algoritmo solo acelerará el cálculo.
- Cuando hay suficiente memoria disponible para adaptarse a todo el árbol de búsqueda, el cálculo se encuentra en su velocidad óptima.
Implementación
La implementación de SMA* es muy similar a la implementación de A* , con la única diferencia de que cuando no queda espacio, los nodos con el costo f más alto se eliminan de la cola. A medida que se eliminan estos nodos, SMA* también debe recordar el costo f del mejor nodo secundario olvidado con el nodo ancestro. Cuando parece que todos los caminos explorados son peores que este olvidado, se recrea el camino [1] .
Pseudocódigo
función SMA - star ( problema ) : ruta
cola : conjunto de nodos , ordenados por f - cost ;
cola de inicio
. insertar ( problema . raíz - nodo ) ;
mientras que True comienza si la cola . vacío () luego devuelve el error ; // no hay solución que quepa en este nodo de memoria := cola . inicio () ; // nodo de coste f mínimo si hay problema . es - objetivo ( nodo ) luego devuelve éxito ;
s : = sucesor siguiente ( nodo ) if ! problema _ es - objetivo ( s ) && profundidad ( s ) == profundidad_máxima luego f ( s ) := inf ; // no queda memoria para pasar s, por lo que toda la ruta es inútil si no f ( s ) := max ( f ( nodo ) , g ( s ) + h ( s )) ; // valor f descendiente: valor f máximo del antepasado y // heurística descendiente + longitud de ruta descendiente endif si no hay más sucesores , actualice f : costo del nodo y los de sus antepasados si es necesario
si nodo . sucesores ⊆ cola luego cola . eliminar ( nodo ) ;
// todos los hijos ya han sido agregados a la cola de una manera más corta
si la memoria está llena , entonces comienza
badNode := el nodo menos profundo con el costo f más alto ; para padre en badNode . los padres comienzan padre . sucesores _ eliminar ( nodomalo ) ; si es necesario , haga cola . insertar ( padre ) ; endfor endif
cola _ insertar ( s ) ;
terminar mientras
termina
Notas
- ↑ Stuart Russell (1992). B. Neumann, ed. “ Métodos de búsqueda eficientes con memoria limitada ”. Viena ( Austria ): John Wylie & Sons , Nueva York ( NY ): 1-5. CiteSeerX 10.1.1.105.7839 .