¿Cuáles son las ventajas y desventajas de la búsqueda A * y el algoritmo de Dijkstra? ¿Cuándo se debe usar cada uno?

Del algoritmo de Dijkstra – Wikipedia: “El algoritmo A * es una generalización del algoritmo de Dijkstra que reduce el tamaño del subgrafo que debe explorarse, si hay información adicional disponible que proporcione un límite inferior en la” distancia “al objetivo. “

Ambos algoritmos funcionan manteniendo en la memoria un conjunto de nodos “fronterizos” para los cuales conocemos la longitud del camino más corto hacia ellos, y extendiendo rutas potenciales hacia el destino a través de cada uno de estos nodos fronterizos al determinar si son parte del proceso más rápido. ruta a cualquiera de sus nodos vecinos (que luego se convierten en nodos fronterizos).

La diferencia es el orden en que se exploran estos nodos fronterizos. En el algoritmo de Dijkstra, se explora primero el nodo de frontera con la distancia más corta desde la fuente. En A *, determinamos el orden por un límite inferior en la longitud total de la ruta, que incluye la distancia desde la fuente, a lo que se agrega un límite inferior en la distancia que aún no se ha recorrido. Por ejemplo, si piensa en buscar una ruta en un mapa, entonces el límite inferior de la distancia desde un punto hasta el destino podría ser la distancia a medida que el cuervo vuela.

Entonces, en la práctica, A * suele ser más adecuado cuando tienes un límite inferior decente en la distancia restante.

El algoritmo de Dijkstra se ejecuta en un gráfico ponderado, comenzando con un nodo inicial y objetivo. Similar a A *, Dijkstra tiene un conjunto visitado y valores de distancia para determinar a qué nodo ir a continuación. Aquí tenemos una función de costo f (x) = g (x) donde nos enfocamos en encontrar el valor de costo real desde el origen hasta cada nodo. Dijkstra no tiene heurística y en cada paso elige bordes con el menor costo, tiende a “cubrir” más de su gráfico. Debido a eso, Dijkstra podría ser más útil que A *. Un buen ejemplo es cuando tiene varios nodos de destino candidatos, pero no sabe cuál es el más cercano. Una búsqueda * tiene dos funciones de costo f (x) = g (x) + h (x) donde g (x) es lo mismo que Dijkstra y h (x) es el costo aproximado del nodo x al nodo objetivo. A * solo expande un nodo si parece prometedor. Esencialmente, A * es una variación informada de Dijkstra. Al usar la mejor primera búsqueda, elige con avidez qué vértice explorar a continuación. A * es completo y óptimo si se trata de una heurística admisible. La diferencia clave entre Dijkstra y A * es que A * se enfoca para alcanzar el nodo objetivo desde el nodo actual, no para alcanzar cualquier otro nodo.

El algoritmo de Dijkstra no presta atención a la dirección en la que va, esto puede hacer que explorar vértices ni siquiera estén cerca del vértice objetivo, por lo que aumenta el tiempo para encontrar el camino más corto. A * es solo una optimización de Dijkstra para una fuente específica y para un objetivo específico. A * utiliza heurística, que resulta ser una estimación de cuán lejos estamos del vértice objetivo, esta heurística es lo que le da a A * su poder real porque tener un sentido de direccionalidad de exploración podría aumentar dramáticamente el tiempo para encontrar el más corto camino.

Y con respecto a dónde usar cuál, creo que es bastante obvio por el comportamiento del algoritmo en sí.

Espero que esto tenga sentido.