Dijkstra y A* camino más corto

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

Si el costo de movimiento es diferente para cada mosaico, el BFS simple por sí solo no puede garantizar la ruta más barata. En este momento, se utilizan algoritmos de ruta más corta como Dijkstra y A*.

Dijkstra

Primero se expande el vértice con el costo acumulado más bajo desde el punto de partida hasta el presente.

Nuevo costo = Costo actual + Costo del siguiente troncal

Si el nuevo costo es menor que el registro anterior
Actualizar distancia y vértices anteriores.

Cuando se utiliza la cola de prioridad, generalmenteO((V + E) log V)Se puede implementar en esa medida. El Dijkstra predeterminado no debe usarse porque la presencia de bordes negativos puede reducir la distancia más corta ya establecida.

A*

A* es el costo real desde el punto de partidagy el costo estimado para alcanzar la meta.hSumar para determinar prioridades.

f(n) = g(n) + h(n)

En las cuadrículas, la distancia de Manhattan o la distancia euclidiana se pueden utilizar como heurística. Para cuadrículas hexagonales, se debe utilizar una función de distancia apropiada para coordenadas hexagonales.

Se puede garantizar el camino más corto si el costo estimado no sobreestima el costo restante más bajo real. Si Heuristic es 0, A* se comporta como Dijkstra.

¿Cuál usar?

Requiere costos de múltiples destinos desde un punto de partida: Dijkstra
Navegue rápidamente a un destino: A*
Todos los costos de troncales son iguales: BFS

El rendimiento de la búsqueda de rutas no está determinado únicamente por el nombre del algoritmo. También se deben verificar el costo de generación de vecinos, la representación de obstáculos, la cola de prioridad y la calidad heurística.