A * (pronunciado "A-star") es un algoritmo de búsqueda de recorrido y recorrido de gráfico , que se utiliza a menudo en muchos campos de la informática debido a su integridad, optimización y eficiencia óptima. [1] Un inconveniente práctico importante es su complejidad del espacio, 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 memoria; sin embargo, A * sigue siendo la mejor solución en muchos casos. [3]
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos | |
Complejidad espacial en el peor de los casos |
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 mediante el uso de heurísticas para guiar su búsqueda.
Historia
A * se creó 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 el uso del algoritmo Graph Traverser [5] para la planificación de rutas de Shakey. [6] Graph Traverser es guiado por una función heurística h ( n ) , la distancia estimada desde el nodo n al nodo objetivo: por completo ignora g ( n ) , la distancia desde el nodo de inicio a n . Bertram Raphael sugirió usar la suma, g ( n ) + h ( n ) . [6] Peter Hart inventó los conceptos que ahora llamamos admisibilidad y consistencia de funciones heurísticas. A * se diseñó 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. [7]
El artículo original de 1968 A * [4] contenía un teorema que establecía 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 ruptura de empates de A * se elige adecuadamente. Unos años más tarde se publicó una ″ corrección ″ [8] que afirmaba que no se requería consistencia, pero se demostró que esto era falso 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 similar a A *. [9]
Descripción
A * es un algoritmo de búsqueda informado , o una búsqueda de mejor primero , 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 tiene el menor costo (menor distancia recorrida, menor tiempo, etc.). Lo hace manteniendo un árbol de caminos que se originan en el nodo de inicio y extendiendo esos caminos un borde a la vez hasta que se satisface su criterio de terminación.
En cada iteración de su bucle principal, A * necesita determinar cuál de sus caminos extender. Lo hace basándose en el 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
donde n es el siguiente nodo en el camino, g ( n ) es el coste de la ruta desde el nodo de inicio a n , y h ( n ) es una heurística función que estima el coste de la ruta más barato de n a la meta. A * termina cuando la ruta que elige extender es una ruta desde el inicio hasta la meta 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 principio hasta la meta.
Las implementaciones típicas de A * usan 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 o franja . En cada paso del algoritmo, el nodo con el más bajo f ( x ) valor se elimina de la cola, los f y g valores de sus vecinos se actualizan en consecuencia, y estos vecinos se añaden 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 esa meta es entonces también el costo del camino más corto, 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 de 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.
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 esa es físicamente la distancia más pequeña posible entre dos puntos cualesquiera. Para un mapa de cuadrícula de un videojuego, usar la distancia de Manhattan o la distancia de octil se vuelve mejor dependiendo del conjunto de movimientos disponibles (4 direcciones u 8 direcciones).
Si la heurística h satisface 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 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 ) .
Pseudocódigo
El siguiente pseudocódigo describe el algoritmo:
función reconstruct_path ( cameFrom , current ) total_path : = {actual} mientras que actual en cameFrom . Claves : actual : = cameFrom [ actual ] total_path . anteponer ( actual ) return 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. 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 conjunto de hash. openSet : = {inicio} // Para el nodo n, cameFrom [n] es el nodo que lo precede inmediatamente en la ruta más barata desde el inicio // an conocido actualmente. cameFrom : = un mapa vacío // Para el nodo n, gScore [n] es el costo de la ruta más barata desde el principio hasta n actualmente conocida. 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 en cuanto a // qué tan corta puede ser una ruta de principio a fin si pasa por n. fScore : = mapa con valor predeterminado de Infinity fScore [ inicio ] : = h ( inicio ) mientras openSet está no vaciar // Esta operación puede ocurrir en O (1) tiempo si openSet es un min-montón o una cola de prioridad actual : = el nodo en openSet que tiene el más bajo fScore [] valor si actual = meta retorno reconstruct_path ( camefrom , actual ) openSet . Eliminar ( actual ) para cada vecino del actual // d (actual, vecino) es el peso del borde del actual al vecino // tentative_gScore es la distancia desde el inicio hasta el vecino hasta el actual tentative_gScore : = gScore [ actual ] + d ( actual , vecino ) si tentative_gScore < gScore [ vecino ] // Esta ruta al vecino es mejor que cualquier anterior. ¡Grabe! cameFrom [ vecino ] : = gScore actual [ vecino ] : = tentative_gScore fScore [ vecino ] : = gScore [ vecino ] + h ( vecino ) si el vecino no está en openSet openSet . agregar ( vecino ) // conjunto abierto está vacía pero el objetivo no se alcanzó retorno fracaso
Observación: En este pseudocódigo, si un nodo es alcanzado por una ruta, eliminado de openSet y posteriormente alcanzado 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 coherente . Si la heurística es coherente, cuando se elimina un nodo de openSet, se garantiza que la ruta a él es óptima, por lo que la prueba 'tentative_gScore
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: gol; naranja: visitado
El algoritmo A * también tiene aplicaciones del mundo real. En este ejemplo, los bordes son vías férreas 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 lazos para 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 utilizar para recuperar la ruta óptima. Si se mantienen estas referencias, 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í, los punteros de prioridad y padre se cambian para corresponder a la ruta de menor costo. Una cola de prioridad basada en el 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 un 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 * dondepara todo x . [10] [11] 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 asignación, disminuimos el contador C en uno. Por tanto, cuanto antes se descubre un nodo, mayor es suvalor. 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.
Propiedades
Terminación e integridad
En gráficos finitos con pesos de borde no negativos, se garantiza que A * terminará y está completo , es decir, siempre encontrará una solución (un camino desde el principio hasta el objetivo) si existe. En gráficas infinitas con un factor de ramificación finito y costos de borde que están limitados desde cero ( para algunos arreglados ), Se garantiza que A * terminará solo si existe una solución. [ cita requerida ]
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 una ruta desde el principio hasta la meta cuyo costo real es menor que el costo estimado de cualquier ruta desde el inicio hasta la meta a través de cualquier nodo abierto (el nodo valor). Cuando la heurística es admisible, esas estimaciones son optimistas (no del todo; consulte 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 principio 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 la 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 la suma no se garantiza que sea optimista.
Eficiencia optima
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 la heurística de A * siendo simplemente admisible o 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 admisibles similares a A * en todos los problemas de búsqueda ″ no patológicos ″. En términos generales, su noción de 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 coherente. En ese caso, Dechter y Pearl demostraron que existen algoritmos similares a A * admisibles 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 que se utiliza es admisible pero no coherente, es posible que un nodo se expanda en 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
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 optimalidad relajando el criterio de admisibilidad. A menudo queremos limitar esta relajación, de modo que podamos garantizar que la ruta de la solución no sea peor que (1 + ε ) veces la ruta de la solución óptima. Esta nueva garantía se denomina ε -admisible.
Hay varios algoritmos ε -admisibles:
- Ponderación ponderada A * / 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 función heurística, y se realiza la A * busca como de costumbre (que eventualmente ocurre más rápido que usar h a ya que se expanden menos nodos). Por tanto, 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. [14]
- La ponderación dinámica [15] utiliza la función de costes., dónde , y donde es la profundidad de la búsqueda y N es la longitud anticipada de la ruta de la solución.
- La ponderación dinámica muestreada [16] utiliza el muestreo de nodos para estimar mejor y eliminar el error heurístico.
- . [17] utiliza 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, 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.
- AlphA * [19] intenta promover la explotación en profundidad prefiriendo los nodos expandidos recientemente. AlphA * usa la función de costo, dónde , donde λ y Λ son constantes con, π ( n ) es el padre de n , y ñ es el nodo expandido más recientemente.
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 ). [20] Esto supone que existe un estado objetivo y que es accesible desde el estado inicial; si no lo es 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 expandiría una búsqueda desinformada. 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 [21]
Las buenas heurísticas son aquellas con un factor de ramificación efectivo bajo (el óptimo es b * = 1 ).
La complejidad del tiempo es polinomial cuando el espacio de búsqueda es un árbol, hay un estado objetivo único y la función heurística h cumple la siguiente condición:
donde h * es la heurística óptima, el costo exacto para ir de xa 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. [14] [20]
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. [22] En la práctica, esto 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 la profundización iterativa A * , la A * limitada por la memoria y la SMA * .
Aplicaciones
A * se usa 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 NLP . [23] Otros casos incluyen una búsqueda informativa con aprendizaje en línea. [24]
Relaciones con otros algoritmos
Lo que distingue a A * de un codicioso algoritmo de búsqueda del 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ísticapara todos los nodos; [10] [11] a su vez, tanto Dijkstra como A * son casos especiales de programación dinámica . [25] A * en sí mismo es un caso especial de una generalización de bifurcación y cota . [26]
Variantes
- En cualquier momento A * [27]
- Bloque A *
- D*
- Campo D *
- Franja
- Fringe Saving A * (FSA *)
- Adaptativo generalizado A * (GAA *)
- Búsqueda heurística incremental
- Reducido A * [28]
- Profundización iterativa A * (IDA *)
- Búsqueda de punto de salto
- Planificación de por vida A * (LPA *)
- Nuevo bidireccional A * (NBA *) [29]
- Memoria simplificada acotada 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. [30]
Ver también
- Búsqueda en amplitud primero
- 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 tomar cualquier ángulo.
Notas
- ^ “A * -like” significa que el algoritmo busca extendiendo las rutas que se originan en el nodo de inicio un borde a la vez, tal como lo hace A *. Esto excluye, por ejemplo, los algoritmos que buscan hacia atrás desde la meta o en ambas direcciones simultáneamente. Además, los algoritmos cubiertos por este teorema deben ser admisibles y "no más informados" que A *.
- ^ Los nodos de objetivo se pueden pasar varias veces si quedan otros nodos convalores de f másbajos, ya que pueden conducir a un camino más corto hacia un objetivo.
Referencias
- ^ Russell, Stuart J. (2018). Inteligencia artificial un enfoque moderno . Norvig, Peter (4ª ed.). Boston: Pearson. ISBN 978-0134610993. OCLC 1021874142 .
- ^ 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 conferencias en Ciencias de la Computación. 5515 . Saltador. págs. 11 个 $ 7–139. CiteSeerX 10.1.1.164.8916 . doi : 10.1007 / 978-3-642-02094-0_7 . ISBN 978-3-642-02093-3.
- ^ Zeng, W .; Iglesia, RL (2009). "Encontrar caminos más cortos en redes de carreteras reales: el caso de A *" . Revista Internacional de Ciencias de la Información Geográfica . 23 (4): 531–543. doi : 10.1080 / 13658810801949850 . S2CID 14833639 .
- ^ a b c Hart, PE; 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–107. doi : 10.1109 / TSSC.1968.300136 .
- ^ Doran, JE; Michie, D. (20 de septiembre de 1966). "Experimentos con el programa Graph Traverser". Proc. R. Soc. Lond. Una . 294 (1437): 235–259. Código Bibliográfico : 1966RSPSA.294..235D . doi : 10.1098 / rspa.1966.0205 . ISSN 0080-4630 . S2CID 21698093 .
- ^ a b Nilsson, Nils J. (30 de octubre de 2009). La búsqueda de la inteligencia artificial (PDF) . Cambridge: Cambridge University Press. ISBN 9780521122931.
- ^ Edelkamp, Stefan; Jabbar, Shahid; Lluch-Lafuente, Alberto (2005). "Búsqueda heurística algebraica de costes" (PDF) . Actas de la XX Conferencia Nacional sobre Inteligencia Artificial (AAAI) : 1362-1367.
- ^ Hart, Peter E .; Nilsson, Nils J .; Rafael, Bertram (1 de diciembre de 1972). "Corrección de '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 . ISSN 0163-5719 . S2CID 6386648 .
- ^ a b Dechter, Rina; Judea Pearl (1985). "Estrategias de búsqueda generalizadas del mejor primero y la optimización de A *". Revista de la ACM . 32 (3): 505–536. doi : 10.1145 / 3828.3830 . S2CID 2092415 .
- ^ a b 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.
- ^ a b Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language , Apress, p. 214, ISBN 9781430232377.
- ^ 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 .
- ^ Pohl, Ira (1970). "Primeros resultados sobre el efecto del error en la búsqueda heurística". Inteligencia de máquina . 5 : 219-236.
- ^ a b 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.
- ^ Pohl, Ira (agosto de 1973). "La evitación de catástrofes (relativas), competencia heurística, ponderación dinámica genuina y problemas computacionales en la resolución de problemas heurísticos" (PDF) . Actas de la Tercera Conferencia Conjunta Internacional sobre Inteligencia Artificial (IJCAI-73) . 3 . California, EE.UU. págs. 11-17.
- ^ Köll, Andreas; Hermann Kaindl (agosto de 1992). "Un nuevo enfoque para la ponderación dinámica". Actas de la Décima Conferencia Europea de Inteligencia Artificial (ECAI-92) . Viena, Austria. págs. 16-17.
- ^ Pearl, Judea; Jin H. Kim (1982). "Estudios en heurística semi-admisible". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 4 (4): 392–399. doi : 10.1109 / TPAMI.1982.4767270 . PMID 21869053 . S2CID 3176931 .
- ^ Ghallab, Malik; Dennis Allard (agosto de 1983). " A ε - un eficiente algoritmo de búsqueda heurística casi admisible" (PDF) . Actas de la Octava Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI-83) . 2 . Karlsruhe, Alemania. págs. 789–791. Archivado desde el original (PDF) el 6 de agosto de 2014.
- ^ Reese, Bjørn (1999). "AlphA *: un ε -admisible algoritmo de búsqueda heurística" . Archivado desde el original el 31 de enero de 2016 . Consultado el 5 de noviembre de 2014 . Cite journal requiere
|journal=
( ayuda ) - ^ a b Russell, Stuart ; Norvig, Peter (2003) [1995]. Inteligencia artificial: un enfoque moderno (2ª ed.). Prentice Hall. págs. 97-104. ISBN 978-0137903955.
- ^ Russell, Stuart ; Norvig, Peter (2009) [1995]. Inteligencia artificial: un enfoque moderno (3ª ed.). Prentice Hall. pag. 103. ISBN 978-0-13-604259-4.
- ^ Russell, Stuart J. (2018). Inteligencia artificial un enfoque moderno . Norvig, Peter (4ª ed.). Boston: Pearson. ISBN 978-0134610993. OCLC 1021874142 .
- ^ Klein, Dan; Manning, Christopher D. (2003). Análisis sintáctico A *: selección rápida y exacta del análisis sintáctico de Viterbi . Proc. NAACL-HLT.
- ^ 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 .
- ^ Ferguson, Dave; Likhachev, Maxim; Stentz, Anthony (2005). Una guía para la planificación de rutas basada en heurística (PDF) . Proc. Taller ICAPS sobre Planificación bajo Incertidumbre para Sistemas Autónomos.
- ^ Nau, Dana S .; Kumar, Vipin; Kanal, Laveen (1984). "Ramificación general y cota, y su relación con A ∗ y AO ∗" (PDF) . Inteligencia artificial . 23 (1): 29–58. doi : 10.1016 / 0004-3702 (84) 90004-3 .
- ^ Hansen, Eric A. y Rong Zhou. " Búsqueda heurística en cualquier momento. Archivado el 5 denoviembre de 2016en la Wayback Machine " J. Artif. Intell. Res. (JAIR) 28 (2007): 267-297.
- ^ https://www.cambridge.org/core/journals/robotica/article/abs/investigating-reduced-path-planning-strategy-for-differential-wheeled-mobile-robot/6EDFFC11CEF00D0E010C0D149FE9C811 .
- ^ Pijls, Wim; Post, Henk " Otro algoritmo bidireccional más para las rutas más cortas " En el Informe del Instituto Econométrico EI 2009-10 / Instituto Econométrico, Universidad Erasmus de Rotterdam. Escuela de Economía Erasmus.
- ^ "Algoritmos de ruta más corta punto a punto eficientes" (PDF) . Cite journal requiere
|journal=
( ayuda )de la Universidad de Princeton
Otras lecturas
- Nilsson, Nueva Jersey (1980). Principios de la inteligencia artificial . Palo Alto, California: Tioga Publishing Company. ISBN 978-0-935382-01-3.
enlaces externos
- Explicación visual clara A *, con consejos y pensamientos sobre la búsqueda de caminos
- Variación en A * llamada Búsqueda de ruta jerárquica A * (HPA *)
- Brian Grinstead. "A * Algoritmo de búsqueda en JavaScript (actualizado)" . Archivado desde el original el 15 de febrero de 2020 . Consultado el 8 de febrero de 2021 .