IDA*

El método IDA* (Iterative Deepening A*) es un algoritmo de búsqueda en grados desarrollado por Korf en 1985^[1]​ de profundidad iterativa y es una modificación de DFS. Hace uso de la información heurística de que se dispone sobre el problema para decidir qué nodo expandir a continuación, y hasta dónde llegar en cada una de las iteraciones del proceso.

En este algoritmo, como en cualquier algoritmo de profundización iterativa, cada iteración es una búsqueda primero en profundidad. En este caso la profundidad se basa en la información heurística y terminará no a una determinada profundidad, sino cuando se llegue a un nodo cuyo coste de la función heurística de evaluación ${\displaystyle f=g+h}$ sea mayor que el actual límite de coste de ${\displaystyle f}$. De esta forma en cada iteración se revisan todos los nodos con un coste de ${\displaystyle f}$ menor o igual que el actual límite de coste. Además de esto se evalúan los nodos del contorno del árbol, que tienen un coste mayor que el actual límite de ${\displaystyle f}$, para calcular el límite de ${\displaystyle f}$ que se utilizará en la siguiente iteración. Este nuevo límite será el valor mínimo de todos los valores de ${\displaystyle f}$ de los nodos del citado contorno.

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