Seguimos con la tercera entrega de la serie sobre “Técnicas utilizadas en la planificación”. En esta ocasión es el turno de los algoritmos:

Aunque parezca que en matemáticas nunca hay disensos porque es una ciencia estructurada, esto no es así del todo. Y una prueba de ello es que para el término algoritmo no existe una definición siquiera intencional (es decir, aquella que proporciona todas las propiedades que requiere un objeto para estar incluido en el término definido).

Sí que hay cierto consenso al señalar que los algoritmos responden a conjuntos prescritos de instrucciones o reglas bien definidas, ordenadas y finitas que permiten resolver un cálculo o, lo que es lo mismo, un número finito de pasos que convierten los datos de un problema (inputs) en una solución (outputs). Pero no está tan claro qué debe pasar entre medias para decidir qué es y qué no es un algoritmo.

Aunque dicho así suene muy complicado, pues permite tantos refinamientos como queramos, hay algoritmos tan sencillos como la suma y la resta, pues las operaciones son casos particulares de los algoritmos. Y además, aunque parezca algo muy abstracto, los algoritmos están presentes en nuestra vida cotidiana a través de gran parte de los objetos y aparatos que utilizamos cada día.

La descripción de un algoritmo usualmente se hace en tres niveles:

1. Descripción de alto nivel. Donde se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal y omitiendo detalles particulares. En algunos casos, también resulta adecuado representar diagramas de flujo que muestren los diferentes pasos para alcanzar la solución.

2. Descripción formal. Para ella se emplea lo que se denomina pseudocódigo y no es más que una descripción de la secuencia de pasos que se siguen para alcanzar la solución.

3. Implementación. Se desarrolla el algoritmo expresado en un lenguaje de programación específico.

Los algoritmos de caminos mínimos

El problema del camino más corto es el aquel que consiste en encontrar un camino entre dos nodos de manera que la suma de los costes de los nodos que lo constituyen es mínima. Por supuesto, este tipo de algoritmos permiten estudiar costes de trayecto diferentes, como la distancia, el tiempo de viaje, el coste generalizado, etc. Y no sólo eso, sino que es posible trabajar con matrices de adyacencias donde no sólo se representen costes medidos sino también ponderados. Un ejemplo clásico en el mundo del transporte es la penalización de cada modo de que se emplea en la 3ª etapa de los modelos de demanda de transporte (recordemos que son: 1) Generación de viajes,  2) Distribución de viajes; 3) Selección modal y 4) Selección de ruta. Por eso, se suele hablar de «modelos de cuatro etapas»).

Los algoritmos más importantes para resolver este problema son:

Dijkstra: resuelve el problema de los caminos más cortos desde un único nodo origen hasta todos los otros nodos del grafo (aunque aplicando una regla de repetición del algoritmo, se puede automatizar la resolución del problema desde todos los nodos de origen hasta todos los nodos del grafo).

Bellman-Ford: resuelve el problema de los caminos más cortos desde un origen permitiendo que la ponderación de los nodos sea negativa.

Algoritmo de Búsqueda A*: resuelve el problema de los caminos más cortos entre un par de nodos usando la heurística para agilizar la búsqueda.

Algoritmo de Floyd-Warshall: resuelve el problema de los caminos más cortos entre todos los nodos.

Algoritmo de Johnson: resuelve el problema de los caminos más cortos entre todos los nodos y puede ser más rápido que el de Floyd-Warshall en grafos de baja densidad.

Algoritmo de Viterbi: resuelve el problema del camino estocástico más corto con un peso probabilístico adicional en cada nodo.

El algoritmo Dijkstra

El algoritmo que más conozco es el de Dijkstra y es del que quiero comentar algunas cosillas. Su nombre se refiere a Edsger Dijkstra, quien lo describió hace ya más de medio siglo, en 1959. La idea que subyace consiste en ir explorando, a través de una estrategia de búsqueda especializada, el camino más corto que parte de un nodo origen y que llevan a todos los demás nodos de un grafo. Veamos en el siguiente vídeo cómo funciona:

Sin embargo, este algoritmo tiene algunas limitaciones, siendo la fundamental que no funciona en grafos con aristas de coste negativo puesto que se producen inestabilidades en la estrategia de búsqueda. Y otra importante es que no es directamente paralelizable, algo muy importante para los procesos que se engloban dentro del Big Data. Pero sí que permite formulaciones muy flexibles para modelizar problemas de transporte y la programación de sumideros para evitar el uso de pesos negativos. Además, pasa a ser paralelizable si empleas el ingenio y bastante tiempo de trabajo y tienes la suerte de que la inspiración de cómo salvar el problema te pilla o trabajando o con una libreta/un móvil a mano. Eso sí, ésta es la parte que ya no cuento porque ahí radica parte de la solución del proyecto de la UE en el que ando metido y con el que, mis compañeros y yo, pretendemos revolucionar la toma de datos de usuarios de transporte, así como el establecimiento de las líneas de deseo y de las rutas de transporte.

En @LetsB_us ya hemos visto a nuestro algoritmo correr. Le cuesta menos correr que andar… qué le vamos a hacer…

— Samir Awad Núñez (@samirawadnunez) 28 de marzo de 2016

Espero que os haya gustado este post y ya irá habiendo más entregas de esta serie sobre “Técnicas utilizadas en la planificación”.