La ruta más rápida: las matemáticas de Google Maps

Google Maps, Apple Maps o Waze, se han convertido en una parte imprescindible de la vida cotidiana de miles de millones de personas en todo el mundo, que necesitan consultar en tiempo real, cuál es la ruta ideal para dirigirse hasta su próxima reunión, la casa rural en la que pasarán sus vacaciones o ese restaurante en el que van a cenar.

Para muchas personas, que estas aplicaciones no solo sean capaces de indicarles el camino idóneo, sino que además tengan en cuenta factores como el tráfico o posibles incidencias en el trayecto, es prácticamente magia. Sin embargo, la respuesta está en las matemáticas.  En este sentido, aplicaciones como Google Maps, modelan las calles como un grafo (una red de nodos y aristas) y emplea algoritmos inteligentes como Dijkstra y A* para calcular el mejor camino.

La representación de la ciudad

Un grafo es, básicamente, un conjunto de puntos conectados por líneas. Aplicado a la estructura de calles de una ciudad, cada punto (o nodo) representa una intersección o un lugar de interés y cada línea (arista) representa un camino o calle que conecta dos nodos. Además, a esas aristas se les puede asociar un peso (por ejemplo, la distancia en kilómetros o el tiempo promedio que toma recorrer esa calle).

Modelar la ciudad como un grafo permite aplicar herramientas matemáticas para buscar caminos óptimos. ¿De qué forma? En primer lugar, cada vez que solicitamos a Google Maps la mejor ruta hasta una dirección determinada, la aplicación “traduce” la ubicación de origen y destino en nodos dentro de un inmenso grafo, que representa todas las calles, carreteras, etc. de una región determinada. Encontrar la ruta más rápida entre esos dos puntos, equivale en realidad, a resolver el “camino más corto” en ese grafo. Para lograrlo, la mayoría de estas aplicaciones recurren a algoritmos especiales que exploran la red de nodos y artistas en busca del trayecto óptimo: el algoritmo de Dijkstra y el algoritmo A* son los más populares.

Dijkstra y A*: explorando el camino más corto

El algoritmo de Dijkstra, nombrado así por el científico Edsger Dijkstra  es un método clásico para hallar caminos más cortos en un grafo. En esencia, Dijkstra toma un nodo inicial (por ejemplo, la dirección de nuestra casa) y explora sistemáticamente todas las rutas posibles hasta el nodo de destino (por ejemplo, nuestra oficina) calculando la distancia acumulada en las distintas posibilidades.

Así, desde el nodo inicial, “visita” primero el lugar accesible más cercano, después el más cercano a este y así sucesivamente, eligiendo siempre el camino de menor distancia acumulada. De esta forma, cada vez que el algoritmo llega a un nuevo cruce, actualiza la distancia más corta conocida a ese punto. Si encuentra una ruta más corta a un sitio al que ya había llegado por otra vía, reajusta ese cálculo.

Al final, el algoritmo devuelve el camino de menor distancia total (o menor tiempo, si usamos tiempo como peso) desde el origen hasta el destino. Esta forma calcular distancias y tiempos es la base de la mayoría de los sistemas GPS tradicionales y se utiliza como parte de cualquier sistema de navegación y planificación de rutas.

Por otro lado, el algoritmo A* toma la solidez de Dijkstra y le añade un toque de inteligencia adicional, introduciendo la “intuición” como parte fundamental de la búsqueda. A* combina dos factores cuando explora el grafo: por un lado, la distancia recorrida desde el inicio (como hacía Dijkstra) y, por otro, una estimación de la distancia que falta hasta el destino. Cada vez que A* evalúa hacia dónde moverse, suma lo que ya ha avanzado + lo que (estima) le queda por avanzar.

Esa estimación, llamada heurística, suele basarse en la distancia en línea recta hasta el destino u otro cálculo aproximado. Por ejemplo, si estamos buscando la ruta hacia una dirección al norte, A* “intuye” que, en igualdad de condiciones, avanzar hacia el norte probablemente le acerque más que ir hacia el sur. Gracias a esta estrategia, A* prioriza explorar primero los caminos que parecen más prometedores para llegar al destino, lo que, en la práctica, le permite visitar menos nodos que Dijkstra y por lo tanto, encontrar la solución de forma más rápida en la mayoría de los casos.

Tráfico y otros ajustes en tiempo real

Pero calcular el camino más corto en un grafo vial es solo parte de lo que hacen estas aplicaciones. La realidad de conducir por la ciudad incluye tener en cuenta el tráfico, accidentes, obras, etc. En los últimos años, aplicaciones como Google Maps integran estos datos en tiempo real, para ajustar sobre la marcha la ruta recomendada. Para ello, los pesos de las aristas (que representan tiempos de viaje) se pueden recalibrar dinámicamente según las condiciones actuales. Si una autopista que normalmente es rápida se congestiona, el algoritmo lo detecta y la “penaliza” aumentando su peso, de modo que tal vez otra ruta alternativa pase a ser más atractiva.

¿De dónde obtienen empresas como Google esos datos de tráfico al instante? La respuesta está en nuestros propios smartphones. Cuando usamos Google Maps, el teléfono envía datos anónimos de ubicación y velocidad a los servidores de la empresa. Al agregar la información de millones de usuarios, el sistema detecta patrones: por ejemplo, si muchos móviles están avanzando muy lento en la misma carretera, eso sugiere un atasco.  Además, también se apoya en convenios con autoridades locales (por ejemplo, sensores de tráfico municipales) y en modelos predictivos: ha acumulado datos históricos que le permiten prever atascos habituales según la hora y el día, usando algoritmos de inteligencia artificial para anticiparse a la congestión. De esta forma, el algoritmo no solo calcula rutas sobre un mapa estático, sino sobre un mapa vivo, que refleja lo que está pasando minuto a minuto en las calles.

Y aunque como hemos visto los algoritmos de rutas en grafos juegan un papel fundamental a la hora de dirigirnos hasta nuestro destino, no son exclusivos de la navegación GPS; tienen infinidad de aplicaciones en tecnología y otros campos, como los videojuegos, la logística o la IA aplicada, mejorando los movimientos de los NPCs (non playable characters), optimizando las rutas de reparto o de transporte público, o ayudando a los vehículos y robots autónomos a evitar obstáculos.

MÁS INFORMACIÓN

Grado en Matemáticas Aplicadas a la Ingeniería de Software

¿Qué necesito para estudiar matemáticas?

5 razones por las que formarte en matemáticas aplicadas a la ingeniería de software