Visualizador de búsqueda de caminos
Observa cómo los algoritmos clásicos de búsqueda en grafos encuentran su camino por una cuadrícula. Arrastra el inicio y el objetivo, pinta muros y celdas con peso, genera un laberinto y anima A*, Dijkstra, la búsqueda voraz primero el mejor, BFS o DFS para comparar cuántas celdas explora cada uno.
Última actualización:
Comparación en este tablero
| Algoritmo | Visitadas | Longitud del camino | Coste del camino | ¿El más corto? |
|---|
Cómo usar Visualizador de búsqueda de caminos
- Elige un algoritmo de la lista. Debajo de la cuadrícula aparece una breve explicación de cómo funciona.
- Edita el tablero: elige Muro, Peso o Borrar y haz clic o arrastra sobre la cuadrícula. Arrastra la flecha verde (inicio) o el objetivo rojo para moverlos.
- Genera un laberinto si quieres un desafío ya hecho: elige un tipo de laberinto y pulsa Generar laberinto.
- Pulsa Iniciar búsqueda para animarlo. Usa el control de velocidad, Pausa o Paso para avanzar celda a celda.
- Pulsa Comparar todos los algoritmos para ejecutar todos los algoritmos en el mismo tablero y ver las celdas visitadas, la longitud del camino, el coste y si cada camino es el más corto.
Comparación de algoritmos de búsqueda de caminos
| Algoritmo | Estructura de datos | Usa pesos | ¿Camino más corto? | Tiempo (cuadrícula con V celdas) | Comportamiento típico |
|---|---|---|---|---|---|
| Búsqueda A* | Cola de prioridad sobre f = g + h | Sí | Sí, con una heurística admisible | O(V log V) en el peor caso | Búsqueda estrecha dirigida al objetivo |
| Algoritmo de Dijkstra | Cola de prioridad sobre g | Sí | Sí (costes no negativos) | O(V log V) | Ondas uniformes en todas las direcciones |
| Voraz primero el mejor | Cola de prioridad sobre h | No (ignora el coste acumulado) | No | O(V log V) en el peor caso | Muy rápida en tableros abiertos, los muros la engañan |
| Búsqueda en anchura | Cola FIFO | No | Solo el menor número de movimientos | O(V) | Capa a capa desde el inicio |
| Búsqueda en profundidad | Pila LIFO | No | No | O(V) | Ramas largas y únicas, mucho retroceso |
En una cuadrícula cada celda tiene como máximo 4 vecinas (8 con diagonales), así que el número de aristas crece linealmente con el número de celdas y las versiones con montículo binario se ejecutan en O(V log V).
Heurísticas usadas en A* y en la búsqueda voraz
- Distancia Manhattan (movimientos en cuatro direcciones): h = |Δfila| + |Δcol|. Es el coste exacto en una cuadrícula vacía sin pesos, así que nunca sobrestima.
- Distancia octil (con diagonales activadas): h = (|Δfila| + |Δcol|) + (√2 − 2) · min(|Δfila|, |Δcol|). Supone que te mueves en diagonal todo lo posible, y cada diagonal cuesta √2.
- Los pasos diagonales solo se permiten cuando las dos celdas rectas vecinas están abiertas, así que un camino nunca se cuela entre dos muros que se tocan en una esquina.
- Los empates en A* se resuelven a favor de la celda con menor h, lo que mantiene la búsqueda enfocada cuando muchas celdas comparten el mismo valor de f.
Experimentos que vale la pena probar
- Pesos frente a BFS: pinta una franja de pesos que cruce la ruta directa. Dijkstra y A* la rodean; BFS la atraviesa y obtiene un coste mayor.
- Trampa voraz: dibuja un muro en forma de U que se abra en dirección contraria al objetivo, con el inicio dentro. La búsqueda voraz llena la U antes de escapar, mientras que A* equilibra distancia y coste.
- Laberintos perfectos: en un laberinto de backtracker recursivo todos los algoritmos encuentran el mismo camino único; la diferencia es solo cuántas celdas explora cada uno antes.
- Sube el coste de peso a 20 y observa cómo Dijkstra y A* dan rodeos más largos que aun así cuestan menos.
Teclado: enfoca la cuadrícula con Tab, mueve la celda resaltada con las flechas, pulsa Espacio para dibujar con la herramienta seleccionada, S para colocar el inicio y T para colocar el objetivo.
Preguntas frecuentes
¿Cuál es el mejor algoritmo de búsqueda de caminos?
Para un único inicio y objetivo en una cuadrícula, A* con una heurística admisible suele ser la mejor opción: siempre encuentra el camino más barato, como Dijkstra, pero explora menos celdas porque la heurística dirige la búsqueda hacia el objetivo. Dijkstra es mejor cuando necesitas distancias a muchos destinos, y BFS es lo más sencillo cuando todos los movimientos cuestan lo mismo.
¿A* siempre encuentra el camino más corto?
A* garantiza encontrar un camino de coste mínimo cuando su heurística nunca sobrestima el coste restante real (una heurística admisible). Esta herramienta usa la distancia Manhattan para el movimiento en cuatro direcciones y la distancia octil para el movimiento diagonal, y ambas son admisibles porque cada movimiento cuesta al menos 1 (o √2 en diagonal).
¿Por qué BFS encuentra un camino más largo o más caro cuando hay pesos?
La búsqueda en anchura cuenta movimientos, no costes. Encuentra la ruta con menos pasos, así que no le importa atravesar celdas con peso. Dijkstra y A* suman el coste de cada celda a la que entran, así que rodean los pesos cuando eso sale más barato. Con los movimientos diagonales activados, BFS también trata una diagonal (coste √2) igual que un movimiento recto.
¿Por qué el camino de DFS es tan largo y sinuoso?
La búsqueda en profundidad sigue en la primera dirección disponible hasta llegar a un callejón sin salida y entonces retrocede. Se detiene en cuanto alcanza el objetivo, así que el camino que informa es simplemente la rama en la que estaba, no una ruta optimizada. DFS garantiza un camino si existe, pero nunca que sea corto.
¿Qué diferencia hay entre Dijkstra y la búsqueda voraz primero el mejor?
Dijkstra ordena las celdas por el coste ya pagado desde el inicio (g), así que se expande de forma uniforme. La búsqueda voraz primero el mejor ordena las celdas solo por la distancia estimada al objetivo (h), así que va directa a la meta. La voraz suele ser mucho más rápida, pero puede devolver un camino bastante más largo, sobre todo alrededor de muros y pesos. A* combina ambas: f = g + h.
¿Qué significan los pesos en este visualizador?
Una celda con peso se puede atravesar, pero entrar en ella cuesta más, como el barro o el tráfico. Entrar cuesta el coste de peso que elijas (5 por defecto) en lugar de 1. En los muros no se puede entrar. El coste del camino es la suma del coste de cada celda en la que se entra después del inicio.
¿Cómo se generan los laberintos?
El backtracker recursivo excava pasillos con una búsqueda en profundidad aleatorizada, lo que produce pasillos largos. El algoritmo de Prim aleatorizado hace crecer el laberinto desde una frontera aleatoria, dando muchos callejones sin salida cortos. La división recursiva parte de una sala abierta y la divide repetidamente con muros que tienen un hueco. Los tres producen laberintos perfectos con exactamente una ruta entre dos celdas abiertas cualesquiera.
¿Se prueban todas las herramientas de FreeToolCabin para comprobar su calidad y precisión?
Sí. Cada herramienta del sitio pasa pruebas automáticas en navegadores reales para comprobar que el resultado es correcto y que no hay errores. Si encuentras un fallo o tienes una sugerencia, escríbenos a [email protected] y lo revisaremos.