Algoritmo de búsqueda A*

A* (pronunciado "A-estrella") es un algoritmo de recorrido de grafos y búsqueda de caminos que se utiliza en muchos campos de la informática debido a su completitud, optimalidad y eficiencia óptima. ^{[ 1 ]} Dado un grafo ponderado , un nodo de origen y un nodo de destino, el algoritmo encuentra el camino más corto (con respecto a los pesos dados) desde el origen hasta el destino.

Una desventaja práctica importante es su${\displaystyle O(b^{d})}$complejidad espacial donde d es la profundidad de la solución menos profunda (la longitud del camino más corto desde el nodo de origen a cualquier nodo de destino dado) y b es el factor de ramificación (el número máximo de sucesores para cualquier estado dado). En sistemas prácticos de enrutamiento de viajes , generalmente es superado por algoritmos que pueden preprocesar el grafo para lograr un mejor rendimiento, ^{[ 2 ]} así como por enfoques con limitaciones de memoria; sin embargo, A* sigue siendo la mejor solución en muchos casos. ^{[ 3 ]}

Peter Hart , Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International ) publicaron el algoritmo por primera vez en 1968. ^{[ 4 ]} Puede considerarse una extensión del algoritmo de Dijkstra . A* logra un mejor rendimiento al utilizar heurísticas para guiar su búsqueda.

El algoritmo A* finaliza una vez que encuentra el camino más corto hacia un objetivo específico, en lugar de generar todo el árbol de caminos más cortos desde un origen específico hasta todos los objetivos posibles.

A* se creó como parte del proyecto Shakey , cuyo objetivo era construir un robot móvil capaz de planificar sus propias acciones. Nils Nilsson propuso originalmente utilizar el algoritmo Graph Traverser ^{[ 5 ]} para la planificación de rutas de Shakey. ^{[ 6 ]} Graph Traverser se guía por una función heurística h ( n ) , la distancia estimada del nodo n al nodo objetivo; ignora por completo g ( n ) , la distancia del nodo inicial a n . Bertram Raphael sugirió utilizar la suma g ( n ) + h ( n ) . ^{[ 7 ]} Peter Hart inventó los conceptos que ahora denominamos admisibilidad y consistencia de las funciones heurísticas. A* se diseñó originalmente para encontrar rutas de menor coste cuando el coste de una ruta es la suma de sus costes, pero se ha demostrado que A* puede utilizarse para encontrar rutas óptimas para cualquier problema que cumpla las condiciones de un álgebra de costes. ^{[ 8 ]}

El artículo original de A* de 1968 ^{[ 4 ]} contenía un teorema que afirmaba que ningún algoritmo similar a A* ^{[ a ]} podía expandir menos nodos que A* si la función heurística era consistente y la regla de desempate de A* se elegía adecuadamente. Unos años más tarde se publicó una "corrección" ^{[ 9 ]} que afirmaba que la consistencia no era necesaria, pero esto se demostró falso en 1985 en el estudio definitivo de Dechter y Pearl sobre la optimalidad de A* (ahora llamada eficiencia óptima), 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*. ^{[ 10 ]}

A* es un algoritmo de búsqueda informada , o búsqueda primero el mejor , lo que significa que se formula en términos de grafos ponderados : partiendo de un nodo inicial específico de un grafo, busca encontrar un camino hacia el nodo objetivo dado con el menor costo (menor distancia recorrida, menor tiempo, etc.). Para ello, mantiene un árbol de caminos que se originan en el nodo inicial y extiende esos caminos arista por arista hasta alcanzar el nodo objetivo.

En cada iteración de su bucle principal, A* necesita determinar cuál de sus caminos extender. Lo hace basándose en el costo del camino y una estimación del costo necesario para extender el camino hasta el objetivo. Específicamente, A* selecciona el camino que minimiza

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

donde n es el siguiente nodo en el camino, g ( n ) es el costo del camino desde el nodo inicial hasta n , y h ( n ) es una función heurística que estima el costo del camino más barato desde n hasta el objetivo. La función heurística es específica para cada problema.

Las implementaciones típicas de A* utilizan una cola de prioridad para realizar la selección repetida de nodos de costo mínimo (estimado) para expandir. Esta cola de prioridad se conoce como conjunto abierto , frontera o borde . 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 eliminado (es decir, el nodo con el valor f más bajo de todos los nodos de la frontera) es un nodo objetivo. ^{[ b ]} El valor f de ese objetivo es entonces también el costo del camino más corto, ya que h en el objetivo es cero en una heurística admisible.

El algoritmo descrito hasta ahora solo proporciona la longitud del camino más corto. Para hallar la secuencia real de pasos, el algoritmo se puede modificar fácilmente de manera que cada nodo del camino registre a su predecesor. Tras ejecutar este algoritmo, el nodo final apuntará a su predecesor, y así sucesivamente, hasta que el predecesor de algún nodo sea el nodo inicial.

Por ejemplo, al buscar la ruta más corta en un mapa, h ( x ) podría representar la distancia en línea recta hasta el objetivo, ya que físicamente es la distancia mínima posible entre dos puntos cualesquiera. En el caso de un mapa cuadriculado de un videojuego, usar la distancia de Taxicab o la distancia de Chebyshev resulta más adecuado según el conjunto de movimientos disponibles (de 4 u 8 vías).

Si la heurística h satisface la condición adicional h ( x ) ≤ d ( x , y ) + h ( y ) para cada arista ( x , y ) del grafo (donde d denota la longitud de esa arista), entonces h se denomina monótona 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 coste reducido d' ( x , y ) = d ( x , y ) + h ( y ) − h ( x ) . ^{[ 11 ]}

Pseudocódigo

El siguiente pseudocódigo describe el algoritmo:

función reconstruir_ruta ( came_from , current ) ruta_total := {current} mientras current en came_from . keys : current := came_from [ current ] ruta_total . prepend ( current ) return ruta_total// A* encuentra un camino desde el inicio hasta el objetivo. // h es la función heurística. h(n) estima el costo para alcanzar el objetivo desde el nodo n. function a_star ( start , goal , h ) // El conjunto de nodos descubiertos que pueden necesitar ser (re)expandidos. // Inicialmente, solo se conoce el nodo de inicio. // Esto generalmente se implementa como un min-heap o una cola de prioridad en lugar de un hash-set. open_set := {start}// Para el nodo n, came_from[n] es el nodo inmediatamente anterior en el camino más barato desde el inicio // hasta n actualmente conocido. came_from := un mapa vacío// Para el nodo n, g_score[n] es el costo actualmente conocido del camino más barato desde start hasta n. g_score := mapa con valor predeterminado de infinito g_score [ start ] := 0// Para el nodo n, f_score[n] := g_score[n] + h(n). f_score[n] representa nuestra mejor estimación actual sobre // cuán barato podría ser un camino desde el inicio hasta el final si pasa por n. f_score := mapa con valor predeterminado de Infinito f_score [ inicio ] := h ( inicio )mientras open_set no esté vacío // Esta operación puede ocurrir en tiempo O(Log(N)) si open_set es un min-heap o una cola de prioridad current := el nodo en open_set con el valor f_score [] más bajo si current = goal return reconstruct_path ( came_from , current )open_set.remove ( current ) para cada vecino de current // d(current,neighbor) es el peso de la arista de current a neighbor // tentative_g_score es la distancia desde start hasta neighbor a través de current tentative_g_score := g_score [ current ] + d ( current , neighbor ) if tentative_g_score < g_score [ neighbor ] // Este camino a neighbor es mejor que cualquiera anterior. ¡Regístralo! came_from [ neighbor ] : = current g_score [ neighbor ] := tentative_g_score f_score [ neighbor ] : = tentative_g_score + h ( neighbor ) if neighbor not in open_set open_set.add ( neighbor )// El conjunto abierto está vacío, pero el objetivo nunca se alcanzó. Devolver error.

Nota: En este pseudocódigo, si un nodo es alcanzado por una ruta, eliminado de open_set, y posteriormente alcanzado por una ruta más barata, se agregará open_setnuevamente a . Esto es esencial para garantizar que la ruta devuelta sea óptima si la función heurística es admisible pero no consistente . Si la heurística es consistente, cuando un nodo es eliminado de open_setla ruta a se garantiza que es óptimo por lo que la prueba ' tentative_g_score < g_score[neighbor]' siempre fallará si el nodo es alcanzado nuevamente. El pseudocódigo implementado aquí a veces se llama la versión de búsqueda en grafo de A*. ^{[ 12 ]} Esto está en contraste con la versión sin la tentative_g_score < g_score[neighbor]prueba '' para agregar nodos de nuevo a open_set, que a veces se llama la versión de búsqueda en árbol de A* y requiere una heurística consistente para garantizar la optimalidad.

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

Existen varios algoritmos ε -admisibles:

• Ponderación estática/A* ponderada. ^{[ 18 ]} Si h _a ( n ) es una función heurística admisible, en la versión ponderada de la búsqueda A* se utiliza h _w ( n ) = ε h _a ( n ) , ε > 1 como función heurística, y se realiza la búsqueda A* como de costumbre (lo que finalmente ocurre más rápido que usando h _a ya que se expanden menos nodos). El camino encontrado por el algoritmo de búsqueda puede tener un costo de como máximo ε veces el del camino de menor costo en el grafo. ^{[ 19 ]}
• Parábola convexa ascendente/descendente (XUP/XDP). ^{[ 20 ]} Modificación de la función de costo en A* ponderado para desplazar la optimalidad hacia el inicio o el objetivo. XDP proporciona caminos que son casi óptimos cerca del inicio, y los caminos XUP son casi óptimos cerca del objetivo. Ambos producen${\displaystyle \epsilon }$-rutas óptimas en general.

  ${\displaystyle f_{\text{XDP}}(n)={\frac {1}{2\epsilon }}\left[\ g(n)+(2\epsilon -1)+{\sqrt {(g(n)-h(n))^{2}+4\epsilon g(n)h(n)}}\ \right]}$.

  ${\displaystyle f_{\text{XUP}}(n)={\frac {1}{2\epsilon }}\left[\ g(n)+h(n)+{\sqrt {(g(n)+h(n))^{2}+4\epsilon (\epsilon -1)h(n)^{2}}}\ \right]}$.

• Curva ascendente/descendente por partes (pwXU/pwXD). ^{[ 21 ]} Similar a XUP/XDP pero con funciones por partes en lugar de parábolas. Las trayectorias de solución también son${\displaystyle \epsilon }$-óptimo.

  ${\displaystyle f_{\text{pwXD}}(n)={\begin{cases}g(n)+h(n),&{\text{if }}h(n)>g(n)\\g(n)+(2\epsilon -1)h(n)/\epsilon ,&{\text{if }}h(n)\leq g(n)\end{cases}}}$

  ${\displaystyle f_{\text{pwXU}}(n)={\begin{cases}g(n)/(2\epsilon -1)+h(n),&{\text{if }}g(n)<(2\epsilon -1)h(n)\\(g(n)+h(n))/\epsilon ,&{\text{if }}g(n)\geq (2\epsilon -1)h(n)\end{cases}}}$

• La ponderación dinámica ^{[ 22 ]} utiliza la función de coste ⁠${\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(n)}$, donde${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}}$y dónde${\displaystyle d(n)}$⁠ es la profundidad de la búsqueda y N es la longitud prevista de la ruta de la solución.
• El ponderado dinámico muestreado ^{[ 23 ]} utiliza el muestreo de nodos para estimar mejor y desviar el error heurístico.
• ${\displaystyle A_{\varepsilon }^{*}}$. ^{[ 24 ]} utiliza dos funciones heurísticas. La primera es la lista FOCAL, que se utiliza para seleccionar nodos candidatos, y la segunda h _F se utiliza para seleccionar el nodo más prometedor de la lista FOCAL.
• Un _ε ^{[ 25 ]} selecciona nodos con la función ⁠${\displaystyle Af(n)+Bh_{F}(n)}$⁠ , donde A y B son constantes. Si no se puede seleccionar ningún nodo, el algoritmo retrocederá con la función ⁠${\displaystyle Cf(n)+Dh_{F}(n)}$donde C y D son constantes.
• AlphA* ^{[ 26 ]} intenta promover la explotación en profundidad dando preferencia a los nodos expandidos recientemente. AlphA* utiliza la función de coste${\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{otherwise}}\end{cases}}}$, donde λ y Λ son constantes con${\displaystyle \lambda \leq \Lambda }$, π ( n ) es el padre de n , y ñ es el nodo expandido más recientemente.

Como algoritmo de búsqueda heurística, el rendimiento de A* está fuertemente influenciado por la calidad de la función heurística.${\textstyle h(n)}$Si la heurística se aproxima bien al coste real para alcanzar el objetivo, A* puede reducir significativamente el número de expansiones de nodos. Por otro lado, una heurística deficiente puede dar lugar a muchas expansiones innecesarias.

En el peor de los casos

En el peor de los casos, A* expande todos los nodos.${\textstyle n}$para qué${\textstyle f(n)=g(n)+h(n)\leq C^{*}}$, dónde${\textstyle C^{*}}$es el costo del nodo objetivo óptimo.

Por qué no puede ser peor

Supongamos que hay un nodo${\textstyle N'}$en la lista abierta con${\textstyle f(N')>C^{*}}$y es el siguiente nodo que se expandirá. Dado que el nodo objetivo tiene${\textstyle f(goal)=g(goal)+h(goal)=g(goal)=C^{*}}$, y${\textstyle f(N')>C^{*}}$, el nodo objetivo tendrá un valor f más bajo y se expandirá antes${\textstyle N'}$Por lo tanto, A* nunca expande nodos con${\textstyle f(n)>C^{*}}$.

Por qué no puede ser mejor

Supongamos que existe un algoritmo óptimo que expande menos nodos que${\textstyle C^{*}}$en el peor de los casos usando la misma heurística. Eso significa que debe haber algún nodo${\textstyle N'}$de tal manera que${\textstyle f(N')<C^{*}}$, sin embargo, el algoritmo opta por no expandirlo.

Ahora consideremos un grafo modificado donde una nueva arista de costo${\textstyle \varepsilon }$(con${\textstyle \varepsilon >0}$) se agrega desde${\textstyle N'}$hacia la meta. Si${\textstyle f(N')+\varepsilon <C^{*}}$, entonces el nuevo camino óptimo pasa por${\textstyle N'}$Sin embargo, dado que el algoritmo aún evita la expansión${\textstyle N'}$, no alcanzará la nueva ruta óptima, violando así su optimalidad.

Por lo tanto, ningún algoritmo óptimo que incluya A* podría expandir menos nodos que${\textstyle C^{*}}$en el peor de los casos.

Notación matemática

La complejidad del peor caso de A* se describe a menudo como${\textstyle O(b^{d})}$, dónde${\displaystyle b}$es el factor de ramificación y${\textstyle d}$es la profundidad del objetivo más superficial. Si bien esto da una idea aproximada, no refleja con precisión el comportamiento real de A*.

Un límite más preciso considera el número de nodos con${\textstyle f(n)\leq C^{*}}$. Si${\displaystyle \varepsilon }$es la diferencia más pequeña posible en${\textstyle f}$-costo entre nodos distintos, entonces A* puede expandirse hasta:

${\displaystyle O\left({\frac {C^{*}}{\varepsilon }}\right)}$

Esto representa la complejidad temporal y espacial en el peor de los casos.

A* se usa frecuentemente para el problema común de búsqueda de rutas en aplicaciones como videojuegos, pero fue diseñado originalmente como un algoritmo general de recorrido de grafos. ^{[ 4 ]} Encuentra aplicaciones en diversos problemas, incluyendo el problema del análisis sintáctico usando gramáticas estocásticas en PLN . ^{[ 27 ]} Otros casos incluyen la búsqueda de información en el aprendizaje en línea. ^{[ 28 ]}

Lo que distingue a A* de un algoritmo de búsqueda voraz primero en amplitud es que toma en cuenta el costo/distancia ya recorrida, g ( n ) .

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

A* es similar a la búsqueda en haz, excepto que la búsqueda en haz mantiene un límite en el número de caminos que tiene que explorar. ^{[ 31 ]}

• En cualquier momento A* ^{[ 32 ]}
• Bloque A*
• D*
• Campo D*
• Franja
• Cuenta de Ahorro Marginal A* (FSA*)
• A* adaptativo generalizado (GAA*)
• Búsqueda heurística incremental
• A* reducido ^{[ 33 ]}
• Profundización iterativa A* (IDA*)
• Búsqueda de puntos de salto
• Planificación a lo largo de la vida A* (LPA*)
• Nuevo A* bidireccional (NBA*) ^{[ 34 ]}
• A* con memoria limitada simplificada (SMA*)
• Theta*

A* también puede adaptarse a un algoritmo de búsqueda bidireccional , pero se debe tener especial cuidado con el criterio de parada. ^{[ 35 ]}

• Planificación de rutas en cualquier ángulo : búsqueda de rutas que no se limiten a moverse a lo largo de los bordes del grafo, sino que puedan adoptar cualquier ángulo.
• Búsqueda en anchura : algoritmo para buscar en los nodos de un grafo. 
• Búsqueda en profundidad : algoritmo para buscar en los nodos de un grafo. 
• Algoritmo de Dijkstra : Algoritmo para encontrar caminos más cortos 

• Nilsson, NJ (1980). Principios de inteligencia artificial . Palo Alto, California: Tioga Publishing Company. ISBN 978-0-935382-01-3.
• Walsh, Toby. La historia más breve de la IA .

• Variación del algoritmo A* denominada A* de búsqueda de rutas jerárquicas (HPA*).
• Brian Grinstead. "Algoritmo de búsqueda A* en JavaScript (actualizado)" . Archivado del original el 15 de febrero de 2020. Consultado el 8 de febrero de 2021 .