Supongo aquí un par de cosas, por algoritmos de flujo de red se entiende algoritmos de flujo máximo st
Otros algoritmos basados en el flujo muy similares son el flujo máximo de todos los pares y el corte mínimo global. El corte máximo de flujo / min de todos los pares encuentra el flujo máximo entre todos los pares st y el corte min global encuentra que el corte mínimo global, que resulta, puede resolverse mucho más fácilmente que el flujo máximo st (corte st min).
Aunque son los algoritmos más representativos, existen muchos otros problemas que se incluyen en la categoría de algoritmos de flujo de red. Una pequeña lista de los problemas más importantes relacionados con los problemas de flujo máximo son
- Descubrí el algoritmo de Dijkstra yo mismo. ¿Puedo decir que soy bueno en informática?
- Cómo demostrar que este gráfico todavía puede estar fuertemente conectado
- ¿Cómo calculamos la complejidad espacio-temporal de un algoritmo?
- ¿Cuáles son algunos algoritmos informáticos inspirados en la naturaleza?
- ¿Por qué el aprendizaje profundo requiere la construcción de modelos de datos generativos?
a. Asignaciones y Emparejamientos
si. Cortes mínimos
do. Costo mínimo de circulaciones.
re. Flujos avanzados:
1. Flujos de productos múltiples.
2. Flujos dinámicos.
3. Flujos no divisibles.
Como se mencionó en otra respuesta, los problemas de flujo máximo pueden formularse como un programa lineal y pueden resolverse utilizando solucionadores de LP. Al aplicar LP en lugar de usar la estructura combinatoria del problema para resolverlo de manera más eficiente, estamos siguiendo la ley del instrumento (si tiene un martillo, todo parece clavos :)). Uno de los primeros enfoques para resolver el flujo de red fue usar una variante de la formulación LP llamada algoritmo de red simplex y fue diseñada específicamente para hacer uso de esta estructura. Estos métodos son muy rápidos en la práctica, aunque no necesariamente para grandes casos de problemas difíciles [Goldberg].
Algoritmos para flujo máximo.
Los algoritmos para el flujo máximo se pueden clasificar en dos. El primero basado en la idea de aumentar los caminos. Esta clase de algoritmos intenta encontrar sub soluciones viables en cada paso, y finalmente alcanza el valor óptimo. Entonces, si desea enviar un flujo máximo de s a t, primero encuentra un flujo de s a t y luego intenta aumentar ese flujo hasta lograr una solución óptima.
La segunda clase se esfuerza por la optimización y luego se ajusta para que el flujo sea factible. Los algoritmos de esta clase se denominan algoritmos Push-Relabel o algoritmos Preflow-Push. Entonces, si desea enviar un flujo máximo de s a t, primero encuentra el flujo máximo que puede enviar desde s a todos sus vecinos, a costa de romper algunas de las restricciones. Pero luego regresa y arregla las restricciones de modo que le deja una solución óptima.
Algoritmos de ruta de aumento
La primera idea principal para el problema del flujo máximo fue presentada por Ford y Fulkerson en su trabajo seminal en 1960 [FF’60]. La idea principal es buscar rutas de aumento (una ruta que permita un flujo de sa t) en el gráfico residual y agregarlas al flujo actual, hasta que no haya más rutas de aumento. Este algoritmo se ejecuta en [matemática] O (mnU) [/ matemática], donde U es el flujo de borde máximo en el gráfico. Sin embargo, este algoritmo no dice nada sobre en qué orden deben examinarse las rutas de aumento. Los siguientes dos algoritmos basados en el trabajo de Edmond y Karp [EK’72], ajustan el orden en que se agregan las rutas. La capacidad máxima o los algoritmos de ruta de aumento más gruesos encuentran la ruta de aumento más gruesa (o la ruta de aumento con el borde de cuello de botella más grande). Este algoritmo se ejecuta en [math] O ((m + nlogn) mlogF) [/ math]. El algoritmo de ruta de aumento más corto agrega los flujos a través de las rutas más cortas sucesivas. Es decir, encuentra las rutas de aumento con longitudes de ruta más cortas. La ruta más corta se puede encontrar ejecutando BFS una vez y etiquetando todos los nodos con una etiqueta de distancia desde s. Ahora, cada vez, se realiza una nueva búsqueda BFS en el gráfico residual para encontrar las rutas más cortas. Ahora, esto presta un algoritmo [matemático] O (m ^ 2n) [/ matemático]. Posiblemente se pueda mejorar este algoritmo, reduciendo el número de cálculos BFS necesarios. Los algoritmos de Dinic, reutilizan la información de la ruta más corta de una búsqueda BFS dada, y encuentran todas las rutas más cortas incidentes en ese flujo de bloqueo. La versión del árbol dinámico hace lo mismo, pero mantiene un árbol dinámico para almacenar las distancias calculadas.
Algoritmo de empuje previo al flujo
Los algoritmos basados en la etiqueta Push fueron introducidos por primera vez por Karzanov [K’74]. La idea es empujar desde la fuente para hundirse, tanto flujo como sea posible. Tomar una instantánea mientras se procesa el algoritmo revelará la cantidad excesiva de flujo agrupado en una capa de nodos. Ahora, la elección de qué nodos deben examinarse a continuación, es algo arbitrario. Cualquier nodo que no esté saturado, se examina y se empuja el flujo hasta que todos sus bordes estén saturados o el exceso en el nodo esté saturado. Debido a la naturaleza general de qué nodos deben procesarse a continuación, la implementación del algoritmo requiere mucha heurística para acelerarlo. Este algoritmo se ejecuta en tiempo [matemático] O (n ^ 2m) [/ matemático] (Tenga en cuenta que este algoritmo no es el algoritmo original de Karzanov). El siguiente algoritmo usa un orden de los nodos a examinar, empujando todos los nodos cercanos al nodo actualmente examinado a un FIFO. Este algoritmo se ejecuta en tiempo [matemático] O (n ^ 3) [/ matemático] y es muy eficiente en la práctica [GT’86]. Otra variante del algoritmo de empuje previo al flujo es el algoritmo de etiqueta más alta. En esta versión, el algoritmo examina los nodos en el orden de la etiqueta más alta. Este algoritmo tiene un tiempo de ejecución teórico de [matemática] O (n ^ 2 sqrt (m)) [/ matemática] [GT86] y probablemente sea uno de los algoritmos más eficientes en la práctica. La versión final de los algoritmos de preflujo es la escala excesiva algoritmo, que se ejecuta en [matemáticas] O (mn + n ^ 2logU) [/ matemáticas]. Este algoritmo realiza push / reetiquetado en nodos con valores suficientemente grandes de exceso de flujo. Entre estos nodos, selecciona nodos con la etiqueta más pequeña.
En cuanto al rendimiento empírico, los algoritmos push-relabel son en general más rápidos que los algoritmos de ruta de aumento. En particular, el algoritmo push-re-etiquetado más alto es una de las implementaciones más rápidas de flujo máximo. En el caso del algoritmo de ruta de aumento, los algoritmos de ruta de aumento más cortos son generalmente rápidos. Un buen artículo para la comparación empírica es este. El flujo máximo (y sus cortes duales mínimos) se usa ampliamente en Computer Vision y puede ver la comparación de los algoritmos de flujo máximo en Computer Vision aquí y aquí.
Aquí no se ha explorado una nueva clase de algoritmos, basada en el seudoflujo e intentará abordarla en una actualización.
Referencias
FF’60: Ford, LR, Jr., y Fulkerson, DR (1956), “Flujo máximo a través de una red”, Canadian Journal of Mathematics 8, 399-404.
EK’72: Edmonds, J. y Karp, RM (1972), Mejoras teóricas en la eficiencia algorítmica para problemas de flujo de red, Journal of ACM 19, 248-264.
D’70: Dinic, EA (1970). “Algoritmo para la solución de un problema de flujo máximo en redes con estimación de potencia”, Soviet Mathematics Doklady 1 1, 1277-1280.
GT’86: Goldberg, AV y Tarjan, RE (1986), “Un nuevo enfoque para el problema del flujo máximo”, Actas del 18º Simposio de ACM sobre la teoría de la producción de maíz, 136-146. Artículo completo en Journal of ACM 35 (1988), 921-940.
K’74: Karzanov, AV (1974), “Determinación del flujo máximo en una red por el método de preflujos”, Matemáticas soviéticas Dokladly 15, 434-437.
G’85:
Descargo de responsabilidad: este no es un material revisado por pares y podría tener errores involuntarios como resultado. Utilice este conocimiento con precaución y verifique, y asegúrese de comprender todo lo que está leyendo. Recomiendo leer los algoritmos de flujo de red de Ahuja et al. Si está buscando una referencia buena y accesible.
