El curso
Grafos y búsqueda de rutas es un curso avanzado de Programación en siete lecciones. Cada lección usa el mismo circuito: una Raspberry Pi 4 con un módulo de semáforo (rojo en GPIO17, ámbar en GPIO27, verde en GPIO22), que es la lámpara de estado del rover. Los mapas y las rutas se imprimen en el monitor serie, y cada paso se comprueba contra lo que la Pi imprime o qué lámpara enciende.
- Grafos como datos: las estaciones y caminos de la Base Jezero como un dict de listas, grados y el nodo con más conexiones, un verificador que encuentra un camino de sentido único, el lema del apretón de manos, y un mapa de terreno convertido en un grafo de celdas.
- BFS: una cola que explora en anillos, distancia en saltos, padres que reconstruyen la ruta, una sola función
routepara las estaciones y para la cuadrícula, el camino dibujado en el mapa, y una lámpara roja cuando un derrumbe encierra la meta. - DFS: recursión y una pila explícita, las estaciones que una tormenta de polvo aísla, un primer camino de 32 pasos donde BFS encontró 24, y el límite de recursión con que choca un campo de 30 por 30.
- Dijkstra: tiempos de viaje como pesos de las aristas,
heapqcomo cola de prioridad, la ruta de 30 minutos que toma un camino más que la de 40, y arena blanda en el mapa de terreno. - A: la prioridad f = g + h, la distancia Manhattan y las heurísticas admisibles, la misma ruta recorriendo 25 casillas en lugar de 42, una llanura de 600 casillas donde A expande 54 casillas contra las 570 de Dijkstra, y la peor ruta que elige una suposición demasiado confiada.
- Laberintos: un DFS aleatorizado talla un laberinto perfecto (39 pasajes para 40 celdas), BFS lo resuelve, la solución se dibuja, se cuentan los callejones sin salida, y una nueva semilla crea un nuevo laberinto.
- Jefe final: un robot que resuelve un laberinto: el gran final.
El catálogo también lista una ESP32-C3 y un chasis de dos ruedas. Este curso está construido solo con la Pi, con el movimiento del rover como comandos de manejo impresos, así cada paso se puede comprobar en el navegador.
El gran final
Rover 7's console reads commands typed in the Serial Monitor. Its canyon is
the maze from lesson 6 with six extra walls knocked out, because a real
canyon has loops. solve plans with A*, amber lamp on while it searches,
then green, and prints the route as drive commands: R F L F F F F R F L F R F L F F R F for the 11 cell route, worked out from the change in compass
heading at each cell. rock 4 9 drops a boulder on the route and the next
solve finds a 13 cell way around. rock 8 15 blocks the goal's only
way in, and the red lamp says so. drive plans and plays the commands
out, one move at a time, until "arrived at the goal. Science time."
Qué hace distinto el motor de la Pi
La Pi ejecuta MicroPython 1.29, no CPython. Para este curso eso se nota en algunos puntos:
heapqtieneheappush,heappopyheapify, que es todo lo que Dijkstra y A* necesitan;collections.dequeestá ahí para BFS.- Un dict no conserva el orden en que entraron las llaves, así que las tablas recorren
sorted(...). Las listas sí conservan su orden, así que las listas de vecinos están a salvo. - La recursión se detiene cerca de 800 marcos con
RuntimeError: pystack exhausted. El límite de CPython es 1,000 y su error esRecursionError. La lección de DFS choca contra el muro a propósito y luego lo arregla con una pila. random.seed(2026)da el mismo laberinto en cada ejecución en este motor. CPython saca sus números aleatorios de un generador distinto, así que la misma semilla allí puede tallar un laberinto diferente e igualmente perfecto.input()lee una línea escrita en el monitor serie.