¿Cómo sabe el GPS qué ruta recomendarnos?

Vivo en Ciudad Real, pero tengo mucha familia en Madrid. Un tema recurrente, desde hace más de treinta y cinco años, cuando llegan o llegamos de viaje, es si hemos ido o venido por la carretera de Toledo o por la de Andalucía. A diferencia del GPS al que podríamos consultar para ver qué camino es mejor, nosotros tenemos mucha experiencia en este recorrido (y en la conversación consiguiente).

El inexperto aparato, sin embargo, recomienda uno u otro camino en función de la distancia, de las características de cada carretera, e incluso de las horas en que preveamos viajar: así, el sistema informático de enrutamiento puede mostrarnos una alternativa u otra. Lo que no hará, seguro, es recomendarnos pasar por Badajoz, o por Valencia, o por Cádiz, para llegar desde nuestro origen, en mitad de La Mancha, hasta la capital, en el centro de la Península Ibérica.

La determinación del camino mínimo desde un lugar de origen a uno de destino es un problema clásico en Informática, que cualquier estudiante universitario de esta disciplina debe saber resolver.

El problema responde a lo que se llama un recorrido en un grafo que, en Informática, es un colección de puntos (ciudades o edificios o direcciones postales, por ejemplo) con líneas que los conectan (carreteras, calles, caminos). A cada línea se le asigna lo que se llama un "peso", que normalmente es la distancia, pero que puede ser otro factor (como el número de carriles o la velocidad máxima permitida) o una conjunción de factores (la distancia y el número de carriles y la velocidad máxima y la existencia de obras en algún trecho).

La determinación del camino mínimo desde un lugar de origen a uno de destino es un problema clásico en Informática, que cualquier estudiante universitario de esta disciplina debe saber resolver

¿Cómo determina un sistema informático la ruta óptima de manera automática? El cálculo del camino óptimo es lo que se llama un problema de orden n², es decir, que su tiempo de cálculo depende del número de puntos en el mapa elevado al cuadrado. Pero son tantos los puntos en el mapa (sólo España tiene más de 8.000 municipios, cada uno con sus calles, cruces, monumentos, edificios públicos…) que la aplicación del llamado algoritmo de Dijkstra se torna imposible.

Para resolver este tipo de problemas en un tiempo razonable se utilizan algoritmos que se llaman "voraces": un algoritmo voraz avanza progresivamente hacia la solución, en varios pasos, tomando en cada paso el trozo "más gordo" de la tarta o, en nuestro contexto, el elemento de la solución que abarata más, al menos parcialmente, el recorrido entre los dos puntos.

En el caso concreto de la determinación del camino mínimo en un mapa se utiliza habitualmente un algoritmo llamado A* ("A asterisco" o "A estrella"), que mezcla la heurística humana (es decir: cómo iríamos de Madrid a Ciudad Real si no tuviéramos GPS) con el rigor matemático y el pseudorigor voraz. En efecto, A* considera todos los lugares a los que podemos llegar directamente desde el lugar origen y calcula la distancia a cada uno: por ejemplo, para llegar de Madrid a Ciudad Real, calcula primero la distancia desde Madrid a sus lugares directamente adyacentes: Alcorcón (16 km), Las Rozas (19), Parla (25) o Alcalá de Henares (35,6); hecho esto, determina la distancia en línea recta desde cada uno de estos lugares intermedios hasta el lugar de destino: 150 km desde Alcorcón, 167 desde Las Rozas, 136 desde Parla, 172 desde Alcalá, y suma las dos distancias: 166 Madrid-Ciudad Real si vamos por Alcorcón; 183 por Las Rozas; 161 si pasamos por Parla; 197 desviándonos por Alcalá.

Para resolver este tipo de problemas en un tiempo razonable se utilizan algoritmos que se llaman "voraces": un algoritmo voraz avanza progresivamente hacia la solución, en varios pasos, tomando en cada paso el trozo 'más gordo' de la tarta

Así que A* se queda con Parla, descarta los demás municipios y repite el proceso: ¿A dónde podemos ir desde Parla? A Getafe, a Pinto, a Fuenlabrada, a Illescas. ¿Qué distancias hay desde Parla a estos sitios? ¿Y qué distancia en línea recta desde estos sitios a Ciudad Real, nuestro destino? Pues A* hace lo mismo: calcula, suma y selecciona; calcula, suma y selecciona; calcula de nuevo, suma otra vez y selecciona un nuevo subobjetivo; e itera así, hasta que consigue al fin recomendarnos las dos rutas, Toledo y Andalucía, sin ser capaz tampoco la Informática y sus métodos de cómputo de resolvernos esa duda que nos corroe a mi familia y a mí desde hace ya tantos años.

Macario Polo Usaola es profesor titular de la Universidad de Castilla-La Mancha (área de Lenguajes y Sistemas Informáticos), en el campus de Ciudad Real.

Crónicas del Intangible es un espacio de divulgación sobre las ciencias de la computación, coordinado por la sociedad académica SISTEDES (Sociedad de Desarrollo de Ingeniería y de Tecnologías de Desarrollo de Software). El intangible es la parte no material de los sistemas informáticos (es decir, el software), y aquí se relatan su historia y su devenir. Los autores son profesores de las universidades españolas, coordinados por Ricardo Peña Marí (catedrático de la Universidad Complutense de Madrid) y Macario Polo Usaola (profesor titular de la Universidad de Castilla-La Mancha.