Búsqueda de caminos en un laberinto – BFS, DFS y A*

Qué muestra

Un laberinto se modela como una cuadrícula de casillas; cada movimiento va a una casilla vecina arriba, abajo, a la izquierda o a la derecha, y todos cuestan lo mismo. La búsqueda en anchura guarda las casillas en espera en una cola: explora primero todas las casillas a un paso, luego a dos pasos, y la primera vez que llega a la meta ya tiene un camino más corto. La búsqueda en profundidad usa una pila y sigue una dirección hasta quedarse atascada, por eso su camino suele ser más largo. A* ordena las casillas por f = g + h, donde h es la distancia Manhattan a la meta.

Cómo usarla

Elige BFS, DFS o A* y pulsa Paso a paso para seguir las casillas numeradas en espera, o Ejecutar para ver una animación. Compara la tabla de resultados tras cada ejecución. Usa Dibujar paredes, Borrar paredes, Poner salida y Poner meta para cambiar la cuadrícula, o elige un Tipo de cuadrícula y pulsa Nueva cuadrícula.

Parámetros que puedes cambiar

• Algoritmo BFS – búsqueda en anchura, DFS – búsqueda en profundidad, A* – guiada por una estimación de distancia
• Tipo de cuadrícula Laberinto con ciclos, Obstáculos aleatorios, Cuadrícula vacía
• Número de columnas 11–41 casillas
• Paredes extra eliminadas (laberinto) 0–60 %
• Densidad de obstáculos 0–45 %
• Velocidad 1–100 pasos/s

Preguntas para explorar

1. ¿Por qué el camino que encuentra BFS siempre es uno de los más cortos y el de DFS a menudo no?
2. ¿Qué algoritmo explora menos casillas en una cuadrícula vacía y por qué?
3. ¿Puedes construir un laberinto donde DFS llegue a la meta explorando menos casillas que BFS?