Páginas

martes, 26 de abril de 2016

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


¿Qué carretera es mejor para ir de Madrid a Ciudad Real?
Para viajar de Ciudad Real a Madrid, ¿es mejor la carretera de Toledo o la de Andalucía? Así toma la decisión tu GPS

By: Macario Polo Usaola  Via: EL PAÍS, TECNOLOGÍA

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).

¿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.




ShareThis