Introducción y generalidades

A partir de esta sesión, y a lo largo de las siguientes, se irán presentando diferentes técnicas de resolución de problemas. Se trata, por lo tanto, de sesiones muy prácticas, en las que se explicarán las generalidades de cada técnica, se expondrán ejemplos resueltos, y se propondrán problemas nuevos que los alumnos deberán intentar resolver.

Para empezar, vamos a centrarnos en los problemas de grafos. La teoría de grafos nos ofrece un amplio abanico de problemas y algoritmos clásicos, que son aplicables en una gran variedad de situaciones. No obstante, en la mayoría de los casos la aplicación del algoritmo clásico es solo un paso dentro de un proceso mayor, puesto que se deben hacer cálculos adicionales sobre los resultados obtenidos. En otros casos es necesario realizar variaciones y modificaciones sobre el algoritmo clásico.

¿Cómo identificar un problema de grafos?

En muchas ocasiones, los problemas de grafos pueden ser identificados de forma sencilla. Pueden ser problemas en los que aparecen ciudades, calles, carreteras, caminos, laberintos, redes de ordenadores, etc. El modelado de estos problemas como problemas de grafos es más o menos inmediato. Básicamente, el modelado del problema consiste en identificar cuáles son los nodos y cuáles son las aristas del grafo.

Sin embargo, en otras muchas ocasiones el modelado y la identificación del problema de grafos no es tan evidente. Son problemas en los que aparece cierto tipo de elementos y relaciones entre ellos. Por ejemplo, estados de cierto proceso y relaciones entre ellos; tareas y relaciones de precedencia; personas y relaciones de amistad, etc. En consecuencia, debemos identificar cuáles son los nodos y las aristas del grafo.

Finalmente, podemos tener un problema que puede parecer de grafos pero no lo es... o resulta poco adecuado resolverlo mediante grafos. Un ejemplo son los problemas de laberintos en los que el laberinto es descrito como una matriz de posiciones. Al estar dados de esta forma, el número de nodos y de aristas sería muy elevado, por lo que el modelado mediante grafos podría requerir mucha memoria, muchos nodos y algoritmos muy lentos. En su lugar, la mayoría de estos problemas están pensados para ser resueltos mediante programación dinámica o con algoritmos de simulación.

¿Qué algoritmos de grafos son aplicables?

Una vez modelado un problema mediante grafos, el siguiente paso sería encontrar qué algoritmo de grafos es más adecuado para el problema. La elección del algoritmo puede ser más o menos evidente. De todos los algoritmos clásicos sobre grafos, los más habituales son:

• Algoritmos de recorrido en grafos: búsqueda primero en profundidad y en anchura. Pueden ser, por ejemplo, problemas para encontrar caminos, buscar los nodos que están conectados, buscar ciclos, etc. Recordar que en un grafo donde todas las aristas tienen el mismo peso, se pueden calcular los caminos mínimos de un nodo hasta los demás usando la búsqueda primero en anchura.
• Algoritmos de caminos mínimos: desde un origen (Dijkstra) o entre todos los pares de nodos (Floyd). Los problemas de caminos mínimos son otros de los más habituales. Como hemos comentado, en muchos casos suelen requerirse cálculos posteriores.
• Otros algoritmos: árboles de expansión de coste mínimo (Prim o Kruskal), flujo máximo, etc. Estos tipos de algoritmos pueden ser útiles, aunque suelen ser menos frecuentes. Por ejemplo, los algoritmos de flujo máximo pueden ser aplicables en problemas de asignación.

¿Cómo representar los grafos?

Básicamente, como ya debes saber, existen dos tipos de representaciones de los grafos: las listas de adyacencia y las matrices de adyacencia. También sabrás que las matrices de adyacencia solo son adecuadas cuando el tamaño del grafo sea pequeño. Pero, ¿cuánto? Por ejemplo, del orden de unos 300 nodos. A partir de 1000 nodos ya sería más discutible el uso de matrices de adyacencia. Y si el tamaño de los grafos no está prefijado en el enunciado, lo más seguro es usar listas de adyacencia.

En consecuencia, para representar los grafos es recomendable usar los tipos vector y list de las STL. Por ejemplo, un grafo no etiquetado representado con listas de adyacencia podría ser del tipo:

vector<list<int> > Grafo(n);

Siendo n el número de nodos del grafo. Con esta representación, el iterador de grafos: para cada nodo w adyacence de v hacer... sería:

for (list<int>::iterator it= Grafo[v].begin(); it!=Grafo[v].end(); it++) {
     int w= *it;
     accion sobre w;
}

Recordar que la representación de los grafos requiere que los nodos estén enumerados con valores consecutivos, desde 1 hasta n, o bien desde 0 hasta n-1. ¿Qué hacer si los nodos no están enumerados en el enunciado, por ejemplo, si los nodos son nombres? En ese caso, lo más interesante es usar el tipo map de las STL. Suponer, por ejemplo, que los nodos son cadenas de texto y que las aristas vienen dadas por dos nombres. Entonces, podemos usar un mapa para asociar números consecutivos a cada nombre:

map<string, int> Numeros;

Si los nombres vienen dados en la entrada, se pueden leer y asociarles un número al mismo tiempo:

string nombre;
for (int i= 0; i<n; i++) {
     cin >> nombre;
     Numeros[nombre]= i;
}

A continuación, para cada arista, leeríamos los dos nombres y los añadimos a la lista de adyacencia:

string v, w;
for (int i= 0; i<num_aristas; i++) {
     cin >> v >> w;
     int nv = Numeros[v];
     int nw = Numeros[w];
     Grafo[nv].push_front(nw);
}

Problema de ejemplo

En esta sesión vamos a analizar y resolver el problema "Krochanska is here!" que apareció en la Olimpiada Murciana de Programación 2010:

PROBLEMA 101. Krochanska is here! Enunciado del problema - Enlace al juez

Para que te vayas acostumbrando, el enunciado del problema está en inglés, en su versión original. Como en muchos casos, el enunciado tiene una introducción un tanto larga y aparentemente irrelevante... aunque esconde un pequeño secreto. :-)

¡Atención: antes de continuar debes haber leído y pensado un poco el problema!

De forma simplificada, el problema nos da un grafo de estaciones de tren. Las líneas ferroviarias definen las aristas entre las estaciones. De este modo, el ejemplo del enunciado daría lugar al siguiente grafo, donde todas las aristas tendrían coste 2.

Grafo de estaciones correspondiente el ejemplo del enunciado. Línea 1: en rojo. Línea 2: en azul. Línea 3: en verde.

Se definen las estaciones importantes como aquellas por las que pasa más de una línea; en el ejemplo, serían 2, 4, 6, 7 y 9. El objetivo del problema es encontrar cuál es la estación importante que minimiza la media de los caminos mínimos de esa estación con el resto de las estaciones importantes.

Se nos garantiza que los grafos serán siempre conexos, es decir, existen caminos entre cualquier par de estaciones.

Resolución del problema

Planteamiento general del problema

El primer paso para resolver un problema consiste en hacer un planteamiento general del problema. En nuestro caso, dos aspectos son los que definen el planteamiento global de partida:

1. Se trata claramente de un problema de grafos. Los nodos son las estaciones y las aristas son las vías entre entre estaciones, definidas en nuestro caso por las líneas existentes.
2. Se trata de un problema de caminos mínimos. Para cada estación, buscamos el camino mínimo con todas las demás estaciones; a continuación, calcularíamos la media de esos caminos mínimos, para las estaciones importantes.

En consecuencia, podríamos definir inicialmente el siguiente algoritmo en pseudocódigo:

1. Construir el grafo, buscando y señalando las estaciones importantes.
2. Calcular los caminos mínimos entre todos los pares de nodos (Floyd).
3. Para cada estación importante v, calcular su excentricidad, definida como la media de los caminos mínimos de v con el resto de estaciones importantes.
4. Quedarse con la estación que tenga menor excentricidad.

Lógicamente, el paso central de nuestra solución es el punto 2, donde se deben calcular los caminos mínimos entre todos los nodos. Claramente, se trataría de aplicar el algoritmo de Floyd, pero...

Hay un pequeño problema. El algoritmo de Floyd tiene un coste de O(n³). En este caso, según el enunciado, n puede valer como máximo 10000. Así que la aplicación directa de Floyd se hace inviable.

Simplificando el grafo del problema

Está claro que debemos buscar alguna forma de poder aplicar el algoritmo de Floyd, pero sin incurrir en un coste excesivo. En relación a esto, podríamos preguntarnos, ¿qué papel tienen las estaciones importantes? ¿Qué papel tienen las estaciones no importantes?

La solución será una estación importante, y solo necesitamos saber caminos mínimos entre estaciones importantes. En consecuencia, sería suficiente aplicar el algoritmo de Floyd solo entre las estaciones importantes, que como máximo puede haber 100.

¿Qué hacemos con las estaciones no importantes? Pues podemos obtener una representación simplificada del grafo, donde solo aparezcan las estaciones importantes. En la figura de abajo se puede ver el grafo simplificado del anterior ejemplo. Recordar que cada arista original tiene un coste de 2 horas de viaje.

Grafo simplificado del ejemplo del enunciado, donde solo aparecen las estaciones importantes.

Floyd y cálculos posteriores

Una vez obtenido el grafo simplificado, es posible aplicar el algoritmo de Floyd en un tiempo muy reducido. Eso nos daría los caminos mínimos entre todos los pares de nodos.

A continuación, para cada nodo del grafo reducido debemos calcular la media de las distancias mínimas con el resto de nodos. O, dicho en otras palabras, tenemos que calcular la suma de cada fila de la matriz devuelta por Floyd, y quedarse con aquella suma que dé el mínimo valor. Sencillo, ¿verdad?

En caso de empate al valor de suma mínimo, nos debemos quedar con el nodo que tenga menor numeración.

Algunos aspectos de implementación

Una vez establecido el algoritmo en pseudocódigo para resolver el problema, vamos a comentar algunos detalles de implementación que hay que tener en cuenta. Estos detalles son interesantes para tener en cuenta el código fuente que viene a continuación.

Como hemos visto, la creación del grafo simplificado es posiblemente lo más interesante de este problema. Para ello, en primer lugar vamos a ir leyendo todas las líneas y almacenándolas en un array lineas. De manera simultánea, se va calculando el número de veces que aparece cada estación, en el array veces. Una estación v será importante si veces[v] es mayor que 1.

Debemos observar que el grafo no se va creando al mismo tiempo de leer la entrada, porque solo al final podemos saber cuáles son las estaciones importantes. Así que, después de leer los datos de las líneas, calculamos el número de estaciones importantes existentes (nreal) y construimos un grafo (matriz de adyacencia grafo) de ese tamaño.

El proceso de creación del grafo consiste en volver a recorrer las líneas, almacenadas en lineas, y quedarse con cada par de estaciones importantes sucesivas que aparezcan en las líneas. Hay que tener en cuenta dos aspectos: el grafo es no dirigido (así que la matriz debe ser simétrica), y entre dos estaciones importantes puede haber varias líneas (como ocurre en el anterior ejemplo entre las estaciones 6 y 7).

En la construcción del grafo reducido, se necesita saber: (i) para cada nodo original cuál es su número correspondiente en el grafo simplificado (para lo cual usamos, en nuestro caso, el mismo array veces); y (ii) para cada nodo del grafo simplificado, cuál es su número original (array corres).

Listado del código

Finalmente, aquí puedes ver (y esperemos que también entender) el código fuente para resolver el problema. Para simplificar la implementación, se usan arrays declarados de forma estática (lo cual es posible porque el enunciado establece tamaños máximos).

// By GinesGM
// Murcia, 11/5/10

#include <iostream>
using namespace std;

#define MAX_N 10000
#define MAX_S 100
#define MAX_L 10000
#define MAX_G 100

#define min(A,B) ((A)<(B)?(A):(B))

int n, s, nreal;
int lineas[MAX_S][MAX_L+2];
int veces[MAX_N+1];
int grafo[MAX_G+1][MAX_G+1];
int corres[MAX_G+1];

void leerCaso (void)
{
    int cuenta;
    cin >> n >> s;
    for (int i= 1; i<=n; i++)
        veces[i]= 0;
    for (int i= 0; i<s; i++) {
        cuenta= 0;
        do {
            cuenta++;
            cin >> lineas[i][cuenta];
            veces[lineas[i][cuenta]]++;
        } while (lineas[i][cuenta]);
        cuenta--;
        lineas[i][0]= cuenta;
    }
}

void creaGrafo (void)
{
    int anterior, valor;
    nreal= 0;
    for (int i= 1; i<=n; i++) {
        if (veces[i]>1) {
            nreal++;
            veces[i]= nreal;
            corres[nreal]= i;
        }
        else veces[i]= 0;
    }
    for (int i= 1; i<=nreal; i++) {
        for (int j= 1; j<=nreal; j++)
            grafo[i][j]= 1000000;
        grafo[i][i]= 0;
    }
    for (int i= 0; i<s; i++) {
        anterior= 0;
        for (int j= 1; j<=lineas[i][0]; j++) {
            if (veces[lineas[i][j]]) {
                if (anterior) {
                    valor= grafo[veces[lineas[i][anterior]]][veces[lineas[i][j]]];
                    grafo[veces[lineas[i][anterior]]][veces[lineas[i][j]]]=
                            grafo[veces[lineas[i][j]]][veces[lineas[i][anterior]]]= min(valor, j-anterior);
                }
                anterior= j;
            }
        }
    }
}

void floyd (void)
{
    int mini= 1000000, posmini= 0;
    for (int k= 1; k<=nreal; k++)
        for (int i= 1; i<=nreal; i++)
            for (int j= 1; j<=nreal; j++)
                grafo[i][j]= min(grafo[i][j], grafo[i][k]+grafo[k][j]);
    for (int i= 1; i<=nreal; i++) {
        grafo[i][0]= 0;
        for (int j= 1; j<=nreal; j++)
            grafo[i][0]+= grafo[i][j];
        if (grafo[i][0]<mini) {
            posmini= i;
            mini= grafo[i][0];
        }
    }
    cout << "Krochanska is in: " << corres[posmini] << endl;
}

int main (void)
{
    int casos, i;
    cin >> casos;
    for (i= 0; i<casos; i++) {
        leerCaso();
        creaGrafo();
        floyd();
    }
}

Problemas propuestos

¡Y ahora ha llegado tu tuno! Te proponemos los dos siguientes problemas de grafos. Ambos problemas tienen también la particularidad de que son problemas de caminos mínimos.

PROBLEMA 102.The Scrooge Co Problem: Enunciado del problema - Enlace al juez
Breve descripción: es un problema muy sencillo para empezar. Tenemos una grafo de carreteras entre ciudades y se trata de encontrar los caminos más cortos, tanto el coste como los nodos por los que va pasando el camino mínimo. Este problema apareció en la Olimpiada Murciana de Programación 2006.

PROBLEMA 103. Traveling Fishmonger: Enunciado del problema - Enlace al juez
Breve descripción: y ahora un problema más largo y complejo. Aparece también un grafo de ciudades, sobre el cual hay que calcular caminos mínimos; en concreto, los caminos mínimos desde las ciudades de destino hasta todas las demás. Además, después será necesario calcular qué permutación de las ciudades de destino es más interesante. Este problema apareció en la Olimpiada Murciana de Programación 2006.

Estos problemas están en nuestro juez on-line local (http://olimpiada.inf.um.es/~mooshak/ concurso "Preparación OMP'13"), así que en caso de tener problemas, no dudes en consultarnos. Todos los alumnos deben tener los datos de su cuenta en Sakai.

Problemas adicionales

PROBLEMA 117. The Postal Worker Rings Once: Enunciado del problema - Enlace al juez
Pistas e indicaciones: en este problema tenemos ciclos de Euler o caminos de Euler. Si en un grafo existe un ciclo/camino de Euler, no necesitamos calcularlo, porque sabemos su coste es la suma de los costes de todas las aristas.

PROBLEMA 534. Frogger: Enunciado del problema - Enlace al juez
Pistas e indicaciones: tomando como base el algoritmo de Dijkstra, se debe modificar para que otra cosa, puesto que el coste de un camino no es la suma de las aristas, sino la mayor de las aristas que lo forman. Recordar que la distancia entre dos puntos (x1, y1) y (x2, y2) es la raíz cuadrada de ((x1-x2)² + (y1-y2)²).

PROBLEMA 1148. The mysterious X network: Enunciado del problema - Enlace al juez
Pistas e indicaciones: este problema apareció en el SWERC'2005. Se ve muy claramente que se trata de un problema de caminos mínimos.

PROBLEMA 10525. New to Bangladesh?: Enunciado del problema - Enlace al juez
Pistas e indicaciones: es un problema de un concurso local... de Bangladesh. Se trata de calcular caminos mínimos, pero al mismo tiempo mínimos en distancia y, en caso de empate, mínimos en tiempo.

PROBLEMA 10986. Sending email: Enunciado del problema - Enlace al juez
Pistas e indicaciones: es un problema de un concurso local. Los grafos pueden ser muy grandes, así que es necesario usar listas de adyacencia y el algoritmo de Dijkstra (no Floyd).

Más problemas de Pekín

1308 Is It A Tree? (1)

1258 Agri-Net (2)

2488 A Knight's Journey (3)

1164 The Castle (3)

2395 Out of Hay (4)

3177 Redundant Paths (4)

1945 Power Hungry Cows (5)

3275 Ranking the Cows (6)

1985 Cow Marathon (7)

2337 Catenyms (7)

2186 Popular Cows (8, challenge problem)

1944 Fiber Communications (8, challenge problem)

Olimpiada de programación - Facultad de Informática - Universidad de Murcia