Flujo Maximo

Los problemas de flujo máximo son problemas que aparecen a menudo en la vida real, como también en competencias de programación. En la forma mas común del problema, tenemos varias tuberías de agua, que están conectadas entre si y tienen distintas capacidades. Cual es la mayor cantidad de agua que se puede transportar de un punto inicial a uno final a través de estas tuberías?

En términos de teoría de grafos, nos dan una red – grafo dirigido, en la cual cada arista tiene una capacidad c asociada, y se selecciona un nodo inicial x y un nodo final y. Nuestra tarea es asignar a cada arista un valor f (f ≤ c de la arista) de manera tal que para todo nodo, la suma de f de todas las aristas que entran, sea igual a la suma de f de todas las aristas que salen. Este valor de f es llamado flujo en la arista. Mas aun, se nos pide maximizar la suma del flujo de las aristas que entran al nodo final.

Redes residuales y caminos de aumento: mas flujo

La red residual del grafo es, dicho de forma simple, el mismo grafo, con aristas duplicadas. Especificamente, si en la arista a-b del grafo original, el flujo es menor que la capacidad, en la red residual ponemos una arista de a-b con capacidad igual a la diferencia entre la capacidad y el flujo (esta es la capacidad residual). Y si en el grafo original, el flujo es mayor que cero, en la red residual ponemos una arista b-a con capacidad del flujo.

Grafo con su red residual

Un camino de aumento es un camino desde el nodo inicial hasta el final, con un flujo incrementado. En la imagen anterior, si consideramos el camino X-A-C-Y en la red residual, podemos incrementar el flujo en el grafo. Las aristas X-A y A-C tienen capacidad 3, pero como C-Y tiene capacidad 1, el menor de estos valores es la capacidad del camino.

Incrementando el flujo en 1
Incrementando el flujo en 1

El valor del flujo total ahora es 2, pero puede ser aun mas. No tiene sentido considerar las aristas X-B ni C-Y, ya que estas estan completas, pero existe otro camino. Vamos a construir nuevamente la red residual

flow3

El único camino que hay de X a Y es X-A-C-B-D-E-Y. Este camino no existe en el grafo real, solo en la red residual ya que C-B no es una arista en el grafo original. Sin embargo, podemos usar este camino para aumentar el flujo en el grafo, y C-B sera usada como un flujo negativo en el grafo real. Una vez mas, la cantidad de flujo que podemos incrementar es 1, que es la menor de las capacidades en el camino.

flow4

Si construimos la red residual con estos nuevos valores, encontramos que no existe ningun camino de X a Y.

Este ejemplo sugiere el siguiente algoritmo: comenzamos con cero flujo en todas las aristas, y vamos incrementando el flujo total mientras exista un camino de aumento sin aristas completas o aristas invertidas vacias, esto es: un camino en la red residual. De hecho, este es el algoritmo encontrado por Ford y Fulkerson y publicado en 1956.

Algoritmo de caminos de aumento: Ford-Fulkerson

La forma general del algoritmo seria asi (pseudocodigo)

function maxflow
result = 0
while (true)
    // encontramos un nuevo camino
    pathCapacity = findPath()
    // no se encontro ninguno
    if (d = 0) exit
    else result += pathCapacity
return result

Este algoritmo siempre llega a una solucion correcta, sin importar como busquemos los caminos de aumento. Sin embargo, cada camino de aumento podria incrementar el flujo en solo 1 unidad, por tanto el numero de iteraciones podria ser muy grande si escogemos un metodo poco eficiente para buscar los caminos de aumento. Tres métodos pueden ser usados:

  • DFS (Depth-First Search o Buscar por Profundidad)
  • BFS (Breadth-First Search o Busqueda por Anchura)
  • PFS (Priority-First Search o Busqueda por Prioridad)

De estas opciones, DFS es la mas sencilla de implementar, pero tiene menor eficiencia que los otros métodos. BFS es la implementacion mas común, ya que es relativamente simple de implementar y siempre encuentra el camino de aumento mas corto entre la fuente y el destino.

Implementando con BFS

Supongamos que tenemos las capacidades de las aristas en una matriz C[x, y]. En el algoritmo con BFS, vamos a buscar el camino mas corto entre la fuente y el destino y calcular la minima capacidad de las aristas en el camino – la capacidad del camino. Posteriormente, para cada arista en el camino, reducimos su capacidad e incrementamos la capacidad de la arista invertida como mostramos anteriormente. Vamos a ver el pseudocodigo.

int bfs()
    queue Q
    meter fuente en Q
    marcar fuente visitado
    // mantenemos el arreglo from, donde from[x] es el nodo anterior
    // en el camino de la fuente a x
    inicializar from con -1 (valor sentinela)
    while Q no vacio
        u = sacar de Q
        para todo vertice v adyacente a u
            if v no visitado y C[u][v] > 0
                meter v en Q
                marcar v visitado
                from[v] = u
                if v = destino
                    terminar while
        fin para todo
    fin while

    // calculamos la capacidad del camino
    v = destino, capacidad = infinito
    while from[v] > -1
        u = from[v] // vertice anterior
        capacidad = mininmo(capacidad, C[u][v])
        v = u
    fin while

    // actualizamos la capacidad residual si se encontro el camino
    v = destino
    while from[v] > -1
        u = from[v]
        C[v][u] -= capacidad
        C[u][v] += capacidad
        v = u
    fin while

    // si no hay camino, capacidad es infinito
    if capacidad = infinito
        return 0
    else
        return capacidad

En cuanto a eficiencia, el peor caso del algoritmo de flujo seria en total O(N×M2), pero usualmente el algoritmo se comporta mejor que esto. Esta implementacion con BFS es conocido como el algoritmo de Edmonds-Karp.

Implementando con PFS

En este caso se busca siempre el camino con mayor capacidad de aumento. A simple vista, esto podría mejorar el algoritmo ya que en cada paso se aumenta el flujo en la mayor cantidad posible, pero en algunos grafos el método de BFS tiene mejores tiempos. Para implementar este método, la prioridad asignada a cada vértice es la menor capacidad en el camino de la fuente al vértice. Procesamos cada vértice en una manera golosa, como en el algoritmo de Dijkstra, de mayor a menor prioridad. Cuando lleguemos al destino, terminamos, ya que se encontró el camino con la mayor capacidad. Este algoritmo lo debemos implementar con una estructura que nos permita encontrar el vértice con mayor prioridad, e incrementar su prioridad de forma eficiente. Esta estructura es un heap o cola con prioridad.

Vamos a ver como implementarlo con el pseudocodigo.

int pfs()
    priority queue PQ
    meter node(source, infinity, -1) en PQ
    mantenemos from como en el BFS
    // si no hay camino de aumento, path_cap es 0
    path_cap = 0
    while PQ no vacia
        aux = sacar de PQ
        u = aux.vertex, cost = aux.priority
        si ya visitamos u continuamos
        from[u] = aux.from
        if u = sink
            path_cap = cost
            salir de while
        marcar u visitado
        para todo vertice v adyacente a u
            if C[u][v] > 0
                new_cost = min(cost, C[u][v])
                meter node(v, new_cost, u) en PQ
        fin para todo
    fin while
    // actualizar red residual
    v = destino
    while from[v] > -1
        u = from[v]
        C[u][v] -= path_cap
        C[v][u] += path_cap
        v = u
    fin while
    return path_cap

El análisis de este método es un poco mas complicado, pero con esta implementacion el algoritmo de flujo seria O(M×logN×F), donde M es la cantidad de aristas, N es la cantidad de vértices y F es el flujo máximo en el grafo. Aunque este algoritmo parece ser mas eficiente, en la practica los dos se comportan de forma similar. Cual escoger a la hora de codificar es un asunto de preferencia, aunque el método de BFS es mas sencillo.

Referencias

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

http://en.wikipedia.org/wiki/Max_flow

http://jason-kok.appspot.com/algorithm/network

http://en.wikipedia.org/wiki/Edmonds-Karp

http://en.wikipedia.org/wiki/Ford-Fulkerson

Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s