La profundización iterativa A * ( IDA * ) es un algoritmo de búsqueda de ruta y recorrido de gráfico que puede encontrar la ruta más corta entre un nodo de inicio designado y cualquier miembro de un conjunto de nodos de meta en un gráfico ponderado. Es una variante de búsqueda iterativa de profundización en profundidad que toma prestada la idea de usar una función heurística para evaluar 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 iterativa de profundización ordinaria, 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 utilizaprogramación dinámica y, por lo tanto, a menudo termina explorando los mismos nodos muchas veces.
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | Árbol , Gráfico |
Complejidad espacial en el peor de los casos |
Mientras que la búsqueda iterativa de profundización primero en profundidad utiliza la profundidad de búsqueda como punto de corte para cada iteración, la IDA * utiliza el método más informativo. , dónde 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 a la meta.
El algoritmo fue descrito por primera vez por Richard Korf en 1985. [1]
Descripción
La profundización iterativa A * funciona de la siguiente manera: en cada iteración, realice una búsqueda en profundidad primero, cortando una rama cuando su costo total supera un umbral determinado . Este umbral comienza en la estimación del costo en el estado inicial y aumenta con 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. [2]
Como en A *, la heurística debe tener propiedades particulares para garantizar la optimalidad (caminos más cortos). Consulte 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 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 ) paso función de costo is_goal ( nodo ) objetivo prueba sucesores ( nodo ) función de expansión de nodo, expandir nodos ordenados por g + h (nodo) ida_star ( raíz ) devuelve NOT_FOUND o un par con el mejor camino y su costo procedimiento ida_star ( root ) bound : = h ( root ) path : = [ root ] loop t : = buscar ( path , 0, bound ) if t = FOUND then return (path, bound) if t = ∞ then return NOT_FOUND bound : = t fin procedimiento de fin de buclefunción búsqueda ( ruta , g , límite ) nodo : = ruta .último f : = g + h ( nodo ) si f > límite entonces devuelve f si is_goal ( nodo ) luego devuelve ENCONTRADO min : = ∞ para succ en sucesores ( nodo ) hacer si succ no está en la ruta, entonces ruta .push ( succ ) t : = buscar ( ruta , g + costo ( nodo , succ ), enlazado ) si t = ENCONTRADO luego devuelve ENCONTRADO si t < min entonces min : = t ruta .pop () end if end para la función return min end
Propiedades
Al igual que A *, se garantiza que IDA * encontrará la ruta más corta que va desde el nodo inicial dado a cualquier nodo objetivo en el gráfico del problema, si la función heurística h es admisible , [2] es decir
para todos los nodos n , donde h * es el costo real del camino más corto desde n hasta la meta más cercana (la "heurística perfecta"). [3]
IDA * es beneficioso cuando el problema está limitado por la 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 de 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 heurística del costo h es consistente , lo que significa que
para todos los nodos ny 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. [4]
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. [3] : 282–289
Aplicaciones
Las aplicaciones de IDA * se encuentran en problemas como la planificación . [5]
Referencias
- ^ Korf, Richard E. (1985). "Profundidad primero iterativa-profundización: una búsqueda óptima de árbol admisible" (PDF) . Inteligencia artificial . 27 : 97-109. doi : 10.1016 / 0004-3702 (85) 90084-0 .
- ^ a b Korf, Richard E. (1985). "Aprendizaje de profundidad" (PDF) : 7. Cite journal requiere
|journal=
( ayuda ) - ^ a b Bratko, Ivan (2001). Programación Prolog para Inteligencia Artificial . Educación Pearson.
- ^ Korf, Richard E .; Reid, Michael; Edelkamp, Stefan (2001). "Complejidad de tiempo de iterativo-profundización-A ∗" . Inteligencia artificial . 129 (1–2): 199–218. doi : 10.1016 / S0004-3702 (01) 00094-7 .
- ^ Bonet, Blai; Geffner, Héctor C. (2001). "Planificación como búsqueda heurística". Inteligencia artificial . 129 (1–2): 5–33. doi : 10.1016 / S0004-3702 (01) 00108-4 . hdl : 10230/36325 .