La profundización iterativa A* ( IDA* ) es un algoritmo de búsqueda de ruta y recorrido de grafos que puede encontrar la ruta más corta entre un nodo de inicio designado y cualquier miembro de un conjunto de nodos de destino en un grafo ponderado. Es una variante de la búsqueda en profundidad con profundización iterativa que toma prestada la idea de utilizar una función heurística para estimar de manera conservadora el costo restante para llegar al destino del algoritmo de búsqueda A* . Dado que es un algoritmo de búsqueda en profundidad, su uso de memoria es menor que en A*, pero a diferencia de la búsqueda de profundización iterativa común, se concentra en explorar los nodos más prometedores y, por lo tanto, no llega a la misma profundidad en todas partes del árbol de búsqueda. A diferencia de A*, IDA* no utiliza programación dinámica y, por lo tanto, a menudo termina explorando los mismos nodos muchas veces.
Mientras que la búsqueda en profundidad iterativa estándar utiliza la profundidad de búsqueda como punto de corte para cada iteración, la IDA* utiliza el método más informativo , donde es el costo de viajar desde la raíz hasta el nodo y es una estimación heurística específica del problema del costo de viajar desde hasta el objetivo.
El algoritmo fue descrito por primera vez por Richard Korf en 1985. [1]
La profundización iterativa A* funciona de la siguiente manera: en cada iteración, se realiza una búsqueda en profundidad y se corta una rama cuando su costo total excede un umbral determinado . Este umbral comienza en la estimación del costo en el estado inicial y aumenta en cada iteración del algoritmo. En cada iteración, el umbral utilizado para la siguiente iteración es el costo mínimo de todos los valores que excedieron el umbral actual. [1]
Al igual que en A*, la heurística debe tener propiedades particulares para garantizar la optimalidad (caminos más cortos). Ver Propiedades a continuación.
ruta ruta de búsqueda actual (actúa como una pila) nodo nodo actual (último nodo en la ruta actual) g el costo para alcanzar el nodo actual f costo estimado de la ruta más barata (raíz..nodo..objetivo) h ( nodo ) costo estimado de la ruta más barata (nodo..objetivo) costo ( nodo , succ ) función de costo de paso is_goal ( nodo ) prueba de objetivo successors ( nodo ) función de expansión de nodos, expande nodos ordenados por g + h(nodo) ida_star ( raíz ) devuelve NOT_FOUND o un par con la mejor ruta y su costo procedimiento ida_star ( raíz ) límite := h ( raíz ) ruta := [ raíz ] bucle t := búsqueda ( ruta , 0, límite ) si t = ENCONTRADO entonces devuelve (ruta, límite) si t = ∞ entonces devuelve NO_ENCONTRADO límite := t fin bucle fin procedimientofunción buscar ( ruta , g , límite ) nodo := ruta .last f := g + h ( nodo ) si f > límite entonces devuelve f si es_objetivo ( nodo ) entonces devuelve ENCONTRADO min := ∞ para succ en sucesores ( nodo ) hacer si succ no está en ruta entonces ruta .push( succ ) t := buscar ( ruta , g + costo ( nodo , succ ), límite ) si t = ENCONTRADO entonces devuelve ENCONTRADO si t < min entonces min := t ruta .pop() fin si fin para devolver min fin función
Al igual que A*, se garantiza que IDA* encontrará la ruta más corta que conduce desde el nodo de inicio dado a cualquier nodo de destino en el gráfico del problema, si la función heurística h es admisible , [1] es decir
para todos los nodos n , donde h * es el costo real del camino más corto desde n hasta el objetivo más cercano (la "heurística perfecta"). [2]
IDA* es beneficioso cuando el problema tiene limitaciones de memoria. Una búsqueda* mantiene una gran cola de nodos inexplorados que pueden llenar rápidamente la memoria. Por el contrario, debido a que IDA* no recuerda ningún nodo excepto los que están en la ruta actual , requiere una cantidad de memoria que es solo lineal en la longitud de la solución que construye. Su complejidad temporal es analizada por Korf et al. bajo el supuesto de que la estimación del costo heurístico h es consistente , lo que significa que
para todos los nodos n y todos los vecinos n' de n ; concluyen que, en comparación con una búsqueda de árbol de fuerza bruta sobre un problema de tamaño exponencial, IDA* logra una profundidad de búsqueda menor (por un factor constante), pero no un factor de ramificación menor. [3]
La búsqueda recursiva del mejor primero es otra versión de la búsqueda A* con restricciones de memoria que puede ser más rápida en la práctica que IDA*, ya que requiere menos regeneración de nodos. [2] : 282–289
Las aplicaciones de IDA* se encuentran en problemas como la planificación . [4] Resolver el cubo de Rubik es un ejemplo de un problema de planificación que se puede resolver con IDA*. [5]
