Por que Importa el Pathfinding
Los algoritmos de busqueda de caminos son fundamentales en ciencias de la computacion e ingenieria. Impulsan la navegacion GPS, la IA de videojuegos, el enrutamiento de redes y la robotica. Entender como diferentes algoritmos exploran un grafo y los compromisos entre optimalidad, velocidad y uso de memoria es esencial.
Busqueda en Anchura vs Profundidad
BFS explora todos los vecinos a la distancia actual antes de moverse mas lejos, garantizando caminos mas cortos en grafos sin peso. DFS sigue un camino lo mas profundo posible antes de retroceder. BFS usa mas memoria (una cola de fronteras) mientras DFS usa menos (una pila).
Dijkstra y Grafos Ponderados
Dijkstra extiende BFS a grafos ponderados expandiendo siempre el nodo con la menor distancia conocida. En cuadriculas sin peso se comporta identicamente a BFS. Su complejidad temporal es O((V+E) log V) con una cola de prioridad.
A* y Busqueda Heuristica
A* combina la optimalidad garantizada de Dijkstra con una estimacion heuristica de la distancia restante. Al priorizar nodos que parecen mas cercanos al objetivo, A* tipicamente explora muchos menos nodos que Dijkstra encontrando el mismo camino mas corto.
