SMA *

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado.
Buscar fuentes: "SMA *" - noticias · periódicos · libros · académico · JSTOR ( marzo de 2015 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

Este artículo puede ser demasiado técnico para que la mayoría de los lectores lo comprendan . Ayude a mejorarlo para que sea comprensible para los no expertos , sin eliminar los detalles técnicos. ( Noviembre de 2009 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Algoritmos de búsqueda de gráficos y árboles
α – β A* B* Retroceso Haz Bellman – Ford Mejor primero Bidireccional Borůvka Rama y encuadernado BFS Museo Británico D* DFS Dijkstra Edmonds Floyd – Warshall Búsqueda de franjas Montañismo IDA * Profundización iterativa Johnson Punto de salto Kruskal BFS lexicográfico LPA * Remilgado SMA *
Listados
Algoritmos de grafos Algoritmos de búsqueda Lista de algoritmos de gráficos
Temas relacionados
Programación dinámica Recorrido del gráfico Cruce de árboles Buscar juegos Coloración gráfica
v t mi

SMA * o Simplified Memory Bounded A * es un algoritmo de ruta más corto basado en el algoritmo A * . La principal ventaja de SMA * es que utiliza una memoria limitada, mientras que el algoritmo A * puede necesitar una memoria exponencial. Todas las demás características de SMA * se heredan de A *.

Proceso

Propiedades

SMA * tiene las siguientes propiedades

Funciona con una heurística , al igual que A *
Está completo si la memoria permitida es lo suficientemente alta como para almacenar la solución más superficial.
Es óptimo si la memoria permitida es lo suficientemente alta para almacenar la solución óptima más superficial; de lo contrario, devolverá la mejor solución que se ajuste a la memoria permitida.
Evita estados repetidos siempre que el límite de la memoria lo permita.
Utilizará toda la memoria disponible
Ampliar el límite de memoria del algoritmo solo acelerará el cálculo
Cuando hay suficiente memoria disponible para contener todo el árbol de búsqueda, el cálculo tiene una velocidad óptima.

Implementación

La implementación de SMA * es muy similar a la de A *, la única diferencia es que cuando no queda espacio, los nodos con el costo f más alto se eliminan de la cola. Debido a que esos nodos se eliminan, el SMA * también debe recordar el costo-f del mejor hijo olvidado con el nodo principal. Cuando parece que todos los caminos explorados son peores que un camino olvidado, el camino se vuelve a generar. ^[1]

Pseudo código:

función  SMA - estrella ( problema ) :  cola de ruta  : conjunto de nodos , ordenados por f - costo ; comenzar la cola . insertar ( problema . raíz - nodo ) ;        mientras que  La verdadera  do  comenzar  si  la cola . vacío ()  luego  devuelve el  error ;  // no hay una solución que quepa en el  nodo de  memoria dado : =  cola . comenzar () ;  // min-f-cost-node  si hay  algún problema . es - objetivo ( nodo )  luego  devuelve  éxito ; s  : =  siguiente - sucesor ( nodo )  si  ! problema . es - meta ( s )  &&  profundidad ( s )  ==  max_depth  luego  f ( s )  : =  inf ;  // no queda memoria para pasar s, por lo que toda la ruta es inútil; de lo  contrario,  f ( s )  : =  max ( f ( nodo ) ,  g ( s )  + h ( s )) ;  // valor f del sucesor es el máximo de  // valor f del padre y  // heurística del sucesor + longitud de la ruta al sucesor  endif  si  no hay  más  sucesores,  entonces  actualice  f - costo  del  nodo  y  los  de  sus  ancestros  si es  necesario si  nodo . sucesores  ⊆  cola y  luego  cola . eliminar ( nodo ) ;  // todos los niños ya se han añadido a la cola de a través de una forma más corta  si  la memoria  está  llena  y luego  comienzan  badNode  : =  menos profunda  nodo  con  mayor  f - costo ;  para el  padre  en  badNode . los padres  no  empiezan  padres . sucesores . eliminar ( badNode );  si es  necesario  ,  haga cola . insertar ( padre ) ;  endfor  endif cola . insertar ( s ) ;  al final mientras que al final

Referencias

^ Russell, S. (1992). "Métodos de búsqueda eficientes limitados a la memoria". En Neumann, B. (ed.). Actas de la X Conferencia Europea de Inteligencia Artificial . Viena, Austria: John Wiley & Sons, Nueva York, NY. págs. 1-5. CiteSeerX 10.1.1.105.7839 .

[1] Russell, S. (1992). "Métodos de búsqueda eficientes limitados a la memoria". En Neumann, B. (ed.). Actas de la X Conferencia Europea de Inteligencia Artificial . Viena, Austria: John Wiley & Sons, Nueva York, NY. págs. 1-5. CiteSeerX 10.1.1.105.7839 .