Un* algoritmo de búsqueda

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

A* (pronunciado "A-star") es un algoritmo de búsqueda de rutas y recorrido de gráficos , que se utiliza en muchos campos de la informática debido a su integridad, optimización y eficiencia óptima. ^[1] Dado un gráfico ponderado , un nodo fuente y un nodo objetivo, el algoritmo encuentra el camino más corto (con respecto a los pesos dados) desde el origen hasta el objetivo.

Un inconveniente práctico importante es su complejidad espacial , ya que almacena todos los nodos generados en la memoria. Por lo tanto, en los sistemas prácticos de rutas de viaje , generalmente se ve superado por algoritmos que pueden preprocesar el gráfico para lograr un mejor rendimiento, ^[2] así como por enfoques limitados por 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 Instituto de Investigación de Stanford (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 utilizando heurísticas para guiar su búsqueda.

En comparación con el algoritmo de Dijkstra, el algoritmo A* solo encuentra el camino más corto desde una fuente específica hasta un objetivo específico, y no el árbol de camino más corto desde una fuente específica hasta todos los objetivos posibles. Ésta es una compensación necesaria para utilizar una heurística dirigida a un objetivo específico. Para el algoritmo de Dijkstra, dado que se genera todo el árbol de ruta más corta, 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 rutas de Shakey the Robot.

A* fue creado como parte del proyecto Shakey , cuyo objetivo era construir un robot móvil que pudiera 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 desde el nodo n hasta el nodo objetivo: ignora por completo g ( n ) , la distancia desde el nodo inicial 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 funciones heurísticas. A* fue diseñado originalmente para encontrar caminos de menor costo cuando el costo de un camino es la suma de sus costos, pero se ha demostrado que A* puede usarse para encontrar caminos óptimos 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 [a]} similar 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] afirmando que no se requería coherencia, pero se demostró que esto era falso en 1985 en el estudio definitivo de Dechter y Pearl sobre la optimización 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 tipo A*. ^[10]

Descripción

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

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

A* es un algoritmo de búsqueda informado , o búsqueda del mejor primero , lo que significa que está formulado en términos de gráficos ponderados : comenzando desde un nodo inicial específico de un gráfico, su objetivo es encontrar una ruta hacia el nodo objetivo dado que tenga el menor coste (menor distancia recorrida, menor tiempo, etc.). Para ello, mantiene un árbol de rutas que se originan en el nodo inicial y extiende esas rutas un borde a la vez 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 requerido para extender el camino 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 la meta. 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á un camino de menor costo desde el principio hasta la meta.

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 marginales) es un nodo objetivo. ^[b] El valor f de ese objetivo es 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 nos da sólo la longitud del camino más corto. Para encontrar la secuencia real de pasos, el algoritmo se puede revisar fácilmente de modo 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 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 la meta, ya que físicamente es la distancia más pequeña posible entre dos puntos cualesquiera. Para un mapa de cuadrícula de un videojuego, usar la distancia Taxicab o la distancia Chebyshev es mejor dependiendo del conjunto de movimientos disponibles (de 4 direcciones 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 gráfico (donde d denota la longitud de esa arista), entonces h se llama 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 ) ^{[ cita necesaria ]} .

Pseudocódigo

El siguiente pseudocódigo describe el algoritmo:

función reconstruct_path ( cameFrom , actual ) total_path := {current} mientras está actual en cameFrom . Claves : actual : = vino de [ actual ] ruta_total . anteponer ( actual ) devolver ruta_total               // A* encuentra un camino desde el principio hasta la meta. // 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 pueden necesitar ser (re)expandidos. // Inicialmente, sólo se conoce el nodo inicial. // Esto generalmente se implementa como un montón mínimo o cola de prioridad en lugar de un conjunto de hash. openSet := {inicio}          // Para el nodo n, vinoDe[n] es el nodo que lo precede inmediatamente en la ruta más barata desde el // inicio hasta n conocido actualmente. 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 suposición actual sobre // cuán barata podría ser una ruta de principio a fin si pasa por n. fScore := mapa con valor predeterminado de Infinity fScore [ inicio ] := h ( inicio )             mientras openSet no está vacío // Esta operación puede ocurrir en tiempo O(Log(N)) si openSet es un montón mínimo o una cola de prioridad actual : = el nodo en openSet que tiene el valor fScore [] más bajo si actual = retorno de objetivo reconstruct_path ( viene de , actual )                        abrirConjunto . Eliminar ( actual ) para cada vecino del actual // d(actual,vecino) es el peso del borde desde el actual al vecino // tentative_gScore es la distancia desde el inicio hasta el vecino hasta el actual tentative_gScore := gScore [ actual ] + d ( actual , vecino ) if tentative_gScore < gScore [ vecino ] // Esta ruta al vecino es mejor que cualquier anterior. ¡Grábalo! cameFrom [ vecino ] := gScore actual [ vecino ] := tentative_gScore fScore [ vecino ] := tentative_gScore + h ( vecino ) si el vecino no está en openSet openSet . agregar vecino ) _                                    // El conjunto abierto está vacío pero el objetivo nunca se alcanzó. Error de devolución  

Observación: En este pseudocódigo, si se llega a un nodo por una ruta, se elimina de openSet y posteriormente se llega a un nodo por una ruta más barata, se 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 será óptima, por lo que la prueba ' tentative_gScore < gScore[neighbor]' siempre fallará si se vuelve a alcanzar el nodo.

Ilustración de la búsqueda A* para encontrar la ruta desde un nodo inicial hasta un nodo objetivo 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 a la meta: cuanto más verde, más cerca. Primero se puede ver a A* moviéndose en línea recta en dirección a la meta, luego, cuando golpea 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 hasta el punto objetivo:

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

El algoritmo A* tiene aplicaciones en el mundo real. En este ejemplo, los bordes 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) al objetivo. El algoritmo busca un camino entre Washington, DC y Los Ángeles.

Detalles de implementacion

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 de prioridad maneja los vínculos puede tener un efecto significativo en el rendimiento en algunas situaciones. Si se rompen los vínculos y la cola se comporta 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 utilizar para recuperar la ruta óptima. Si estas referencias se mantienen, entonces 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 agregarse ya aparece en la cola de prioridad. Si es así, 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, 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 un tiempo amortizado constante .

Casos especiales

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

Propiedades

Terminación e integridad

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 (un camino desde el principio hasta la meta) si existe. En gráficos infinitos con un factor de ramificación finito y costos de borde acotados desde cero ( para algunos fijos ), 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* finaliza 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 del nodo). Cuando la heurística es admisible, esas estimaciones son optimistas (no del todo; consulte el párrafo siguiente), por lo que A* puede ignorar con seguridad esos nodos 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 principio hasta la meta y, por lo tanto, continuará buscando hasta que tales posibilidades no existan. ${\displaystyle f}$

La prueba real es un poco más complicada porque no se garantiza que los valores de 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 que la suma sea optimista. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle g+h}$

Optimidad 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 que una variedad de definiciones de Alts y P en combinación con la heurística de A* eran simplemente admisibles o eran a la vez consistentes y admisibles. 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 entendemos por "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 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 la heurística utilizada es admisible pero no consistente, es posible que un nodo se expanda A* muchas veces, un número exponencial de veces en el peor de los casos. ^[13] 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 del borde del gráfico de búsqueda es exponencial en el tamaño del gráfico y que ciertas heurísticas inconsistentes (pero admisibles) pueden conducir a un número reducido de expansiones de nodos. en búsquedas A*. ^{[14] [15]}

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 un camino de solución óptimo, también significa que A* debe examinar todos los caminos igualmente meritorios para encontrar el camino óptimo. Para calcular los caminos más cortos aproximados, es posible acelerar la búsqueda a expensas de la optimización 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 denomina ε -admisible.

Hay varios algoritmos ε -admisibles:

• Ponderación A*/ponderación estática. ^[16] 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 (que eventualmente ocurre más rápido que usar 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 gráfico. ^[17]
• Ponderación dinámica ^[18] utiliza la función de costo , donde y donde es la profundidad de la búsqueda y N es la longitud anticipada de la ruta de solución. ${\displaystyle f(n)=g(n)+(1+\varepsilon w(n))h(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 ^[19] utiliza el muestreo de nodos para estimar mejor y desviar el error heurístico.
• ${\displaystyle A_{\varepsilon }^{*}}$. ^[20] 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 _ε ^[21] selecciona nodos con la función , donde A y B son constantes. Si no se pueden seleccionar nodos, el algoritmo retrocederá con la función , donde C y D son constantes. ${\displaystyle Af(n)+Bh_{F}(n)}$ ${\displaystyle Cf(n)+Dh_{F}(n)}$
• AlphA* ^[22] intenta promover la explotación en profundidad prefiriendo nodos recientemente expandidos. AlphA* usa 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 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 (el camino más corto) d : O ( b ^d ) , donde b es el factor de ramificación (el número promedio de sucesores por estado ). ^[23] Esto supone que existe un estado objetivo y que es alcanzable 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 desempeño práctico de la búsqueda A*, ya que una buena heurística permite a A* eliminar muchos de los bd nodos 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 el número de nodos generados por la expansión, N , y la profundidad de la solución, y luego resolviendo ^[24]

${\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 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 distancia verdadera desde x hasta la meta. ^{[17] [23]}

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 a la memoria, como la profundización iterativa A* , la A* limitada a la memoria y la SMA* .

Aplicaciones

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

Relaciones con otros algoritmos

Lo que distingue a A* de un algoritmo codicioso de búsqueda 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; ^{[11] [12]} a su vez, tanto Dijkstra como A* son casos especiales de programación dinámica . ^[27] A* en sí mismo es un caso especial de generalización de rama y límite . ^[28] ${\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 el número de caminos que tiene que explorar. ^[29]

Variantes

• En cualquier momento A* ^[30]
• Bloque A*
• D*
• Campo D*
• Franja
• Ahorro complementario A* (FSA*)
• Adaptativo generalizado A* (GAA*)
• Búsqueda heurística incremental
• Reducido A* ^[31]
• Profundización iterativa A* (IDA*)
• Búsqueda de punto de salto
• Planificación permanente A* (LPA*)
• Nuevo Bidireccional A* (NBA*) ^[32]
• Memoria simplificada limitada A* (SMA*)
• theta*

A* también se puede adaptar a un algoritmo de búsqueda bidireccional . Se debe tener especial cuidado con el criterio de parada. ^[33]

Ver también

• Búsqueda en amplitud
• Búsqueda en profundidad
• Planificación de rutas en cualquier ángulo , busque rutas que no se limiten a moverse a lo largo de los bordes del gráfico, sino que puedan adoptar cualquier ángulo.

Notas

1. “A*-like” significa que el algoritmo busca extendiendo las rutas que se originan en el nodo inicial un borde a la 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 de objetivo se pueden pasar varias veces si quedan otros nodos con valores f más bajos , ya que pueden conducir a un camino más corto hacia un objetivo.

Referencias

1. Russell, Stuart J. (2018). Inteligencia artificial un enfoque moderno . Norvig, Peter (4ª ed.). Boston: Pearson. ISBN 978-0134610993. OCLC  1021874142.
2. Delling, D.; Lijadoras, P .; Schultes, D.; Wagner, D. (2009). "Ingeniería de algoritmos de planificación de rutas". Algorítmica de redes grandes y complejas: diseño, análisis y simulación . Apuntes de conferencias sobre informática. vol. 5515. Saltador. págs. 117-139. doi :10.1007/978-3-642-02094-0_7. ISBN 978-3-642-02093-3.
3. Zeng, W.; Iglesia, RL (2009). "Encontrar caminos más cortos en redes de carreteras reales: el caso de A*". Revista Internacional de Ciencia de la Información Geográfica . 23 (4): 531–543. doi :10.1080/13658810801949850. S2CID  14833639.
4. Hart, educación física ; Nilsson, Nueva Jersey ; Rafael, B. (1968). "Una base formal para la determinación heurística de rutas de costo mínimo". Transacciones IEEE sobre ciencia de sistemas y cibernética . 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. Londres. 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: Prensa de la Universidad de Cambridge. ISBN 9780521122931. Uno de los primeros problemas que consideramos fue cómo planificar una secuencia de "puntos de ruta" que Shakey pudiera utilizar para navegar de un lugar a otro. […] El problema de navegación de Shakey es un problema de búsqueda, similar a los que mencioné anteriormente.
7. Nilsson, Nils J. (30 de octubre de 2009). La búsqueda de la inteligencia artificial (PDF) . Cambridge: Prensa de la Universidad de Cambridge. ISBN 9780521122931. Bertram 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 ahora desde la posición inicial más mi estimación heurística de hasta dónde tenía que llegar el robot.
8. Edelkamp, ​​Stefan; Jabbar, Shahid; Lluch-Lafuente, Alberto (2005). "Búsqueda heurística algebraica de costos" (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.; Rafael, Bertram (1 de diciembre de 1972). "Corrección a 'Una base formal para la determinación heurística de rutas de costo mínimo'" (PDF) . Boletín ACM SIGART (37): 28–29. doi :10.1145/1056777.1056779. S2CID  6386648.
10. Dechter, Rina; Perla de Judea (1985). "Estrategias generalizadas de búsqueda de mejor primero y optimización de A *". Revista de la ACM . 32 (3): 505–536. doi : 10.1145/3828.3830 . S2CID  2092415.
11. 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. 344, ISBN 9781905886609.
12. Hetland, Magnus Lie (2010), Algoritmos de Python: dominio de algoritmos básicos en el lenguaje Python, Apress, p. 214, ISBN 9781430232377.
13. 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.
14. Felner, Ariel; Uzi Zahavi (2011). "Heurísticas inconsistentes en la teoría y la práctica". Inteligencia artificial . 175 (9–10): 1570–1603. doi : 10.1016/j.artint.2011.02.001 .
15. Zhang, Zhifu; NR Sturtevant (2009). Uso de heurísticas inconsistentes en la búsqueda A*. XXI Conferencia Internacional Conjunta sobre Inteligencia Artificial. págs. 634–639.
16. Pohl, Ira (1970). "Primeros resultados sobre el efecto del error en la búsqueda heurística". Inteligencia de las máquinas 5 . Prensa de la Universidad de Edimburgo: 219–236. ISBN 978-0-85224-176-9. OCLC  1067280266.
17. Perla, 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.
18. Pohl, Ira (agosto de 1973). "Evitar 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 Internacional Conjunta sobre Inteligencia Artificial (IJCAI-73) . vol. 3. California, Estados Unidos. págs. 11-17.
19. Köll, Andreas; Hermann Kaindl (agosto de 1992). "Un nuevo enfoque de la ponderación dinámica". Actas de la Décima Conferencia Europea sobre Inteligencia Artificial (ECAI-92) . Viena, Austria: Wiley. págs. 16-17. ISBN 978-0-471-93608-4.
20. Perla, Judea; Jin H. Kim (1982). "Estudios en heurísticas semiadmisibles". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 4 (4): 392–399. doi :10.1109/TPAMI.1982.4767270. PMID  21869053. S2CID  3176931.
21. Ghallab, Malik; Dennis Allard (agosto de 1983). "Aε: un algoritmo de búsqueda heurístico eficiente y casi admisible" (PDF) . Actas de la Octava Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI-83) . vol. 2. Karlsruhe, Alemania. págs. 789–791. Archivado desde el original (PDF) el 6 de agosto de 2014.
22. Reese, Bjørn (1999). AlphA*: Un algoritmo de búsqueda heurístico admisible ε (Reporte). Instituto de Tecnología de Producción, Universidad del Sur de Dinamarca. Archivado desde el original el 31 de enero de 2016 . Consultado el 5 de noviembre de 2014 .
23. Russell, Estuardo ; Norvig, Peter (2003) [1995]. Inteligencia artificial: un enfoque moderno (2ª ed.). Prentice Hall. págs. 97-104. ISBN 978-0137903955.
24. Russell, Estuardo ; Norvig, Peter (2009) [1995]. Inteligencia artificial: un enfoque moderno (3ª ed.). Prentice Hall. pag. 103.ISBN _ 978-0-13-604259-4.
25. Klein, Dan; Manning, Christopher D. (2003). "Análisis A *: selección rápida y exacta del análisis de Viterbi" (PDF) . Actas de la Conferencia sobre 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.
26. Kagan E.; Ben-Gal I. (2014). "Un algoritmo de prueba grupal con aprendizaje informativo en línea" (PDF) . Transacciones IIE . 46 (2): 164–184. doi :10.1080/0740817X.2013.803639. S2CID  18588494. Archivado desde el original (PDF) el 5 de noviembre de 2016 . Consultado el 12 de febrero de 2016 .
27. Ferguson, Dave; Lijachev, 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 bajo incertidumbre para sistemas autónomos, conferencia internacional sobre planificación y programación automatizadas (ICAPS) . págs. 9-18. Archivado (PDF) desde el original el 29 de junio de 2016.
28. Nau, Dana S.; Kumar, VIPIN; Canal, Laveen (1984). "Rama general y encuadernado, 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 4 de octubre de 2012.
29. "Variantes de A*". teoría.stanford.edu . Consultado el 9 de junio de 2023 .
30. 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.
31. Fareh, Raouf; Baziyad, Mahoma; Rahman, Mohammad H.; Rabie, domadora; Bettayeb, Maamar (14 de mayo de 2019). "Investigación de la estrategia de planificación de trayectoria reducida para robots móviles con ruedas diferenciales". Robótica . 38 (2): 235–255. doi :10.1017/S0263574719000572. ISSN  0263-5747. S2CID  181849209.
32. Pijls, Wim; Correo, Henk. Otro algoritmo bidireccional más para caminos más cortos (PDF) (Informe técnico). Instituto Econométrico, Universidad Erasmus de Rotterdam. IE 2009-10. Archivado (PDF) desde el original el 11 de junio de 2014.
33. Goldberg, Andrés V.; Harrelson, Chris; Kaplan, Haim; Werneck, Renato F. "Algoritmos eficientes de ruta más corta punto a punto" (PDF) . Universidad de Princeton . Archivado (PDF) desde el original el 18 de mayo de 2022.

Otras lecturas

• Nilsson, Nueva Jersey (1980). Principios de la Inteligencia Artificial. Palo Alto, California: Compañía editorial Tioga. ISBN 978-0-935382-01-3.

enlaces externos

• Variación de A* llamada 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 .