El problema de la Evacuación

Feb 22, 2011 Programacion 4 comentarios

El semestre pasado, dimos la asignatura DAA (Diseño y Análisis de Algoritmos), que nos introducía varias técnicas, métodos y trucos para programar ciertos problemas de forma eficiente. Al final del semestre, nos dejan 3 o 4 problemas por equipo, para los cuales no solo tenemos que programar una solución eficiente, sino que tenemos que demostrar que funciona, y que es bastante eficiente… pues aquí les dejo mi informe del problema que me orientaron. Pasé largos días buscando información de varios lugares, pero por fin pude reunir toda la información que necesitaba y tuve que leer bastante sobre grafos y en especial el método de Ford Fulkerson para encontrar flujo máximo en un grafo, y la verdad me sorprendí bastante cuando logré terminar este ejercicio, justo a tiempo. En la literatura y en Internet se refieren a este problema como “Escape Problem” o “Evacuation Problem”. Aquí están las demostraciones de por que el algoritmo funciona correctamente, y al final, un zip con la solución del problema implementado en C#.

Cual es el problema?

Una rejilla n × n es un grafo no dirigido que consiste de n filas y n columnas de vértices. El vértice de la fila i y la columna j se denota (i, j). Todos los vértices en la rejilla tienen exactamente 4 vecinos, excepto los vértices frontera que corresponden a los (i, j) para los cuales: i = 1, i = n, j = 1 o j = n. Dados m <n2 puntos iniciales (x1, y1), (x2, y2), . . . , (xm, ym) en la rejilla, el problema de la evacuación consiste en determinar si existen m caminos disjuntos (no tienen vértices comunes), que comiencen en los puntos iniciales y lleguen hasta m puntos diferentes de la frontera.

Resumen

El problema consiste en encontrar m caminos disjuntos entre dos conjuntos A y B, donde A son los m puntos de entrada y B es el conjunto de los vértices en la frontera. Primeramente se verá cómo podemos reducir el problema de encontrar m caminos vértice-disjuntos en encontrar m caminos arista-disjuntos entre dos nuevos vértices s y t transformando la entrada. En la segunda parte reduciremos el problema de saber si existen m caminos arista-disjuntos entre s y t, en un problema de flujo máximo con capacidades 1 y 0, exponiendo una condición necesaria y suficiente. Por último mostraremos un algoritmo para encontrar el flujo máximo en un grafo en O(n3).

1. Transformando la entrada

Primeramente veremos cómo el problema de encontrar m caminos vértice-disjuntos entre dos conjuntos de vértices se puede reducir a encontrar m caminos vértice-disjuntos entre dos nuevos vértices s y t.

Sean:
i. A⊂V(G) y B⊂V(G) | A∩B=∅ ^ |A|=m
ii. s y t dos nuevos vértices donde s,t ∉V(G).
iii. ∀v∈A, E(G) = E(G) + <s,v>

iv. ∀v∈B, E(G) = E(G) + <v,t>

Sea k la cantidad de caminos vértice-disjuntos que van desde A hasta B y sea k’ la cantidad de caminos disjuntos que van de s a t, donde estos son los únicos vértices comunes en los k’ caminos, entonces k=k’, ya que aumentamos cada uno de los A-B caminos vértice-disjuntos con dos aristas <s,v0> y <vn,t> donde v0 es el primer vértice de un A-B camino y vn el último.Luego, si hacemos estos cambios al grafo de la entrada tendremos un nuevo grafo G’=<V’,E’>, donde:

V’=V+{s,t}
E’=E+{s,u}+{v,t} | u∈A ^ v∈B

Ahora convertiremos el grafo G’ en un grafo dirigido de la siguiente forma:

Por cada arista no dirigida en G’, pondremos dos aristas dirigidas, una en cada sentido. Luego, los k caminos vértice-disjuntos en G’ se mantienen luego de hacer esta transformación. Lo siguiente que haremos será convertir los caminos vértice-disjuntos en G en caminos arista-disjuntos en G´, para esto hacemos:

V’ = {vin, vout | v∈V(G)}
E’ = {(vout, win) | (v,w) ∈E(G)} ∪ {(vin, vin) | v∈V(G)}

Con las transformaciones propuestas obtenemos un nuevo grafo G’ donde cada camino vértice-disjunto en G corresponde con un camino arista-disjunto en G’ entre los vértices s y t, ya que cada camino que pasa por un vértice v pasará solo a través de la arista (vin, vout). El costo de obtener G’ a partir de G es claramente O(V), lo que en términos de la entrada sería O(n2).

2. Reduciendo el problema de encontrar k caminos arista-disjuntos a un problema de flujo máximo en una red de flujo.

En esta segunda parte, definiremos una red de flujo matemáticamente y veremos en detalle cómo resolver nuestro problema original utilizando un algoritmo para encontrar el flujo máximo en una red con capacidades de valor 1.

Sin pérdida de generalidad, sea G=<V,E> un grafo conexo y dirigido con dos vértices distinguidos s y t que llamaremos origen y destino respectivamente, donde indeg(s)=exdeg(t)=0. Definamos una función c: E→Z+ en G que llamaremos capacidad, y representa intuitivamente la cantidad máxima de flujo que puede pasar por la arista (u,v).

Diremos que un flujo s-t es una función f:E→Z+ donde el valor f(u,v) representa la cantidad de flujo que puede pasar entre los vértices u y v. El flujo f debe satisfacer las siguientes dos propiedades:

i. 0≤f(u,v)≤c(u,v), ∀(u,v)∈E(G).

ii. La sumatoria de los flujos que entran en un vértice es igual a la sumatoria de los flujos que salen de él (no lo puedo porner matemáticamente)

Obviamente la propiedad (ii) no se cumple para s y t, ya que indeg(s)=exdeg(t)=0. Llamaremos flujo de G y lo denotaremos por f(G) a la cantidad de flujo generado por s, luego f(G) es la suma de los flujos de las aristas que salen de s. El problema del flujo máximo es hallar cual es el máximo valor de f(G). O sea, ¿Cuál es la mayor cantidad de flujo que se puede enviar desde s sin violar las capacidades de las aristas? Denotaremos el flujo máximo de G como f*(G).

Volviendo a nuestro problema, después de hacer los cambios propuestos en (1) a la rejilla de entrada, tendremos un grafo D=<V,E> conexo, dirigido y dos vértices distinguidos s y t, indeg(s)=exdeg(t)=0. Luego, podemos definir un flujo s-t en D, donde en un principio todas las aristas tendrán capacidad 1 y se puede ver fácilmente que no se viola ninguna de las dos propiedades. Veamos una condición necesaria y suficiente para saber cuál es el número máximo de caminos arista disjuntos entre s y t:

Teor: El número máximo de caminos arista-disjuntos entre s y t en D, es igual al flujo máximo en D entre s y t donde todas las aristas tienen capacidad 1.

D/ Sea k el número de caminos arista-disjuntos en D entre s y t, entonces el flujo máximo f(D)≥k.

Sea P el conjunto de los k caminos disjuntos de s a t. Vamos a hacer lo siguiente:

1. f(u,v)=1 ∀(u,v)∈E(P)

2. f(u,v)=0 ∀(u,v)∉E(P)

f(u,v) solo toma valores 0 ó 1, por lo que se cumple la propiedad (i). Además, todo camino empieza en s y termina en t, y esto implica que todos los vértices interiores que participan en alguno de los k caminos arista-disjuntos tiene una arista que entra y una que sale de v con flujo 1 por construcción, por lo que se cumplirá la propiedad (ii). Luego, tendremos un flujo válido en D, f(G) =k, que son la cantidad de aristas con flujo que salen de s. Luego, f*(G) ≥f(G) ≥k.

Sea D una red de flujo, donde f(D)= k y todas las aristas tienen capacidad 1, entonces existen al menos k caminos arista-disjuntos entre s y t.

En otras palabras, lo que tenemos que demostrar es que el conjunto de aristas con f(u,v)=1 contiene un subconjunto de k caminos arista-disjuntos entre s y t, esto es porque el flujo en este caso toma siempre valores 0 ó 1, por la forma en la que construimos nuestro grafo D.

Sea f(D)=k y m’ el conjunto de aristas tal que f(u,v)=1.

Para esta demostración haremos inducción en el número de aristas con f(u,v)=1.

(CB) para m’=0 no hay caminos disjuntos en D, ya que no hay ninguna arista con f(u,v)=1, y f(G)=0.

(HI)Supongamos que en D hay un subconjunto de k caminos arista-disjuntos con menos de m’ aristas que llevan flujo.

Sea (s,v) una arista que lleva flujo (tiene que existir porque f(D)>0). Entonces, por la propiedad (ii) de conservación, hay alguna arista que sale de v con f(v,x) =1, x∈V(D). Repitiendo este proceso tenemos dos posibilidades, llegamos a t (1) o volvemos a un vértice que ya habíamos visitado (2).

Caso1: Si alcanzamos a t, encontramos un camino arista-disjunto partiendo desde s. Sea p dicho camino. Si hacemos f(u,v)=0 ∀(u,v)∈P, se siguen cumpliendo las propiedades (i) y (ii), además reducimos f(G) en 1 unidad. Como tendremos menos de m’ aristas que llevan flujo, entonces tendremos k-1 caminos disjuntos, por hipótesis de inducción, luego volvemos a añadir P, y tendremos k-1+1=k caminos disjuntos desde s hasta t.

Caso2: Si visitamos un vértice por segunda vez, encontramos un ciclo. Sea C el conjunto de aristas de dicho ciclo. Podemos hacer f(u,v)=0 ∀(u,v)∈C, sin que se afecte el flujo de s a t, ya que cada arista del camino entra y sale de un vértice en C, luego se siguen cumpliendo las propiedades (i) y (ii), y tendremos menos de m´ aristas con flujo. Como f(G) sigue siendo k, por hipótesis de inducción tendremos un conjunto de k caminos disjuntos de s a t.

En virtud del principio de inducción queda demostrado.

Esta demostración no solo nos da una condición necesaria y suficiente para saber cuándo hay m caminos arista-disjuntos en una red de flujo donde todas las aristas tienen capacidades 1, sino como obtener dichos caminos, aunque en nuestro problema solo hay que decir si existen o no.

Luego, el problema se convierte en saber si el flujo máximo de nuestro nuevo grafo (después de hacer las transformaciones y ponerle capacidades 1 a todas las aristas) es igual a m, ya que m son la cantidad máxima de caminos arista-disjuntos que podemos encontrar en G.

3. Calculando el flujo máximo en una red de flujo

Para calcular el flujo máximo en un grafo dirigido, conexo y con capacidades en las aristas usaremos el método de Ford Fulkerson, basado en tres conceptos principales: red residual, camino aumentable y corte:

La capacidad residual de un arco intuitivamente es la cantidad de flujo sobrante de cada arco, y representa el flujo que puede pasar por dicho arco sin que se viole la capacidad: cf(u,v)=c(u,v)-f(u,v), note que por la propiedad (i), cf(u,v)≥0

Una red residual es aquella formada por el conjunto de las aristas con capacidades residuales positivas que denotaremos por: Df= (u,v)∈E(D) | Cf(u,v)>0.
La capacidad residual de un camino es el mínimo de las capacidades residuales de sus arcos, donde: Cf(p)= min{cf(u,v) | (u,v) ∈p}
Un camino aumentable es un camino p simple y dirigido de s a t, donde todos sus arcos tienen capacidad residual positiva:∀(u,v)∈p f(u,v)>0.
Un corte es una partición de D en dos componentes cualquiera S y T, donde s∈S y t∈T, que denotaremos por (S,T).
La capacidad de un corte es la suma de las capacidades de los arcos que cruzan el corte, en el sentido de origen al destino.
Definiremos como flujo de un corte a la suma de los flujos que cruzan dicho corte en dirección de s a t.

Veamos un pseudocódigo del algoritmo propuesto:

FORD-FULKERSON-METHOD(G, s, t)
1 inicializar el flujo f a 0
2 while exista un camino aumentable p en la red residual
3 do aumentar cf(p) en todas las aristas de p
4 return f

En la línea 1 comenzamos con un flujo 0, que asegura el cumplimiento de las propiedades (i) y (ii), ya que por definición c(u,v)>0 ∀(u,v)∈E(D).
En la línea 2 trataremos repetidamente de obtener un camino aumentable p en Gf.
En la línea 3 aumentamos el flujo f a través de todo el camino p por la capacidad residual de p
Por último, en la línea 4, una vez que no hayan más caminos aumentables, el flujo obtenido es máximo.

4. Correctitud del algoritmo de Ford-Fulkerson

Para demostrar la correctitud del algoritmo tendremos que probar lo siguiente:
Sea f un flujo en una red de flujo entre s y t. Entonces se cumple que f es un flujo máximo si solo si no hay caminos aumentables en Gf
Sea f(G) el flujo máximo de G. Entonces no hay caminos aumentables en Gf
Para llegar a una contradicción, supongamos que existe al menos un camino aumentable en Gf y f es máximo.
Entonces existe un camino simple entre s y t, donde f(u,v)>0 ∀(u,v) ∈p, luego podemos aumentar el flujo a través de todo el camino sin violar ninguna de las propiedades debido a la elección de cf(p), luego el flujo f(G) aumentará al menos en 1 unidad en nuestro caso, que estamos trabajando con capacidades enteras. Después de ese proceso tendremos un nuevo flujo f’(G)=f(G)+k, donde k = cf(p)>0. Luego, f’(G)>f(G), y por tanto f(G) no es máximo, lo cual es una contradicción, luego lo supuesto es falso, y se cumple lo planteado.
Si no hay caminos aumentables, entonces el flujo f que se tiene en ese momento es máximo.
Supongamos que no hay caminos aumentables en Gf. Sea S el conjunto de vértices que son alcanzables por s y T = V-S. Podemos definir el corte (S,T) donde s∈S y t∈T, ya que si t∈S entonces hubiera un camino aumentable. Fácilmente se puede demostrar que f(S,T)≤c(S,T) para todo corte de G, por la propiedad de conservación (i). Se puede notar f(S,T)=c(S,T), ya que toda arista que cruza el corte en Gf tiene flujo 0 por la forma en que construimos el corte, luego como f(G) ≤c(S,T) y tenemos f(G)=f(S,T)=c(S,T), entonces f(G) es máximo.

5. Nuestra implementación del método Ford Fulkerson

Ahora podemos ver el pseudocódigo de nuestra implementación del método Ford Fulkerson, adaptado a nuestro problema donde todas las aristas tienen capacidades de una unidad.

FORD-FULKERSON(G, s, t)
1 foreach arco (u, v) en E[G]
2 do f[u, v] ← 0
3 f[v, u] ← 0
4 while BFS(s, t) en Gf
5 do f← f + 1
6 foreach arco (u, v) en p
7 do f[u, v] ← f[u, v] + 1 8 f[v, u] ← f[u, v] – 1
9 return f

En las líneas 1-3 inicializamos el flujo de cada arista en 0, para que se cumplan todas las propiedades del flujo.
En la línea 4 verificamos la existencia de un camino aumentable en Gf mediante un BFS, que devuelve el camino más corto entre s y t, lo cual mejora la constante de nuestro algoritmo, aunque bien se podía utilizar cualquier otro método que nos dé un camino entre dos vértices de un grafo.
En la línea 5, simplemente aumentamos el flujo en 1, ya que cada vez que se encuentra un nuevo camino aumentable, el flujo aumenta a lo sumo en 1, y todas las capacidades son enteras.
En las líneas 6-8, sumamos una unidad al flujo de cada arista de p en Gf y restamos esta misma cantidad en G.
En la línea 9 simplemente se devuelve el flujo máximo de la red de flujo definida por G, s y t, el cual sabemos que es máximo por el teorema demostrado en (4).

6- Análisis del tiempo de ejecución

El costo de reducir nuestro problema original de comprobar cuando o no hay m caminos entre dos conjuntos dados en el problema de encontrar el flujo máximo en una red dirigida es O(|V|) como se vio en la primera parte, donde en el grafo obtenido se tiene:

|V|= 2+2n^2=O(n^2)
|E|= m+ 4n^2-4=O(n^2)

El tiempo de ejecución del método Ford-Fulkerson depende principalmente de cómo se escoja el camino aumentable en cada paso del ciclo, en nuestro caso usamos BFS(G, s, t), que es O(|V|+|E|), y esta operación se hace a lo sumo f* veces, donde f* es el flujo máximo de G, que es el máximo de veces que se ejecuta el ciclo while de nuestro algoritmo. Luego tendremos un costo temporal:
T(n) = O(|V|) + O((|V|+|E|) · f*), pero |V| es O(E), luego:
= O(|V|) + O((|E|) · f*)=max(|V|,|E| · f*)
Además, tenemos que el flujo máximo cumple que: f*≤m≤4*(n-2), luego f* es O(n), luego en total tenemos que nuestro algoritmo es:
O(|E| · f*)=O((n^2)n)=O(n^3)

Luego, hemos encontrado un algoritmo que calcula el flujo máximo en un grafo con características propias de nuestro problema en orden polinomial.

Tendrás que disculparme por algunos errores en este post, sobre todo de notaciones y simbología. Esto se debe a que lo tuve que copiar desde un archivo PDF, y aún no he encontrado un buen plugin para wodpress para trabajar con notaciones matemáticas y simbología, a lo mejor me embullo y lo implemento yo mismo.

Ah, se me olvidaba, aquí está lo más importante: El código en C# de EscapeProblem. Cualquier duda (que seguro vas a tener unas cuantas) en los comentarios por favor.

Compartir:

4 comentarios

Forma parte de nuestra discusión y síguela de cerca

Hola, muchas gracias por toda esta informacion. Veo que ha pasado tiempo desde que lo posteaste pero me ha servido de mucho! Sobre todo las restricciones y la explicacion del metodo de ford-fulkerson.

Autor: Alirio | Fecha: May 2, 2012.

Lo publiqué sobre todo porque no encontré nada en la red cuando estuve resolviendo este problema ;)

Autor: Tomy | Fecha: May 8, 2012.

Disculpa no veo el código me lo puedes pasar o decir como acceder a él.. por favor.

Gracias

Autor: Claudia | Fecha: Oct 23, 2012.

Claudia, se me había olvidado adjuntar el código, ya puedes verlo en un enlace al final del post.
Saludos

Autor: Tomy | Fecha: Oct 23, 2012.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.