Algoritmo Push-Relabel
- Propuesto por
- Andrew V. Goldberg and Robert E. Tarjan
- Año
- 1988
- Tipo
- algorithm
- Familia
- Graph Algorithms
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El Algoritmo Push-Relabel, desarrollado por Andrew V. Goldberg y Robert E. Tarjan en 1988, es un método muy eficiente para calcular el flujo máximo en redes.
A diferencia de los métodos de caminos aumentantes, mantiene un preflujo y utiliza operaciones locales de empuje (push) y de reetiquetado global (relabel) para dirigir el flujo hacia el sumidero, logrando una complejidad superior en el peor de los casos.
La intuición detrás del método
El algoritmo mantiene una 'altura' o 'etiqueta de distancia' para cada nodo y utiliza preflujo (donde los nodos pueden exceder temporalmente la demanda del sumidero). Repetidamente empuja el exceso de flujo de nodos con etiquetas más altas a vecinos con etiquetas más bajas y reetiqueta los nodos para crear caminos hacia el sumidero. La idea clave es que, al mantener invariantes de altura y utilizar estructuras de datos eficientes, el algoritmo evita explorar todo el grafo repetidamente, como deben hacer los métodos de caminos aumentantes. El algoritmo termina cuando todo el exceso de flujo llega al sumidero.
Historia
Goldberg y Tarjan publicaron su algoritmo push-relabel en 1988, introduciendo un paradigma fundamentalmente diferente para el cálculo del flujo máximo. Su algoritmo logró una complejidad en el peor de los casos de O(V³), una mejora sobre el O(VE²) de Edmonds-Karp. Durante las décadas siguientes, se han desarrollado numerosas variantes, incluidas las heurísticas de brecha (Goldberg y Tarjan, 1990), las reglas de etiqueta más alta y las variantes más recientes que logran un rendimiento empírico casi lineal en redes del mundo real.
Cuándo usarlo
Aplicar el algoritmo push-relabel para calcular el flujo máximo en redes grandes y densas donde los métodos de caminos aumentantes se vuelven ineficientes. Es particularmente efectivo para redes con miles o millones de aristas. Úselo cuando necesite un rendimiento garantizado en tiempo polinomial y desee aprovechar estructuras de datos modernas. Para redes dispersas o fines educativos, los métodos de caminos aumentantes pueden ser más sencillos de entender e implementar.
Limitaciones y consideraciones
- Más complejo de entender e implementar que los métodos de caminos aumentantes
- Requiere un manejo cuidadoso de las estructuras de datos (listas de descarga, heurísticas de brecha) para un rendimiento óptimo
- La complejidad en el peor de los casos sigue siendo mayor que la de algunos algoritmos especializados para clases de grafos especiales
- Menor intuición del proceso de solución en comparación con los caminos aumentantes
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Complejidad temporal superior en el peor de los casos: O(V³) o O(V²√E) con heurística de brecha (gap heuristic)
- Altamente eficiente en la práctica, especialmente para redes grandes y densas
- Localidad de las operaciones (push/relabel) permite un buen rendimiento de caché
- Adaptable a implementaciones paralelas y distribuidas
- Múltiples variantes de implementación para diferentes estructuras de problemas
Aplicaciones
- Enrutamiento de redes: cálculo del rendimiento máximo en redes de comunicación a gran escala
- Procesamiento de imágenes: uso de max-flow para aplicaciones de segmentación y mate de imágenes
- Optimización de aerolíneas: determinación del flujo máximo de pasajeros a través de complejas redes de enrutamiento
- Análisis de redes eléctricas: cálculo de la capacidad máxima de transmisión de energía en redes eléctricas
- Gestión de la cadena de suministro: optimización del flujo de productos a través de redes de distribución de múltiples niveles
- Redes biológicas: análisis del flujo máximo en redes metabólicas y de interacción de proteínas
Cómo funciona
Cómo funciona
Establecer la altura de la fuente al número de vértices, todas las demás alturas a cero. Saturar todos los aristas que salen de la fuente, creando un preflujo inicial (exceso en los nodos vecinos).
Seleccionar repetidamente un nodo activo (con exceso de flujo) y empujar el exceso a un vecino de menor altura o reetiquetar el nodo para aumentar su altura. Utilizar estrategias de selección eficientes y operaciones de descarga para minimizar las iteraciones.
Continuar hasta que no queden nodos activos, momento en el cual todo el preflujo se ha resuelto en un flujo máximo desde la fuente hasta el sumidero.
Errores comunes
- Implementar incorrectamente las actualizaciones de altura o las operaciones de empuje que conducen a flujos no máximos
- Omitir el uso de heurísticas de brecha y selección eficiente de nodos, lo que resulta en un rendimiento práctico deficiente
- No mantener adecuadamente el invariante de preflujo (exceso en los nodos y restricciones de capacidad en las aristas)
Preguntas frecuentes
¿Cuál es la diferencia entre preflujo y flujo?
El preflujo permite temporalmente que los nodos retengan exceso de flujo (el flujo entrante menos el flujo saliente puede ser positivo), mientras que el flujo real debe conservarse en todos los nodos excepto la fuente y el sumidero. El algoritmo termina cuando el preflujo se convierte en un flujo válido.
¿Cuál es el propósito de la función de altura?
Las alturas crean una medida cuasi-distancia: el flujo solo puede ser empujado cuesta abajo (de alturas más altas a más bajas), previniendo ciclos innecesarios y asegurando la terminación. Las alturas se incrementan mediante reetiquetado para crear nuevos caminos cuando es necesario.
¿Qué es la heurística de brecha y por qué es importante?
La heurística de brecha detecta cuando ningún nodo tiene una altura en un cierto rango, lo que indica que algunos nodos no pueden alcanzar el sumidero. Estos nodos y su exceso se identifican y procesan rápidamente, mejorando significativamente el rendimiento práctico.
¿Cómo se compara push-relabel en la práctica con Edmonds-Karp?
Push-relabel tiene una mejor complejidad en el peor de los casos y típicamente supera a Edmonds-Karp en redes grandes, pero para redes pequeñas o grafos dispersos, Edmonds-Karp puede ser más sencillo de implementar con un rendimiento competitivo.
Métodos relacionados
Fuentes
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
Abrir referencia DOICopiado.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
Abrir referencia de la publicaciónCopiado.