Algoritmo Push-Relabel
- Proposto por
- Andrew V. Goldberg and Robert E. Tarjan
- Ano
- 1988
- Tipo
- algorithm
- Família
- Graph Algorithms
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
O Algoritmo Push-Relabel, desenvolvido por Andrew V. Goldberg e Robert E. Tarjan em 1988, é um método altamente eficiente para calcular o fluxo máximo em redes.
Diferentemente dos métodos de caminho aumentante, ele mantém um pré-fluxo e utiliza operações locais de "push" (empurrar) e globais de "relabel" (re-rotular) para direcionar o fluxo em direção ao sumidouro, alcançando uma complexidade de pior caso superior.
A intuição por trás do método
O algoritmo mantém uma "altura" ou "rótulo de distância" para cada nó e utiliza pré-fluxo (onde os nós podem temporariamente exceder a demanda do sumidouro). Ele repetidamente empurra o excesso de fluxo de nós com rótulos mais altos para vizinhos com rótulos mais baixos e re-rotula nós para criar caminhos para o sumidouro. A principal sacada é que, ao manter invariantes de altura e usar estruturas de dados eficientes, o algoritmo evita explorar o grafo inteiro repetidamente, como os métodos de caminho aumentante devem fazer. O algoritmo termina quando todo o excesso de fluxo atinge o sumidouro.
História
Goldberg e Tarjan publicaram seu algoritmo push-relabel em 1988, introduzindo um paradigma fundamentalmente diferente para o cálculo de fluxo máximo. Seu algoritmo alcançou complexidade de pior caso O(V³), uma melhoria em relação ao O(VE²) de Edmonds-Karp. Nas décadas seguintes, inúmeras variantes foram desenvolvidas, incluindo heurísticas de "gap" (Goldberg e Tarjan, 1990), regras de rótulo mais alto e as variantes mais recentes que alcançam desempenho empírico quase linear em redes do mundo real.
Quando usar
Aplique o algoritmo push-relabel para calcular o fluxo máximo em grandes redes densas onde os métodos de caminho aumentante se tornam ineficientes. É particularmente eficaz para redes com milhares ou milhões de arestas. Use-o quando precisar de desempenho garantido em tempo polinomial e quiser aproveitar estruturas de dados modernas. Para redes esparsas ou fins educacionais, os métodos de caminho aumentante podem ser mais simples de entender e implementar.
Limitações e considerações
- Mais complexo de entender e implementar do que os métodos de caminho aumentante
- Requer manuseio cuidadoso de estruturas de dados (listas de descarga, heurísticas de "gap") para desempenho ótimo
- A complexidade de pior caso ainda é maior do que alguns algoritmos especializados para classes de grafos especiais
- Compreensão menos intuitiva do processo de solução em comparação com os caminhos aumentantes
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Complexidade de tempo de pior caso superior: O(V³) ou O(V²√E) com heurística de "gap"
- Altamente eficiente na prática, especialmente para redes grandes e densas
- A localidade das operações (push/relabel) permite um bom desempenho de cache
- Adequado para paralelização e implementações distribuídas
- Múltiplas variantes de implementação para diferentes estruturas de problemas
Aplicações
- Roteamento de rede: cálculo do rendimento máximo em grandes redes de comunicação
- Processamento de imagem: uso de fluxo máximo para segmentação de imagem e aplicações de "matting"
- Otimização de companhias aéreas: determinação do fluxo máximo de passageiros através de redes de roteamento complexas
- Análise de redes elétricas: cálculo da capacidade máxima de transmissão de energia em redes elétricas
- Gestão da cadeia de suprimentos: otimização do fluxo de produtos através de redes de distribuição de múltiplos níveis
- Redes biológicas: análise do fluxo máximo em redes metabólicas e de interação proteica
Como funciona
Como funciona
Defina a altura da fonte como o número de vértices, e todas as outras alturas como zero. Sature todas as arestas que saem da fonte, criando um pré-fluxo inicial (excesso nos nós vizinhos).
Selecione repetidamente um nó ativo (com excesso de fluxo) e empurre o excesso para um vizinho de altura inferior ou re-rotule o nó para aumentar sua altura. Use estratégias de seleção e operações de descarga eficientes para minimizar as iterações.
Continue até que não restem nós ativos, momento em que todo o pré-fluxo foi resolvido em um fluxo máximo da fonte para o sumidouro.
Erros comuns
- Implementar incorretamente as atualizações de altura ou operações de "push" levando a fluxos não máximos
- Negligenciar o uso de heurísticas de "gap" e seleção eficiente de nós, resultando em desempenho prático insatisfatório
- Não conseguir manter adequadamente o invariante de pré-fluxo (excesso nos nós e restrições de capacidade nas arestas)
Perguntas frequentes
Qual a diferença entre pré-fluxo e fluxo?
O pré-fluxo permite temporariamente que os nós retenham excesso de fluxo (o fluxo de entrada menos o fluxo de saída pode ser positivo), enquanto o fluxo verdadeiro deve ser conservado em todos os nós, exceto na fonte e no sumidouro. O algoritmo termina quando o pré-fluxo se torna um fluxo válido.
Qual o propósito da função de altura?
As alturas criam uma medida de quase-distância: o fluxo só pode ser empurrado "ladeira abaixo" (de alturas mais altas para mais baixas), evitando ciclos desnecessários e garantindo a terminação. As alturas são aumentadas através do re-rotulamento para criar novos caminhos quando necessário.
O que é a heurística de "gap" e por que ela é importante?
A heurística de "gap" detecta quando nenhum nó tem uma altura em um determinado intervalo, indicando que alguns nós não conseguem alcançar o sumidouro. Esses nós e seu excesso são rapidamente identificados e processados, melhorando significativamente o desempenho prático.
Como o push-relabel se compara na prática ao Edmonds-Karp?
O push-relabel tem uma complexidade de pior caso melhor e geralmente supera o Edmonds-Karp em grandes redes, mas para redes pequenas ou grafos esparsos, o Edmonds-Karp pode ser mais simples de implementar com desempenho competitivo.
Métodos relacionados
Fontes
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
Abrir referência DOICopiado.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
Abrir referência da publicaçãoCopiado.