Algoritmo de Dijkstra y Best-First-Search#
El Algoritmo de Dijkstra funciona visitando los vértices del grafo empezando por el punto de partida del objeto. A continuación, examina repetidamente el vértice más cercano aún no examinado, añadiendo sus vértices al conjunto de vértices a examinar. Se expande hacia fuera desde el punto de partida hasta llegar a la meta. Se garantiza que el Algoritmo de Dijkstra encuentra el camino más corto desde el punto de partida hasta la meta, siempre que ninguna de las aristas tenga un coste negativo. (Escribo «un camino más corto» porque a menudo hay múltiples caminos equivalentemente cortos). En el siguiente diagrama, el cuadrado rosa es el punto de partida, el cuadrado azul es la meta, y las áreas de color verde azulado muestran las áreas que el Algoritmo de Dijkstra escaneó. Las áreas de color verde azulado más claras son las más alejadas del punto de partida y, por lo tanto, forman la «frontera» de la exploración:
El algoritmo Greedy Best-First-Search funciona de manera similar, excepto que tiene alguna estimación (llamada heurística) de lo lejos que está cualquier vértice de la meta. En lugar de seleccionar el vértice más cercano al punto de partida, selecciona el vértice más cercano a la meta. La búsqueda codiciosa del mejor primero no garantiza que se encuentre el camino más corto. Sin embargo, se ejecuta mucho más rápido que el Algoritmo de Dijkstra porque utiliza la función heurística para guiar su camino hacia la meta muy rápidamente. Por ejemplo, si la meta se encuentra al sur de la posición inicial, el Greedy Best-First-Search tenderá a centrarse en los caminos que llevan hacia el sur. En el siguiente diagrama, el color amarillo representa los nodos con un valor heurístico alto (alto coste para llegar a la meta) y el negro representa los nodos con un valor heurístico bajo (bajo coste para llegar a la meta). Esto demuestra que el Greedy Best-First-Search puede encontrar caminos muy rápidamente en comparación con el Algoritmo de Dijkstra:
Sin embargo, ambos ejemplos ilustran el caso más simple – cuando el mapa no tiene obstáculos, y el camino más corto es realmente una línea recta. Consideremos el obstáculo cóncavo descrito en la sección anterior. El Algoritmo de Dijkstra trabaja más duro pero está garantizado que encuentra el camino más corto:
La Búsqueda Rápida y Codiciosa, por otro lado, trabaja menos pero su camino no es tan bueno:
El problema es que la Búsqueda Rápida y Codiciosa es «codiciosa» y trata de ir hacia la meta aunque no sea el camino correcto. Como sólo tiene en cuenta el coste de llegar a la meta e ignora el coste del camino hasta el momento, sigue avanzando aunque el camino en el que se encuentra se haya vuelto realmente largo.
¿No sería bueno combinar lo mejor de ambos? A* fue desarrollado en 1968 para combinar enfoques heurísticos como el Greedy Best-First-Search y enfoques formales como el Algoritmo de Dijsktra. Es un poco inusual, ya que los enfoques heurísticos suelen ofrecer una forma aproximada de resolver los problemas sin garantizar que se obtenga la mejor respuesta. Sin embargo, A* se construye sobre la heurística, y aunque la heurística en sí no le da una garantía, A* puede garantizar un camino más corto.