algorithm - pathfinding - path finding online
Diferencia y ventajas entre dijkstra y una estrella (5)
Esta pregunta ya tiene una respuesta aquí:
Leí esto: http://en.wikipedia.org/wiki/A*_search_algorithm
Dice que A * es más rápido que usar dijkstra y usa best-first-search para acelerar las cosas.
Si necesito que el algoritmo se ejecute en milisegundos, ¿cuándo A * se convierte en la elección más destacada?
Por lo que entiendo, no necesariamente devuelve los mejores resultados.
Si necesito resultados rápidos, ¿es mejor precomputar las rutas? Puede tomar megabytes de espacio para almacenarlos.
Dice que A * es más rápido que usar dijkstra y usa best-first-search para acelerar las cosas.
A * es básicamente una variación informada de Dijkstra.
A * se considera una "mejor primera búsqueda" porque elige con avidez qué vértice explorar a continuación, de acuerdo con el valor de f(v) [ f(v) = h(v) + g(v) ] - donde h es el heurística g es el costo hasta el momento.
Tenga en cuenta que si utiliza una función heurística no informativa: h(v) = 0 para cada v : obtiene que A * elige qué vértice desarrollar a continuación de acuerdo con el "costo hasta ahora" ( g(v) ) solamente, igual que Algoritmo de Dijkstra - entonces si h(v) = 0 , A * se ajusta por defecto al algoritmo de Dijkstra.
Si necesito que el algoritmo se ejecute en milisegundos, ¿cuándo A * se convierte en la elección más destacada?
No del todo, depende de muchas cosas. Si tiene una función heurística de descenso, desde mi experiencia personal, lo mejor primero codicioso (elegir según la función heurística sola) es generalmente mucho más rápido que A * (pero ni siquiera es casi óptimo).
Por lo que entiendo, no necesariamente devuelve los mejores resultados.
A * está completo (encuentra una ruta si existe) y es óptimo (siempre encuentra la ruta más corta) si usa una función heurística Admisible . Si su función no es admisible, todas las apuestas están desactivadas.
Si necesito resultados rápidos, ¿es mejor precomputar las rutas? Puede tomar megabytes de espacio para almacenarlos.
Esta es una optimización común realizada en algunos problemas, por ejemplo en el problema de los 15 rompecabezas , pero es más avanzado. Un camino desde el punto A al punto B se llama Macro. Algunos caminos son muy útiles y deben ser recordados. Se agrega un componente de aprendizaje automático al algoritmo para acelerar las cosas al recordar estas macros.
Tenga en cuenta que la ruta del punto A al punto B aquí no suele estar en el gráfico de estados, sino en el problema en sí (por ejemplo, cómo mover un cuadrado desde la línea más baja a la línea superior ...)
Para acelerar las cosas:
Si tiene una heurística y la encuentra demasiado lenta, y desea una solución más rápida, incluso si no es óptima, A * Epsilon suele ser más rápido que A *, mientras le da un límite en la optimalidad de la ruta (qué tan cerca está para ser óptimo).
Dijkstra es un caso especial para A * (cuando la heurística es cero).
Una búsqueda:
Tiene dos funciones de costo.
g(n): same as Dijkstra. The real cost to reach a node n.
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.
El costo total de cada nodo se calcula mediante f (n) = g (n) + h (n)
Dijkstra:
Tiene una función de costo, que es el valor del costo real desde la fuente hasta cada nodo: f (n) = g (n) Encuentra la ruta más corta desde la fuente a cada otro nodo al considerar solo el costo real.
Estos algorithems se pueden usar en pathfinding y graph crossing, el proceso de trazar una ruta eficientemente dirigida entre múltiples puntos, llamados nodos.
La fórmula para a* is f =g + h. , g significa costo real yh significa costo heurístico. La fórmula para Dijktras es f = g . no hay costo heurístico cuando estamos usando a* y si el costo heurístico es 0 entonces será igual a Dijktras algorithem.
Respuesta corta: A * usa heurística para optimizar la búsqueda. Es decir, puede definir una función que, hasta cierto punto, puede estimar el costo de un nodo al objetivo. Esto es particularmente útil cuando busca una ruta en una representación geográfica (mapa) donde puede, por ejemplo, adivinar la distancia al objetivo desde un nodo de gráfico determinado. Por lo tanto, típicamente A * se usa para encontrar rutas en juegos, etc. Donde Djikstra se usa en casos más genéricos.
No, A * no siempre dará el mejor camino. Si heurística es la distancia "geográfica", el siguiente ejemplo podría dar la ruta no óptima.
[airport] - [road] - [start] -> [road] -> [road] -> [road] -> [road] -> [target] - [airport]
|----------------------------------------------------------------|
A * es como Dijkstra , la única diferencia es que A * intenta buscar una mejor ruta mediante el uso de una función heurística que da prioridad a los nodos que se supone que son mejores que otros, mientras que Dijkstra solo explora todas las rutas posibles.
Su optimalidad depende de la función heurística utilizada, de modo que sí puede devolver un resultado no óptimo debido a esto y al mismo tiempo mejorar la heurística para su diseño específico, y mejores serán los resultados (y posiblemente la velocidad).
Está destinado a ser más rápido que Dijkstra, incluso si requiere más memoria y más operaciones por nodo, ya que explora muchos menos nodos y la ganancia es buena en cualquier caso.
La precomputación de las rutas podría ser la única manera si necesita resultados en tiempo real y la gráfica es bastante grande, pero generalmente desea buscar la ruta con menos frecuencia (supongo que desea calcularla con frecuencia).