IDA*

El método IDA* (Iterative Deepening A*) es un algoritmo de búsqueda en grafos creado por Korf en 1985. Este método combina la profundización iterativa con una variante del Depth-First Search (DFS). La idea central es utilizar información heurística disponible para decidir qué nodo explorar y hasta qué punto avanzar en cada ciclo del proceso.

En este algoritmo, cada iteración se asemeja a una búsqueda en profundidad, donde la profundidad está determinada por la información heurística. La búsqueda se detiene cuando se alcanza un nodo cuyo costo total de la función heurística de evaluación f=g+h es mayor que el límite de coste actual f. En cada iteración, se revisan los nodos con un costo de f menor o igual al límite actual.

El algoritmo

Para desarrollar IDA* se utiliza el planteamiento heurístico de A* que tiene una forma de búsqueda semejante al BFS y se combina con IDA*. Se incrementa con cada iteración no la profundidad de niveles sino el costo total del camino y con el comportamiento siguiente: "en cada iteración se realizará un DFS que se interrumpirá si el costo total (g + h) excede una variable memoria dada. Esta memoria comienza en el costo estimado del primer estado y se incrementa por cada iteración del algoritmo. En cada iteración la memoria que se utiliza para la próxima iteración es el mínimo de los costos de todos los valores superiores a la memoria actual”.^[1] Explicando el algoritmo debe recalcarse que sigue conservándose la condición hˆ(n) ≤ h(n) para que sea admisible hˆ(n). El autor de IDA* además plantea que el algoritmo encuentra el camino óptimo y que expande el mismo número de nodos que A*. De lo antes expuesto se debe remarcar que A* realiza una búsqueda BFS informada, mientras que IDA* realiza DFS.^[2] A* crea árboles de búsqueda menores ya que se beneficia de usar un registro de almacenamiento en forma de listas abiertas y cerradas, lo cual no realiza IDA*. Esto conlleva a que IDA* utilice menos espacio de memoria al realizar sus búsquedas, y no gasta recursos en mantener estas dos listas. Sin embargo, el prescindir de un almacenamiento trae consigo fuertes desventajas.^[3]

Limitantes

• No puede detectar estados repetidos ya que no cuenta con un almacenamiento de estados visitados a diferencia de A*.
• A* mantiene una frontera de búsqueda mediante la lista abierta donde se almacenan los estados visitados, lo cual no puede realizar IDA*.
• A* utiliza como frontera una lista ordenada expandiendo los nodos en un orden, mientras que IDA* tiene que utilizar una búsqueda de izquierda a derecha simple.

Algoritmos relacionados

• Fringe Search es una mejora de IDA* que supera muchas de sus limitantes y a su vez obtiene mejor rendimiento que A*.
• A* realiza BFS en vez de DFS, y obtiene caminos óptimos en ciertas circunstancias, pero se ejecuta con mayor lentitud.

Referencias

1. Korf, Richard E. «Depth-first iterative-deepening». Artificial Intelligence 27 (1): 97-109. doi:10.1016/0004-3702(85)90084-0. Consultado el 29 de octubre de 2017.
2. Mager Hois, Jesús Manuel (2015). «El Algoritmo Fringe Search como solución superior a A* en la búsqueda de caminos sobre gráficos de malla.». UNAM.
3. Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C.; Schaeffer, Jonathan (2005). «Fringe search: beating A* at pathfinding on game maps». In Proceedings of IEEE Symposium on Computational Intelligence and Games: 125-132. Consultado el 29 de octubre de 2017.

• Datos: Q5477480