Algoritmos y Estructuras de Datos (VJ1215)

Análisis de coste temporal

Clase de teoría TE1 23/11

Sea G = (V, E) un grafo, dirigido o no dirigido. Considera el siguiente fragmento de pseudocódigo:

contador = 0
para cada vértice v ∈ V:
   para cada arco (v, w) ∈ E que sale de ese v :
      contador = contador + 1
	      

La forma eficiente de implementar eso es utilizar una representación del grafo mediante listas de adyacencia. Puedes ver esa representación gráficamente en las animaciones de David Galles (por ejemplo, Breadth-First Search) eligiendo la opción Adjacency List Representation.

Empleando la clase GrafoDirigido, quedaría:

int contador = 0;
for (int v = 0; v < vertices.size(); v++)
   for (Arco * arco = vertices[v].primerArcoDeSalida;
        arco != nullptr;
        arco = arco->siguiente)
      contador = contador + 1;
	      

Empleando la clase GrafoNoDirigido, quedaría:

for (int v = 0; v < vertices.size(); v++)
   for (Arco * arco = vertices[v].primerArco;
        arco != nullptr;
        arco = arco->siguiente)
      contador = contador + 1;
	      

¿Cuál es en ese caso el coste temporal de esos dos bucles anidados?

1. O(|V| · |E|)
2. O(|V|²)
3. O(|V| + |E|)
4. O(|V|)
5. O(|E|)

Solución

Caminos óptimos sin pesos mediante búsqueda en anchura

1. Clase de prácticas LA2 y LA4 28/11, LA1 y LA3 30/11

   Vas a realizar una implementación del algoritmo de cálculo de caminos óptimos sin pesos mediante búsqueda en anchura que hemos presentado en el apartado 6.3 (lo puedes consultar en el apartado 9.3.1 del libro "Data Structures and Algorithm Analysis in C++" (2014)). En este ejercicio, no busques el algoritmo en Internet: escríbelo tú, sabiendo lo que tiene que hacer. La animación Breadth-First Search de David Galles te puede servir de ayuda.

   Añade a la clase GrafoDirigido un método público

   vector<int> arbolDeCaminosOptimosSinPesos(int s) const;
   	      

   que reciba como argumento un entero s y devuelva como resultado un vector de enteros en el que, para cada vértice v distinto de s, la posición v contenga el vértice predecesor de v en el camino más corto (con menos arcos) desde s hasta v, como ilustra el vector Parent en la animación de David Galles. Si v no es alcanzable desde s, en la posición v devuelve un -1 para indicarlo; si v es s, indícalo con un -2.

   Los caminos más cortos desde un vértice hasta todos los demás forman un árbol, que queda representado en ese vector por el padre de cada vértice en el árbol.

   Por ejemplo, con este grafo ejemploInalcanzable.gr y origen 3 un resultado podría ser [2, 0, 3, -2, 1, 3, 7, 3, 7, -1].

   

   

   Ayuda con C++: colas en la STL

   Recuerda ejemplo_queue_enteros.cpp

   Solución

   Prueba de la solución

   Ejemplo de error

2. Supongamos que en un videojuego hay varios monstruos y un jugador. Cada monstruo está situado en un vértice de un grafo y el jugador está situado en otro vértice. El jugador se puede desplazar de vértice a vértice siguiendo los arcos. Tienes que encontrar el monstruo al que puede llegar el jugador atravesando la mínima cantidad de arcos. ¿Qué algoritmo puedes emplear? No se pide que lo implementes, solo que lo razones.

   Solución

Aciclicidad y ordenación topológica mediante el algoritmo de Kahn

En este ejercicio debes realizar una implementación del algoritmo de Kahn, que hemos presentado en el apartado 6.2 del tema, para encontrar una ordenación topológica (topological sort). Lo puedes consultar en el apartado 9.2 del libro "Data Structures and Algorithm Analysis in C++" (2014). La animación Topological Sort (Using Indegree array) de David Galles te puede servir de ayuda.

Añade a la clase GrafoDirigido el siguiente método público:

void mostrarOrdenTopologico() const;
	      

Si el grafo no es acíclico, detéctalo y termina lanzando una excepción que lo indique, sin haber mostrado una ordenación topológica incompleta en la salida estándar.

Solución

Prueba de la solución

Caminos óptimos sin pesos mediante búsqueda en anchura

Tenemos un grafo no dirigido que representa el escenario en el que se desarrolla un videojuego. Cada vértice representan una isla. Cada arco representa un puente que une dos islas, que puede atravesarse en ambos sentidos. El grafo no es necesariamente conexo.

Para cada vértice, tenemos un contador con la cantidad de enemigos presentes en esa isla.

Añade a la clase GrafoNoDirigido un método público

int contarEnemigosCercanos(int islaJugador,
                           int puentes,
                           const vector<int> & cantidadDeEnemigos) const;
	      

que reciba como argumentos el vértice (la isla) en que se encuentra el jugador, una cantidad de puentes, y un vector en el que la posición i tiene la cantidad de enemigos presentes en la isla i, para cada isla. El método debe devolver la cantidad de enemigos que en ese momento podrían alcanzar al jugador atravesando a lo sumo esa cantidad de puentes, incluyendo los enemigos que ya están en la misma isla que el jugador. Analiza su coste temporal y espacial.

Por ejemplo, con el siguiente grafo ejemploIslas.gr, si el jugador se encuenta en la isla 1, si la máxima cantidad de puentes que puede utilizar cada enemigo es 2, y si la cantidad de enemigos presentes en cada isla coincide con el número de la isla, entonces el resultado es 1 + 5 + 6 + 7 + 8 + 10 = 37.

Solución

Prueba de la solución

Si tuvieras que comprobar que un grafo dirigido es acíclico (es decir, no contiene ningún ciclo), ¿qué algoritmo de los que conoces por ahora podrías utilizar? Impleméntalo, añadiendo el siguiente método público a la clase GrafoDirigido:

bool esAciclico() const;
	      

¿Cuál es su coste temporal y espacial?

Solución

[Fuente: adaptación del ejercicio 9.52 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

Tenemos un grafo dirigido acíclico en el que cada vértice representa una asignatura y cada arco (a, b) representa que es necesario finalizar la asignatura a antes de empezar la asignatura b. Los estudiantes pueden cursar simultáneamente tantas asignaturas como quieran con la única condición de respetar todas las restricciones representadas en ese grafo. Todas las asignaturas son anuales y se ofrecen todos los años.

Diseña un algoritmo eficiente que, dado el grafo, calcule la mínima cantidad de años necesarios para completar todas las asignaturas. Haz que muestre también cuáles son las asignaturas a cursar cada año para conseguir eso. Analiza su coste temporal y espacial. Impleméntalo, añadiendo el siguiente método público a la clase GrafoDirigido:

int minimaCantidadAnyos() const;
	      

Por ejemplo, con el grafo ejemplo.gr se obtiene este resultado (los pesos de los arcos puedes ignorarlos).

Solución

Prueba de la solución

Sea G = (V, E) un grafo dirigido que representa posibles desplazamientos en un juego. En el juego participan n jugadores, que deben alcanzar un objetivo situado en un vértice t. Cada jugador está situado en un vértice, y la distancia del jugador al objetivo es la mínima cantidad de arcos que debe atravesar el jugador para llegar desde su posición hasta t (la distancia es ∞ si t es inalcanzable). Puede haber varios jugadores en el mismo vértice.

Añade a la clase GrafoDirigido un método

void rankingPorDistanciaAlObjetivo(int t, vector<int> & jugadores) const
	      

que recibe el vértice t y un vector de talla n que contiene los vértices en los que están situados los jugadores. El método debe ordenar el vector de menor a mayor distancia a t.

Por ejemplo, con el siguiente grafo:

si nos dan jugadores = [4, 6, 8, 4, 4, 5], significa que el primer jugador está en el vértice 4, el segundo jugador está en el vértice 6, el tercer jugador está en el vértice 8, etc. En ese ejemplo hay 3 jugadores en el vértice 4. Si además nos dan t = 7, entonces el resultado que nos piden sería [6, 5, 4, 4, 4, 8], porque el vértice 6 está a distancia 1 del vértice 7, el vértice 5 está a distancia 2, el vértice 4 está a distancia 5 y el vértice 8 está a distancia 7.

Analiza el coste temporal y espacial de tu solución en función de |V|, |E| y n.

Solución

Supongamos que una determinada enfermedad muy virulenta se puede adquirir por contagio de persona a persona o por la picadura de un mosquito infectado. Tenemos un grafo no dirigido, no necesariamente conexo, en el que los vértices representan personas y un arco entre dos personas representa que si cualquiera de las dos adquiere la enfermedad entonces rápidamente se la contagiará a la otra.

Por ejemplo, con el siguiente grafo ejemploPicaduras.gr, si un mosquito picase a 4, por esa sola picadura acabarían infectados 0, 1, 4 y 5.

Diseña un algoritmo eficiente para averiguar cuál es la mínima cantidad de picaduras necesaria para que se infecten todas las personas. Por ejemplo, con el grafo anterior el resultado sería 3. Analiza su coste temporal y espacial. Impleméntalo añadiendo el siguiente método público a la clase GrafoNoDirigido:

int contarPicaduras() const;
	      

Solución

Prueba de la solución

Clase de teoría TE1 30/11

1. Utiliza búsqueda en anchura para obtener un árbol de caminos óptimos sin pesos desde el vértice origen 3 hasta todos los demás vértices en el siguiente grafo ponderado dirigido.

   

   Solución

2. Utiliza el algoritmo de Dijkstra para obtener un árbol de caminos óptimos con pesos desde el vértice origen 3 hasta todos los demás vértices en el grafo anterior. Compara el resultado con el de la búsqueda en anchura observando, para cada vértice, qué camino llega haste él utilizando la mínima cantidad de arcos y qué camino llega hasta él con mínimo peso.

   Solución

Clase de teoría TE1 14/12

Considera de nuevo la versión del algoritmo de Dijkstra que puedes encontrar en el apartado "Using a priority queue" de la página "Dijkstra's algorithm" de la Wikipedia.

1. En el ejercicio 12 se te ha proporcionado la clase ColaDePrioridad, en la que internamente se utiliza un vector no ordenado. Analiza el coste temporal del algoritmo de Dijkstra cuando se hace uso de esa implementación de la cola de prioridad.

2. Analiza cuál sería el coste temporal del algoritmo de Dijkstra si la cola de prioridad se implementase empleando un montículo binario. Para ello, recuerda la solución del ejercicio 8 del tema 4.

3. A la vista de los resultados anteriores, ¿para qué tipo de grafo es preferible utilizar un vector no ordenado en vez de un montículo binario, y viceversa?

Solución

¿En qué se diferenciaría el análisis de costes del ejercicio 14 si se tratase de analizar el algoritmo de Prim (ejercicio 13) en vez del algoritmo de Dijkstra?

Solución

[Fuente: varios alumnos de cursos pasados querían resolver este problema en un videojuego que estaban desarrollando]

Estamos trabajando con grafos dirigidos y ponderados que representan posibles desplazamientos en un juego. Cada arco (u, v) lleva asociado un peso no negativo que es la energía que consume el jugador al desplazarse del vértice u al v. Añade a la clase GrafoDirigido un método público

vector<bool> destinosValidos(int s, float e) const;
	      

que reciba como argumento el vértice s en el que se encuentra el jugador y la energía total e que puede consumir. El resultado debe ser un vector en el que cada posición i tenga el valor true si, y solo si, existe algún camino desde el vértice s hasta el vértice i cuyo peso (suma de los pesos de sus arcos) sea menor o igual que e.

Solución

Prueba de la solución

1. Tenemos un grafo dirigido y ponderado que representa las calles de una ciudad. El grafo no es necesariamente acíclico. Cuando sucede un accidente en un vértice, los servicios de emergencia deciden la cantidad de ambulancias n necesarias y a continuación es necesario localizar rápidamente las n ambulancias que pueden llegar en el mínimo tiempo posible al lugar del accidente. El peso de cada arco es el tiempo estimado que le costaría a una ambulancia moverse de un vértice a otro siguiendo ese arco.

   Cada ambulancia tiene asociado un número entero que la identifica. Para cada vértice v del grafo disponemos de un dato de tipo entero ambulancia[v]. Si en ese vértice hay una ambulancia, ese dato es el identificador de la ambulancia; en caso contrario, vale -1. No hay más de una ambulancia en el mismo vértice. Podría haber inicialmente una en el vértice del accidente.

   Diseña un algoritmo para resolver eficientemente ese problema, e impleméntalo añadiendo a la clase GrafoDirigido el siguiente método público:

   void mostrarAmbulancias(int destino,
                           int n,
                           const vector<int> & ambulancia) const;
   		  

   El primer argumento es el vértice destino, el segundo es la cantidad de ambulancias necesarias y el tercero es el vector ambulancia descrito antes. Ese método deberá mostrar en la salida estándar lo antes posible los identificadores de las n ambulancias requeridas. En caso de no localizar suficientes, deberá mostrar las que encuentre e indicar que no hay más.

   Por ejemplo, con el siguiente grafo:

   

   si ambulancias contiene [-1, 330, -1, 440, -1, -1, -1, -1, 550], significa que hay 3 ambulancias disponibles: la ambulancia 330 en el vértice 1, la ambulancia 440 en el vértice 3 y la ambulancia 550 en el vértice 8. Si sucede un accidente en el vértice 7 que requiere 2 ambulancias, las elegidas serán en primer lugar la 550 (cuyo tiempo de llegada es 9) y en segundo lugar la 330 (cuyo tiempo de llegada es 20). No se elegirá la 440, porque su tiempo de llegada es superior, 21.

   Solución

   Prueba de la solución

2. Escribe otro algoritmo para resolver más eficientemente el mismo problema en el caso particular de que el peso de todos los arcos sea 10.

   Solución

   Prueba de la solución

[Fuente: adaptación del ejercicio 9.10 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

Al aplicar el algoritmo de Dijkstra para encontrar caminos óptimos, podría suceder que hubiese varios caminos igual de buenos. En ese caso, el algoritmo elegiría uno cualquiera de ellos.

Modifíca la solución del ejercicio 12 para convertirla en un método que reciba como argumentos dos vértices s y t y devuelva como resultado la cantidad de caminos óptimos (caminos de mínimo peso) de s a t, suponiendo que no hay arcos de peso cero.

int contarCaminosOptimos(int s, int t) const;
	      

Puedes probarlo con ejemploEmpates.gr: contarCaminosOptimos(4, 2) debe devolver 5.

Solución

Prueba de la solución

Componentes conexas mediante búsqueda en profundidad

Implementa de nuevo el método del ejercicio 9, utilizando esta vez búsqueda en profundidad en vez de búsqueda en anchura en el siguiente método de la clase GrafoNoDirigido:

int contarPicaduras() const;
	      

Analiza su coste temporal y compáralo con el de la solución del ejercicio 9.

Solución

Prueba de la solución

Sea G = (V, E) un grafo dirigido que representa el escenario de un videojuego en el que se sitúan varios ratones que deben alcanzar un queso. Para cada vértice u ∈ V tenemos un booleano raton[u] que indica si en ese vértice se encuentra un ratón. El queso se encuentra en un vértice q ∈ V. Cada arco dirigido (v, w) ∈ E representa un movimiento válido que permite a los ratones desplazarse del vértice v al vértice w (el movimiento de w a v no tiene por qué ser válido; por eso el grafo es dirigido).

Para que el juego esté bien configurado, para cada ratón debe existir en el grafo al menos un camino desde el ratón hasta el queso (sin importar si pasa por vértices ocupados por otros ratones).

Diseña un algoritmo eficiente que verifique que se cumple eso y analiza su coste temporal.

Añade a la clase GrafoDirigido el siguiente método público:

bool quesoAlcanzablePorTodosLosRatones(int q, const vector<bool> & raton) const;
	      

El primer argumento es el vértice en que se encuentra el queso y el segundo es el vector de booleanos que indica en qué vértices hay un ratón. El resultado debe ser un booleano, que valdrá cierto si y solo si el queso es alcanzable por todos los ratones.

Diseña una solución que no siga recorriendo el grafo si, con lo visto hasta ese momento, ya se puede determinar el resultado.

Solución

Prueba de la solución

Componentes fuertemente conexas mediante el algoritmo de Kosaraju-Sharir

Clase de teoría TE1 07/12

Aplica a este grafo el algoritmo de Kosaraju-Sharir para encontrar las componentes fuertemente conexas. Las dos versiones del algoritmo que aparecen en esos dos apartados de la Wikipedia son equivalentes (piensa por qué). También puedes seguir la explicación del apartado 9.6.5 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss, que incluye la demostración de que el algoritmo resuelve correctamente el problema.

Ayuda: Grafo invertido

Componentes fuertemente conexas mediante el algoritmo de Kosaraju-Sharir

Dado un grafo dirigido, queremos asignar un color a cada vértice con la siguiente condición: para todo par de vértices u y v, si se puede ir desde u hasta v y desde v hasta u (utilizando uno o más arcos) entonces el color de u debe coincidir con el de v; en caso contrario, sus colores deben ser diferentes.

Podemos utilizar valores enteros positivos para identificar los colores.

Añade a la clase GrafoDirigido el siguiente método público:

vector<int> colorearConectados() const;
	      

El resultado debe ser un vector de enteros que en la posición v tenga el color asignado al vértice v, para cada vértice v del grafo.

Por ejemplo, con este grafo ejemploColorearConectados.gr

una solución es [1, 1, 2, 2, 1, 3, 2, 2], donde 1 representa el color amarillo, 2 representa el verde y 3 representa el naranja:

Solución

Prueba de la solución

Grafos bipartidos mediante búsqueda en anchura o en profundidad

Tenemos un grafo no dirigido que representa el escenario en el que se desarrolla un videojuego. Cada vértice representan una isla. Cada arco representa un puente que une dos islas, que puede atravesarse en ambos sentidos. El grafo no es necesariamente conexo.

En el juego participan dos equipos de jugadores. Para empezar el juego tenemos que asignar un equipo a cada isla consiguiendo que (i) cada isla pertenezca a un equipo y solo uno; (ii) no haya dos islas conectadas por un puente asignadas al mismo equipo. No se exige asignar la misma cantidad de islas a cada equipo.

Diseña un algoritmo para resolver eficientemente ese problema, e impleméntalo añadiendo a la clase GrafoNoDirigido un método público

vector<int> repartirIslas() const;
	      

que devuelva como resultado un vector en el que la posición v contenga el equipo asignado al vértice v, o lance una excepción si no existe solución. Analiza su coste temporal.

Por ejemplo, con el siguiente grafo ejemploIslas.gr

un resultado correcto sería [1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2], es decir, asignar las islas 0, 2, 6, 8 y 9 al equipo 1 y las restantes islas al equipo 2:

Sin embargo, si añadiéramos un puente entre las islas 4 y 5, o entre las islas 8 y 2, no existiría ningún reparto válido.

Solución

Prueba de la solución