En general, se dice que A * es el mejor algoritmo para resolver problemas de pathfinding.¿Es A * el mejor algoritmo de determinación de ruta?
¿Hay alguna situación en la que A * es no el mejor algoritmo para encontrar una solución?
¿Qué tan bueno es A * en comparación con BFS, DFS, UCS, etc.?
A * es especial porque se puede transformar en otros algoritmos de búsqueda de ruta al jugar con la forma en que evalúa los nodos y la heurística que utiliza. Puede hacer esto para simular Djikstra, la búsqueda de la primera búsqueda, la búsqueda de la respiración en primer lugar y la búsqueda de búsqueda en profundidad.
Además, a menudo es más fácil acelerarlo. Por ejemplo, si multiplicas una heurística admisible por una constante, c, puedes garantizar que el costo de la secuencia de nodos resultante no es más que c veces el resultado óptimo.
Por ejemplo, tome este awesome paper por Ian Davis (escrito para Star Trek armada). A * se usa con un conjunto jerárquico de puntos de referencia, lo que resulta en una ruta aproximada. LUEGO, para suavizar la ruta, vuelven a ejecutar A * en un nuevo gráfico generado que contiene los nodos en la ruta y los que están cerca para obtener una ruta más razonable. Finalmente, ejecutan bandas de goma para eliminar los nodos redundantes.
Por lo tanto, A * no es la solución para todo, pero es una herramienta muy versátil.
La respuesta corta es sí, hay situaciones en las que A * no es el mejor algoritmo para resolver un problema. Sin embargo, hay una serie de formas de evaluar qué constituye el mejor algoritmo para encontrar una solución.
Si usted está considerando mejor en términos de rendimiento de múltiples búsquedas de una sola fuente a muchos destinos, entonces usted debe considerar el uso de un enfoque más adecuado (Dijkstra's algorithm).
Si usted está considerando mejor en términos de rendimiento , a continuación, en algunos casos especiales DFS y BFS superará significativamente A *. De la experiencia pasada, esto ocurre para gráficos muy pequeños, casi triviales, pero requeriría pruebas cuidadosas y perfiles para hacer una declaración más fuerte.
Si usted está considerando mejor en términos de la longitud del recorrido, que es el tiempo que la ruta final producido por el algoritmo es, entonces A * es equivalente a cualquier otro algoritmo de búsqueda óptima.
Si usted está considerando mejor en términos de integridad , es decir, el algoritmo será siempre encontrar un camino hacia la meta, si existe tal camino. Si es así, entonces A * es equivalente a cualquier otro algoritmo completo (por ejemplo, búsqueda de ancho primero).
Si usted está considerando mejor en los casos en que algunos de los pesos en el gráfico son negativos, entonces usted tendrá que utilizar un algoritmo especial para resolver esos problemas (por ejemplo bellman-ford)
Si están considerando mejor en los casos en que la sin heurística es disponible entonces se debe recurrir a h(x,y)=0 forall states x and y. En este caso, A * es equivalente a la mejor primera búsqueda.
Si usted está considerando mejor en casos relacionados con la planificación de movimientos en espacio de configuración continuas, entonces A * puede trabajar adecuadamente en las dimensiones bajas, pero el almacenamiento de la gráfica de búsqueda empieza a ser poco práctico en altas dimensiones, y el necesitará utilizar algoritmos probabilísticamente completos aumenta (por ejemplo RRT, Bi-RRT, RDT)
Si está pensando en mejor en los casos en que la gráfica es parcialmente observable, sólo se conoce un subconjunto de todos los posibles vértices y bordes dentro del gráfico en una ny el tiempo, y hay que cambiar de estado para observar más de la gráfica, entonces necesita un algoritmo alternativo diseñado para ello (por ejemplo, planificación de toda la vida de Keonig *, * LPA, hace exactamente esto).
Si usted está considerando mejor en los casos donde el gráfico cambios en el tiempo, lo cual ocurre con frecuencia en la robótica al incorporar obstáculos en movimiento, entonces usted necesita un algoritmo que está diseñado para esto (por ejemplo Stentz de D* o Koenig & D * -Lite de Likhachev).
+1, aunque su descripción de LPA * es incorrecta. LPA * es como A *, pero en varias ejecuciones después de pequeños cambios en el gráfico * (modificador de pesos de borde, agregar/quitar vértices) *, puede recalcular la mejor ruta de principio a fin mucho más rápido que ejecutar A * nuevamente. El inicio/finalización siempre está en el mismo lugar; esto se contrasta con D \ * - Lite * (que se ha obsoleto D \ * completamente) *, en el que el "nodo de inicio" * (que representa el robot en movimiento, o lo que sea) * se mueve constantemente a lo largo de la mejor ruta entre recálculos. [Ver también] (http://cstheory.stackexchange.com/a/11866/8532). –
Una alternativa extremadamente simple (sin disputas con la heurística) es Collaborative Diffusion. Funciona excelentemente cuando es necesario apuntar a un objetivo o cualquier miembro de un grupo, de manera indiscriminada, y en este caso puede ser más rápido que A *. Simula el juego "Te estás poniendo más cálido/frío".
La difusión colaborativa crea un mapa de calor por "grupo" al que desea dirigirse ... si desea rastrear un objetivo específico, trátelo como su propio grupo creando un mapa de calor solo para ese objetivo; Dominio de colaboración difusión es juegos como el fútbol (en el que ambos equipos de agentes seguimiento de la bola y postes en concreto, lo que lleva a sólo 3 mapas de influencia) o Pacman (similares, múltiples agentes seguimiento PAC) o los juegos del ejército, donde hay un mapa de calor combinado que representa el cuerpo (agregado) de cada ejército según lo determinado por cada agente en ese ejército, para que un ejército pueda acercarse al "otro ejército" en lugar de "unidades específicas dentro del otro ejército". Esta generalidad puede permitir un mayor rendimiento.
Caminar consiste en escalada (que va desde la celda actual a una célula vecina más caliente) hasta llegar al destino (punto más caliente). El enfoque trata implícitamente con obstáculos en movimiento, es decir, otros agentes.
Es el más adecuado donde los mapas son bastante densamente pobladas con muchos, moviendo unidades, lo que justifica la amplia difusión que deberá efectuarse a través de todo el espacio de búsqueda en cada actualización.Está claro cómo un enfoque A * bien ajustado puede ser un orden de magnitud más barato en un mapa grande y escaso donde tenemos una unidad que apunta solo a otra unidad, porque con A * en este caso solo está trabajando en una fracción de mosaicos de mapas entre el buscador y el objetivo; mientras que con Collaborative Diffusion, en su lugar, se está difundiendo por todo el mapa solo para hacer lo mismo, lo que lo hace mucho más costoso.
Vale la pena señalar que el truco de multiplicar la heurística por una constante hará que la heurística sea inadmisible, y como resultado, la búsqueda ya no será óptima. –
Sí, pero como se indicó anteriormente, existen límites comprobables sobre el tipo de aproximación del resultado óptimo que esto producirá. En particular, para una constante, c, la ruta resultante no será más de c veces más larga que la ruta óptima. – sjdlgjsljg