Un tal Prim asfaltando caminos

Seguramente todos de pequeños jugasteis a aquello de unir varios puntos sin levantar el lápiz del papel para formar una figura. Lo curioso es que ese juego tan inocente, con una pequeña variación, tiene una aplicación muy similar en la vida real que nos permite ahorrar mucho dinero. Imaginaos que hubiera una vieja red de carreteras donde cada una conecta dos pueblos. El ayuntamiento, ante las quejas de sus vecinos por el mal estado de las mismas, está dispuesto a dotar presupuesto suficiente para asfaltarlas de nuevo, de tal manera que todos los pueblos se puedan seguir comunicando mediante los nuevos viales, independientemente de que queden multitud de viejos caminos sin asfaltar. Las únicas condiciones impuestas son que el gasto ha de ser el mínimo posible y que se pueda viajar entre dos pueblos cualesquiera sin necesidad de circular por trazados bacheados. Entonces, llega el ingeniero de turno y realiza un estudio del coste estimado para asfaltar cada vieja carretera. Sólo queda saber elegir cuáles se asfaltarán y cuáles no para comunicar todos los pueblos con el mínimo gasto posible. ¿Quién dijo que era fácil ser alcalde de un ayuntamiento!

Este problema se puede resolver utilizando algoritmos voraces, es decir, algoritmos que seleccionan en cada momento uno de entre varios candidatos (“pueblos”) para optimizar una función objetivo (“el gasto en asfaltado”) sin retractarse de ninguna decisión tomada con anterioridad (“sin levantar el lápiz del papel”). En términos más formales, la red de carreteras es un grafo no dirigido y conexo y lo que pretendemos calcular es el llamado árbol de recubrimiento mínimo. Existen básicamente dos aproximaciones para resolver este problema: el algoritmo de Prim y el algoritmo de Kruskal. Hoy vamos a ver el algoritmo de Prim porque como ya dije es el que más se parece a ese inocente juego de hacer trazados sin levantar el lápiz del papel. Consiste en lo siguiente:

1. Consideramos siempre dos conjuntos, el conjunto de vértices (“pueblos”) que forman parte del recubrimiento mínimo en construcción (“red de carreteras que se asfaltará”) y el de los vértices aún no considerados (“pueblos candidatos”).
2. Inicialmente, el primer conjunto incluye un vértice arbitrario.
3. A continuación, se consideran todas las aristas o carreteras (u,v) tales que u está en el primer conjunto y v en el segundo para seleccionar la de menor coste. Dicha arista se incorpora a la solución (“esa carretera será definitivamente asfaltada”). Obviamente, la arista escogida ya no será considerada de nuevo y el vértice v se elimina del conjunto de candidatos y se incluye en el de vértices pertenecientes al recubrimiento.
4. El algoritmo acaba cuando ya no queden vértices candidatos.
5. La mala noticia para el alcalde es que hay casos en que existe más de un recubrimiento mínimo para un mismo grafo y, dependiendo del vértice que se escoja al principio o de la arista que se tome en caso de haber varias con el mismo coste, obtendremos uno u otro. Eso quiere decir que determinados vecinos pueden reclamar soluciones alternativas con el mismo coste que les resulten más ventajosas. Por ejemplo, podrían preferir un trazado A frente a otro B, a pesar de costar lo mismo y ser igualmente óptimos, por el simple hecho de que A los mantiene más cerca del único pueblo con supermercado que el trazado B. Para este tipo de problemas, la algoritmia no nos sirve. ¡Lo siento, señor alcalde!
   

Aquí tenéis un traceado del algoritmo sobre un grafo de ejemplo por si os habéis perdido en algún punto de la explicación.

Referencias:

El grafo de ejemplo ha sido extraído del punto 11.4.1 de los apuntes de algorítmica de A. Marzal, M.J. Castro y P. Aibar. También podéis encontrar en su obra las soluciones a este y otros muchos problemas implementados en Python, con detallados análisis de su corrección y complejidad.