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.
Para resolver el problema se reduce el mapa de carreteras y callejero a lo que en matemáticas se denomina un grafo: una serie de puntos o vértices (ciudades o lugares concretos, como los portales de una calle) conectados por caminos o aristas. En su forma más básica y simplificada se conocen las distancias que conectan unos puntos con otros (que en el algoritmo se llaman “pesos”) y a partir de ahí se van aplicando las reglas del algoritmo, empezando por el punto de salida. El resultado al cabo de unos cuantos cálculos y pruebas es el camino óptimo: el más corto.
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 otro algoritmo es el filtro de Kalman, que sirve para “identificar el estado de un sistema dinámico lineal cuando se le añade ruido blanco“. Esta explicación teórica suena un poco complicada, pero traduciéndola a un lenguaje más fácil de entender podría decirse que es lo que permite que el navegador GPS pueda seguir con una ruta cuando se pierde la señal o no hay cobertura: el sistema (el cálculo de la ruta en base a los datos disponibles) se ve afectado por ruido (en este caso: datos incompletos por falta de señal), pero aun así mantiene actualizada la posición en el mapa. Gracias a sus cálculos permite conocer la posición, tiempo, y velocidad –dentro de unos límites– aunque no se esté obteniendo la información en tiempo real sino un poco de “ruido”.
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
