LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

 A * (pronunciado "A-estrella") es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el gráfico de recorrido , que es el proceso de encontrar un camino entre varios puntos, llamados "nodos". Disfruta de un uso generalizado debido a su rendimiento y precisión. Sin embargo, en los sistemas prácticos de enrutamiento de viaje , generalmente es superado por algoritmos que pueden preprocesar el gráfico para lograr un mejor rendimiento, ^[1] aunque otros trabajos han encontrado que A * es superior a otros enfoques. ^[2]

Peter Hart , Nils Nilsson y Bertram Raphael del Stanford Research Institute (ahora SRI International ) publicaron el algoritmo por primera vez en 1968. ^[3] Puede verse como una extensión del algoritmo de 1959 de Edsger Dijkstra . A * logra un mejor rendimiento mediante el uso de heurística para guiar su búsqueda.

Historia [ editar ]

A * fue inventado por investigadores que trabajan en la planificación del camino de Shakey the Robot.

A * fue creado como parte del proyecto Shakey , que tenía el objetivo de construir un robot móvil que pudiera planificar sus propias acciones. Nils Nilsson propuso originalmente usar el algoritmo Graph Traverser ^[4] para la planificación de ruta de Shakey. ^[5] Graph Traverser se guía por una función heurística$${\ displaystyle h (n),} la distancia estimada desde el nodo $${\ displaystyle n} para el nodo objetivo, ignora por completo $${\ displaystyle g (n),} la distancia desde el nodo de inicio hasta $${\ displaystyle n.} Bertram Raphael sugirió usar la suma, $${\ displaystyle g (n) + h (n)}. ^[5] Peter Hart inventó los conceptos que ahora llamamos admisibilidad y consistencia de las funciones heurísticas. A * se diseñó originalmente para encontrar rutas de menor costo cuando el costo de una ruta es la suma de sus costos de borde, pero se ha demostrado que A * puede usarse para encontrar rutas óptimas para cualquier problema que satisfaga las condiciones de un álgebra de costos . ^[6]

El artículo original de 1968 A * ^[3] contenía un teorema de que ningún algoritmo similar a A * ^[7] podría expandir menos nodos que A * si la función heurística es consistente y la regla de desempate de A * se elige adecuadamente. Se publicó una ″ corrección ″ unos años más tarde ^[8] alegando que no se requería consistencia, solo admisibilidad, pero se demostró que esto era falso en el estudio definitivo de Dechter y Pearl sobre la óptima de A * (eficiencia óptima como ahora se llama ), que dio un ejemplo de A * con una heurística que era admisible pero no consistente, expandiendo arbitrariamente más nodos que un algoritmo alternativo similar a A *. ^[9]

Descripción [ editar ]

A * es un algoritmo de búsqueda informado , o una búsqueda de primer orden , lo que significa que está formulado en términos de gráficos ponderados : a partir de un nodo inicial específico de un gráfico, su objetivo es encontrar una ruta al nodo objetivo dado que tenga el más pequeño costo (menor distancia recorrida, menor tiempo, etc.). Lo hace manteniendo un árbol de rutas que se originan en el nodo de inicio y extendiendo esas rutas un borde a la vez hasta que se cumpla su criterio de terminación.

En cada iteración de su ciclo principal, A * necesita determinar cuál de sus caminos se extenderá. Lo hace en función del costo de la ruta y una estimación del costo requerido para extender la ruta hasta la meta. Específicamente, A * selecciona la ruta que minimiza

$${\ displaystyle f (n) = g (n) + h (n)}

donde n es el siguiente nodo en la ruta, g ( n ) es el costo de la ruta desde el nodo inicial hasta n , y h ( n ) es una función heurística que estima el costo de la ruta más barata desde n hasta el objetivo. A * finaliza cuando la ruta que elige extender es una ruta desde el inicio hasta el objetivo o si no hay rutas elegibles para ser extendidas. La función heurística es específica del problema. Si la función heurística es admisible , lo que significa que nunca sobreestima el costo real para llegar a la meta, se garantiza que A * devolverá una ruta de menor costo desde el inicio hasta la meta.

Las implementaciones típicas de A * utilizan una cola prioritaria para realizar la selección repetida de nodos de costo mínimo (estimado) para expandirse. Esta cola prioritaria se conoce como conjunto abierto o franja . En cada paso del algoritmo, el nodo con el valor f ( x ) más bajo se elimina de la cola, los valores f y g de sus vecinos se actualizan en consecuencia, y estos vecinos se agregan a la cola. El algoritmo continúa hasta que un nodo objetivo tenga un valor f más bajo que cualquier nodo en la cola (o hasta que la cola esté vacía). ^[a] La fEl valor de la meta es entonces el costo de la ruta más corta, ya que h en la meta es cero en una heurística admisible.

El algoritmo descrito hasta ahora nos da solo la longitud del camino más corto. Para encontrar la secuencia real de pasos, el algoritmo se puede revisar fácilmente para que cada nodo en la ruta realice un seguimiento de su predecesor. Después de ejecutar este algoritmo, el nodo final apuntará a su predecesor, y así sucesivamente, hasta que el predecesor de algún nodo sea el nodo de inicio.

Como ejemplo, al buscar la ruta más corta en un mapa, h ( x ) podría representar la distancia en línea recta a la meta, ya que físicamente es la distancia más pequeña posible entre dos puntos.

Si la heurística h cumple la condición adicional h ( x ) ≤ d ( x , y ) + h ( y ) para cada borde ( x , y ) de la gráfica (donde d denota la longitud de ese borde), entonces se llama h monótono o consistente . Con una heurística consistente, se garantiza que A * encontrará una ruta óptima sin procesar ningún nodo más de una vez y A * es equivalente a ejecutar el algoritmo de Dijkstra con el costo reducido d ' (x , y ) = d ( x , y ) + h ( y ) - h ( x ) .

Pseudocódigo [ editar ]

El siguiente pseudocódigo describe el algoritmo:

función  reconstruct_path ( cameFrom ,  current ) 
    total_path  : =  {current} 
    mientras  actual  en  cameFrom . Claves : 
        current  : =  cameFrom [ current ] 
        total_path . anteponer ( actual ) 
    return  total_path

// A * encuentra un camino desde el inicio hasta el objetivo. 
// h es la función heurística. h (n) estima el costo para alcanzar la meta desde el nodo n. 
función  A_Star ( inicio ,  objetivo ,  h ) 
    // El conjunto de nodos descubiertos que deben (re) expandirse. 
    // Inicialmente, solo se conoce el nodo de inicio. 
    openSet  : =  {inicio}

    // Para el nodo n, cameFrom [n] es el nodo que lo precede inmediatamente en la ruta más barata desde el inicio hasta n actualmente conocido. 
    cameFrom  : =  un  mapa vacío 

    // Para el nodo n, gScore [n] es el costo de la ruta más barata desde el inicio hasta n actualmente conocido. 
    gScore  : =  mapa  con  el  valor  predeterminado de  Infinity 
    gScore [ inicio ]  : =  0

    // Para el nodo n, fScore [n]: = gScore [n] + h (n). 
    fScore  : =  mapa  con  el  valor  predeterminado de  Infinity 
    fScore [ inicio ]  : =  h ( inicio )

    mientras  openSet  es  no  vacío 
        actual  : =  el  nodo  en  openSet  que tiene  el  más bajo  fScore []  valor 
        si  actual  =  meta 
            retorno  reconstruct_path ( camefrom ,  actual )

        OpenSet . Eliminar ( actual ) conjunto 
        cerrado . Agregue ( actual ) 
        para  cada  vecino  de la  corriente 
            si el  vecino  en  cerrado Establezca  
                continuar 
            // d (actual, vecino) es el peso del borde de actual a vecino 
            // tentative_gScore es la distancia desde el inicio hasta el vecino a través de 
            tentative_gScore  actual : =  gScore [ actual ]  +  d ( actual ,  vecino ) 
            si  tentative_gScore  <  gScore[ vecino ] 
                // Esta ruta al vecino es mejor que cualquiera anterior. Grabarlo! 
                cameFrom [ vecino ]  : =  gScore actual 
                [ vecino ] : = tentative_gScore fScore [ vecino ] : = gScore [ vecino ] + h ( vecino ) si el vecino no está en openSet openSet . agregar ( vecino )  
                    
                    
                    

    // El conjunto abierto está vacío pero nunca se alcanzó el objetivo 
    error de retorno 

Observación: en este pseudocódigo, si se alcanza un nodo por una ruta, se elimina de openSet y, posteriormente, se alcanza por una ruta más barata, se agregará a openSet nuevamente. Esto es esencial para garantizar que el camino devuelto sea óptimo si la función heurística es admisible pero no consistente . Si la heurística es coherente, cuando se elimina un nodo de openSet, se garantiza que la ruta hacia él sea óptima, por lo que la prueba 'tentative_gScore

Ilustración de la búsqueda A * para encontrar la ruta desde un nodo de inicio a un nodo objetivo en un problema de planificación de movimiento del robot . Los círculos vacíos representan los nodos en el conjunto abierto , es decir, los que quedan por explorar, y los rellenos están en el conjunto cerrado. El color en cada nodo cerrado indica la distancia desde el inicio: cuanto más verde, más lejos. Primero se puede ver el A * moviéndose en línea recta en la dirección de la portería, luego, al golpear el obstáculo, explora rutas alternativas a través de los nodos desde el conjunto abierto.

Ver también: algoritmo de Dijkstra

Ejemplo [ editar ]

Un ejemplo de un algoritmo A * en acción donde los nodos son ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto objetivo:

Clave: verde: inicio; azul: gol; naranja: visitado

El algoritmo A * también tiene aplicaciones del mundo real. En este ejemplo, los bordes son ferrocarriles y h (x) es la distancia del gran círculo (la distancia más corta posible en una esfera) al objetivo. El algoritmo está buscando un camino entre Washington, DC y Los Ángeles.

Detalles de implementación [ editar ]

Hay una serie de optimizaciones simples o detalles de implementación que pueden afectar significativamente el rendimiento de una implementación A *. El primer detalle a tener en cuenta es que la forma en que la cola prioritaria maneja los vínculos puede tener un efecto significativo en el rendimiento en algunas situaciones. Si se rompen los empates para que la cola se comporte de manera LIFO , A * se comportará como una búsqueda de profundidad primero entre rutas de igual costo (evitando explorar más de una solución igualmente óptima).

Cuando se requiere una ruta al final de la búsqueda, es común mantener con cada nodo una referencia al padre de ese nodo. Al final de la búsqueda, estas referencias se pueden utilizar para recuperar la ruta óptima. Si se mantienen estas referencias, puede ser importante que el mismo nodo no aparezca en la cola de prioridad más de una vez (cada entrada corresponde a una ruta diferente al nodo y cada una con un costo diferente). Un enfoque estándar aquí es verificar si un nodo a punto de ser agregado ya aparece en la cola de prioridad. Si es así, la prioridad y los punteros principales se cambian para corresponder con la ruta de menor costo. Una cola de prioridad basada en un montón binario estándar no admite directamente la operación de búsqueda de uno de sus elementos, pero se puede aumentar con una tabla hashque asigna elementos a su posición en el montón, permitiendo que esta operación de disminución de prioridad se realice en tiempo logarítmico. Alternativamente, un montón de Fibonacci puede realizar las mismas operaciones de disminución de prioridad en tiempo amortizado constante .

Casos especiales [ editar ]

El algoritmo de Dijkstra , como otro ejemplo de algoritmo de búsqueda de costo uniforme, puede verse como un caso especial de A * donde$${\ displaystyle h (x) = 0}para todo x . ^[10] [11] La búsqueda general en profundidad se puede implementar usando A * al considerar que hay un contador global C inicializado con un valor muy grande. Cada vez que procesamos un nodo asignamos C a todos sus vecinos recién descubiertos. Después de cada tarea individual, disminuimos el contador C en uno. Así, cuanto antes se descubra un nodo, mayor será su$${\ displaystyle h (x)}valor. Tanto el algoritmo de Dijkstra como la búsqueda en profundidad se pueden implementar de manera más eficiente sin incluir un$${\ displaystyle h (x)} valor en cada nodo.

Propiedades [ editar ]

Terminación e integridad [ editar ]

En gráficos finitos con pesos de borde no negativos, se garantiza que A * terminará y estará completo , es decir, siempre encontrará una solución (una ruta desde el inicio hasta el objetivo) si existe. En gráficos infinitos con un factor de ramificación finito y costos de borde limitados desde cero ({\ textstyle d (x, y)> \ varepsilon> 0} para algunos fijos $${\ displaystyle \ varepsilon}), Se garantiza que A * terminará solo si existe una solución.

Admisibilidad [ editar ]

Se dice que un algoritmo de búsqueda es admisible si se garantiza que devolverá una solución óptima. Si la función heurística utilizada por A * es admisible , entonces A * es admisible. Una ″ prueba ″ intuitiva de esto es la siguiente:

Cuando A * finaliza su búsqueda, ha encontrado una ruta desde el inicio hasta el objetivo cuyo costo real es menor que el costo estimado de cualquier ruta desde el inicio hasta el objetivo a través de cualquier nodo abierto (el nodo $${\ displaystyle f}valor). Cuando la heurística es admisible, esas estimaciones son optimistas (no del todo; vea el siguiente párrafo), por lo que A * puede ignorar esos nodos de manera segura porque no pueden conducir a una solución más barata que la que ya tiene. En otras palabras, A * nunca pasará por alto la posibilidad de una ruta de menor costo desde el inicio hasta el objetivo y, por lo tanto, continuará buscando hasta que no existan tales posibilidades.

La prueba real es un poco más complicada porque el $${\ displaystyle f}No se garantiza que los valores de los nodos abiertos sean optimistas incluso si la heurística es admisible. Esto es porque el$${\ displaystyle g} No se garantiza que los valores de los nodos abiertos sean óptimos, por lo que la suma $${\ displaystyle g + h} No se garantiza que sea optimista.

Eficiencia óptima [ editar ]

El algoritmo A es óptimamente eficiente con respecto a un conjunto de algoritmos alternativos Alts en un conjunto de problemas P si para cada problema P en P y cada algoritmo A 'en Alts , el conjunto de nodos expandidos por A para resolver P es un subconjunto (posiblemente igual) del conjunto de nodos expandidos por A 'en la resolución de P. El estudio definitivo de la eficiencia óptima de A * se debe a Rina Dechter y Judea Pearl. ^[9] Consideraron una variedad de definiciones de Alts y P en combinación con que la heurística de A * sea simplemente admisible o sea consistente y admisible. El resultado positivo más interesante que demostraron es que A *, con una heurística consistente, es óptimamente eficiente con respecto a todos los algoritmos de búsqueda tipo A * admisibles en todos los problemas de búsqueda "no patológicos". Hablando en términos generales, su noción de problema no patológico es lo que ahora queremos decir con "hasta romper el empate". Este resultado no se cumple si la heurística de A * es admisible pero no es consistente. En ese caso, Dechter y Pearl mostraron que existen algoritmos admisibles tipo A * que pueden expandir arbitrariamente menos nodos que A * en algunos problemas no patológicos.

La eficiencia óptima se trata del conjunto de nodos expandidos, no del número de expansiones de nodos (el número de iteraciones del bucle principal de A *). Cuando el uso de la heurística es admisible pero no consistente, es posible que un nodo se expanda por A * muchas veces, un número exponencial de veces en el peor de los casos. ^[12] En tales circunstancias, el algoritmo de Dijkstra podría superar a A * por un amplio margen.

Relajación limitada [ editar ]

Una búsqueda * que usa una heurística que es 5.0 (= ε) veces una heurística consistente y obtiene una ruta subóptima.

Si bien el criterio de admisibilidad garantiza una ruta de solución óptima, también significa que A * debe examinar todas las rutas igualmente meritorias para encontrar la ruta óptima. Para calcular las rutas más cortas aproximadas, es posible acelerar la búsqueda a expensas de la optimización relajando el criterio de admisibilidad. A menudo queremos limitar esta relajación, para poder garantizar que la ruta de solución no sea peor que (1 + ε ) veces la ruta de solución óptima. Esta nueva garantía se conoce como ε -admisible.

Existen varios algoritmos ε admisibles:

• Ponderado A * / Ponderación estática. ^[13] Si h _a ( n ) es una función heurística admisible, en la versión ponderada de la búsqueda A * se usa h _w ( n ) = ε h _a ( n ) , ε > 1 como la función heurística, y realiza el A * busca como de costumbre (lo que finalmente sucede más rápido que usar h _a ya que se expanden menos nodos). Por lo tanto, la ruta encontrada por el algoritmo de búsqueda puede tener un costo como máximo ε veces mayor que la ruta de menor costo en el gráfico. ^[14]

• La ponderación dinámica ^[15] utiliza la función de costo$${\ displaystyle f (n) = g (n) + (1+ \ varepsilon w (n)) h (n)}, dónde {\ displaystyle w (n) = {\ begin {cases} 1 - {\ frac {d (n)} {N}} & d (n) \ leq N \\ 0 & {\ text {else}} \ end {cases }}}, y donde $${\ displaystyle d (n)}es la profundidad de la búsqueda y N es la longitud prevista de la ruta de la solución.

• La ponderación dinámica muestreada ^[16] utiliza el muestreo de nodos para estimar mejor y debia el error heurístico.

• $${\ displaystyle A _ {\ varepsilon} ^ {*}}. ^[17] usa dos funciones heurísticas. La primera es la lista FOCAL, que se usa para seleccionar nodos candidatos, y la segunda h _F se usa para seleccionar el nodo más prometedor de la lista FOCAL.

• A _ε ^[18] selecciona nodos con la función$${\ displaystyle Af (n) + Bh_ {F} (n)}, donde A y B son constantes. Si no se pueden seleccionar nodos, el algoritmo retrocederá con la función$${\ displaystyle Cf (n) + Dh_ {F} (n)}, donde C y D son constantes.

• AlphA * ^[19] intenta promover la explotación en profundidad prefiriendo nodos recientemente expandidos. AlphA * usa la función de costo$${\ displaystyle f _ {\ alpha} (n) = (1 + w _ {\ alpha} (n)) f (n)}, dónde {\ displaystyle w _ {\ alpha} (n) = {\ begin {cases} \ lambda & g (\ pi (n)) \ leq g ({\ tilde {n}}) \\\ Lambda & {\ text {de lo contrario }} \ end {casos}}}, donde λ y Λ son constantes con$${\ displaystyle \ lambda \ leq \ Lambda}, π ( n ) es el padre de n , y ñ es el nodo expandido más recientemente.

Complejidad [ editar ]

La complejidad temporal de A * depende de la heurística. En el peor de los casos de un espacio de búsqueda ilimitado, el número de nodos expandidos es exponencial en la profundidad de la solución (la ruta más corta) d : O ( b ^d ) , donde b es el factor de ramificación (el número promedio de sucesores por estado ) ^[20] Esto supone que existe un estado objetivo y que es accesible desde el estado inicial; si no lo es, y el espacio de estado es infinito, el algoritmo no terminará.

La función heurística tiene un efecto importante en el rendimiento práctico de la búsqueda A *, ya que una buena heurística permite que A * elimine muchos de los nodos b ^d que una búsqueda desinformada expandiría. Su calidad puede expresarse en términos del factor de ramificación efectivo b * , que puede determinarse empíricamente para una instancia de problema midiendo el número de nodos expandidos, N y la profundidad de la solución, luego resolviendo ^[21]

$${\ displaystyle N + 1 = 1 + b ^ {*} + (b ^ {*}) ^ {2} + \ dots + (b ^ {*}) ^ {d}.}

Las buenas heurísticas son aquellas con un factor de ramificación efectivo bajo (el óptimo es b * = 1 ).

La complejidad del tiempo es polinómica cuando el espacio de búsqueda es un árbol, hay un único estado objetivo y la función heurística h cumple la siguiente condición:

$${\ displaystyle | h (x) -h ^ {*} (x) | = O (\ log h ^ {*} (x))}

donde h ^* es la heurística óptima, el costo exacto para llegar de x a la meta. En otras palabras, el error de h no crecerá más rápido que el logaritmo de la "heurística perfecta" h ^* que devuelve la verdadera distancia desde x hasta la meta. ^[14] [20]

Aplicaciones [ editar ]

A * se usa comúnmente para el problema de búsqueda de ruta común en aplicaciones como los videojuegos, pero originalmente se diseñó como un algoritmo general de recorrido de gráficos. ^[3] Encuentra aplicaciones para diversos problemas, incluido el problema del análisis mediante gramáticas estocásticas en PNL . ^[22] Otros casos incluyen una búsqueda informativa con aprendizaje en línea. ^[23]

Relaciones con otros algoritmos [ editar ]

Lo que distingue a A * de un codicioso algoritmo de primera búsqueda es que tiene en cuenta el costo / distancia ya recorrida, g ( n ) .

Algunas variantes comunes del algoritmo de Dijkstra pueden verse como un caso especial de A * donde la heurística$${\ displaystyle h (n) = 0}para todos los nodos; ^[10] [11] a su vez, tanto Dijkstra como A * son casos especiales de programación dinámica . ^[24] A * en sí mismo es un caso especial de una generalización de rama y límite .