Redes de Flujo: Acelerando Ford Fulkerson, Programación de Vuelos, Segmentación de Imágenes, Eliminación en Torneo

Question 1

Acelerando Ford Fulkerson: Explique el problema

Answer 1

Sea G un grafo, podemos resolver el problema del flujo máximo.

Pero la selección de camino s-t malos puede relentizar mucho la finalización del algoritmo. Se busca entonces la forma de mejorarlo.

Question 2

Acelerando Ford Fulkerson: Explique la selección eficiente del camino s-t

Answer 2

Lo mejor sería intentar elegir aquellos caminos con mayor cuellos de botella. Pero mantener esta información actualizada puede ser costoso. Por lo que tenemos varios métodos para intentar realizar selecciones convenientes.

Question 3

Acelerando Ford Fulkerson: Explique el método de parámetro escalado Δ (Delta)

Answer 3

Se utilizará un parámetro Δ y sólo se buscarán aquellos P caminos s-t con un cuello de botella mayor a Δ.

Inicialmente, Δ tomará la potencia de 2 más grande posible, que no sea mayor a la suma de las capacidades de los ejes que salen de s.

Luego repetimos hasta hallar el flujo máximo:
- Para eso, el grafo residual se arma únicamente con aquellos ejes que superen a Δ.
- Una vez que no existen más caminos, se reduce Δ a la mitad.

Question 4

Acelerando Ford Fulkerson: Explique el pseudocódigo del método de parámetro escalado Δ (Delta) y su complejidad.

Answer 4

Calcular f(e) = 0 para e en G.

Definir delta como la potencia de 2 más grande, que no sea mayor a la capacidad máxima que sale de s.

Mientras delta >= 1:
     Mientras exista un camino s-t en el grafo Gf(delta):
          Sea P camino simple en Gf(delta):
               f' = aumento(f,P)

               Actualizar f para ser f' y actualizar Gf(delta)

     delta = delta / 2

Retornar f

Complejidad:

• El número de iteraciones está definido por delta, y limitado por la capacidad de los ejes que salen de s : 1 + log2 C
• En cada iteración hay a lo sumo 2 * |E| caminos de aumento.

=> El tiempo de ejecución es O(|E|^2 * log2 C). Cuando C es muy grande, es mejor que O( |E| * C)

Question 5

Acelerando Ford Fulkerson: Explique el algoritmo de Edmonds-Karp

Answer 5

El algoritmo de Edmonds-Karp es Ford-Fulkerson pero con un único cambio: calcula el camino de aumento de longitud mínima.

Su complejidad es fuertemente polinómica (a diferencia de Ford-Fulkerson, que es pseudopolinómica ya que depende de las capacidades).

Question 6

Acelerando Ford Fulkerson: Explique el pseudocódigo del algoritmo de Edmonds-Karp y su complejidad.

Answer 6

f(e) = 0 para todo e en G

Mientras haya un camino s-t en Gf:
         Sea P un camino s-t simple en Gf, de Longitud Mínima (obtenido usando BFS)
         f' = aumento(f,P)

         Actualizar f para ser f'
         Actualizar Gf para ser Gf'

Retornar f

• Cuanto mayor longitud tiene el camino de aumento, más probable que el cuello de botella encontrado sea menor.
• Progresivamente, se van consumiento los caminos de menor longitud.

Complejidad:

• Cada iteracion Ford-Fulkerson se puede implementar en O(E).
• La cantidad de iteraciones está dada por la cantidad de caminos de aumento y es O(VE)

=> La complejidad temporal es O(E^2 * V)

Question 7

Programación de Vuelos: Explique el problema

Answer 7

Tenemos una flota de k aviones y un conjunto de m rutas de vuelo rentables. Cada ruta de vuelo está definida por:

• Un aeropuerto de inicio
• Un aeropuerto de finalización
• Una hora de partida
• Una hora de llegada

Queremos determinar si podemos cubrir las rutas utilizando como mucho nuestros k aviones.

Question 8

Programación de Vuelos: Explique el concepto de Compatibilidad de Rutas

Answer 8

La ruta de vuelo j es alcanzable desde la ruta de vuelo i si la ciudad de llegada de i es la ciudad de partida de j, y la hora de llegade de i da tiempo de preparación suficiente a la hora de partida de j.

También si el tiempo de vuelo y preparación desde la ciudad de llegada i (a partir de su hora de llegada) es suficiente para estar en la ciudad de partida de j a la hora de salida programada.

Question 9

Programación de Vuelos: Explique la construcción de la solución.

Answer 9

1. Podemos representar a cada vuelo como:
   - 1 nodo de ciudad/hora partida
   - 1 nodo de ciudad/hora llegada
   - 1 eje dirigido de vuelo.
2. Podemos representr a la compatibilidad de vuelos como:
   - 1 eje entre el nodo de llegada del vuelo i y la ciudad de partida del vuelo j.

Question 10

Programación de Vuelos: Explique la transformación en un problema de flujos.

Answer 10

1. Vamos a agregar un nodo s y generamos un eje entre s y cada nodo de partida de un vuelo (cada vuelo puede ser el inicio de un recorrido de un avión).
2. Vamos a agregar un nodo t y generamos un eje entre cada nodo de llegada de un vuelo y t(cada vuelo puede ser el final de un recorrido de un avión).

Question 11

Programación de Vuelos: Explique la construcción de la solución. capacidades y límites

Answer 11

Siendo i un nodo de inicio y f un nodo de fin de vuelo:

1. Queremos que cada vuelo se ejecute 1 vez: la capacidad y el límite inferior del eje del vuelo va a ser 1.
2. Un avión podría partir o no de una determinada ruta: Cada eje s-i va a tener capacidad 1 y límite 0
3. Un avión puede terminar o no en una determinada ruta: Cada eje f-t va a tener capacidad 1 y límite 0.
4. Un avión también puede finalizar vuelo y comenzar otor: Los vielos compatibles van a tener ejes entre sí de capadidad 1 y límite 0.

La capacidad es el “máximo disponible” y el límite el “mínimo necesario”.

Question 12

Programación de Vuelos: Explique el uso de la demanda.

Answer 12

El nodo s produce k unidades, mientras que el nodo t las consume.
El resto de los nodos no produce ni consume.

Question 13

Programación de Vuelos: ¿Para qué se agrega un nodo s-t?

Answer 13

Se agrega un nodo s-t con capacidad k y límite inferior 0 para determinar cuántos aviones no son necesarios.

Question 14

Programación de Vuelos: Indique los pasos para la resolución.

Answer 14

1. Construir con los n vuelos la red de flujo (con demandas y límite inferior).
2. Reducirlo a un problema con demanda
3. Reducirlo a un problema de flujo máximo
4. Resolverlo mediante Ford-Fulkerson
5. Verificar si los flujos resultantes satisfacen las restricciones

Question 15

Arme el grafo para la siguiente programación de vuelos:

A: A1 -> A2

B: B1 -> B2

C: C1 -> C2

A es compatible con B

Answer 15

Click aqui para ver grafo

Question 16

Explique el problema de Segmentación de Imágenes

Answer 16

Contamos con una imagen, y queremos separar el fondo de la imagen de lo que está pasando en primer plano.

• Vamos a llamar V al conjunto de pixeles que forman la imagen (y que forman una cuadrícula).
• Cada pixel i tiene un conjunto de pixels vecinos: 8 para los pixels internos y 3 o 5 para los externos.

Cada relación de vecindad es bidireccional.

Question 17

Segmentación de Imágenes: Explique la probabilidad de pertenencia

Answer 17

Para cada pixel i tenemos:

• Valor “deseo” ai de que pertenezca al primer plano
• Valor “deseo” bi de que pertenezca al fondo.

Ambos valores son positivos y disponibles para la segmentación.

Si tomamos un pixel como aislado tal que ai > bi, entonces pertenece al primer plano. De lo contrario, pertenece al fondo.

Question 18

Segmentación de Imágenes: Explique la penalidad por cambio

Answer 18

Si muchos de los vecinos del pixel i pertenecen al fondo, es más “deseable” que i también pertenezca.

Por cada par de pixels (i,j) vecinos, existe una penalidad p_ij de que pertenezcan a diferente segmento (fondo / 1er plano).

El valor de p_ij es mayor a cero.

Question 19

Segmentación de Imágenes: Explique el Problema de Maximización

Answer 19

Sea A el conjunto de pixeles de la imgen que pertenecen al primer plano, y B el conjunto de los píxeles de la imagen que pertenecen al fondo, podemos calcular la “deseabilidad” de la segmentación A/B como:

ai deseo de los elementos de A de ser primer plano
bi deseo de los elementos de B de ser fondo
pij penalidad entre vecinos de A y B

q(A,B) = ∑(ai) + ∑(bj) - ∑(pij)

Queremos seleccionar la elección de los segmentos A,B que maximicen q(A,B). Es decir, donde la suma de los deseos sea máxima y las penalidades entre conjuntos sean mínimas.

Question 20

Segmentación de Imágenes: Explique la Transformación en Mínimización

Answer 20

Si llamamos Q a ∑(ai+bi+aj+bj) , vemos que:

∑(ai) + ∑(bj) = Q - ∑(bi) - ∑(aj)

Entonces:

q(A,B) = Q - ∑(bi) - ∑(aj) - ∑(pij)

Podemos transformar este problema en un problema de minimización de q'(A,B), siendo:

q'(A,B) = ∑(bi) + ∑(aj) + ∑(pij)

y

q(A,B) = Q - q'(A,B)

Question 21

Segmentación de Imágenes: Explique la Transformación en un problema de corte mínimo

Answer 21

• Usamos un nodo s fuente como representación del primer plano.
• Usamos un nodo t sumidero como representación del segmento fondo.

Creamos 3 tipos de ejes:
1. s-i para cada nodo, con capacidad ai.
2. i-t para cada nodo, con capacidad bi.
3. i-j por cada vecino, con capacidad pij. Este genera 1 eje de ida y otro de vuelta para cada par.

Con los cambios propuestos, tenemos una rede de flujo G'=(V',E').

Question 22

Segmentación de Imágenes: Explique el corte s-t. ¿A qué llamamos capacidad del corte?

Answer 22

Si analizamos un corte A-B, llamamos c(A,B) a la capacidad del corte A-B, que es la suma de las capacidades de los ejes que van de A a B.

Los ejes del corte corresponden a:

• ejes s-j con j en B, con capacidad ai
• ejes i-tcon i en A, con capacodad bj
• ejes i-j, con capacidad pij.

Sumando las capacidades, tenemos entonces que el resultado equivale a la fórmula de q'(A,B).

Podemos hacer cortes arbitrariamente. Algunos tendrán capacidad mayor y otros menor, pero nos interesa el menor de los posibles.

Question 23

Segmentación de Imágenes: Explique los pasos para la segmentación.

Answer 23

1. Dada la imagen y los parámtros pij, ai, bi para todo pixel; construir la red de flujo según método.
2. Resolver problema de flujo máximo mediante Ford-Fulkerson.
3. Desde el grafo residual final, realizar BFS desde nodo s. Todos los alcanzables serán los pixels del segmento “fondo”, y el resto serán los que pertenecen al primer plano.

> The value of the maximum flow from the source S to the sink P is equal to the capacity of the minimum cut CT separating S and P (más info acá)

Question 24

Resuelva:

Segmentación de Imágenes

Nodo ai bi
A 1 2
B 2 3
C 2 2
D 1 2
E 4 2

eje pij
A-B 3
B-C 3
C-D 4
D-A 3
E-A 3
E-B 2
E-D 3
E-C 2

Answer 24

Deseabilidad Máxima: 11 (creo)

Question 25

Eliminación en Torneo: Explique el problema, con sus supuestos y propuestas.

Answer 25

Sea un torneo donde participan S equipos, y cada equipo s tiene una cantidad wi de partidos ganados. Para cada par de equipos x,y, les queda por enfrentarse una cantidad gxy veces.

Queremos, dado un equipo z, determinar si tiene posibilidad de quedar primero.

Supuestos y Propuestas:

Si suponemos que z gana todos sus partidos pendientes, llamaremos gi a la cantidad de partidos pendientes del equipo i.

Al final del torneo, z tendrá m puntos, con m = wz + gz.
Queremos ver si existe una combinación de resultados tal que otro equipo no pueda sumar más de m puntos.

En un partido entre x,y en S' (S' = S-z), sólo uno de los equipos puede ser ganador. Por lo tanto, debemos determinar quién gana cada uno de los partidos para que ningún equipo supere a z.

Question 26

Eliminación en Torneo: Defina el total de los partidos

Answer 26

Al total de los partidos lo vamos a llamar g*, tal que:

g* = ∑gxy     ;     x,y en S'

Question 27

Eliminación en Torneo: Explique la red de flujo

Answer 27

Armaremos una red de flujo y resolveremos el problema mediante el cálculo del flujo máximo.

Creamos:
- Un nodo vx por cada equipo x en S’
- Un nodo vxy por cada par de equipos x,y en S’, que tiene al menos un partido pendiente
- S nodo fuente
- T nodo sumidero

Creamos además:
- Un eje s-uxy, con capacidad gxy (representan los partidos pendientes entre x e y)
- Un eje uxy-vx, con capacidad gxy (representan los partidos entre x e y que gana x)
- Un eje uxy-vy con capacidad gxy (representan los partidos entre x e y que gana y)
- Un eje vi-t con capacidad m-wi (representan los partidos que puede ganar i sin pasar a z).

Question 28

Resuelva:

Eliminación en Torneo: Arme la red de flujo para los siguientes equipos:

Equipo     ganados     perdidos     pendientes(1, 2, 3, 4)
1                    50               40                   (0,3,5,2)
2                     48               47                (3,0,0,2)
3                    45                48               (5,0,0,2)
4                    42                 52              (2,2,2,0)

z = 3

Answer 28

solución

Question 29

Eliminación en Torneo: Explique el Problema del Flujo Máximo

Answer 29

Si existe un flujo de g* = ∑gxy, implica que todos los resultados se pueden repartir entre los equipos sin infringir el máximo de puntos por equipo (sin pasar a z).

Si existe un flujo menor a g*, el equipo z no puede quedar primero. Esto es porque los puntos “no repartidos” tienen que ir a parar a algún equipo entre los que disputan. Y a quien le llegue al menos 1 punto de más, superará a z.

Por lo tanto, el flujo encontrado tiene que ser, si o si, igual a g* para que pueda ganar z.

Question 30

Eliminación en Torneo: Explique el Teorema de Hoffman-Rivlin

Answer 30

Sea un subconjunto de equipos S*, llamaremos:
- g(S*) a la cantidad de partidos pendientes entre todos los equipos de S*.
- w(S*) a la cantidad de partidos ganados por cada equipo de S*.
- |S*| a la cantidad de equipos en S*.

Entonces, si:

wz + gz < (w(S*) + g(S*)) / |S*|

el equipo z no puede ganar.

Afirmamos entonces que si existe al menos un subconjunto de equipos con las características deseadas, se lo puede encontrar como un corte s-t mínimo del problema de flujo planteado.

Podemos proponer que todos los ejes uxy - vx y uxy - vy tengan capacidad infinita, porque no hay riesgo de modificar resultados ya que el máximo está delimitado por los ejes s-uxy. De esta forma, ninguno de estos ejes pertenecerá al corte mínimo.

Question 31

Resolver:

Eliminación en Torneo: ¿Puede ganar el equipo 3?

Equipo     ganados     perdidos     pendientes(1, 2, 3, 4)
1                    50               40                   (0,3,5,2)
2                     48               47                (3,0,0,2)
3                    45                48               (5,0,0,2)
4                    42                 52              (2,2,2,0)

Answer 31

Flujo máximo: 7

m = 45 + 7 = 52

El equipo 3 puede ganar