Algoritmo di Ford-Fulkerson
- Introdotto da
- Lester R. Ford and Delbert R. Fulkerson
- Anno
- 1956
- 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 di Ford-Fulkerson, sviluppato da Lester R. Ford e Delbert R. Fulkerson nel 1956, è un metodo fondamentale per calcolare il flusso massimo in una rete di flusso.
Trova la quantità massima di flusso che può essere inviata da una sorgente a un pozzo attraverso un grafo orientato con vincoli di capacità sugli archi.
L’intuizione alla base del metodo
L'algoritmo funziona trovando ripetutamente percorsi aumentanti dalla sorgente al pozzo attraverso la rete residua, dove ogni arco ha capacità residua. Ogni percorso contribuisce con un flusso aggiuntivo pari alla sua capacità di collo di bottiglia (l'arco con la capacità residua minima sul percorso). Il processo continua finché non esistono più percorsi aumentanti, momento in cui si raggiunge il flusso massimo. L'intuizione chiave è il teorema del flusso massimo-taglio minimo: il flusso massimo è uguale alla capacità del taglio minimo nella rete.
Storia
Ford e Fulkerson introdussero il problema del flusso massimo e il loro lavoro seminale nel 1956. Il lavoro fu rivoluzionario, stabilendo sia un metodo algoritmico che il celebrato teorema del flusso massimo-taglio minimo. Edmonds e Karp (1972) migliorarono la complessità nel caso peggiore utilizzando la ricerca in ampiezza per la selezione del percorso. Successivi progressi da parte di Dinic, Karzanov e altri portarono ad algoritmi ancora più veloci, ma il metodo di Ford-Fulkerson rimane un algoritmo classico e pedagogicamente valido in informatica.
Quando usarlo
Applicare l'algoritmo di Ford-Fulkerson per trovare il flusso massimo in reti di flusso orientate o non orientate con capacità intere positive. Funziona bene per reti di piccole e medie dimensioni e fornisce una comprensione intuitiva dei concetti di flusso di rete. Per reti molto grandi o quando sono richiesti flussi interi, considerare l'algoritmo di Edmonds-Karp (utilizzando BFS) o l'algoritmo di Dinic per migliori prestazioni nel caso peggiore. Usarlo quando la comprensione del comportamento dell'algoritmo è importante quanto la velocità.
Limiti e considerazioni
- La complessità temporale dipende dai valori di capacità (non polinomiale in generale; può essere esponenziale con capacità irrazionali)
- Potrebbe non terminare se le capacità sono irrazionali (richiede un'implementazione attenta con aritmetica razionale)
- Meno efficiente di algoritmi specializzati come Edmonds-Karp o Dinic su reti di grandi dimensioni
- Sensibile all'ordine di selezione dei percorsi aumentanti
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Approccio semplice e intuitivo basato sui percorsi aumentanti
- Soluzione ottimale garantita quando le capacità sono razionali o intere
- Efficiente per reti con piccole capacità intere
- Costituisce il fondamento teorico per la comprensione della dualità flusso massimo-taglio minimo
- Funziona sia con grafi orientati che non orientati
Applicazioni
- Routing di rete: massimizzare il throughput dei dati da sorgente a destinazione nelle reti di comunicazione
- Reti di trasporto: determinare la capacità massima di carico tra città considerando vincoli stradali e ferroviari
- Matching bipartito: trovare matching massimi in grafi bipartiti costruendo reti di flusso
- Segmentazione di immagini: utilizzo di algoritmi di flusso massimo per partizionare immagini in primo piano e sfondo
- Pianificazione aerea: ottimizzare il routing degli aeromobili per massimizzare il flusso di passeggeri attraverso reti hub-and-spoke
- Analisi proteica: calcolo del flusso massimo in reti biologiche per comprendere i percorsi di interazione
Come funziona
Come funziona
Inizializzare il grafo residuo con capacità uguali alle capacità degli archi originali e flusso zero su tutti gli archi.
Trovare un percorso aumentante dalla sorgente al pozzo nel grafo residuo utilizzando la ricerca in profondità o in ampiezza, calcolare la capacità minima lungo il percorso e aggiungere questo flusso a tutti gli archi sul percorso riducendo le loro capacità residue.
Ripetere l'aumento finché non esiste più un percorso aumentante nel grafo residuo; il flusso totale accumulato è il flusso massimo.
Errori comuni
- Scegliere percorsi aumentanti errati che portano a una convergenza lenta o a risultati errati
- Mancata corretta aggiornamento delle capacità residue o aggiunta di archi inversi per annullare il flusso
- Utilizzo di divisione intera o aritmetica in virgola mobile quando è richiesta aritmetica esatta per la correttezza
Domande frequenti
Cos'è il teorema del flusso massimo-taglio minimo?
Il teorema afferma che il flusso massimo da sorgente a pozzo è uguale alla capacità minima di qualsiasi taglio che separa la sorgente dal pozzo. Questo fornisce sia un'intuizione teorica che un metodo di verifica per gli algoritmi di flusso.
Perché l'algoritmo a volte converge lentamente?
Con selezioni di percorso sfortunate, l'algoritmo può aumentare di una sola unità di flusso per iterazione, anche quando sono possibili aumenti maggiori. L'uso della ricerca in ampiezza (Edmonds-Karp) garantisce una convergenza in tempo polinomiale.
Come gestisce l'algoritmo gli archi non orientati?
Sostituire ogni arco non orientato con due archi orientati in direzioni opposte, entrambi con la stessa capacità. L'algoritmo trova quindi il flusso sulla rete orientata.
Qual è la differenza tra flusso su un arco e capacità residua?
Il flusso su un arco rappresenta la quantità di materiale inviato lungo di esso, mentre la capacità residua è la capacità rimanente disponibile. La capacità residua diminuisce all'aumentare del flusso, e gli archi inversi tracciano la capacità di annullare il flusso.
Metodi correlati
Fonti
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
Apri il riferimento DOICopiato.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Copiato.