Algoritmo Push-Relabel
- Introdotto da
- Andrew V. Goldberg and Robert E. Tarjan
- Anno
- 1988
- Tipo
- algorithm
- Famiglia
- Graph Algorithms
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'Algoritmo Push-Relabel, sviluppato da Andrew V. Goldberg e Robert E. Tarjan nel 1988, è un metodo altamente efficiente per il calcolo del flusso massimo nelle reti.
A differenza dei metodi basati sui cammini aumentanti, mantiene un preflusso e utilizza operazioni locali di push (spinta) e globali di relabel (rietichettatura) per dirigere il flusso verso il pozzo (sink), ottenendo una complessità nel caso peggiore superiore.
L’intuizione alla base del metodo
L'algoritmo mantiene un'etichetta di 'altezza' o 'distanza' per ogni nodo e utilizza un preflusso (dove i nodi possono temporaneamente eccedere la domanda del pozzo). Spinge ripetutamente l'eccesso di flusso dai nodi con etichette più alte ai vicini con etichette più basse e rietichetta i nodi per creare cammini verso il pozzo. L'intuizione chiave è che, mantenendo invarianti di altezza e utilizzando strutture dati efficienti, l'algoritmo evita di esplorare ripetutamente l'intero grafo, come devono fare i metodi basati sui cammini aumentanti. L'algoritmo termina quando tutto il preflusso raggiunge il pozzo.
Storia
Goldberg e Tarjan pubblicarono il loro algoritmo push-relabel nel 1988, introducendo un paradigma fondamentalmente diverso per il calcolo del flusso massimo. Il loro algoritmo raggiunse una complessità nel caso peggiore di O(V³), un miglioramento rispetto a O(VE²) di Edmonds-Karp. Nei decenni successivi, sono state sviluppate numerose varianti, tra cui le gap heuristics (Goldberg e Tarjan, 1990), le regole highest-label e le ultime varianti che raggiungono prestazioni empiriche quasi lineari su reti reali.
Quando usarlo
Applicare l'algoritmo push-relabel per il calcolo del flusso massimo in reti grandi e dense dove i metodi basati sui cammini aumentanti diventano inefficienti. È particolarmente efficace per reti con migliaia o milioni di archi. Usarlo quando si necessita di prestazioni garantite in tempo polinomiale e si desidera sfruttare strutture dati moderne. Per reti sparse o scopi didattici, i metodi basati sui cammini aumentanti possono essere più semplici da comprendere e implementare.
Limiti e considerazioni
- Più complesso da comprendere e implementare rispetto ai metodi basati sui cammini aumentanti
- Richiede un'attenta gestione delle strutture dati (liste di scarico, gap heuristics) per prestazioni ottimali
- La complessità nel caso peggiore è comunque superiore ad alcuni algoritmi specializzati per classi di grafi particolari
- Comprensione meno intuitiva del processo di soluzione rispetto ai cammini aumentanti
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Complessità temporale nel caso peggiore superiore: O(V³) o O(V²√E) con gap heuristic
- Altamente efficiente in pratica, specialmente per reti grandi e dense
- Località delle operazioni (push/relabel) consente buone prestazioni della cache
- Adatto a parallelizzazione e implementazioni distribuite
- Molteplici varianti di implementazione per diverse strutture di problemi
Applicazioni
- Routing di rete: calcolo del throughput massimo in reti di comunicazione su larga scala
- Elaborazione di immagini: utilizzo del max-flow per la segmentazione di immagini e applicazioni di matting
- Ottimizzazione delle compagnie aeree: determinazione del flusso massimo di passeggeri attraverso complesse reti di routing
- Analisi della rete elettrica: calcolo della capacità massima di trasmissione di potenza nelle reti elettriche
- Gestione della catena di approvvigionamento: ottimizzazione del flusso di prodotti attraverso reti di distribuzione multi-livello
- Reti biologiche: analisi del flusso massimo nelle reti metaboliche e di interazione proteica
Come funziona
Come funziona
Impostare l'altezza della sorgente al numero di vertici, tutte le altre altezze a zero. Saturare tutti gli archi uscenti dalla sorgente, creando un preflusso iniziale (eccesso nei nodi vicini).
Selezionare ripetutamente un nodo attivo (con eccesso di flusso) e o spingere l'eccesso verso un vicino con altezza inferiore o rietichettare il nodo per aumentarne l'altezza. Utilizzare strategie di selezione efficienti e operazioni di scarico (discharge) per minimizzare le iterazioni.
Continuare finché non rimangono nodi attivi; a quel punto, tutto il preflusso è stato risolto in un flusso massimo dalla sorgente al pozzo.
Errori comuni
- Implementazione errata degli aggiornamenti di altezza o delle operazioni di push che porta a flussi non massimi
- Trascurare l'uso di gap heuristics e la selezione efficiente dei nodi, con conseguenti scarse prestazioni pratiche
- Mancata corretta manutenzione dell'invariante di preflusso (eccesso nei nodi e vincoli di capacità sugli archi)
Domande frequenti
Qual è la differenza tra preflusso e flusso?
Il preflusso consente temporaneamente ai nodi di trattenere un eccesso di flusso (flusso in entrata meno flusso in uscita può essere positivo), mentre il flusso vero e proprio deve essere conservato in tutti i nodi tranne sorgente e pozzo. L'algoritmo termina quando il preflusso diventa un flusso valido.
Qual è lo scopo della funzione di altezza?
Le altezze creano una misura quasi-distanza: il flusso può essere spinto solo in discesa (da altezze maggiori a minori), prevenendo cicli non necessari e garantendo la terminazione. Le altezze vengono aumentate tramite rietichettatura per creare nuovi cammini quando necessario.
Cos'è la gap heuristic e perché è importante?
La gap heuristic rileva quando nessun nodo ha un'altezza in un certo intervallo, indicando che alcuni nodi non possono raggiungere il pozzo. Questi nodi e il loro eccesso vengono identificati ed elaborati rapidamente, migliorando significativamente le prestazioni pratiche.
Come si confronta push-relabel in pratica con Edmonds-Karp?
Push-relabel ha una complessità nel caso peggiore migliore e generalmente supera Edmonds-Karp su reti grandi, ma per reti piccole o grafi sparsi, Edmonds-Karp può essere più semplice da implementare con prestazioni competitive.
Metodi correlati
Fonti
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
Apri il riferimento DOICopiato.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
Apri il riferimento della pubblicazioneCopiato.