martes, 18 de mayo de 2010

Proyecto 5

Descripción

En la Ciencia de la computación y teoría de los grafos, el Algoritmo de Edmonds-Karp es una implementación del Algoritmo de Ford-Fulkerson para la resolución del problema de flujo máximo en una red de flujo. La característica que lo distingue es que el camino de aumento más corto es usado en cada interacción, lo que garantiza que lo calculo va a terminar. En la mayoría de las implementaciones, el camino de aumento más corto es encontrado usando una búsqueda en anchura, la cual rueda un tiempo de Lo(VE2). Es decir asintóticamente más lento que algoritmo remarcagem-para-frente, el cual rueda en Lo(V3), pero es frecuentemente más rápido para utilización en grafos esparsos. El algoritmo fue publicado por primera vez por el científico ruso Dinic, en 1970, y después, de forma independiente, por Edmonds y Karp que lo publicaron en 1972. El algoritmo de Dinic incluye técnicas adicionales para reducir el tiempo para la orden de Lo(V2Y)

Problema que resuelve

Este algoritmo es idéntico al Algoritmo de Ford-Fulkerson, excepto que la orden de búsqueda cuando encuentra que el camino de aumento de flujo definido. El camino encontrado debe ser el camino más corto con capacidad disponible. Esto lo podemos encontrar por una primera búsqueda de amplitud dejando que los bordes sean la unidad de longitud. El tiempo de duración de O(|V|*|E|^2) se encuentra mostrando que cada trayectoria de aumento se puede encontrar en O(|E|)tiempo, y que a su vez al menos uno de los bordes de E se satura, la distancia desde un borde saturado a la fuente de la trayectoria de aumento debe ser más larga que la última vez que estaba saturado y la distancia es en la mayoría de V de largo.

Ejemplo

Dato una red de siete nudos, y capacidad como mostrado abajo:






En el pares f / c escritos en los arcos, f es el flujo actual, y c es la capacidad. La capacidad residual de u para v es cf(u,v) = c(u,v) − f(u,v), la capacidad total, menos la que ya está siendo usada. Si el flujo de la red de u para v es negativo, esto contribuye para capacidad residual.



Pseudocodigo

//Edmonds-Karp
//return the largest flow;flow[] will record every edge's flow
//n, the number of nodes in the graph;cap, the capacity
//O(VE^2)
#define N 100
#define inf 0x3f3f3f3f
int Edmonds_Karp(int n,int cap[][N],int source,int sink){
int flow[N][N];
int pre[N],que[N],d[N],p,q,t,i,j;
if (source==sink) return inf;
memset(flow,0,sizeof(flow));
while (true){
memset(pre,-1,sizeof(pre));
d[source]=inf;p=q=0,que[q++]=source;
while(p<0){ t="que[p++];" i="0;i
if (pre[i]<0&&(j=cap[t][i]-flow[t][i])) i="sink;i!=" i="pre[i])" j="i=">
return j;
}





Bibliografia
ww.cse.ohio-state.edu/~tamaldey/course/794/ek-algo.pdf
www.cs.umass.edu/~barring/cs611/lecture/11.pdf


8 comentarios:

  1. AutoEvaluacion:Me costo trabajo entender el tema bien pero despues de investigar y ver la similitud con el algoritmo de Ford-Fulkerson del cual se encuentra mas informacion, fue mas facil entender los recorridos del algoritmo.

    ResponderEliminar
  2. De casualidad sabes a que se refiere con Lo(VE2)?

    ResponderEliminar
  3. Buen ccontenido, pero tengo una duda, que diferencia tiene este algoritmo al de Ford-Fulkerson ya que son algo semejantes...
    saludos

    ResponderEliminar
  4. Si viene siendo casi lo mismo Abraham ya que es una implementacion del algoritmo de Ford-Fulkerson la diferencia es que en este caso se utiliza el camino mas corto para cada interacción esto garantiza que el calculo se pueda terminar.

    ResponderEliminar
  5. Cynthia no estoy muy seguro de lo que es creo que es una funcion del tiempo en el que rueda y es Lo(VE^2)la E esta al cuadrado solo que al momento de hacer la entrada se cambio

    ResponderEliminar
  6. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  7. Yo tenia la misma duda que Cynthia. Esas cosas Lo() no imagino que serán... ¿Omegas? En particular el símbolo Y al final del primer párrafo me confunde :S

    ResponderEliminar
  8. Dea cuerdo al teorema en una red de flujo
    G={N,A}, es a lo sumo O(na)osea que el tiempo total de ejecucion es O(na^2)

    ResponderEliminar