path-finding - distancia - algoritmo a* ejemplo
¿Es A*el mejor algoritmo de búsqueda de caminos? (4)
A * es especial porque puede transformarse en otros algoritmos de búsqueda de caminos al jugar con la forma en que evalúa los nodos y las heurísticas que utiliza. Puedes hacer esto para simular la mejor búsqueda de Djikstra, la búsqueda en primer lugar, la búsqueda en profundidad y la búsqueda en profundidad.
Además, a menudo es fácil acelerarlo. Por ejemplo, si multiplica una heurística admisible por una constante, c, puede garantizar que el costo de la secuencia de nodos resultante no es más que c veces el resultado óptimo.
Por ejemplo, tome este impresionante documento de Ian Davis (escrito para Star Trek Armada). A * se utiliza con un conjunto jerárquico de puntos de ruta, lo que resulta en una ruta aproximada. ENTONCES, para suavizar la ruta, ejecutan A * nuevamente en un nuevo gráfico generado que contiene los nodos de 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.
Entonces, A * no es la solución para todo, pero es una herramienta muy versátil.
En general, se dice que A * es el mejor algoritmo para resolver problemas de búsqueda de rutas.
¿Hay alguna situación en la que A * no sea el mejor algoritmo para encontrar una solución?
¿Qué tan bueno es A * en comparación con BFS, DFS, UCS, etc.?
La respuesta corta es sí, hay situaciones en las que A * no es el mejor algoritmo para resolver un problema. Sin embargo, hay varias formas de evaluar qué constituye el mejor algoritmo para encontrar una solución.
Si está considerando lo mejor en términos de rendimiento de búsquedas múltiples desde una sola fuente a muchos destinos , entonces debería considerar usar un enfoque más adecuado ( el algoritmo de Dijkstra ).
Si está considerando lo mejor en términos de rendimiento , en algunos casos especiales, DFS y BFS superarán significativamente a A *. De la experiencia pasada, esto ocurre para gráficos muy pequeños, casi triviales, pero requeriría pruebas y perfiles detallados para hacer una declaración más fuerte.
Si está considerando lo mejor en términos de longitud de ruta , ese es el tiempo que dura la ruta final producida por el algoritmo, entonces A * es equivalente a cualquier otro algoritmo de búsqueda óptimo.
Si está considerando lo mejor en términos de integridad , es decir, el algoritmo siempre encontrará una ruta hacia la meta si existe tal ruta. Si es así, entonces A * es equivalente a cualquier otro algoritmo completo (por ejemplo, búsqueda en primer lugar).
Si está considerando lo mejor en casos donde algunos de los pesos en el gráfico son negativos , entonces necesitará usar un algoritmo especial para resolver esos problemas (por ejemplo, bellman-ford ).
Si está considerando lo mejor en los casos en que no hay heurística disponible , 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 está considerando lo mejor en casos relacionados con la planificación de movimiento en espacios de configuración continua , entonces A * puede funcionar adecuadamente en dimensiones bajas, pero el almacenamiento del gráfico de búsqueda comienza a ser poco práctico en dimensiones altas, y aumenta la necesidad de utilizar algoritmos probabilísticamente completos ( por ejemplo RRT , Bi-RRT, RDT)
Si está considerando lo mejor en los casos en que el gráfico es parcialmente observable , solo conoce un subconjunto de todos los vértices y bordes posibles dentro del gráfico en cualquier momento, y necesita cambiar de estado para observar más del gráfico, entonces necesita un algoritmo alternativo diseñado para esto (por ejemplo, la Planificación de por vida de Keonig A *, LPA *, hace exactamente esto).
Si está considerando lo mejor en casos donde el gráfico cambia con el tiempo , lo que ocurre con frecuencia en robótica cuando incorpora obstáculos en movimiento, entonces necesita un algoritmo diseñado para esto (por ejemplo, D* Stentz o D * -Lite de Koenig & Likhachev) .
Una alternativa extremadamente simple (sin tener que lidiar con las heurísticas) es la difusión colaborativa . Funciona magníficamente cuando necesita apuntar a un objetivo o a cualquier miembro de un grupo, indiscriminadamente , y en este caso puede ser más rápido que A *. Imita el juego "Te estás calentando / enfriando".
La difusión colaborativa crea un mapa de calor por "grupo" al que desea dirigirse ... si desea realizar un seguimiento de un objetivo específico, trátelo como su propio grupo creando un mapa de calor solo para ese objetivo; El dominio de Collaborative Diffusion son juegos como el fútbol (donde ambos equipos de agentes rastrean la pelota y los postes específicamente, lo que lleva a solo 3 mapas de influencia) o Pacman (similar, múltiples agentes que siguen a Pac) o juegos del ejército donde hay un mapa de calor que representa al cuerpo agregado) de cada ejército según lo determinado por cada agente en ese ejército, de modo que un ejército pueda acercarse a "el otro ejército" en lugar de "unidades específicas dentro del otro ejército". Esta generalidad puede permitir un mayor rendimiento.
Caminar consiste en escalar colinas (desde la celda actual hasta una celda vecina más cálida) hasta llegar al destino (el punto más cálido). El enfoque aborda implícitamente los obstáculos en movimiento, es decir, otros agentes.
Se adapta mejor cuando los mapas están bastante densamente poblados con muchas unidades en movimiento, lo que justifica la difusión extensa que debe ocurrir en todo el espacio de búsqueda en cada actualización. Está claro cómo un enfoque A * bien sintonizado puede ser un orden de magnitud más barato en un mapa grande y disperso donde solo tenemos una unidad enfocada en 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 lugar de eso, se está difundiendo por todo el mapa para hacer lo mismo, lo que lo hace mucho más costoso.
Veo que la pregunta es vieja, pero probablemente esta solución práctica sea útil para alguien. Recientemente encontré un código fuente muy bueno escrito en python
El código contiene los siguientes algoritmos de búsqueda de rutas:
- UNA*
- Dijkstra
- Mejor primero
- Bidireccional a *
- Primera búsqueda de amplitud (BFS)
- Profundización iterativa A * (IDA *)
cambiar el tamaño de la matriz y los valores permite sentir la diferencia entre diferentes algoritmos de búsqueda de ruta. Como se menciona en Wikipedia : "A * está completo y siempre encontrará una solución si existe"