El inexperto aparato 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. 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).
¿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 n2, 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á.
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.
