6.6 L'algoritmo di cancellazione dei cicli¶
Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Slide · Esercizi: Flusso di costo minimo · App: Flusso di costo minimo: cancellazione dei cicli e cammini minimi successivi
- Il Teorema 6.7 suggerisce un algoritmo dovuto a Klein: finché \(G(\vet{x})\) ha un ciclo negativo, aumentiamo lungo di esso. Aumentando di \(r(W)\) saturiamo un arco di \(W\), che esce da \(G(\vet{x})\): il ciclo è cancellato.
6.6.1 Trovare un ciclo negativo¶
- Un ciclo negativo di \(G(\vet{x})\) non è necessariamente raggiungibile da un nodo dato. Eseguiamo l'algoritmo di Bellman–Ford del Capitolo 3 da un nuovo nodo \(r\) collegato a ogni nodo da un arco di costo \(0\); la sua prima passata dà etichetta \(0\) a ogni nodo, e scriviamo la tabella da lì.
Proposizione 6.13: Bellman–Ford sulla rete residua
Sia \(d^0(j)=0\) per ogni \(j \in N\) e, per \(k \ge 1\),
-
(a) \(d^k(j)\) è il costo minimo di una passeggiata di \(G(\vet{x})\) con al più \(k\) archi che termina in \(j\), dove la passeggiata senza archi ha costo \(0\).
-
(b) \(G(\vet{x})\) ha un ciclo negativo se e solo se \(d^n \neq d^{n-1}\). In tal caso, se \(d^n(j)<d^{n-1}(j)\), i predecessori letti all'indietro a partire da \(j\), una riga per passata dalla riga \(n\) alla riga \(1\), danno una passeggiata di \(G(\vet{x})\) con \(n\) archi, che termina in \(j\) e contiene un ciclo negativo.
-
(c) Se \(d^k=d^{k-1}\) per qualche \(k \le n\), i potenziali \(\pi_i=-d^k(i)\) soddisfano \(c^x_{ij}-\pi_i+\pi_j \ge 0\) su ogni arco di \(G(\vet{x})\).
Dimostrazione
Sia \(H\) il grafo \(G(\vet{x})\) con l'aggiunta del nodo \(r\) e degli archi \((r,i)\) di costo \(0\), e siano \(D^k\) le etichette di Bellman–Ford da \(r\) in \(H\): \(D^1(i)=0\) per ogni \(i \in N\), e \(D^k(r)=0\) per ogni \(k\).
-
Per induzione su \(k\), \(D^{k+1}(j)=d^k(j)\) per \(j \in N\): le ricorsioni coincidono, e l'arco \((r,j)\) offre \(D^k(r)+0=0\), che non abbassa mai il minimo perché \(d^{k-1}(j) \le d^0(j)=0\). Una passeggiata da \(r\) con \(k+1\) archi è un arco \((r,i)\) seguito da una passeggiata di \(G(\vet{x})\) con \(k\) archi a partire da \(i\): questo dimostra (a).
-
In \(H\) ogni nodo è raggiungibile da \(r\), e i cicli sono quelli di \(G(\vet{x})\). Per il Teorema «rilevazione di un ciclo negativo» del Capitolo 3, applicato agli \(n+1\) nodi di \(H\), esiste un ciclo negativo se e solo se \(D^{n+1} \neq D^{n}\), cioè \(d^n \neq d^{n-1}\). La passeggiata da \(r\) con \(n+1\) archi letta nelle righe \(n+1,\dots,2\) di \(H\), che sono le nostre righe \(n,\dots,1\), contiene un ciclo negativo; senza il suo primo arco \((r,\cdot)\) è una passeggiata di \(G(\vet{x})\) con \(n\) archi, e il ciclo non contiene \(r\). Questo dimostra (b).
-
Se \(d^k=d^{k-1}\), la passata successiva ripete le etichette: \(d^k(j) \le d^k(i)+c^x_{ij}\) per ogni arco \((i,j)\) di \(G(\vet{x})\), che è (c) con \(\pi=-d^k\). □
-
Regole di questo capitolo. Gli archi di \(G(\vet{x})\) sono esaminati in ordine lessicografico; come nel Capitolo 3, i pareggi nel minimo vanno alla coda più piccola e un predecessore cambia solo quando l'etichetta diminuisce strettamente. Se \(d^n \neq d^{n-1}\), \(j\) è il nodo più piccolo con \(d^n(j)<d^{n-1}(j)\), e il ciclo è il tratto della passeggiata tra le due occorrenze del primo nodo incontrato due volte, leggendo la passeggiata dal suo primo nodo.
-
All'arresto i potenziali \(\pi_i=-d^k(i)\) sono traslati in modo che \(\pi_n=0\).
6.6.2 L'algoritmo¶
Algoritmo: Algoritmo di cancellazione dei cicli
STOP: illimitato.STOP: inammissibile.STOP: \(\vet{x}\) è ottimo, con \(\vet{\pi}=-d^k\).-
Il test del Passo 0 è la Proposizione 6.13 applicata al grafo degli archi con \(u_{ij}=+\infty\) e ai loro costi. Quando il test non scatta, ogni ciclo negativo di \(G(\vet{x})\) ha un arco di capacità residua finita (dimostrazione della Proposizione 6.8), quindi \(r(W)<+\infty\) nel Passo 2.
-
Nel Passo 0 va bene qualsiasi flusso ammissibile; il flusso massimo è un modo per trovarlo.
Teorema 6.14: correttezza della cancellazione dei cicli
Siano interi i bilanci, le capacità e i costi, con capacità eventualmente \(+\infty\), e l'algoritmo superi il Passo 0 con un flusso ammissibile intero \(\vet{x}^0\). Allora ogni flusso dell'algoritmo è intero e ammissibile, ogni iterazione abbassa il costo di almeno \(1\), e l'algoritmo si ferma dopo al più \(\vet{c}'\vet{x}^0-z(\mathrm{MCF})\) iterazioni con un flusso ottimo.
Dimostrazione
Per la Proposizione 6.8 il modello è limitato, quindi ha un valore ottimo \(z(\mathrm{MCF})\).
-
Se \(\vet{x}\) è intero, le capacità residue sono interi positivi o \(+\infty\), e \(r(W)\) è un intero positivo, perché \(r(W)<+\infty\). Per la Proposizione 6.3 il nuovo flusso è ammissibile e intero.
-
Il costo cambia di \(r(W)\,c(W)\), dove \(r(W) \ge 1\) e \(c(W) \le -1\) sono interi: diminuisce di almeno \(1\).
-
Il costo parte da \(\vet{c}'\vet{x}^0\) e non scende mai sotto \(z(\mathrm{MCF})\), quindi le iterazioni sono al più \(\vet{c}'\vet{x}^0-z(\mathrm{MCF})\). All'arresto \(G(\vet{x})\) non ha cicli negativi (Proposizione 6.13), e \(\vet{x}\) è ottimo per il Teorema 6.7. □
-
Tempo di esecuzione. \(G(\vet{x})\) ha al più \(2m\) archi, quindi il Passo 1 richiede tempo \(O(n\,m)\). Con capacità finite, \(U=\max u_{ij}\) e \(K=\max |c_{ij}|\), ogni flusso costa tra \(-mKU\) e \(mKU\): al più \(2mKU\) iterazioni, e tempo \(O(n\,m^2 K U)\).
-
Il limite dipende dalla grandezza dei numeri \(K\) e \(U\), non solo da \(n\) e \(m\): è un limite pseudopolinomiale.
6.6.3 La cancellazione dei cicli sulla rete di riferimento¶
-
Sulla rete di riferimento il Passo 0 restituisce \(\tilde{\vet{x}}\) (Esempio 6.5), e l'algoritmo si ferma alla prima esecuzione di Bellman–Ford. Per vederlo all'opera partiamo dal flusso più costoso \(\vet{x}^0\) dell'Esempio 6.1, di costo \(80\).
-
Nelle tabelle ogni riga è una passata \(k\); accanto a un'etichetta che è diminuita, tra parentesi, il suo nuovo predecessore. Le caselle lette all'indietro per trovare la passeggiata sono in grassetto.
Esempio 6.6: cancellazione dei cicli dal flusso più costoso
Iterazione 1
\(G(\vet{x}^0)\) è la rete residua dell'Esempio 6.1. Bellman–Ford dà:
Tutte le etichette diminuiscono nella passata \(6\), quindi \(j=1\). Leggendo all'indietro: la riga \(6\) dà \(2\), la riga \(5\) per il nodo \(2\) dà \(4\), poi \(3\), \(5\), \(4\), \(6\). La passeggiata \(6,4,5,3,4,2,1\) incontra due volte il nodo \(4\): \(W=4,5,3,4\), con \(c(W)=-11\) e \(r(W)=1\). Il nuovo flusso è \(\vet{x}^1=(1,4,4,1,3,0,3,2,1)\), di costo \(69\).
Iterazione 2
Gli archi di \(W\) cambiano: \((4,5)\) e \((5,3)\) perdono un'unità, \((3,4)\) scompare, e compaiono gli archi in avanti \((3,5)\), \((5,4)\). \(G(\vet{x}^1)\) è:
| arco \((i,j)\) | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(x^1_{ij}\) | \(1\) | \(4\) | \(4\) | \(1\) | \(3\) | \(0\) | \(3\) | \(2\) | \(1\) |
| in avanti \((i,j)\): \(r,c\) | \(3,2\) | – | – | \(1,2\) | \(1,3\) | \(3,3\) | \(2,5\) | \(1,5\) | \(1,3\) |
| all'indietro \((j,i)\): \(r,c\) | \(1,-2\) | \(4,-2\) | \(4,-5\) | \(1,-2\) | \(3,-3\) | – | \(3,-5\) | \(2,-5\) | \(1,-3\) |
Ancora \(j=1\), e la passeggiata è \(6,4,5,6,4,2,1\): \(W=6,4,5,6\), formato dagli archi all'indietro di \((4,6)\) e \((5,4)\) e dall'arco in avanti \((5,6)\), con \(c(W)=-5-5+3=-7\) e \(r(W)=\min\{3,2,1\}=1\). Il nuovo flusso è \(\vet{x}^2=(1,4,4,1,3,0,2,1,2)\), di costo \(62\).
Iterazione 3
In \(G(\vet{x}^2)\) l'arco \((5,6)\) è saturo: resta solo il suo arco all'indietro \((6,5)\), con \(r=2\); gli archi \((6,4)\), \((4,5)\) hanno capacità residue \(2\) e \(1\), gli archi in avanti \((4,6)\), \((5,4)\) capacità residue \(3\) e \(2\). Bellman–Ford dà:
Solo il nodo \(3\) diminuisce nella passata \(6\): \(j=3\), e la passeggiata è \(6,4,5,3,1,2,3\). Il nodo \(3\) compare due volte: \(W=3,1,2,3\), formato dall'arco all'indietro di \((1,3)\), dall'arco in avanti \((1,2)\) e dall'arco all'indietro di \((3,2)\), con \(c(W)=-2+2-2=-2\) e \(r(W)=\min\{4,3,1\}=1\). Il nuovo flusso è \(\vet{x}^3=(2,3,4,0,3,0,2,1,2)=\tilde{\vet{x}}\), di costo \(60\).
Iterazione 4
Bellman–Ford su \(G(\tilde{\vet{x}})\) ripete le righe \(0\)–\(5\) dell'iterazione \(3\), e nella passata \(6\) nessuna etichetta diminuisce: \(d^6=d^5=(-15,-13,-13,-5,-10,0)\). L'algoritmo si ferma con \(\tilde{\vet{x}}\), certificato da \(\vet{\pi}=-d^6=(15,13,13,5,10,0)\), già normalizzati con \(\pi_6=0\): i potenziali del Capitolo 4.
-
In sintesi:
iterazione costo di \(\vet{x}\) \(j\) ciclo \(W\) \(c(W)\) \(r(W)\) \(1\) \(80\) \(1\) \(4,5,3,4\) \(-11\) \(1\) \(2\) \(69\) \(1\) \(6,4,5,6\) \(-7\) \(1\) \(3\) \(62\) \(3\) \(3,1,2,3\) \(-2\) \(1\) \(4\) \(60\) – nessun ciclo negativo – – -
Il limite del Teorema 6.14 ammette \(80-60=20\) iterazioni; ne bastano tre. I tre cicli sono quelli della scomposizione dell'Esempio 6.2, trovati in un ordine diverso.
L'algoritmo di cancellazione dei cicli parte da un flusso ammissibile e cancella i cicli negativi di \(G(\vet{x})\), trovati da Bellman–Ford a partire da etichette tutte uguali a \(0\). Con dati interi ogni cancellazione abbassa il costo di almeno \(1\); all'arresto le etichette danno i potenziali che certificano il flusso ottimo.