algorithm - mas - ¿Es A*realmente mejor que Dijkstra en la búsqueda de caminos en el mundo real?

camino mas corto grafos java

Question

Estoy desarrollando un programa de búsqueda de caminos. Se dice teóricamente que A * es mejor que Dijkstra. De hecho, este último es un caso especial del primero. Sin embargo, al realizar pruebas en el mundo real, empiezo a dudar de que A * es realmente mejor.

Utilicé datos de la ciudad de Nueva York, del Desafío de Implementación del 9º DIMACS - Rutas más cortas , en las que se da la latitud y longitud de cada nodo.

Cuando aplico A *, necesito calcular la distancia esférica entre dos puntos, usando la fórmula de Haversine , que involucra pecado, cos, arcsina, raíz cuadrada. Todos estos consumen mucho tiempo.

El resultado es,

Usando Dijkstra: 39.953 ms, 256540 nodos expandidos.

Usando A *, 108.475 ms, se expandieron 255135 nodos.

Notando que en A *, expandimos menos 1405 nodos. Sin embargo, el tiempo para calcular una heurística es mucho más que el ahorro.

A mi entender, la razón es que en un gráfico real muy grande, el peso de la heurística será muy pequeño, y su efecto se puede ignorar, mientras que el tiempo de cálculo es dominante.

Answer 1

Como todo lo demás en el universo, hay una compensación. Puedes tomar el algoritmo de dijkstra para calcular con precisión la heurística, pero eso no serviría para nada, ¿no?

A * es un gran algoritmo en el sentido de que te hace inclinarte hacia la meta, teniendo una idea genuina de en qué dirección expandir primero. Dicho esto, debe mantener la heurística lo más simple posible, ya que todo lo que necesita es una dirección general.

De hecho, los cálculos geométricos más precisos que no se basan en los datos reales no necesariamente le dan una mejor dirección. Siempre y cuando no se basen en los datos, todas esas heurísticas le dan una dirección que es igualmente (in) correcta.

Answer 2

Creo que estás perdiendo más o menos el punto de A *. Está pensado para ser un algoritmo de gran rendimiento, parcialmente al hacer más trabajo intencionalmente pero con heurísticas baratas, y usted está casi rompiéndolo en pedazos al cargarlo con una pesada heurística de predicción extremadamente precisa.

Para la selección de nodos en A * solo debe usar una aproximación de distancia. El simple uso de (latdiff ^ 2) + (lngdiff ^ 2) como la distancia aproximada debería hacer que su algoritmo tenga un rendimiento mucho mayor que el de Dijkstra, y no dar resultados mucho peores en ningún escenario del mundo real. En realidad, los resultados deberían ser exactamente los mismos si calcula correctamente la distancia recorrida en un nodo seleccionado con el Haversine. Simplemente use un algoritmo barato para seleccionar posibles recorridos próximos.

Answer 3

En general, A * es más eficaz que Dijkstra, pero realmente depende de la función heurística que utilice en A *. Querrá una h (n) que sea optimista y que encuentre la ruta de menor costo, h (n) debería ser menor que el costo real. Si h (n)> = costo, entonces terminará en una situación como la que describió.

¿Podrías publicar tu función heurística?

Answer 4

También tenga en cuenta que el rendimiento de estos algoritmos depende en gran medida de la naturaleza del gráfico, que está estrechamente relacionado con la precisión de la heurística.

Si compara Dijkstra vs A * al navegar fuera de un laberinto en el que cada pasaje corresponde a un borde de un solo gráfico, probablemente haya muy poca diferencia en el rendimiento. Por otro lado, si la gráfica tiene muchos bordes entre nodos "lejanos", la diferencia puede ser bastante dramática. Piense en un robot (o un personaje de juego de computadora controlado por la IA) navegando en un terreno casi abierto con algunos obstáculos.

Mi punto es que, aunque el conjunto de datos de Nueva York que utilizó es definitivamente un buen ejemplo de gráfico "del mundo real", no es representativo de todos los problemas de búsqueda de caminos en el mundo real.

Answer 5

A* se puede reducir a Dijkstra estableciendo algunos parámetros triviales. Hay tres formas posibles en las que no mejora en Dijkstra:

1. La heurística utilizada es incorrecta: no es la llamada heurística admisible. A* debe usar una heurística que no sobreestime la distancia al objetivo como parte de su función de costo.
2. La heurística es demasiado cara de calcular.
3. La estructura gráfica del mundo real es especial.

En el caso de este último, debe tratar de basarse en la investigación existente, por ejemplo, "Dimensión de autopista, Caminos más cortos y Algoritmos demostrablemente eficientes" de Abraham et al.