Algoritmo de búsqueda A*

Algoritmo utilizado para la búsqueda de rutas y el recorrido de gráficos

A* (pronunciado "A-star") es un algoritmo de recorrido de grafos y búsqueda de rutas , 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 la ruta más corta (con respecto a los pesos dados) desde el origen hasta el destino.

Una desventaja práctica importante es su complejidad espacial, donde d es la profundidad de la solución (la longitud del camino más corto) y b es el factor de ramificación (el número promedio de sucesores por estado), ya que almacena todos los nodos generados en la memoria. Por lo tanto, en los sistemas prácticos de enrutamiento de viajes , generalmente es superado por algoritmos que pueden preprocesar el gráfico para lograr un mejor rendimiento, ^[2] así como por enfoques limitados por la memoria; sin embargo, A* sigue siendo la mejor solución en muchos casos. ^[3] ${\displaystyle O(b^{d})}$

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

En comparación con el algoritmo de Dijkstra, el algoritmo A* solo encuentra la ruta más corta desde una fuente específica hasta un objetivo específico, y no el árbol de rutas más cortas desde una fuente específica hasta todos los objetivos posibles. Esta es una compensación necesaria para usar una heurística dirigida a un objetivo específico. Para el algoritmo de Dijkstra, dado que se genera todo el árbol de rutas más cortas, cada nodo es un objetivo y no puede haber una heurística dirigida a un objetivo específico.

Historia

A* fue inventado por investigadores que trabajaban en la planificación de la trayectoria del robot Shakey.

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 ^[5] para la planificación de rutas de Shakey. ^[6] Graph Traverser está guiado por una función heurística h ( n ) , la distancia estimada desde el nodo n hasta el nodo objetivo: ignora por completo g ( n ) , la distancia desde el nodo de inicio hasta n . Bertram Raphael sugirió usar la suma, g ( n ) + h ( n ) . ^[7] Peter Hart inventó los conceptos que ahora llamamos admisibilidad y consistencia de las funciones heurísticas. A* fue diseñado originalmente para encontrar rutas de menor costo cuando el costo de una ruta es la suma de sus costos, pero se ha demostrado que A* se puede usar para encontrar rutas óptimas para cualquier problema que satisfaga las condiciones de un álgebra de costos. ^[8]

El artículo original de A* de 1968 ^[4] contenía un teorema que afirmaba que ningún algoritmo similar a A* ^[a] 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. Unos años más tarde se publicó una "corrección" ^[9] que afirmaba que no se requería consistencia, pero se demostró que esto era 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 al expandir arbitrariamente más nodos que un algoritmo alternativo similar a A*. ^[10]

Descripción

Un algoritmo de búsqueda de rutas que navega por un laberinto generado aleatoriamente

Ilustración de una búsqueda A* para encontrar un camino entre dos puntos de un gráfico. De izquierda a derecha, se utiliza cada vez más una heurística que prefiere los puntos más cercanos al objetivo.

A* es un algoritmo de búsqueda informado , o una búsqueda del tipo "mejor primero" , lo que significa que está formulado en términos de gráficos ponderados : a partir de un nodo de inicio específico de un gráfico, tiene como objetivo encontrar una ruta hacia el nodo objetivo dado que tenga el menor 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 alcanza el nodo objetivo.

En cada iteración de su bucle principal, A* debe determinar cuál de sus caminos extender. Lo hace en función del costo del camino y de una estimación del costo necesario para extender el camino hasta el objetivo. En concreto, A* selecciona el camino 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 de inicio 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. La función heurística es específica del problema. Si la función heurística es admisible , es decir, nunca sobreestima el costo real para llegar al objetivo, se garantiza que A* devolverá una ruta de menor costo desde el inicio hasta el objetivo.

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 , franja o frontera . 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 (por lo tanto, el nodo con el valor f más bajo de todos los nodos de franja) es un nodo objetivo. ^[b] El valor f de ese objetivo es entonces también el costo de la ruta más corta, ya que h en el objetivo es cero en una heurística admisible.

El algoritmo descrito hasta ahora sólo proporciona la longitud de la ruta más corta. Para encontrar la secuencia real de pasos, el algoritmo se puede revisar fácilmente de modo que cada nodo de la ruta mantenga un registro 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 inicial.

Por ejemplo, al buscar la ruta más corta en un mapa, h ( x ) puede representar la distancia en línea recta hasta el objetivo, ya que es la distancia física más pequeña posible entre dos puntos. Para un mapa de cuadrícula de un videojuego, resulta mejor utilizar la distancia de taxi o la distancia de Chebyshev según el conjunto de movimientos disponibles (de 4 u 8 direcciones).

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 llama monótona o consistente . Con una heurística consistente, se garantiza que A* encuentre 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 ) . ^[11]

Pseudocódigo

El siguiente pseudocódigo describe el algoritmo:

función reconstruir_ruta ( caminodesde , actual ) ruta_total := {actual} mientras actual en caminódesde . Claves : actual := caminódesde [ actual ] ruta_total . prepend ( actual ) devolver ruta_total               // A* encuentra una ruta desde el inicio hasta la meta. // h es la función heurística. h(n) estima el costo para alcanzar la meta desde el nodo n. function A_Star ( inicio , meta , 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 conjunto hash. openSet := {start}          // Para el nodo n, cameFrom[n] es el nodo inmediatamente anterior 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 conocida actualmente. gScore := mapa con valor predeterminado de Infinity gScore [ inicio ] := 0            // Para el nodo n, fScore[n] := gScore[n] + h(n). fScore[n] representa nuestra mejor estimación actual de cuán barata podría ser una ruta desde el inicio hasta el final si pasa por n. fScore := mapa con valor predeterminado de Infinito fScore [ inicio ] := h ( inicio )             mientras openSet no esté vacío // Esta operación puede ocurrir en tiempo O(Log(N)) si openSet es un min-heap o una cola de prioridad actual := el nodo en openSet que tiene el valor fScore [] más bajo si actual = objetivo return reconstruct_path ( cameFrom , current )                        openSet . Remove ( current ) para cada vecino de current // d(current,neighbor) es el peso del borde de current a neighbor // tentative_gScore es la distancia desde el inicio hasta el vecino a través de current tentative_gScore := gScore [ current ] + d ( current , neighbor ) if tentative_gScore < gScore [ neighbor ] // Esta ruta a neighbor es mejor que cualquier otra anterior. ¡Regístrala! cameFrom [ neighbor ] := current gScore [ neighbor ] := tentative_gScore fScore [ neighbor ] := tentative_gScore + h ( neighbor ) if neighbor not in openSet openSet . add ( neighbor )                                    // El conjunto abierto está vacío pero el objetivo nunca se alcanzó y se devolvió un error  

Observación: En este pseudocódigo, si se llega a un nodo por una ruta, se lo elimina de openSet y, posteriormente, se lo alcanza por una ruta más barata, se lo agregará nuevamente a openSet. 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 se elimina un nodo de openSet, se garantiza que la ruta hacia él sea óptima, por lo que la prueba ' tentative_gScore < gScore[neighbor]' siempre fallará si se llega nuevamente al nodo.

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

Ejemplo

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: objetivo; naranja: visitado

El algoritmo A* tiene aplicaciones en el mundo real. En este ejemplo, las aristas son vías de ferrocarril y h(x) es la distancia del círculo máximo (la distancia más corta posible en una esfera) hasta el objetivo. El algoritmo busca una ruta entre Washington, DC y Los Ángeles.

Detalles de implementación

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 que se debe tener en cuenta es que la forma en que la cola de prioridad maneja los empates puede tener un efecto significativo en el rendimiento en algunas situaciones. Si se rompen los empates de modo que la cola se comporte de manera LIFO , A* se comportará como una búsqueda en profundidad 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 usar 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 que está a punto de agregarse ya aparece en la cola de prioridad. Si lo hace, entonces los punteros de prioridad y padre se cambian para corresponder a la ruta de menor costo. Una cola de prioridad basada en 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 hash que asigna elementos a su posición en el montón, lo que permite 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

El algoritmo de Dijkstra , como otro ejemplo de un algoritmo de búsqueda de costo uniforme, puede verse como un caso especial de A* donde ⁠ ⁠ ${\displaystyle h(x)=0}$ para todo x . ^{[12] [13]} La búsqueda en profundidad general se puede implementar usando A* considerando 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 asignación, disminuimos el contador C en uno. Por lo tanto, cuanto antes se descubra un nodo, mayor será su valor ⁠ ⁠ ${\displaystyle h(x)}$ . Tanto el algoritmo de Dijkstra como la búsqueda en profundidad se pueden implementar de manera más eficiente sin incluir un valor ⁠ ⁠ ${\displaystyle h(x)}$ en cada nodo.

Propiedades

Terminación y completitud

En los grafos finitos con pesos de arista no negativos, se garantiza que A* terminará y será completo , es decir, siempre encontrará una solución (un camino desde el inicio hasta el objetivo) si existe una. En los grafos infinitos con un factor de ramificación finito y costos de arista que están acotados lejos de cero ( para algún valor fijo ), se garantiza que A* terminará solo si existe una solución. ^[1] ${\textstyle d(x,y)>\varepsilon >0}$ ${\displaystyle \varepsilon }$

Admisibilidad

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* termina su búsqueda, ha encontrado un camino desde el inicio hasta la meta cuyo costo real es menor que el costo estimado de cualquier camino desde el inicio hasta la meta a través de cualquier nodo abierto (el valor ⁠ ⁠ ${\displaystyle f}$ del nodo ). Cuando la heurística es admisible, esas estimaciones son optimistas (no del todo; véase el párrafo siguiente), por lo que A* puede ignorar esos nodos con seguridad porque no es posible que conduzcan a una solución más barata que la que ya tiene. En otras palabras, A* nunca pasará por alto la posibilidad de un camino de menor costo desde el inicio hasta la meta y, por lo tanto, continuará buscando hasta que no existan tales posibilidades.

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

Optimalidad y consistencia

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 al resolver P es un subconjunto (posiblemente igual) del conjunto de nodos expandidos por A′ al resolver P. El estudio definitivo de la eficiencia óptima de A* se debe a Rina Dechter y Judea Pearl. ^[10] Consideraron una variedad de definiciones de Alts y P en combinación con la heurística de A* siendo meramente admisible o siendo 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 similares a A* admisibles en todos los problemas de búsqueda "no patológicos". En términos generales, su noción del problema no patológico es lo que ahora queremos decir con "hasta el desempate". Este resultado no se cumple si la heurística de A* es admisible pero no consistente. En ese caso, Dechter y Pearl demostraron que existen algoritmos admisibles similares a A* que pueden expandir arbitrariamente menos nodos que A* en algunos problemas no patológicos.

La eficiencia óptima se refiere al conjunto de nodos expandidos, no al número de expansiones de nodos (el número de iteraciones del bucle principal de A*). Cuando la heurística que se utiliza es admisible pero no consistente, es posible que un nodo sea expandido por A* muchas veces, un número exponencial de veces en el peor de los casos. ^[14] En tales circunstancias, el algoritmo de Dijkstra podría superar a A* por un amplio margen. Sin embargo, investigaciones más recientes encontraron que este caso patológico solo ocurre en ciertas situaciones artificiales donde el peso de la arista del gráfico de búsqueda es exponencial en el tamaño del gráfico y que ciertas heurísticas inconsistentes (pero admisibles) pueden llevar a un número reducido de expansiones de nodos en búsquedas A*. ^{[15] [16]}

Relajación limitada

Una* búsqueda que utiliza 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 rutas más cortas aproximadas, es posible acelerar la búsqueda a expensas de la optimalidad relajando el criterio de admisibilidad. A menudo queremos limitar esta relajación, de modo que podamos 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.

Hay varios algoritmos ε -admisibles:

• Ponderación estática/A* ponderada. ^[17] 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 sucede más rápido que si se utiliza h _a ya que se expanden menos nodos). La ruta encontrada por el algoritmo de búsqueda puede tener un costo de, como máximo, ε veces el de la ruta de menor costo en el grafo. ^[18]
• La ponderación dinámica ^[19] utiliza la función de costo ⁠ ⁠ ${\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(n)}$ , donde , y donde ⁠ ⁠ es la profundidad de la búsqueda y N es la longitud anticipada de la ruta de la solución. ${\displaystyle w(n)={\begin{cases}1-{\frac {d(n)}{N}}&d(n)\leq N\\0&{\text{otherwise}}\end{cases}}}$ ${\displaystyle d(n)}$
• La ponderación dinámica muestreada ^[20] utiliza el muestreo de nodos para estimar mejor y eliminar el sesgo del error heurístico.
• ${\displaystyle A_{\varepsilon }^{*}}$. ^[21] 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.
• A _ε ^[22] 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* ^[23] intenta promover la explotación en profundidad al preferir nodos expandidos recientemente. AlphA* utiliza la función de costo , donde , donde λ y Λ son constantes con , π ( n ) es el padre de n , y ñ es el nodo expandido más recientemente. ${\displaystyle f_{\alpha }(n)=(1+w_{\alpha }(n))f(n)}$ ${\displaystyle w_{\alpha }(n)={\begin{cases}\lambda &g(\pi (n))\leq g({\tilde {n}})\\\Lambda &{\text{otherwise}}\end{cases}}}$ ${\displaystyle \lambda \leq \Lambda }$

Complejidad

La complejidad temporal de A* depende de la heurística. En el peor caso de un espacio de búsqueda ilimitado, la cantidad 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 (la cantidad promedio de sucesores por estado). ^[24] Esto supone que existe un estado objetivo y que se puede alcanzar desde el estado inicial; si no es así y el espacio de estados 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 a A* eliminar muchos de los nodos b ^d que una búsqueda no informada expandiría. Su calidad se puede expresar en términos del factor de ramificación efectivo b * , que se puede determinar empíricamente para una instancia de problema midiendo la cantidad de nodos generados por la expansión, N , y la profundidad de la solución, y luego resolviendo ^[25]

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

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

La complejidad temporal 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 coste exacto para llegar desde x al objetivo. 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 distancia real desde x al objetivo. ^{[18] [24]}

La complejidad espacial de A* es aproximadamente la misma que la de todos los demás algoritmos de búsqueda de gráficos, ya que mantiene todos los nodos generados en la memoria. ^[1] En la práctica, este resulta ser el mayor inconveniente de la búsqueda A*, lo que lleva al desarrollo de búsquedas heurísticas limitadas por la memoria, como Iterative deepening A* , memory-bounded A* y SMA* .

Aplicaciones

A* se utiliza a menudo para el problema común de búsqueda de rutas en aplicaciones como los videojuegos, pero originalmente fue diseñado como un algoritmo general de recorrido de gráficos. ^[4] Encuentra aplicaciones en diversos problemas, incluido el problema del análisis sintáctico mediante gramáticas estocásticas en PNL . ^[26] Otros casos incluyen una búsqueda de información con aprendizaje en línea. ^[27]

Relaciones con otros algoritmos

Lo que diferencia a A* de un algoritmo de búsqueda codicioso de "lo mejor primero" 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 para todos los nodos; ^{[12] [13]} a su vez, tanto Dijkstra como A* son casos especiales de programación dinámica . ^[28] A* en sí mismo es un caso especial de una generalización de rama y límite . ^[29] ${\displaystyle h(n)=0}$

A* es similar a la búsqueda de haz excepto que la búsqueda de haz mantiene un límite en la cantidad de caminos que debe explorar. ^[30]

Variantes

• En cualquier momento A* ^[31]
• Bloque A*
• D*
• Campo D*
• Franja
• Ahorro adicional A* (FSA*)
• A* adaptativa generalizada (GAA*)
• Búsqueda heurística incremental
• A* reducida ^[32]
• Profundización iterativa A* (IDA*)
• Búsqueda de puntos de salto
• Planificación de por vida A* (LPA*)
• Nueva A* Bidireccional (NBA*) ^[33]
• Memoria simplificada limitada A* (SMA*)
• Teta*

A* también se puede adaptar a un algoritmo de búsqueda bidireccional , pero se debe tener especial cuidado con el criterio de detención. ^[34]

Véase también

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

Notas

1. “Similar a A*” significa que el algoritmo busca extendiendo las rutas que se originan en el nodo de inicio, un borde por vez, tal como lo hace A*. Esto excluye, por ejemplo, los algoritmos que buscan hacia atrás desde el objetivo o en ambas direcciones simultáneamente. Además, los algoritmos cubiertos por este teorema deben ser admisibles y “no más informados” que A*.
2. Los nodos objetivo pueden ser recorridos varias veces si quedan otros nodos con valores f más bajos , ya que pueden conducir a una ruta más corta hacia un objetivo.

Referencias

1. Russell, Stuart J. ; Norvig, Peter (2018). Inteligencia artificial: un enfoque moderno (4.ª ed.). Boston: Pearson. ISBN 978-0134610993.OCLC 1021874142  .
2. Delling, D.; Sanders, P .; Schultes, D.; Wagner, D. (2009). "Algoritmos de planificación de rutas de ingeniería". Algoritmos de redes grandes y complejas: diseño, análisis y simulación . Apuntes de clase en informática. Vol. 5515. Springer. págs. 117–139. doi :10.1007/978-3-642-02094-0_7. ISBN . 978-3-642-02093-3.
3. Zeng, W.; Church, RL (2009). "Encontrar rutas más cortas en redes de carreteras reales: el caso de A*". Revista Internacional de Ciencias de la Información Geográfica . 23 (4): 531–543. Código Bibliográfico :2009IJGIS..23..531Z. doi :10.1080/13658810801949850. S2CID  14833639.
4. Hart, PE ; Nilsson, NJ ; Raphael, B. (1968). "Una base formal para la determinación heurística de caminos de costo mínimo". IEEE Transactions on Systems Science and Cybernetics . 4 (2): 100–7. doi :10.1109/TSSC.1968.300136.
5. Doran, JE; Michie, D. (20 de septiembre de 1966). "Experimentos con el programa Graph Traverser". Proc. R. Soc. Lond. A . 294 (1437): 235–259. Código Bibliográfico :1966RSPSA.294..235D. doi :10.1098/rspa.1966.0205. S2CID  21698093.
6. Nilsson, Nils J. (30 de octubre de 2009). La búsqueda de la inteligencia artificial (PDF) . Cambridge: Cambridge University Press. ISBN 9780521122931Uno de los primeros problemas que consideramos fue cómo planificar una secuencia de "puntos de referencia" que Shakey pudiera usar para navegar de un lugar a otro. […] El problema de navegación de Shakey es un problema de búsqueda, similar a los que he mencionado antes.
7. Nilsson, Nils J. (30 de octubre de 2009). La búsqueda de la inteligencia artificial (PDF) . Cambridge: Cambridge University Press. ISBN 9780521122931Bertram Raphael, que dirigía el trabajo sobre Shakey en ese momento, observó que un mejor valor para la puntuación sería la suma de la distancia recorrida hasta el momento desde la posición inicial más mi estimación heurística de la distancia que debía recorrer el robot .
8. Edelkamp, ​​Stefan; Jabbar, Shahid; Lluch-Lafuente, Alberto (2005). "Búsqueda heurística algebraica de costes" (PDF) . Actas de la Vigésima Conferencia Nacional sobre Inteligencia Artificial (AAAI) : 1362–7. ISBN 978-1-57735-236-5.
9. Hart, Peter E.; Nilsson, Nils J .; Raphael, Bertram (1972-12-01). "Corrección a 'Una base formal para la determinación heurística de trayectorias de costo mínimo'" (PDF) . Boletín ACM SIGART (37): 28–29. doi :10.1145/1056777.1056779. S2CID  6386648.
10. Dechter, Rina; Judea Pearl (1985). "Estrategias de búsqueda generalizadas de mejor primero y la optimalidad de A*". Revista de la ACM . 32 (3): 505–536. doi : 10.1145/3828.3830 . S2CID  2092415.
11. Nannicini, Giacomo; Delling, Daniel; Schultes, Dominik; Liberti, Leo (2012). "Búsqueda A* bidireccional en redes viales dependientes del tiempo" (PDF) . Redes . 59 (2): 240–251. doi :10.1002/NET.20438.
12. De Smith, Michael John; Goodchild, Michael F.; Longley, Paul (2007), Análisis geoespacial: una guía completa de principios, técnicas y herramientas de software, Troubadour Publishing Ltd, pág. 344, ISBN 9781905886609.
13. Hetland, Magnus Lie (2010), Algoritmos de Python: Dominar los algoritmos básicos en el lenguaje Python, Apress, pág. 214, ISBN 9781430232377.
14. Martelli, Alberto (1977). "Sobre la complejidad de los algoritmos de búsqueda admisibles". Inteligencia artificial . 8 (1): 1–13. doi :10.1016/0004-3702(77)90002-9.
15. Felner, Ariel; Uzi Zahavi (2011). "Heurísticas inconsistentes en teoría y práctica". Inteligencia artificial . 175 (9–10): 1570–1603. doi : 10.1016/j.artint.2011.02.001 .
16. Zhang, Zhifu; NR Sturtevant (2009). Uso de heurísticas inconsistentes en búsquedas A*. Vigésima primera conferencia conjunta internacional sobre inteligencia artificial. págs. 634–639.
17. Pohl, Ira (1970). "Primeros resultados sobre el efecto del error en la búsqueda heurística". Machine Intelligence 5. Edinburgh University Press: 219–236. ISBN 978-0-85224-176-9.OCLC 1067280266  .
18. Pearl, Judea (1984). Heurística: estrategias de búsqueda inteligente para la resolución de problemas informáticos. Addison-Wesley. ISBN 978-0-201-05594-8.
19. Pohl, Ira (agosto de 1973). "La evitación de catástrofes (relativas), competencia heurística, ponderación dinámica genuina y cuestiones computacionales en la resolución de problemas heurísticos" (PDF) . Actas de la Tercera Conferencia Conjunta Internacional sobre Inteligencia Artificial (IJCAI-73) . Vol. 3. California, EE. UU., págs. 11–17.
20. Köll, Andreas; Hermann Kaindl (agosto de 1992). "Un nuevo enfoque para la ponderación dinámica". Actas de la Décima Conferencia Europea sobre Inteligencia Artificial (ECAI-92) . Viena, Austria: Wiley. pp. 16-17. ISBN 978-0-471-93608-4.
21. Pearl, Judea; Jin H. Kim (1982). "Estudios en heurísticas semiadmisibles". IEEE Transactions on Pattern Analysis and Machine Intelligence . 4 (4): 392–399. doi :10.1109/TPAMI.1982.4767270. PMID  21869053. S2CID  3176931.
22. Ghallab, Malik; Dennis Allard (agosto de 1983). "Aε – un algoritmo de búsqueda heurística eficiente y casi admisible" (PDF) . Actas de la Octava Conferencia Conjunta Internacional sobre Inteligencia Artificial (IJCAI-83) . Vol. 2. Karlsruhe, Alemania. págs. 789–791. Archivado desde el original (PDF) el 6 de agosto de 2014.
23. Reese, Bjørn (1999). AlphA*: Un algoritmo de búsqueda heurística ε-admisible (Informe). Instituto de Tecnología de Producción, Universidad del Sur de Dinamarca. Archivado desde el original el 2016-01-31 . Consultado el 2014-11-05 .
24. Russell, Stuart ; Norvig, Peter (2003) [1995]. Inteligencia artificial: un enfoque moderno (2.ª ed.). Prentice Hall. págs. 97–104. ISBN 978-0137903955.
25. Russell, Stuart ; Norvig, Peter (2009) [1995]. Inteligencia artificial: un enfoque moderno (3.ª ed.). Prentice Hall. pág. 103. ISBN 978-0-13-604259-4.
26. Klein, Dan; Manning, Christopher D. (2003). "A* parsing: fast exact Viterbi parse selection" (PDF) . Actas de la Conferencia de Tecnología del Lenguaje Humano de 2003 del Capítulo Norteamericano de la Asociación de Lingüística Computacional . págs. 119–126. doi :10.3115/1073445.1073461.
27. Kagan E.; Ben-Gal I. (2014). "Un algoritmo de prueba grupal con aprendizaje informativo en línea" (PDF) . IIE Transactions . 46 (2): 164–184. doi :10.1080/0740817X.2013.803639. S2CID  18588494. Archivado desde el original (PDF) el 2016-11-05 . Consultado el 2016-02-12 .
28. Ferguson, Dave; Likhachev, Maxim; Stentz, Anthony (2005). "Una guía para la planificación de rutas basada en heurísticas" (PDF) . Actas del taller internacional sobre planificación en condiciones de incertidumbre para sistemas autónomos, conferencia internacional sobre planificación y programación automatizadas (ICAPS) . pp. 9–18. Archivado (PDF) desde el original el 29 de junio de 2016.
29. Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984). "Rama y límite general, y su relación con A∗ y AO∗" (PDF) . Inteligencia Artificial . 23 (1): 29–58. doi :10.1016/0004-3702(84)90004-3. Archivado (PDF) desde el original el 2012-10-04.
30. "Variantes de A*". theory.stanford.edu . Consultado el 9 de junio de 2023 .
31. Hansen, Eric A.; Zhou, Rong (2007). "Búsqueda heurística en cualquier momento". Revista de investigación en inteligencia artificial . 28 : 267–297. arXiv : 1110.2737 . doi : 10.1613/jair.2096 . S2CID  9832874.
32. Fareh, Raouf; Baziyad, Mohammed; Rahman, Mohammad H.; Rabie, Tamer; Bettayeb, Maamar (14 de mayo de 2019). "Investigación de la estrategia de planificación de ruta reducida para un robot móvil con ruedas diferencial". Robotica . 38 (2): 235–255. doi :10.1017/S0263574719000572. ISSN  0263-5747. S2CID  181849209.
33. Pijls, Wim; Post, Henk. Yet another bidirectional algorithm for shortest paths (PDF) (Informe técnico). Instituto de Econometría, Universidad Erasmus de Róterdam. EI 2009-10. Archivado (PDF) desde el original el 11 de junio de 2014.
34. Goldberg, Andrew V.; Harrelson, Chris; Kaplan, Haim; Werneck, Renato F. "Algoritmos eficientes de ruta más corta punto a punto" (PDF) . Universidad de Princeton . Archivado (PDF) del original el 18 de mayo de 2022.

Lectura adicional

• Nilsson, NJ (1980). Principios de inteligencia artificial. Palo Alto, California: Tioga Publishing Company. ISBN 978-0-935382-01-3.

Enlaces externos

• Variación de A* denominada búsqueda de ruta jerárquica A* (HPA*)
• Brian Grinstead. «Algoritmo de búsqueda A* en JavaScript (actualizado)». Archivado desde el original el 15 de febrero de 2020. Consultado el 8 de febrero de 2021 .