La ciencia de dos algoritmos que nos permiten viajar en coche sin mayores problemas
Un algoritmo (no confundir con logaritmo) es un método para lograr un objetivo siguiendo una serie de reglas definidas paso a paso. Los ordenadores y otros dispositivos utilizan algoritmos más o menos complejos para todo tipo de tareas, desde ordenar una serie de números a hacer salir a un robot de un laberinto o mantener estable la temperatura de una habitación. Relacionados con el mundo del automóvil hay dos que resultan especialmente interesantes y que –sin que mucha sea consciente de su existencia– nos ayudan en el día a día. Tienen nombres propios: Dijkstra y Kalman y están relacionados con los sistemas de navegación y rutas.
Algoritmo de Dijkstra
El algoritmo de Dijkstra, llamado así en honor de su descubridor el informático Edsger Dijkstra allá por 1959, es la forma de encontrar la ruta más corta entre dos puntos de un mapa. Es una forma eficiente de solucionar un problema aparentemente sencillo, pero en realidad muy complejo, dado que el número de posibles rutas de un lugar A a otro lugar B, si se tienen en cuenta todas las posibilidades, crece exponencialmente a medida que aumenta el número de puntos.
Naturalmente, el algoritmo de los navegadores más complejos tiene en cuenta otros factores (y existen algoritmos similares al de Dijkstra, como el llamado algoritmo A* o el Bellman-Ford, con sus ventajas o desventajas). Se puede, por ejemplo, usar el dato del tiempo que se tarda en ir de un punto a otro en vez de la distancia, si lo que se quiere es llegar antes en vez de recorrer la mínima distancia. Esto puede hacerse conociendo los límites de velocidad en cada tramo / camino –información que suele estar en los mapas. O, como se hace actualmente, considerando un histórico de la velocidad típica de los coches que pasan por allí e incluso del estado del tráfico en tiempo real. Estas variantes permiten responder incluso a preguntas como: ¿a qué hora tengo que salir para llegar a las 10:00 a tal sitio?, y que el resultado sea preciso y esté perfectamente justificado.
Algoritmos: El filtro de Kalman
El efecto del filtro de Kalman es lo que permite que el navegador siga funcionando aún dentro de un túnel cuando no se puede recibir la señal de los satélites GPS: el icono del vehículo traza la ruta calculada a la velocidad prevista durante cierto tiempo. También produce el efecto de que cuando tomamos erróneamente una salida de la autopista el navegador se confunda durante un breve instante suponiendo que hemos ido por el camino previsto (puesto que tarda en actualizar los datos reales del GPS y recalcular la ruta). Gracias a ese filtro los aviones, naves espaciales y automóviles pueden “seguir su ruta” a pesar de que las señales de posicionamiento no se reciban perfectamente.
Foto | Kalman Filtering (CC) Wikimedia