Hispanopedia Wiki
Articulo de referencia

Profundización iterativa A*

\\Omega(n^2) "},"space":{"wt":" O(d) "},"optimal":{"wt":""},"complete":{"wt":""}},"i":0}}]}"> El algoritmo A* de profundización iterativa ( IDA* ) es un algoritmo de recorrido d...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo A* de profundización iterativa ( IDA* ) es un algoritmo de recorrido de grafos y búsqueda de rutas que puede encontrar la ruta más corta entre un nodo de inicio designado y cualquier miembro de un conjunto de nodos objetivo en un grafo ponderado. Es una variante de la búsqueda en profundidad iterativa que toma prestada la idea de usar una función heurística para estimar de forma conservadora el costo restante para llegar al objetivo 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 en profundidad iterativa ordinaria, se concentra en explorar los nodos más prometedores y, por lo tanto, no alcanza la misma profundidad en todo el á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 límite para cada iteración, el IDA* utiliza el método más informativo.F(norte)=gramo(norte)+h(norte){\displaystyle f(n)=g(n)+h(n)}, dóndegramo(norte){\displaystyle g(n)}es el costo de viajar desde la raíz hasta el nodonorte{\displaystyle n}yh(norte){\displaystyle h(n)}es una estimación heurística específica del problema del costo de viajar desdenorte{\displaystyle n}hacia la meta.

El algoritmo fue descrito por primera vez por Richard E. Korf en 1985. [ 1 ]

Descripción

El algoritmo Iterative-deepening-A* funciona de la siguiente manera: en cada iteración, se realiza una búsqueda en profundidad , truncando una rama cuando su costo total es cero.F(norte)=gramo(norte)+h(norte){\displaystyle f(n)=g(n)+h(n)}supera un umbral determinado . Este umbral comienza con 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 superaron el umbral actual. [ 1 ]

Al igual que en A*, la heurística debe poseer propiedades específicas para garantizar la optimalidad (caminos más cortos). Consulte la sección Propiedades a continuación.

Pseudocódigo

ruta ruta de búsqueda actual (actúa como una pila) nodo nodo actual (último nodo en la ruta actual) g el costo para llegar al 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 es_objetivo ( nodo ) prueba de objetivo sucesores ( nodo ) función de expansión de nodo, expande nodos ordenados por g + h(nodo) ida_star ( raíz ) devuelve NOT_FOUND o un par con la mejor ruta y su costoprocedimiento ida_star ( raíz ) límite := h ( raíz ) ruta := [ raíz ] bucle t := búsqueda ( ruta , 0, límite ) si t = ENCONTRADO entonces devolver (ruta, límite) si t = ∞ entonces devolver NO_ENCONTRADO límite := t fin del bucle fin del procedimientofunción búsqueda ( ruta , g , límite ) nodo := ruta .last f := g + h ( nodo ) si f > límite entonces devolver f si es_objetivo ( nodo ) entonces devolver ENCONTRADO min := ∞ para succ en sucesores ( nodo ) hacer si succ no está en ruta entonces ruta .push( succ ) t := búsqueda ( ruta , g + costo ( nodo , succ ), límite ) si t = ENCONTRADO entonces devolver ENCONTRADO si t < min entonces min := t ruta .pop() fin si fin para devolver min fin función

Propiedades

Al igual que A*, IDA* garantiza encontrar el camino más corto que lleva desde el nodo inicial dado a cualquier nodo objetivo en el grafo del problema, si la función heurística h es admisible , [ 1 ] es decir

h(norte)≤h∗(norte){\displaystyle h(n)\leq h^{*}(n)}

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. La búsqueda A* mantiene una gran cola de nodos no explorados que pueden llenar rápidamente la memoria. Por el contrario, debido a que IDA* no recuerda ningún nodo excepto los que se encuentran 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

h(norte)≤doost(norte,norte′)+h(norte′){\displaystyle h(n)\leq \mathrm {cost} (n,n')+h(n')}

para todos los nodos n y todos los vecinos n' de n ; concluyen que, en comparación con una búsqueda de árbol por 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 primero en amplitud 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

Complejidad temporal

Si bien IDA* suele ser elogiado por su eficiencia en el uso de memoria en comparación con A*, su complejidad temporal en el peor de los casos puede ser significativamente peor bajo ciertas condiciones:

IDA* en árboles: Crecimiento umbral lento

IDA* se basa en la profundización iterativa utilizando unF{\displaystyle f}-umbral de costo que aumenta en cada iteración. Normalmente, IDA* funciona de manera eficiente cuando el número de nodos expandidos en cada iteración crece exponencialmente. Sin embargo, Patrick, Almulla y Newborn (1992) demostraron que cuando elF{\displaystyle f}-el umbral de costo aumenta en la cantidad mínima posible en cada iteración, como cuandoF{\displaystyle f}Los valores son únicos y estrictamente crecientes: IDA* expande exactamente un nodo adicional por iteración. Bajo estas condiciones de unicidad y monotonicidad del peor caso, IDA* expandenorte(norte+1)/2=Θ(norte2){\displaystyle N(N+1)/2=\Theta (N^{2})}nodos, dondenorte{\displaystyle N}es el número de nodos seguramente expandidos por A*, lo que produce una complejidad cuadrática en comparación con la lineal de A*.O(norte){\displaystyle O(N)}complejidad. [ 4 ] Mahanti et al. (1992) demostraron además que esta limitación no es exclusiva de IDA*: ningún algoritmo de búsqueda heurística de memoria limitada de mejor primero puede lograr universalmenteO(norte){\displaystyle O(N)}complejidad en árboles debido a restricciones de memoria. [ 5 ] También especifican que IDA* lograO(norte){\displaystyle O(N)}La complejidad solo existe si el número de iteraciones con crecimiento mínimo de nodos está acotado, una condición que no siempre se cumple. Para evitar el peor escenario posible, se introdujo la Búsqueda Exponencial Presupuestada Iterativa (IBEX) en 2019. [ 6 ]

IDA* en grafos: Impacto de las transposiciones

IDA* explora el espacio de búsqueda en profundidad y no conserva memoria de los nodos previamente expandidos más allá de la ruta actual. En consecuencia, en grafos que contienen transposiciones —donde múltiples rutas distintas conducen al mismo nodo— IDA* vuelve a expandir los nodos repetidamente. Mahanti et al. (1992) demostraron que para grafos dirigidos acíclicos , estas expansiones repetidas conducen a una grave degradación del rendimiento, con una complejidad en el peor de los casos que alcanzaΩ(22norte){\displaystyle \Omega (2^{2N})}, dóndenorte{\displaystyle N}es el número de nodos elegibles para expansión por A*. [ 5 ] Mahanti et al. (1991) también señalan la degradación exponencial de IDA* en grafos en comparación con la lineal de A*.O(norte){\displaystyle O(N)}rendimiento bajo heurísticas monótonas. [ 7 ] Por lo tanto, en escenarios que involucran transposiciones o estructuras de grafos, IDA* puede ser significativamente menos eficiente que A*, lo que sugiere que otros algoritmos de búsqueda de grafos pueden ser opciones más apropiadas.

Aplicaciones

Las aplicaciones de IDA* se encuentran en problemas como la planificación . [ 8 ] Resolver el cubo de Rubik es un ejemplo de un problema de planificación que se puede resolver con IDA*. [ 9 ]

Referencias

  1. 1 2 3 Korf, Richard E. (1985). "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search" (PDF) . Artificial Intelligence . 27 : 97–109 . doi : 10.1016/0004-3702(85)90084-0 . S2CID 10956233 . 
  2. 1 2 Bratko, Ivan (2001). Programación en Prolog para inteligencia artificial . Pearson Education.
  3. ↑ Korf, Richard E. ; Reid, Michael; Edelkamp, ​​Stefan (2001). "Complejidad temporal de iterative-deepening-A*" . Inteligencia Artificial . 129 ( 1–2 ): 199–218 . doi : 10.1016/S0004-3702(01)00094-7 .
  4. ↑ Patrick, BG; Almulla, M.; Newborn, MM (1992). "Un límite superior para la complejidad temporal del algoritmo iterativo de profundización A*". Annals of Mathematics and Artificial Intelligence . 5 ( 2–4 ): 265–278 . doi : 10.1007/BF01543478 .
  5. 1 2 Mahanti, A.; Ghosh, S.; Nau, DS; Pal, AK; Kanal, LN (1992). "Rendimiento de IDA* en árboles y grafos". Actas de la Décima Conferencia Nacional sobre Inteligencia Artificial : 539–544 .
  6. ↑ Helmert, Malte; Lattimore, Tor; Lelis, Levi HS; Orseau, Laurent; Sturtevant, Nathan R. (2019). "Búsqueda exponencial presupuestada iterativa". arXiv : 1907.13062 [ cs.DS ].
  7. ↑ Mahanti, A.; Pal, AK; Ghosh, S.; Kanal, L. N; Nau, DS (1991). "Rendimiento de A* e IDA*: un análisis del peor caso". [ Actas ] Simposio de 1991 sobre Computación Aplicada . pág. 123. doi : 10.1109/SOAC.1991.143859 . ISBN  0-8186-2136-2.
  8. ↑ Bonet, Blai; Geffner, Héctor C. (2001). "Planning as heuristic search". Artificial Intelligence . 129 ( 1– 2): 5– 33. doi : 10.1016/S0004-3702(01)00108-4 . hdl : 10230/36325 .
  9. ↑ Richard Korf (1997). "Encontrar soluciones óptimas para el cubo de Rubik usando bases de datos de patrones" (PDF) . Archivado del original (PDF) el 19 de agosto de 2019. Consultado el 11 de septiembre de 2023 .