Loading AI tools
Da Wikipedia, l'enciclopedia libera
Nella teoria dell'ottimizzazione, il problema del flusso massimo consiste nel trovare, in una rete di flusso con una sola sorgente ed un solo pozzo, un flusso ammissibile che sia massimo.
Il problema del flusso massimo può essere visto come un caso particolare di problemi più complessi sulle reti di flusso, come il problema della circolazione. Il valore massimo di un flusso s-t (ovvero un flusso generato da una sorgente s che si esaurisce in un pozzo t) è equivalente alla capacità minima di un taglio s-t nella medesima rete, come enunciato dal teorema del flusso massimo e taglio minimo.
Il problema del flusso massimo venne formulato per la prima volta nel 1954 da T. E. Harris e F. S. Ross per la semplificazione del modello del flusso del sistema ferroviario sovietico.[1][2][3] Nel 1955, Lester R. Ford, Jr. e Delbert R. Fulkerson pubblicarono il primo algoritmo noto, l'algoritmo di Ford-Fulkerson.[4][5]
Negli anni a venire, vennero ideate varie soluzioni al problema, fra cui le più note sono quelle degli statunitensi Edmonds e Karp (1972) e del sovietico Dinitz (1970).
Sia una rete con rispettivamente sorgente e pozzo di .
La capacità di un arco è una funzione , indicata con o , che rappresenta il massimo flusso che può passare per un arco.
Un flusso è una funzione , indicata con o , soggetta ai due vincoli seguenti:
Il valore di flusso è definito da , dove è la sorgente di . Esso rappresenta l'ammontare di flusso che parte dalla sorgente per arrivare al pozzo.
Il problema del flusso massimo è quello di massimizzare , ovvero, di instradare quanto più flusso possibile da a .
Per comprendere le varie soluzioni del problema è necessario introdurre il concetto di rete residua. Data una rete di flusso ed un flusso su , definiamo la rete residua su rispetto a come segue:
La seguente tabella elenca gli algoritmi più noti per risolvere il problema del flusso massimo.
Metodo | Complessità computazionale | Note |
---|---|---|
Algoritmo di Ford-Fulkerson | La terminazione dell'algoritmo è garantita se tutti i pesi sono razionali, altrimenti è possibile che l'algoritmo non converga al valore massimo. In ogni caso, se l'algoritmo termina, è garantita la correttezza del risultato. | |
Algoritmo di Edmonds-Karp | Una specializzazione dell'algoritmo di Ford–Fulkerson sfruttante la ricerca in ampiezza. | |
Algoritmo di Dinic con flusso bloccante | In ogni fase dell'algoritmo viene costruito un grafo stratificato tramite ricerca in ampiezza sul grafo residuo. Il flusso massimo su un grafo stratificato può essere calcolato in tempo e il massimo numero di fasi è . In reti con capacità unitarie l'algoritmo termina in tempo . | |
Algoritmo MPM (Malhotra, Pramodh-Kumar e Maheshwari)[6] | Ci si riferisca alla pubblicazione originale. | |
Algoritmo di Dinic | La struttura di albero dinamico velocizza la computazione del flusso massimo nel grafo stratificato fino a . | |
Algoritmo push-relabel generico | ||
Algoritmo push-relabel con selezione FIFO | ||
Algoritmo push-relabel con alberi dinamici | ||
Algoritmo KRT (King, Rao, Tarjan)[7] | ||
Algoritmo binario con flusso bloccante[8] | Il valore corrisponde alla capacità massima della rete. | |
Algoritmo di James B Orlin + KRT (King, Rao, Tarjan)[9] | L'algoritmo di Orlin trova il flusso massimo in tempo per mentre KRT risolve il problema in per . |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.