6.6 L'algoritmo di annullamento del ciclo¶
Parte 3 · Flussi · Capitolo 6 · Capitolo 6: Flusso di costo minimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso di costo minimo
- Teorema 6.7 suggerisce un algoritmo dovuto a Klein: mentre \(G(\vet{x})\) ha ciclo negativo, aumenta lungo di esso. L'aumento di \(r(W)\) satura un arco di \(W\), che lascia \(G(\vet{x})\): il ciclo è annullato.
6.6.1 Trovare un ciclo negativo¶
- Non è necessario che un ciclo negativo di \(G(\vet{x})\) sia raggiungibile da un dato nodo. Eseguiamo l'algoritmo Bellman–Ford di Capitolo 3 da un nuovo nodo \(r\) unito ad ogni nodo da un arco di costo \(0\); il suo primo passaggio assegna l'etichetta \(0\) a ogni nodo e noi scrivi 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 un cammino in \(G(\vet{x})\) con al massimo \(k\) archi che termina a \(j\), il cammino senza archi con 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 leggono all'indietro da \(j\), una riga per passaggio dalla riga \(n\) alla riga \(1\), danno una passeggiata di \(G(\vet{x})\) con Archi \(n\), che terminano in \(j\), che contengono un ciclo negativo.
-
(c) Se \(d^k=d^{k-1}\) per alcuni \(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\) \(G(\vet{x})\) più il nodo \(r\) e gli archi \((r,i)\) di costo \(0\), e siano \(D^k\) le etichette di Bellman–Ford da \(r\) a \(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 da \(d^{k-1}(j) \le d^0(j)=0\). Una passeggiata da \(r\) con gli archi \(k+1\) è un arco \((r,i)\) seguito da un cammino in \(G(\vet{x})\) con archi \(k\) da \(i\): questo dimostra (a).
-
In \(H\) ogni nodo è raggiungibile da \(r\), ed i cicli sono quelli di \(G(\vet{x})\). Per il Teorema «rilevazione di a ciclo negativo» del Capitolo 3, applicato ai nodi \(n+1\) di \(H\), esiste un ciclo negativo se e solo se \(D^{n+1} \neq D^{n}\), cioè \(d^n \neq d^{n-1}\). La cammino da \(r\) con gli archi \(n+1\) letti in righe \(n+1,\dots,2\) di \(H\), quali sono le nostre righe \(n,\dots,1\), contiene un ciclo negativo; senza il suo primo arco \((r,\cdot)\) è una passeggiata \(G(\vet{x})\) con archi \(n\) e il ciclo non contiene \(r\). Ciò 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})\) vengono scanditi in ordine lessicografo; come nel capitolo 3, i legami nel minimo vanno alla coda più piccola e un predecessore cambia solo quando l'etichetta diminuisce rigorosamente. Se \(d^n \neq d^{n-1}\), \(j\) è il nodo più piccolo con \(d^n(j)<d^{n-1}(j)\) e il ciclo è la parte del percorso tra le due occorrenze del primo nodo si sono incontrate due volte, leggendo il cammino dal suo primo nodo.
-
Alla fermata i potenziali \(\pi_i=-d^k(i)\) vengono spostati in modo che \(\pi_n=0\).
6.6.2 L'algoritmo¶
Algoritmo: Algoritmo di annullamento ciclo
STOP: illimitato.STOP: impossibile.STOP: \(\vet{x}\) è ottimale, con \(\vet{\pi}=-d^k\).-
Il test del Passo 0 è Proposizione 6.13 applicato al grafo degli archi con \(u_{ij}=+\infty\) e relativi costi. Quando fallisce, ogni ciclo negativo di \(G(\vet{x})\) ha un arco di residuo finito capacità (prova di Proposizione 6.8), quindi \(r(W)<+\infty\) nel passaggio 2.
-
Qualsiasi flusso fattibile può essere utilizzato nel passaggio 0; il flusso massimo è un modo per trovarlo.
Teorema 6.14: correttezza annullamento ciclo
Siano interi i saldi, le capacità ed i costi, con capacità possibilmente \(+\infty\), e si lasci che l'algoritmo superare il passo 0 con un flusso ammissibile intero \(\vet{x}^0\). Allora ogni flusso dell'algoritmo è intero e ammissibile, ogni l'iterazione riduce il costo almeno di \(1\) e l'algoritmo si ferma al massimo dopo \(\vet{c}'\vet{x}^0-z(\mathrm{MCF})\) iterazioni con un flusso ottimale.
Dimostrazione
Con Proposizione 6.8 il modello è limitato, quindi ha un valore ottimale \(z(\mathrm{MCF})\).
-
Se \(\vet{x}\) è un numero intero, le capacità residue sono numeri interi positivi o \(+\infty\) e \(r(W)\) è un valore positivo intero, poiché \(r(W)<+\infty\). Per Proposizione 6.3 il nuovo flusso è fattibile e intero.
-
Il costo varia di \(r(W)\,c(W)\), dove \(r(W) \ge 1\) e \(c(W) \le -1\) sono numeri interi: diminuisce di almeno \(1\).
-
Il costo parte da \(\vet{c}'\vet{x}^0\) e non scende mai sotto \(z(\mathrm{MCF})\), quindi ci sono al massimo Iterazioni \(\vet{c}'\vet{x}^0-z(\mathrm{MCF})\). Alla fermata \(G(\vet{x})\) non ha ciclo negativo (Proposizione 6.13) e \(\vet{x}\) è ottimale per Teorema 6.7. □
-
Tempo di esecuzione. \(G(\vet{x})\) ha al massimo archi \(2m\), quindi il passaggio 1 richiede tempo \(O(n\,m)\). Con finito capacità, \(U=\max u_{ij}\) e \(K=\max |c_{ij}|\), ogni flusso costa tra \(-mKU\) e \(mKU\): al massimo \(2mKU\) iterazioni e tempo \(O(n\,m^2 K U)\).
-
Il limite dipende dalla dimensione dei numeri \(K\) e \(U\), non solo da \(n\) e \(m\): è un Limite pseudo-polinomio.
6.6.3 Annullamento ciclo sulla rete di riferimento¶
-
Sulla rete di riferimento, il Passaggio 0 restituisce \(\tilde{\vet{x}}\) (Esempio 6.5) e l'algoritmo termina alla prima esecuzione di Bellman–Ford. Per osservarne il funzionamento, partiamo dal flusso di costo massimo \(\vet{x}^0\) di Esempio 6.1, di costo \(80\).
-
Nelle tabelle ogni riga è una tessera \(k\); accanto a un'etichetta diminuita, il suo nuovo predecessore tra parentesi. Le etichette lette in ordine inverso per ricostruire il cammino sono in grassetto.
Esempio 6.6: ciclo di annullamento dal flusso più costoso
Iterazione 1
\(G(\vet{x}^0)\) è la rete residua di Esempio 6.1. Bellman–Ford fornisce:
Tutte le etichette diminuiscono nel passaggio \(6\), quindi \(j=1\). Leggendo all'indietro: la riga \(6\) dà \(2\), la riga \(5\) per il nodo \(2\) dà \(4\), quindi \(3\), \(5\), \(4\), \(6\). La passeggiata \(6,4,5,3,4,2,1\) incontra il nodo \(4\) due volte: \(W=4,5,3,4\), con \(c(W)=-11\) e \(r(W)=1\). Il 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 gli archi in avanti Vengono visualizzati \((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\) |
| avanti \((i,j)\): \(r,c\) | \(3,2\) | – | – | \(1,2\) | \(1,3\) | \(3,3\) | \(2,5\) | \(1,5\) | \(1,3\) |
| 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 il cammino è \(6,4,5,6,4,2,1\): \(W=6,4,5,6\), formato dagli archi all'indietro di \((4,6)\) e \((5,4)\) e da l'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: rimane solo il suo arco all'indietro \((6,5)\), con \(r=2\), e gli archi \((6,4)\), \((4,5)\) hanno capacità residue \(2\) e \(1\), gli archi in avanti \((4,6)\), \((5,4)\) residui capacità \(3\) e \(2\). Bellman–Ford fornisce:
Solo il nodo \(3\) diminuisce nel passaggio \(6\): \(j=3\) e il cammino è \(6,4,5,3,1,2,3\). Il nodo \(3\) è soddisfatto due volte: \(W=3,1,2,3\), realizzato dell'arco all'indietro di \((1,3)\), dell'arco in avanti \((1,2)\) e dell'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 nel passaggio \(6\) no l'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à normalizzato con \(\pi_6=0\): i potenziali del capitolo 4.
-
In sintesi:
iterazione e costo di \(\vet{x}\) e \(j\) e ciclo \(W\) e \(c(W)\) e \(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 di Teorema 6.14 consente le iterazioni \(80-60=20\); ne bastano tre. I tre i cicli sono i cicli della scomposizione di Esempio 6.2, trovati in un ordine diverso.
L'algoritmo di annullamento del ciclo parte da un flusso ammissibile e annulla i cicli negativi di \(G(\vet{x})\), trovati da Bellman–Ford dalle etichette tutte uguali a \(0\). Con dati interi ogni cancellazione abbassa il costo di almeno \(1\); a allo stop le etichette danno i potenziali che certificano il flusso ottimale.