El método de Ford-Fulkerson o algoritmo de Ford-Fulkerson ( FFA ) es un algoritmo codicioso que calcula el flujo máximo en una red de flujo . A veces se le llama "método" en lugar de "algoritmo", ya que el enfoque para encontrar rutas de aumento en un gráfico residual no está completamente especificado [1] o se especifica en varias implementaciones con diferentes tiempos de ejecución. [2] Fue publicado en 1956 por LR Ford Jr. y DR Fulkerson . [3] El nombre "Ford-Fulkerson" también se utiliza a menudo para el algoritmo de Edmonds-Karp., que es una implementación completamente definida del método Ford-Fulkerson.
La idea detrás del algoritmo es la siguiente: siempre que haya una ruta desde la fuente (nodo de inicio) hasta el sumidero (nodo final), con capacidad disponible en todos los bordes de la ruta, enviamos flujo a lo largo de una de las rutas. Luego encontramos otro camino y así sucesivamente. Una ruta con capacidad disponible se denomina ruta de aumento .
Algoritmo
Dejar ser un gráfico, y para cada arista de u a v , sea ser la capacidad y ser el flujo. Queremos encontrar el flujo máximo desde la fuente s hasta el sumidero t . Después de cada paso del algoritmo, se mantiene lo siguiente:
Limitaciones de capacidad El flujo a lo largo de un borde no puede exceder su capacidad. Simetría sesgada El flujo neto de u a v debe ser el opuesto al flujo neto de v a u (ver ejemplo). Conservación de flujo El flujo neto a un nodo es cero, excepto para la fuente, que "produce" flujo, y el sumidero, que "consume" flujo. Valor (f) El flujo que sale de s debe ser igual al flujo que llega a t .
Esto significa que el flujo a través de la red es un flujo legal después de cada ronda del algoritmo. Definimos la red residual ser la red con capacidad y sin flujo. Tenga en cuenta que puede suceder que un flujo de v a U está permitido en la red residual, aunque no permitido en la red original: si y luego .
Algoritmo Ford – Fulkerson
- Entradas dada una red con capacidad de flujo c , un nodo fuente sy un nodo sumidero t
- Salida Calcular un flujo f de s a t de valor máximo
- para todos los bordes
- Si bien hay un camino p de s a t en, tal que para todos los bordes :
- Encontrar
- Por cada borde
- ( Envía flujo a lo largo del camino )
- ( El flujo podría "devolverse" más tarde )
- "←" denota asignación . Por ejemplo, " más grande ← artículo significa" que el valor de los mayores cambios en el valor del elemento .
- " return " termina el algoritmo y genera el siguiente valor.
La ruta en el paso 2 se puede encontrar con, por ejemplo, una búsqueda en amplitud (BFS) o una búsqueda en profundidad en. Si usa el primero, el algoritmo se llama Edmonds – Karp .
Cuando no se puedan encontrar más rutas en el paso 2, s no podrá alcanzar t en la red residual. Si S es el conjunto de los nodos alcanzables por s en la red residual, entonces la capacidad total de la red original de bordes de S para el resto de V es por un lado igual al flujo total que encontramos de s a t , y por otro lado, sirve como límite superior para todos esos flujos. Esto prueba que el flujo que encontramos es máximo. Véase también el teorema de corte mínimo de flujo máximo .
Si el gráfico tiene múltiples fuentes y sumideros, actuamos de la siguiente manera: Supongamos que y . Agregar una nueva fuente con un borde de a cada nodo , con capacidad . Y agregue un nuevo fregadero con un borde desde cada nodo a , con capacidad . Luego aplique el algoritmo de Ford-Fulkerson.
Además, si un nodo u tiene una restricción de capacidad, reemplazamos este nodo con dos nodos y una ventaja , con capacidad . Luego aplique el algoritmo de Ford-Fulkerson.
Complejidad
Al agregar la ruta de aumento de flujo al flujo ya establecido en el gráfico, se alcanzará el flujo máximo cuando no se puedan encontrar más rutas de aumento de flujo en el gráfico. Sin embargo, no hay certeza de que alguna vez se llegue a esta situación, por lo que lo mejor que se puede garantizar es que la respuesta será correcta si el algoritmo termina. En el caso de que el algoritmo se ejecute indefinidamente, es posible que el flujo ni siquiera converja hacia el flujo máximo. Sin embargo, esta situación solo ocurre con valores de flujo irracionales. [ cita requerida ] Cuando las capacidades son números enteros, el tiempo de ejecución de Ford-Fulkerson está limitado por(vea la notación O grande ), donde es el número de aristas en el gráfico y es el caudal máximo en el gráfico. Esto se debe a que cada ruta de aumento se puede encontrar en tiempo y aumenta el flujo en una cantidad entera de al menos , con el límite superior .
Una variación del algoritmo de Ford-Fulkerson con terminación garantizada y un tiempo de ejecución independiente del valor de flujo máximo es el algoritmo de Edmonds-Karp , que se ejecuta en hora.
Ejemplo integral
El siguiente ejemplo muestra los primeros pasos de Ford-Fulkerson en una red de flujo con 4 nodos, fuente y hundirse . Este ejemplo muestra el peor comportamiento del algoritmo. En cada paso, solo un flujo dese envía a través de la red. Si se utilizara la búsqueda primero en amplitud, solo se necesitarían dos pasos.
Camino | Capacidad | Red de flujo resultante |
---|---|---|
Red de flujo inicial | ||
Después de 1998 más pasos ... | ||
Red de flujo final |
Observe cómo el flujo "retrocede" desde a al encontrar el camino .
Ejemplo no terminante
Considere la red de flujo que se muestra a la derecha, con fuente , lavabo , capacidades de los bordes , y respectivamente , y y la capacidad de todos los demás bordes es un número entero . El constante fue elegido para que . Usamos rutas de aumento de acuerdo con la siguiente tabla, donde, y .
Paso | Camino de aumento | Flujo enviado | Capacidades residuales | ||
---|---|---|---|---|---|
0 | |||||
1 | |||||
2 | |||||
3 | |||||
4 | |||||
5 |
Tenga en cuenta que después del paso 1 y del paso 5, las capacidades residuales de los bordes , y están en la forma , y , respectivamente, para algunos . Esto significa que podemos usar rutas de aumento, , y infinitas veces y las capacidades residuales de estos bordes siempre estarán en la misma forma. El flujo total en la red después del paso 5 es. Si continuamos usando rutas de aumento como arriba, el flujo total converge a. Sin embargo, tenga en cuenta que hay un flujo de valor, enviando unidades de flujo a lo largo , 1 unidad de caudal a lo largo , y unidades de flujo a lo largo . Por lo tanto, el algoritmo nunca termina y el flujo ni siquiera converge al flujo máximo. [4]
Otro ejemplo no terminante basado en el algoritmo euclidiano lo dan Backman & Huynh (2018) , donde también muestran que el peor tiempo de ejecución del algoritmo Ford-Fulkerson en una reden números ordinales es.
Implementación en Python del algoritmo Edmonds-Karp
importar coleccionesclass Graph : "" "Esta clase representa un gráfico dirigido que utiliza una representación de matriz de adyacencia." "" def __init__ ( self , graph ): self . gráfico = gráfico # gráfico residual self . fila = len ( gráfico ) def bfs ( self , s , t , parent ): "" "Devuelve verdadero si hay una ruta desde la fuente 's' hasta el sumidero 't' en el gráfico residual. También llena parent [] para almacenar la ruta." "" # Marcar todos los vértices como no visitados visitados = [ Falso ] * self . fila # Cree una cola para las colecciones queue = de BFS . deque () # Marque el nodo de origen como visitado y colóquelo en la cola . append ( s ) visitaron [ s ] = Verdadero # Bucle BFS estándar mientras cola : u = cola . popleft () # Obtener todos los vértices adyacentes del vértice quitado de la cola u # Si no se ha visitado un adyacente, márquelo # visitado y colóquelo para ind , val in enumerate ( self . Graph [ u ]): if ( visitado [ ind ] == False ) y ( val > 0 ): cola . append ( ind ) visitado [ ind ] = Verdadero padre [ ind ] = u # Si llegamos al sumidero en BFS a partir de la fuente, devolvemos # verdadero, de lo contrario, devuelve falso visitado [ t ] # Devuelve el flujo máximo de sa t en el gráfico dado def edmonds_karp ( self , source , sink ): # Esta matriz se llena con BFS y para almacenar la ruta parent = [ - 1 ] * self . fila max_flow = 0 # No hay flujo inicialmente # Aumente el flujo mientras hay un camino desde la fuente hasta el sumidero mientras se auto . bfs ( fuente , receptor , padre ): # Encuentre la capacidad residual mínima de los bordes a lo largo del # camino llenado por BFS. O podemos decir encontrar el flujo máximo # a través de la ruta encontrada. path_flow = float ( "Inf" ) s = hundir mientras s ! = source : path_flow = min ( path_flow , self . graph [ padre [ s ]] [ s ]) s = padre [ s ] # Agregar flujo de ruta al flujo total max_flow + = path_flow # actualizar las capacidades residuales de los bordes y los bordes inversos # a lo largo del camino v = sumidero mientras v ! = fuente : u = padre [ v ] propio . gráfico [ u ] [ v ] - = path_flow self . gráfico [ v ] [ u ] + = path_flow v = principal [ v ] retorno max_flow
Ver también
Notas
- ^ Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng (2009). Automatización del diseño electrónico: síntesis, verificación y prueba . Morgan Kaufmann. pp. 204 . ISBN 978-0080922003.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introducción a los algoritmos . Prensa del MIT. págs. 714 . ISBN 978-0262258104.
- ^ Ford, LR ; Fulkerson, DR (1956). "Flujo máximo a través de una red" (PDF) . Revista Canadiense de Matemáticas . 8 : 399–404. doi : 10.4153 / CJM-1956-045-5 .
- ^ Zwick, Uri (21 de agosto de 1995). "Las redes más pequeñas en las que el procedimiento de flujo máximo de Ford-Fulkerson puede no terminar". Informática Teórica . 148 (1): 165-170. doi : 10.1016 / 0304-3975 (95) 00022-O .
Referencias
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Sección 26.2: El método Ford-Fulkerson". Introducción a los algoritmos (Segunda ed.). MIT Press y McGraw – Hill. págs. 651–664. ISBN 0-262-03293-7.
- George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Capítulo 8: Algoritmos de flujo de red". Algoritmos en pocas palabras . Oreilly Media . págs. 226–250. ISBN 978-0-596-51624-6.
- Jon Kleinberg ; Éva Tardos (2006). "Capítulo 7: Extensiones al problema de flujo máximo" . Diseño de algoritmos . Educación Pearson. págs. 378–384 . ISBN 0-321-29535-8.
- Samuel Gutekunst (2009). ENGRI 1101 . Universidad de Cornell.
- Backman, Spencer; Huynh, Tony (2018). "Transfinite Ford-Fulkerson en una red finita". Computabilidad . 7 (4): 341–347. arXiv : 1504.04363 . doi : 10.3233 / COM-180082 . S2CID 15497138 .
enlaces externos
- Un tutorial que explica el método Ford-Fulkerson para resolver el problema de flujo máximo
- Otra animación de Java
- Aplicación Java Web Start
Medios relacionados con el algoritmo de Ford-Fulkerson en Wikimedia Commons