Acerca de este experimento
Los planificadores de rutas en mapas, robots y videojuegos resuelven el mismo problema: encontrar la forma más barata de ir desde un inicio hasta una meta. En esta cuadrícula, cada paso por una carretera cuesta 1, un paso por el barro cuesta 5 y no se pueden atravesar las paredes. Observa cómo se expanden desde S tres algoritmos clásicos. La búsqueda en anchura cuenta los pasos e ignora el barro; Dijkstra siempre explora primero la celda más barata, y A* añade una estimación de la distancia que queda por recorrer para poder dirigirse directamente a la meta. Crea tus propios mapas y compara cuánto trabajo realiza cada uno.
Objetivos de aprendizaje
- Representar un mapa como un grafo de celdas conectadas con sus vecinas, asignando un coste a cada paso
- Describir cómo la búsqueda en anchura explora en anillos con el mismo número de pasos
- Explica por qué Dijkstra encuentra el camino más barato cuando los pasos tienen costes diferentes
- Explica cómo la heurística de A* reduce el número de celdas exploradas sin dejar de encontrar el mejor camino
- Compara los algoritmos según el coste del camino que encuentran y el trabajo que realizan
Cómo usarlo
- 1Elige BFS y pulsa Buscar. ¿El camino que encuentra pasa por el barro? Consulta su coste en la tabla.
- 2Elige Dijkstra y vuelve a buscar. Compara el camino y su coste con los de BFS.
- 3Elige A*. ¿El coste de su camino es el mismo que el de Dijkstra? ¿Cuántas celdas menos exploró?
- 4Observa la frontera azul durante la búsqueda. ¿En qué se diferencia su forma con Dijkstra y A*?
- 5Pinta una pared para cerrar el camino alrededor del barro. ¿Qué algoritmo cambia su camino y por qué?
- 6Pulsa Limpiar mapa y separa S y G arrastrándolas. Sin obstáculos, ¿cuántas celdas explora cada algoritmo?
El modelo
Supuestos
- Solo se puede mover hacia arriba, abajo, izquierda y derecha. Entrar en una celda cuesta 1 en carretera y 5 en barro; no se puede entrar en las paredes.
- Al buscar, BFS considera que cada paso cuesta 1, por lo que encuentra el camino con menos pasos. El coste de la tabla es el coste real de ese camino, incluido el barro.
- Si dos celdas tienen la misma prioridad, se explora primero la que se añadió antes, así que todas las ejecuciones con el mismo mapa dan exactamente el mismo orden.
- La búsqueda se detiene en cuanto se saca el objetivo de la frontera; en ese momento se conoce su coste mínimo.
Pruébalo en clase
- Q1¿Por qué puede BFS dar un camino más caro que Dijkstra, aunque tenga menos pasos?
- Q2Si todas las celdas fueran carreteras, ¿BFS y Dijkstra encontrarían caminos con el mismo coste? ¿Por qué?
- Q3¿Qué le pasaría a A* si la estimación h fuera diez veces la distancia de Manhattan?
- Q4¿Por qué A* explora menos celdas cuando el objetivo está en una zona abierta, pero aproximadamente tantas como Dijkstra en un laberinto?
- Q5Un navegador encuentra una ruta rápida a través de un país con millones de cruces de carreteras en menos de un segundo. ¿Qué ideas de este laboratorio lo hacen posible?
Preguntas frecuentes
¿Cuál es el mejor algoritmo?
Depende del problema. BFS es sencillo y correcto cuando todos los pasos cuestan lo mismo. Dijkstra admite costes distintos. A* da el mismo resultado que Dijkstra explorando menos celdas, siempre que se disponga de una buena estimación de la distancia hasta el objetivo.
¿Qué es la frontera?
La frontera es el conjunto de celdas a las que se ha llegado, pero que aún no se han explorado. Cada algoritmo toma una celda de la frontera cada vez; la única diferencia entre ellos es la regla que determina qué celda se toma a continuación.
¿Pueden estos algoritmos manejar costes negativos?
Dijkstra y A* suponen que ningún paso tiene un coste negativo. Con costes negativos, una celda que se había dado por definitiva podría resultar más adelante tener una ruta más barata, por lo que se necesita otro algoritmo, como Bellman-Ford.