Discusión:Algoritmo de Ford–Fulkerson

Después de 1998 más pasos…

Soy nuevo en esto, así que no lo cambié directamente porque no estoy 100% seguro. Pero el flujo no se incrementa en 1 sino en min{capacidades de aristas en la ruta encontrada}, por lo que solo debería tomar 1 paso para llenar una ruta. —Comentario anterior sin firmar agregado por 85.180.69.27 (discusión) 12:19, 20 de febrero de 2009 (UTC) [ responder ]

Los algoritmos terminan por naturaleza. Este artículo está lleno de referencias a "si el algoritmo termina" y "una variación que está garantizada que terminará". ¡Estas frases son problemáticas! ¿FF no es un algoritmo en absoluto, sino un enfoque/procedimiento? Aaronbrick 04:34, 12 de mayo de 2006 (UTC) [ responder ]

Este es un punto válido. Esta entrada debería llamarse en realidad el método Ford-Fulkerson. No se llama algoritmo, porque hay alguna parte del procedimiento que no se especifica. El método Ford-Fulkerson dice que hay que seguir encontrando caminos de aumento en el grafo residual, pero no lo limita a ninguna forma específica de encontrar esos caminos de aumento. Ésa es exactamente la razón por la que el procedimiento puede no terminar nunca, como se describe en el cuerpo del artículo. Por otro lado, un algoritmo siempre debería terminar con una respuesta, o con el anuncio de que no se puede encontrar ninguna respuesta. Ése es el criterio básico para la decidibilidad, y un algoritmo se define formalmente como un procedimiento para probar la pertenencia a lenguajes decidibles. —Comentario anterior sin firmar añadido por 128.227.179.104 (discusión) 02:58, 11 de octubre de 2007 (UTC)[ responder ]

Deberíamos utilizar el nombre que se utiliza con más frecuencia en este campo, independientemente de que pueda ser técnicamente inexacto en función de una definición particular de "algoritmo". Sin embargo, lo he visto llamado "método Ford-Fulkerson", por lo que esto puede estar justificado. Dcoetzee 00:10, 3 de octubre de 2008 (UTC) [ responder ]

Según conozco el término algoritmo, no tiene por qué terminar.

"Deberíamos utilizar el nombre más comúnmente utilizado en el campo" ¿Por qué? Si es un término incorrecto, pero común, entonces simplemente dejemos que ese término redirija al término correcto. Wikipedia es enormemente responsable de los términos que la gente utiliza "en el campo", por lo que solo sería responsable de perpetuar un término incorrecto "en el campo". En cuanto a "Por lo que sé, el término algoritmo no tiene por qué terminar", parece que lo conoces de manera diferente al resto de nosotros. Mangledorf ( discusión ) 00:15 13 nov 2009 (UTC) [ responder ]

Estoy de acuerdo con el penúltimo colaborador. La definición del concepto "algoritmo" no debería postular la terminación. De lo contrario, debido a la no decidibilidad de la detención, se tendría una situación inaceptable en la que no se puede decir si algo es un algoritmo o no a menos que se tenga una prueba de terminación para ello. Por supuesto, dado un algoritmo, se tiene derecho a buscar pruebas de que termina, o más generalmente de que es correcto con respecto a cualquier especificación dada. Esta es la forma en que se presentaría la cuestión en un libro de texto de Computabilidad; es cierto que en los libros de texto de Algoritmos (donde a menudo se encontraría el método de Ford-Fulkerson), uno generalmente enfatiza que los algoritmos deben ser correctos y, en particular, terminar, en la medida en que se pueda entender que un algoritmo incorrecto no es digno de su nombre. Pero en un nivel más fundamental, se deben admitir algoritmos tanto correctos como incorrectos, terminantes y no terminantes. Además, los algoritmos no terminantes son útiles en muchas situaciones prácticas, por ejemplo, cuando un algoritmo no puede alcanzar una solución óptima exactamente en un tiempo finito, sino que sólo converge hacia el óptimo; y el usuario puede decidir detener el proceso en algún punto según sus recursos o requisitos. Véase también Algoritmo en Wikipedia. AmirOnWiki ( discusión ) 23:31 10 feb 2010 (UTC) [ responder ]

Independientemente del problema de terminación, considero que el uso del "método Ford-Fulkerson" es una buena opción, ya que enfatiza que el subalgoritmo para encontrar caminos de aumento se ha dejado sin especificar. AmirOnWiki ( discusión ) 04:37 11 feb 2010 (UTC) [ responder ]

Error en ejemplo_2.svg

La flecha del medio debe apuntar de C a B, no de B a C.

Errores en la sección de algoritmos

Parece haber un pequeño error en la sección "Algoritmo". Hay tres fórmulas con tres descripciones informales al lado. Las descripciones informales de la segunda y la tercera parecen haberse intercambiado. En resumen, es:

2. f(u,v)=-f(v,u) - Mantenemos el flujo neto.
3. suma(f(u,v))=0 para todos los nodos excepto s y t - La cantidad de flujo que entra a un nodo es igual al flujo que sale del nodo.

mientras que debería ser:

2. f(u,v)=-f(v,u) - La cantidad de flujo que entra a un nodo es igual al flujo que sale del nodo.
3. suma(f(u,v))=0 para todos los nodos excepto s y t - Mantenemos el flujo neto.

También sugeriría reemplazar "para todos los nodos" por "para todos los nodos u" para mayor claridad.

Viridium 03:27 10 abril 2007 (UTC) [ responder ]

La redacción quizás no es muy clara. Con "mantener el flujo neto", se quiere decir que si en realidad van, por ejemplo, 5 camiones de a , y 3 camiones de a , entonces mantenemos y , de modo que . Para el tercer invariante, podría resultar más claro si se escribiera ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle f(u,v)=2}$ ${\displaystyle f(v,u)=-2}$ ${\displaystyle f(u,v)=-f(v,u)}$

${\displaystyle \sum _{v}f(u,v)=0\Longleftrightarrow \sum _{v}f_{-}(u,v)+\sum _{v}f_{+}(u,v)=0\Longleftrightarrow \sum _{v}f_{-}(u,v)=\sum _{v}f_{+}(u,v)\Longleftrightarrow f_{in}(u)=f_{out}(u)}$

donde solo se encuentran los valores negativos y solo los positivos. Klem fra Nils Grimsmo 05:39, 11 de abril de 2007 (UTC) ${\displaystyle f_{-}}$ ${\displaystyle f_{+}}$

Buena aclaración, pero hay algunos detalles incorrectos (en la ecuación anterior). Falta un signo menos. El lugar donde debe ir este signo menos depende de la convención que utilice para la definición de  : ¿es el valor absoluto del flujo negativo o es el flujo negativo real completo con su negatividad numérica? ${\displaystyle f_{-}(u,v)}$

En el ejemplo, no veo cómo se puede obviar la posibilidad de flujo directo a lo largo de ABD en el segundo paso, dado que este ejemplo de mal comportamiento pretende ser el resultado de una búsqueda en profundidad. Seguramente, en una "búsqueda en profundidad" alfabética, se debería intentar la ruta ABD a continuación, ¡antes de intentar ACBD! --Comentario anterior sin firmar dejado por 128.227.179.104 02:58, 11 de octubre de 2007 (UTC)

La búsqueda en profundidad no debe ser alfabética, parece ser que se trata de un caso extremo. Ese tipo de cosas pueden ocurrir si los bordes se almacenan en un conjunto no determinista y desordenado en lugar de una matriz. Es bastante improbable, pero eso es lo que significa el caso extremo. -- Brilliand 22:58, 26 de octubre de 2007 (UTC) [ responder ]

Svend 11:36, 3 de septiembre de 2011 (UTC) [ respuesta ]

En las líneas mencionadas arriba ahora dice:

Conservación del flujo: es decir, a menos que u = s o w = t. El flujo neto hacia un nodo es cero, excepto para la fuente, que "produce" flujo, y el sumidero, que "consume" flujo. ${\displaystyle \sum _{w\in V}f(u,w)=0}$

Pero creo que esto es un poco erróneo. Debería decir "a menos que o o similar, ya que f(t,w) sería negativa (si hubiera algún flujo) y, de la misma manera, f(u,s) sería negativa". ${\displaystyle u\in \{s,t\}}$ ${\displaystyle w\in \{s,t\}}$

contraejemplo

Sería bueno tener el contraejemplo de cuando no termina y converge al valor incorrecto. -- MarSch ( discusión ) 15:43 2 oct 2008 (UTC) [ responder ]

Encontré una posible referencia para esto (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.2479), pero no sé si tendré tiempo para escribirlo. -- MarSch ( discusión ) 15:50 2 oct 2008 (UTC) [ responder ]

El libro "Matching Theory" de Plummer y Lovasz lo explica. Zero ^talk 12:27 15 oct 2009 (UTC) [ responder ]

Agregué el contraejemplo . Svick ( discusión ) 01:38 16 oct 2009 (UTC) [ responder ]

Gracias, pero ¿podrías describirlo mejor, por favor? El algoritmo solo converge al valor incorrecto si se elige una secuencia particular de rutas de aumento. No ^{se habla de nada.}

He ampliado esa sección. ¿Crees que es comprensible y correcta? (Como has señalado, antes no lo era). Svick ( discusión ) 23:34 9 nov 2009 (UTC) [ responder ]

El flujo converge a 3+2r, no a 3. Además, hice los cálculos y creo que basta con que M sea al menos 2 (no es que sea importante). —Comentario anterior sin firmar añadido por Mkonva (discusión • contribs ) 04:37, 2 de diciembre de 2009 (UTC)[ responder ]

Revisé la fuente que cité y dice que el flujo converge a . Pero creo que tienes razón y debería ser , pero tal vez entendí mal algo. ¿Alguien podría leer el artículo y confirmar que realmente está mal? Si ese es el caso, deberíamos buscar otra fuente. ${\displaystyle \textstyle 1+2\sum _{i=2}^{\infty }r^{i}=3}$ ${\displaystyle 3+2r}$

Creo que tienes razón en que es suficiente, pero, repito, la fuente dice que es ... Repito, deberíamos buscar otra fuente. ${\displaystyle M=2}$ ${\displaystyle 4}$

Gracias por encontrar los (posibles) errores. Svick ( discusión ) 18:54 2 dic 2009 (UTC) [ responder ]

Ejemplo de Python

¿No se parece más al algoritmo de Edmonds-Karp ? Pensé que el algoritmo de Ford Fulkerson mantiene la selección de las rutas sin especificar... — Comentario anterior sin firmar añadido por 2001:9E8:1120:8C00:386F:F73E:7DE:BE89 (discusión) 19:34 3 abr 2024 (UTC) [ responder ]

El código de Python es inútil sin una llamada de ejemplo. En particular, no está claro cómo instanciar la clase (y por qué debería ser una clase de todos modos). — Comentario anterior sin firmar agregado por 2001:9E8:1120:8C00:386F:F73E:7DE:BE89 (discusión) 09:31, 3 abril 2024 (UTC) [ responder ]

Un anónimo hizo el siguiente comentario sobre el programa Python. Alguien debería comprobarlo.

"El código está incompleto y no funciona en absoluto. La comprensión de las características del lenguaje Python es muy buena, pero la comprensión del algoritmo Ford-Fulkerson es muy pobre. El DFS en find_path ni siquiera es correcto". Zero ^talk 12:23, 15 de octubre de 2009 (UTC) [ responder ]

Veo algunos problemas en el find_pathcódigo (la ruta que devuelve no es una ruta simple cuando debería y no se ejecuta en el tiempo óptimo), que deberían corregirse, pero creo que el código completo funciona correctamente. Svick ( discusión ) 23:37 15 oct 2009 (UTC) [ responder ]

Puede que me equivoque, pero veo al menos un problema más: ¿por qué adj[u]no es lo mismo que adj[v]en add_edge? ¿No deberían tener ambas aristas la misma capacidad wen lugar de que una sea 0? musically_ut ( discusión ) 07:04 5 nov 2009 (UTC) [ responder ]

No, esta versión también es correcta. En una red dirigida, la arista de a con capacidad no significa que exista una arista de a con la misma capacidad. Si su red no está dirigida (similar a las tuberías reales), debe agregar cada arista dos veces, una para cada dirección. Su versión también funcionaría, pero solo para redes no dirigidas. Svick ( discusión ) 23:42 9 nov 2009 (UTC) [ responder ] ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle c}$ ${\displaystyle v}$ ${\displaystyle u}$

El siguiente ejemplo demuestra un error en el código:

g = FlowNetwork () map ( g . add_vertex ,  [ 's' , 'n' , 't' ]) g . add_edge ( 's' , 'n' , 4 ) g . add_edge ( 's' , 'n' , 4 ) g . add_edge ( 's' , 't' , 4 ) g . add_edge ( 's' , 't' , 4 ) print  g . max_flow ( 's' , 't' )

El código da incorrectamente el valor de flujo 12. El problema es que la variable self.flow solo puede manejar un borde entre dos nodos cualesquiera, mientras que a menudo no es así. Al agregar un arco (i,j), el código también agrega el arco (j,i). Si ahora el usuario agrega el arco (j,i), hay un problema. -- Petter ( discusión ) 15:20, 21 de abril de 2010 (UTC) [ responder ]

Ya he corregido ese error en particular. -- Petter ( discusión ) 15:26 21 abr 2010 (UTC) [ responder ]

El problema mencionado anteriormente, que find_pathno devuelve una ruta simple, puede provocar una gran pérdida de rendimiento. En mi aplicación, tardé unos 16 minutos en encontrar algunos flujos máximos en un gráfico. Para forzar rutas simples, agregué la siguiente función:

def  edgeinpath ( self , edge ,  path ) :  for  ( pedge ,  presidual )  in  path :  si  pedge  ==  edge  o  pedge  ==  edge.redge : devuelve Verdadero devuelve Falso​    

y reemplazado

si  residuo  >  0  y  no  ( arista , residuo )  en  la ruta :

con

si  residual  >  0  y  no  self . edgeinpath ( borde ,  ruta ):

Esto redujo el tiempo de ejecución a menos de 3 segundos. Wouter - 12:40, 18 de agosto de 2010 (UTC) —Comentario anterior sin firmar agregado por 212.19.199.55 ( discusión )

El código parece Erlang

El siguiente comentario fue trasladado desde el artículo (sección Implementación de Python ), donde no pertenece. Svick ( discusión ) 22:35, 3 de noviembre de 2010 (UTC) [ responder ]

¿Soy yo o este código se parece más a Erlang que a Python? Hay mucha recursión de cola, coincidencia de patrones, concatenación de listas, etc., en este código. Todas ellas son prácticas de programación comunes en Erlang. — Comentario anterior sin firmar añadido por 75.92.222.10 (discusión) 04:37, 3 de noviembre de 2010 (UTC) [ responder ]

¿Por qué las citas están en la sección Notas?

Me pregunto por qué todas mis citas se colocaron en la sección "Notas". ¿Es este un error que se debe corregir? 09:21, 27 de marzo de 2015 (UTC) Kapil.xerox ( discusión ) 09:21, 27 de marzo de 2015 (UTC) [ responder ]

Fusionar con el algoritmo Edmonds-Karp

La siguiente discusión está cerrada. Por favor, no la modifique. Los comentarios posteriores deberán realizarse en una nueva sección. A continuación se presenta un resumen de las conclusiones alcanzadas.

No fusionar, sino considerar la reestructuración (eliminación o traslado) de parte del material para que los contenidos coincidan mejor con el título de la página. Klbrain ( discusión ) 12:09 27 sep 2024 (UTC) [ responder ]

---

El algoritmo Edmonds-Karp es simplemente una implementación de Ford-Fulkerson que especifica que la ruta de ampliación debe encontrarse mediante una búsqueda en amplitud . El artículo sobre Edmonds-Karp es WP:Semi-duplicate y contiene contenido en gran parte similar, todo lo cual realmente debería estar en este artículo. ¿Quieres fusionar Edmonds-Karp con este artículo? IntGrah ( discusión ) 22:51 12 abr 2024 (UTC) [ responder ]

Me inclino en contra de esta fusión. Es un algoritmo con nombre que se cubre comúnmente en los libros de texto de algoritmos ( Introducción a los algoritmos le dedica algunas páginas), y no conozco ningún otro algoritmo con nombre que obtenga tanta cobertura y no tenga su propio artículo. También es más un subtema del algoritmo de Ford-Fulkerson que un duplicado, y en mi opinión, los contenidos no son lo suficientemente similares como para requerir una fusión. Por ejemplo, el artículo de Ford-Fulkerson podría servir como una descripción general de alto nivel del método al discutir el concepto de encontrar caminos de aumento en una red residual, por qué funciona este método ( teorema de corte mínimo de flujo máximo ), casos de falla con capacidades de borde irracionales y su tiempo de ejecución dependiente del flujo máximo, mientras que el artículo de Edmonds-Karp podría profundizar en su tiempo de ejecución (por qué es polinomial e independiente del valor de flujo máximo) e incluir detalles de implementación como pseudocódigo. Malerisch ( discusión ) 02:46, 2 de junio de 2024 (UTC) [ respuesta ]

En mi opinión, en este artículo se le da un peso indebido al caso no terminal con capacidades de borde irracionales. También creo que el análisis de las complejidades temporales debería pertenecer a este artículo; ¿dónde más iría una comparación de DFS (ingenuo) y BFS (Edmonds–Karp)? IntGrah ( discusión ) 02:20 8 jun 2024 (UTC) [ responder ]

Aunque Introduction to Algorithms (4.ª ed.) solo menciona brevemente las capacidades de borde irracionales, la mayor parte de la sección que cubre el algoritmo Ford-Fulkerson en Algorithms [1] de Jeff Erickson trata sobre este caso de falla, por lo que no estoy seguro de que su cobertura en este artículo sea indebida. En cuanto a DFS, yo diría que ninguno de los artículos debería cubrirlo en detalle; después de todo, un punto clave de Ford-Fulkerson es que el método para encontrar una ruta de aumento no está especificado, en lugar de algo concreto como DFS. (Ni CLRS ni Erickson discuten DFS en mucho detalle con Ford-Fulkerson; CLRS solo menciona DFS brevemente cuando afirma que encontrar una ruta lleva tiempo). En cambio, este artículo podría explicar por qué el tiempo de ejecución de Ford-Fulkerson es con capacidades enteras y mencionar a Edmonds-Karp como una mejora; el artículo de Edmonds-Karp podría mencionar el tiempo de ejecución de Ford-Fulkerson y explicar por qué BFS lo mejora a . En otras palabras, ambos artículos incluirían una comparación de los tiempos de ejecución de sus algoritmos (es inevitable que haya cierta superposición), pero cada artículo se centraría en su propio algoritmo. Creo que esto se alinea con la forma en que los libros de texto cubren estos dos temas. Malerisch ( discusión ) 10:08, 8 de junio de 2024 (UTC) [ responder ] ${\displaystyle O(E)}$ ${\displaystyle O(E|f^{*}|)}$ ${\displaystyle O(VE^{2})}$

La discusión anterior está cerrada. No la modifique. Los comentarios posteriores deben realizarse en la página de discusión correspondiente. No se deben realizar más modificaciones a esta discusión.