Algoritmi e Strutture di Dati (3 Ed.) Algoritmo dei tre indiani

Algoritmi e Strutture di Dati (3a Ed.)
Algoritmo dei tre indiani
Alan Bertossi, Alberto Montresor
Vediamo a grandi linee un algoritmo proposto da Kumar, Malhotra e Maheswari (1978) come raffinamento di altri algoritmi precedenti, che è noto come l’algoritmo dei tre indiani e richiede O(n3 )
tempo. Questo algoritmo si basa sulla strategia di aumentare ripetutamente lungo tutti i cammini aumentanti più corti, cioè aventi il minimo numero di archi. Il procedimento ha inizio con flusso f nullo e
consta delle seguenti tre fasi, che vengono iterate:
(1) si costruisce un grafo residuo R, semplificato in modo che sia formato da tutti e soli i cammini
aumentanti per f comprendenti il minimo numero k archi;
(2) si saturano in una sola volta tutti i cammini di R, in modo da non avere più cammini aumentanti
per f con k archi, determinando un flusso saturante g di valore |g| per R;
(3) si aggiorna f sommando ad esso il flusso saturante g.
Come sarà dimostrato nel seguito, le tre fasi dell’algoritmo sono iterate per O(n) volte, in quanto il
numero k di archi dei cammini minimi di R cresce ad ogni iterazione ed un cammino non può avere più
di n − 1 archi. Poiché le fasi (2) e (3) richiedono O(n2 ) tempo, mentre la fase (1) ne richiede O(m), la
complessità dell’algoritmo è O(n3 ). La procedura kmn() descrive l’algoritmo dei 3 indiani.
integer[ ][ ] kmn(G RAPH G, N ODE s, N ODE p, integer[ ][ ] c)
N ODE u, v
G RAPH R ← Graph()
integer[ ][ ] r ← new integer[ ][ ]
integer[ ][ ] f ← new integer[ ][ ]
integer[ ][ ] g ← new integer[ ][ ]
foreach u, v ∈ G.V() do f [u, v] ← 0
boolean stop ← false
while not stop do
residuo(G, s, p, c, f, R, r)
satura(R, s, p, r, g)
foreach u, v ∈ G.V() do f [u, v] ← f [u, v] + g[u, v]
if ∀u, v ∈ G.V() : g[u, v] = 0 then stop ← true
return f
% Indici nodi
% Grafo residuo
% Capacità residua
% Flusso parziale
% Flusso da cammino aumentante
% Inizializza un flusso nullo
% f =f +g
Le procedure residuo() e satura() sono usate per realizzare le prime due fasi, mentre l’inizializzazione di f al flusso nullo di valore |f | = 0 e la sommatoria del flusso aumentante g al flusso f sono
semplicemente realizzate con due cicli foreach, ripresi da maxFlow().
La procedura residuo() costruisce in O(m) tempo il grafo residuo R = (V, Er ) con una BFS modificata, dove un arco (u, v) viene aggiunto ad Er con capacità r(u, v) = c(u, v) − f (u, v) per ogni
arco (u, v) ∈ E o (v, u) ∈ E tale che r(u, v) > 0. Si assume che G ed R siano rappresentati con gli
insiemi di adiacenza sia degli archi uscenti che degli archi entranti di ciascun nodo. Durante la visita, è
assegnata ad ogni nodo u la sua “distanza minima” du dalla sorgente s, intesa come il minimo numero
di archi in un cammino tra s e u. Il grafo R è semplificato, con un’altra eventuale passata e sempre
in O(m) tempo, per eliminare tutti quei nodi e quegli archi che non risiedono sui cammini aumentanti
più corti da s a p. Infatti, si possono eliminare tutti i nodi v diversi da p con dv ≥ dp , insieme a tutti
gli archi incidenti in essi. Inoltre, poiché un cammino più corto può contenere solo archi da un nodo
u a distanza du ad un altro nodo v a distanza dv = du + 1, si può eliminare ogni arco (u, v) tale che
c
Alan
Bertossi, Alberto Montresor. Algoritmi e Strutture di Dati.
1 (3)
(3)
(2)
1
(3)
(1)
(1)
(3)
3
2
4
2 (2)
6
5
(2)
3
2
1 (2)
1
1 (3)
(2)
4
1 (2)
a)
5
2 (2)
3
1 (1)
1 (1)
1 (1)
1 (2)
6
b)
3
2
1
1 (3)
2
1 (2)
6
1 (1)
1 (1)
1
1 (1)
4
4
1 (1)
6
5
d)
c)
3 (3)
2 (2)
1
3 (3)
3
2
0 (1)
6
1 (1)
4
2 (2)
3 (3)
5
2 (2)
e)
Figura 1: a) Un grafo G, con capacità degli archi indicate tra parentesi. b) Il grafo residuo R semplificato
alla prima iterazione, con un flusso saturante g e le capacità residue tra parentesi. c)-d) R alla seconda e
terza iterazione, con un flusso saturante g. e) Il flusso massimo f per G.
dv ≤ du . Il grafo R così semplificato è aciclico e “stratificato”, cioè ogni arco (u, v) unisce due nodi
tali che dv = du + 1, ed ogni nodo u ∈ V − {s, p} ha distanza du tale che 0 = ds < du < dp . Inoltre, R
può essere ulteriormente semplificato con un’altra passata, che parte dal pozzo p ed esamina “a ritroso”
gli archi, marcando così i nodi dai quali si può raggiungere p, e cancellando successivamente tutti i nodi
non marcati, insieme agli archi incidenti. Dopo quest’ultima semplificazione, ogni nodo di R sta su un
cammino minimo tra s e p, se esiste un tale cammino. In altri termini, R contiene tutti e soli i cammini
aumentanti per f di lunghezza minima k = dp .
Una volta costruito il grafo residuo semplificato R in O(m) tempo, la procedura satura() cerca un
flusso saturante per esso, cioè un flusso g che saturi tutti i cammini presenti in R. Un arco è saturo
se il flusso che lo attraversa è pari alla capacità dell’arco, ed un cammino di R è saturo se contiene
almeno un arco saturo. Un flusso saturante per R non è detto che sia massimo per R (si potrebbe infatti
aumentare percorrendo qualche arco nel verso opposto all’orientamento), ma garantisce comunque che
in futuro non potranno più essere considerati cammini aumentanti di lunghezza k = dp . Infatti, sia G0r
il grafo residuo all’iterazione successiva, con distanze d0 . Ciascun arco (u, v) di R ha dv = du + 1,
mentre ciascun arco di G0r o è un arco di R o è un arco di R con orientamento opposto. Ma allora ogni
arco in G0r ha dv ≤ du + 1, e quindi d0p ≥ dp . Se per assurdo fosse d0p = dp , allora esisterebbe un
cammino minimo da s a p in R che non è stato saturato tale che ogni arco (u, v) ha dv = du + 1. Ma
ciò contraddice il fatto che almeno un arco di ogni cammino in R è saturato e quindi non compare in
G0r . Pertanto, d0p > dp e in futuro non potranno più essere considerati cammini aumentanti di lunghezza
k ≤ dp .
Esempio 1 (Flusso saturante). La Fig. 1(a) mostra un grafo G con sorgente s = 1, pozzo p = 6, e
capacità degli archi indicate tra parentesi. Alla prima iterazione il flusso f è nullo e il grafo residuo
semplificato R, che contiene tutti i cammini aumentanti di lunghezza minima (uguale a 3), è mostrato
c
Alan
Bertossi, Alberto Montresor. Algoritmi e Strutture di Dati.
nella Fig. 1(b), insieme ad un flusso saturante g per R. Le componenti del flusso g sono indicate senza
parentesi, seguite dalle capacità residue di R tra parentesi. Alla seconda iterazione, il flusso f è uguale al
flusso saturante g trovato alla prima iterazione, ed il grafo residuo semplificato R (che contiene cammini
lunghi 4) è mostrato nella Fig. 1(c), insieme a un flusso saturante. Il grafo R alla terza iterazione (con
cammini lunghi 5) ed un flusso saturante sono illustrati nella Fig. 1(d). Infine, la Fig. 1(e) mostra il
grafo G con il flusso massimo f così trovato. Un taglio minimo si può individuare dal grafo residuo R
per f ponendo in S la sorgente s e tutti i nodi raggiungibili da s con archi di R (nessuno nell’esempio
di Fig. 1e), perché f satura entrambi gli archi uscenti da 1 in G), ottenendo così S = {1} e P =
{2, 3, 4, 5, 6}.
Per trovare un flusso saturante g per R, si definisce per ogni nodo u di R la sua portata, ovvero
l’ammontare massimo di flusso che può attraversare il nodo u, come il minimo tra la somma delle
capacità residue degli archi entranti in u e quella degli archi uscenti da u:
)
(
X
X
r(u, v)
portata[u] = min
r(v, u),
v
v
dove, per applicare la definizione anche ad s ed a p, si può assumere di avere un arco “fittizio di ritorno”
(p, s) con capacità infinita.
Il vettore portata può essere calcolato in O(m) tempo. Selezionando poi in O(n) tempo il nodo
u con portata minima, si è sicuri di poter trasmettere portata[u] unità di flusso da s a p in R con una
opportuna procedura instrada(). Questa procedura, partendo dal nodo u, modifica il flusso g, aggiungendovi portata[u] unità di flusso che sono instradate da u verso p ed a ritroso da u verso s, ed aggiorna
le portate dei nodi. Effettuato l’instradamento, con una semplice procedura aggiorna() sono eliminati
i nodi diversi da s con portata nulla, tra i quali c’è almeno u, e gli archi incidenti in essi. Se il flusso
g non è saturante, cioè la portata della sorgente è positiva, allora si instradano altre unità di flusso che
sono sommate al flusso g. Il procedimento è iterato finché il flusso g non è saturante.
satura(G RAPH R, N ODE s, N ODE p, integer[ ][ ] r, integer[ ][ ] g)
N ODE u, v
integer[ ] portata ← new integer[1 . . . R.n]
foreach u, v ∈ V do g[u, v] ← 0
foreach u ∈ R.V() do P
P
portata[u] ← min{ v r[v, u], v r[u, v]}
% Indici nodi
% Vettore portata
% Inizializza g al flusso nullo
while portata[s] > 0 do
seleziona il nodo u con portata[u] minima
instrada(R, u, portata, g)
aggiorna(R, portata, g)
La complessità della procedura satura() è determinata da quella del ciclo while, che a sua volta dipende da un’accorta realizzazione della procedura instrada(). Questa procedura aggiunge x = portata[u]
unità di flusso a g, instradandole da u verso p ed a ritroso da u verso s, secondo una visita BFS. Ad ogni
chiamata, esamina ciascun nodo v di R al più una volta allontanandosi progressivamente dal nodo u nel
grafo stratificato. In questo modo, quando è considerato il nodo v, il flusso sugli archi entranti in v (se v
sta in un cammino tra u e p) oppure su quelli uscenti da v (se v sta tra s ed u) è già stato tutto instradato.
c
Alan
Bertossi, Alberto Montresor. Algoritmi e Strutture di Dati.
instrada(G RAPH R, N ODE u, integer[ ] portata, integer[ ][ ] g)
% Instrada portata[u] unità di flusso da u a p, modificando g
% L’instradamento da s a u non è mostrato in quanto simmetrico
Q UEUE Q ← Queue()
Q.enqueue(u)
integer[ ] esci ← new integer[1 . . . R.n]
foreach v ∈ R.V() do esci[v] ← 0
esci[u] ← portata[u]
portata[u] ← 0
while not Q.isEmpty() do
integer v ← Q.dequeue()
while esci[v] > 0 do
considera un arco (v, w) uscente da R
integer M ← min{r[v, w], esci[v]}
r[v, w] ← r[v, w] − M
if r[v, w] = 0 then cancella (v, w) da R
esci[v] ← esci[v] − M
esci[w] ← esci[w] + M
g[v, w] = g[v, w] + M
g[w, v] = −g[v, w]
portata[w] = portata[w] − M
Q.enqueue(w)
Per semplicità, nella procedura instrada() non è mostrato tutto l’instradamento, ma solo quello da u
verso p poiché l’altro è perfettamente analogo. Durante la visita, instrada() calcola e aggiorna la quantità
esci[j], che denota quante unità di flusso devono uscire dal nodo v, ed aggiorna le portate dei nodi.
Il tempo richiesto della procedura satura() dipende dal numero di ripetizioni del ciclo while, ove
è richiamata la instrada(). Poiché ad ogni iterazione è eliminato almeno un nodo saturo (con portata
divenuta nulla), il numero di iterazioni è O(n). Ogni arco di R può essere cancellato da aggiorna()
oppure saturato e cancellato da instrada(), ma una sola volta, oppure può essere riempito con una certa
quantità di flusso senza essere saturato, ma solo una volta per ciascuna iterazione e per non più di un arco
per nodo. Inoltre, non sono mai esaminati tutti gli archi uscenti da v, ma soltanto i primi yv , dei quali i
primi yv − 1 sono saturati e cancellati, mentre l’yv -esimo è eventualmente riempito ma non saturato.
Pertanto, le saturazioni e cancellazioni di archi sono in totale O(m), mentre i riempimenti senza
saturazione sono in totale O(n2 ), ed il tempo richiesto da satura() è così O(n2 ). Ne segue che ciascuna
iterazione della procedura kmn() prende O(n2 ) tempo, dovuto alla satura(). Poiché kmn() effettua al più
n − 1 iterazioni in ciascuna delle quali cerca un flusso saturante, la complessità dell’algoritmo dei tre
indiani per trovare il flusso massimo risulta essere O(n3 ).
c
Alan
Bertossi, Alberto Montresor. Algoritmi e Strutture di Dati.