- IDA*
-
El método IDA* (Iterative Deepening A*) consiste, como su nombre indica, en un algoritmo de profundidad iterativa en el que se 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 f = g + h sea mayor que el actual límite de coste de f. De esta forma en cada iteración se revisan todos los nodos con un coste de 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 f, para calcular el límite de f que se utilizará en la siguiente iteración. Este nuevo límite será el valor mínimo de todos los valores de f de los nodos del citado contorno.
Wikimedia foundation. 2010.