Por qué Importa el Pathfinding
Los algoritmos de búsqueda de caminos son fundamentales en ciencias de la computación e ingeniería. Impulsan la navegación GPS, la IA de videojuegos, el enrutamiento de redes y la robótica. Entender como diferentes algoritmos exploran un grafo y los compromisos entré optimalidad, velocidad y uso de memoria es esencial.
Búsqueda en Anchura vs Profundidad
BFS explora todos los vecinos a la distancia actual antes de moverse más lejos, garantizando caminos más cortos en grafos sin peso. DFS sigue un camino lo más 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 Búsqueda Heuristica
A* combina la optimalidad garantizada de Dijkstra con una estimación heuristica de la distancia restante. Al priorizar nodos que parecen más cercanos al objetivo, A* típicamente explora muchos menos nodos que Dijkstra encontrando el mismo camino más cortó.
