Vai al contenuto

6.7 L'algoritmo dei cammini minimi successivi

Definizione 6.15: pseudoflusso e squilibri

Uno pseudoflusso è un vettore \(\vet{x}\) con \(\vet{l} \le \vet{x} \le \vet{u}\), che può violare la conservazione del flusso. Lo squilibrio del nodo \(i\) è

\[ e_i=b_i-\Big(\sum_{(i,j) \in \delta^+(i)} x_{ij}-\sum_{(j,i) \in \delta^-(i)} x_{ji}\Big): \]

l'offerta che \(i\) deve ancora mandare se \(e_i>0\) (un nodo in eccesso), la domanda che deve ancora ricevere se \(e_i<0\) (un nodo in deficit).

  • Uno pseudoflusso è un flusso ammissibile esattamente quando \(\vet{e}=\vet{0}\). Gli squilibri hanno somma zero, perché i bilanci hanno somma zero e ogni arco aggiunge \(x_{ij}\) alla sua coda e lo sottrae alla sua testa.

  • La rete residua \(G(\vet{x})\) di uno pseudoflusso si definisce come nella Definizione 6.1. Aumentare \(\vet{x}\) lungo un cammino \(P\) di \(G(\vet{x})\) da \(s\) a \(t\) di \(\delta \le r(P)=\min_{(i,j) \in P}r_{ij}\) si definisce come per i cicli: i limiti restano soddisfatti, \(e_s\) diminuisce di \(\delta\), \(e_t\) aumenta di \(\delta\), e il costo cresce di \(\delta\, c(P)\), dove \(c(P)=\sum_{(i,j) \in P} c^x_{ij}\).

  • L'idea è mantenere potenziali con costi ridotti non negativi su \(G(\vet{x})\), la condizione del Teorema 6.9, mentre gli squilibri vanno a zero. Con \(\vet{x}=\vet{0}\), \(\vet{\pi}= \vet{0}\) e costi \(c_{ij} \ge 0\) la condizione vale all'inizio.

Lemma 6.16: i cammini minimi mantengono non negativi i costi ridotti

Sia \(\vet{x}\) uno pseudoflusso e siano \(\vet{\pi}\) potenziali con \(\bar{c}^{\pi}_{ij}=c^x_{ij}-\pi_i+\pi_j \ge 0\) su ogni arco di \(G(\vet{x})\). Siano \(d(i)\) le distanze da un nodo \(s\) in \(G(\vet{x})\) con le lunghezze \(\bar{c}^{\pi}\) (\(d(i)=+\infty\) se \(i\) non è raggiungibile), \(t\) un nodo con \(d(t)<+\infty\), \(P\) un cammino minimo da \(s\) a \(t\), e

\[ \pi'_i=\pi_i-\min\{d(i),d(t)\}, \qquad \forall i \in N . \]
  • (a) \(c^x_{ij}-\pi'_i+\pi'_j \ge 0\) su ogni arco di \(G(\vet{x})\).

  • (b) \(c^x_{ij}-\pi'_i+\pi'_j=0\) su ogni arco di \(P\).

  • (c) Se \(\vet{x}'\) è \(\vet{x}\) aumentato lungo \(P\) di \(\delta \le r(P)\), allora \(c^{x'}_{ij}-\pi'_i+\pi'_j \ge 0\) su ogni arco di \(G(\vet{x}')\).

Dimostrazione

Sia \(\hat{d}(i)=\min\{d(i),d(t)\}\). Il costo ridotto di \((i,j)\) con \(\vet{\pi}'\) è \(\bar{c}^{\pi}_{ij}+\hat{d}(i)- \hat{d}(j)\).

  • (a) Sia \((i,j)\) un arco di \(G(\vet{x})\). Se \(d(i)<+\infty\), un cammino minimo fino a \(i\) seguito da \((i,j)\) dà \(d(j) \le d(i)+\bar{c}^{\pi}_{ij}\), quindi \(\hat{d}(j) \le \min\{d(i)+\bar{c}^{\pi}_{ij},\,d(t)\} \le \hat{d}(i)+ \bar{c}^{\pi}_{ij}\), perché \(\bar{c}^{\pi}_{ij} \ge 0\). Se \(d(i)=+\infty\), allora \(\hat{d}(i)=d(t) \ge \hat{d}(j)\). In entrambi i casi il nuovo costo ridotto è non negativo.

  • (b) I sottocammini di \(P\) sono minimi (Lemma «ottimalità dei sottocammini» del Capitolo 3), quindi \(d(j)=d(i)+ \bar{c}^{\pi}_{ij}\) su ogni arco di \(P\), e \(d(i) \le d(t)\) lungo \(P\) perché le lunghezze sono non negative. Quindi \(\hat{d}=d\) su \(P\), e il nuovo costo ridotto è \(0\).

  • (c) Aumentare lungo \(P\) cambia \(G(\vet{x})\) solo sugli archi di \(P\): un arco \((i,j)\) di \(P\) può scomparire, e può comparire l'arco opposto \((j,i)\). L'opposto di un arco residuo ha il costo opposto, quindi per (b) costo ridotto \(0\); gli altri archi mantengono i loro costi ridotti, non negativi per (a).

□

  • Per ogni cammino \(P\) da \(s\) a \(t\) i potenziali danno una somma telescopica: \(\sum_{(i,j) \in P}\bar{c}^{\pi}_{ij}=c(P)-\pi_s+ \pi_t\). Un cammino minimo per i costi ridotti è un cammino di costo minimo di \(G(\vet{x})\): il flusso viaggia lungo i cammini più economici, da cui il nome dell'algoritmo.

Algoritmo: Algoritmo dei cammini minimi successivi

Input: una rete bilanciata con \(\vet{l}=\vet{0}\), \(b_i\) e \(u_{ij}\) interi, costi \(c_{ij} \ge 0\)
Output: un flusso ottimo \(\vet{x}\) con il suo certificato \(\vet{\pi}\), oppure «inammissibile»
1Passo 0 (inizializzazione). Porre \(\vet{x}:=\vet{0}\), \(\vet{\pi}:=\vet{0}\) e \(\vet{e}:=\vet{b}\).
2Passo 1 (selezione). Se \(\vet{e}=\vet{0}\), STOP: \(\vet{x}\) è ottimo, con \(\vet{\pi}\).
3 Altrimenti sia \(s\) il nodo di indice minimo con \(e_s>0\).
4Passo 2 (cammini minimi). Eseguire Dijkstra da \(s\) su \(G(\vet{x})\), lunghezze \(c^x_{ij}-\pi_i+\pi_j\).
5 Se nessun nodo con \(e_t<0\) è raggiungibile, STOP: inammissibile.
6 Altrimenti \(t\) è il nodo raggiungibile con \(e_t<0\) e \(d(t)\) minima, e \(P\) il suo cammino.
7Passo 3 (aumento). Porre \(\pi_i:=\pi_i-\min\{d(i),d(t)\}\) per ogni \(i \in N\).
8 Aumentare \(\vet{x}\) lungo \(P\) di \(\delta:=\min\{e_s,-e_t,r(P)\}\), e aggiornare \(e_s\), \(e_t\).
9 Andare al Passo 1.

  • Regole di questo capitolo. L'algoritmo di Dijkstra risolve i pareggi con l'indice minimo, come nel Capitolo 3; tra i nodi in deficit alla stessa distanza, \(t\) è quello di indice minimo.

Teorema 6.17: correttezza dell'algoritmo dei cammini minimi successivi

Con i dati di ingresso dell'algoritmo, all'inizio di ogni iterazione \(\vet{x}\) è uno pseudoflusso intero e \(c^x_{ij}-\pi_i+\pi_j \ge 0\) su ogni arco di \(G(\vet{x})\). L'algoritmo si ferma dopo al più \(D=\sum_{i: b_i>0}b_i\) iterazioni. Se si ferma al Passo 1, \(\vet{x}\) è un flusso ottimo; se si ferma al Passo 2, la rete non ha flussi ammissibili.

Dimostrazione

Dimostriamo l'invariante, poi il limite sulle iterazioni e i due arresti.

  1. Invariante. All'inizio \(G(\vet{0})\) ha solo gli archi in avanti, con costi \(c_{ij} \ge 0\), e \(\vet{\pi}=\vet{0}\). L'algoritmo di Dijkstra si può applicare, perché le lunghezze sono non negative, e il Lemma 6.16(c) mantiene non negativi i costi ridotti. La quantità \(\delta\) è un intero positivo, perché \(e_s\), \(-e_t\) e le capacità residue sono interi positivi (o \(+\infty\)), quindi \(\vet{x}\) resta intero.

  2. Limite. Se \(e_s>0\), qualche nodo ha \(e_t<0\), perché gli squilibri hanno somma zero. Ogni iterazione abbassa \(\sum_{i: e_i>0}e_i\) di \(\delta \ge 1\), e nessuno squilibrio cambia segno, perché \(\delta \le e_s\) e \(\delta \le -e_t\). La somma parte da \(D\).

  3. Arresto al Passo 1. \(\vet{e}=\vet{0}\), quindi \(\vet{x}\) è un flusso ammissibile, ottimo per l'invariante e il Teorema 6.9.

  4. Arresto al Passo 2. Sia \(S\) l'insieme dei nodi raggiungibili da \(s\). Nessun arco di \(G(\vet{x})\) esce da \(S\), quindi \(x_{ij}=u_{ij}\) su \(\delta^+(S)\) e \(x_{ij}=0\) su \(\delta^-(S)\). Lo pseudoflusso soddisfa la conservazione con i bilanci \(b_i-e_i\), quindi per il Lemma «flusso attraverso un taglio» del Capitolo 4

    \[ \sum_{i \in S} b_i=x(\delta^+(S))-x(\delta^-(S))+\sum_{i \in S} e_i=u(\delta^+(S))+\sum_{i \in S}e_i>u(\delta^+(S)), \]

    perché \(e_s>0\) e nessun nodo di \(S\) ha \(e_i<0\). La condizione sui tagli del Capitolo 4 è violata da \(S\): non esistono flussi ammissibili.

□

  • Tempo di esecuzione. Ogni iterazione esegue l'algoritmo di Dijkstra in tempo \(O(n^2)\): \(O(D\,n^2)\) in totale, un limite pseudopolinomiale.

  • Costi negativi. Se alcuni archi di capacità finita hanno \(c_{ij}<0\), si parte da \(x_{ij}=u_{ij}\) su questi archi e \(x_{ij}=0\) altrove, con \(\vet{e}=\vet{b}-\mat{B}\vet{x}\): un arco di questo tipo dà solo il suo arco all'indietro, di costo \(-c_{ij}>0\), e \(\vet{\pi}=\vet{0}\) funziona di nuovo.

6.7.1 I cammini minimi successivi sulla rete di riferimento

Esempio 6.7: cammini minimi successivi

Partiamo da \(\vet{x}=\vet{0}\), \(\vet{\pi}=\vet{0}\) e \(\vet{e}=\vet{b}=(5,2,0,-3,0,-4)\). Nella prima tabella ogni riga è un'iterazione, con il nodo \(s\), le distanze dell'algoritmo di Dijkstra e il nodo \(t\); la seconda tabella dà il cammino \(P\), il suo costo ridotto \(d(t)\) e il suo costo \(c(P)\), la quantità \(\delta\) e il costo del nuovo flusso.

it. \(s\) \(d(1)\) \(d(2)\) \(d(3)\) \(d(4)\) \(d(5)\) \(d(6)\) \(t\)
\(1\) \(1\) \(0\) \(2\) \(2\) \(7\) \(5\) \(8\) \(4\)
\(2\) \(1\) \(0\) \(0\) \(0\) \(0\) \(0\) \(1\) \(6\)
\(3\) \(2\) \(0\) \(0\) \(0\) \(0\) \(0\) \(4\) \(6\)
\(4\) \(2\) \(0\) \(0\) \(0\) \(3\) \(0\) \(3\) \(6\)

it. \(P\) \(d(t)\) \(c(P)\) \(\delta\) costo
\(1\) \(1,2,4\) \(7\) \(7\) \(3\) \(21\)
\(2\) \(1,3,5,6\) \(1\) \(8\) \(2\) \(37\)
\(3\) \(2,4,6\) \(4\) \(10\) \(1\) \(47\)
\(4\) \(2,1,3,5,4,6\) \(3\) \(13\) \(1\) \(60\)

La terza tabella dà, dopo ogni iterazione, i potenziali, gli squilibri e il flusso.

it. \(\vet{\pi}\) \(\vet{e}\) \(\vet{x}\)
\(0\) \((0,0,0,0,0,0)\) \((5,2,0,-3,0,-4)\) \((0,0,0,0,0,0,0,0,0)\)
\(1\) \((0,-2,-2,-7,-5,-7)\) \((2,2,0,0,0,-4)\) \((3,0,3,0,0,0,0,0,0)\)
\(2\) \((0,-2,-2,-7,-5,-8)\) \((0,2,0,0,0,-2)\) \((3,2,3,0,2,0,0,0,2)\)
\(3\) \((0,-2,-2,-7,-5,-12)\) \((0,1,0,0,0,-1)\) \((3,2,4,0,2,0,1,0,2)\)
\(4\) \((0,-2,-2,-10,-5,-15)\) \((0,0,0,0,0,0)\) \((2,3,4,0,3,0,2,1,2)\)

I costi ridotti \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\) degli archi di \(A\), prima di ogni iterazione, sono (l'arco in avanti ha \(\bar{c}_{ij}\) se \(x_{ij}<u_{ij}\), l'arco all'indietro \(-\bar{c}_{ij}\) se \(x_{ij}>0\)):

it. \((1,2)\) \((1,3)\) \((2,4)\) \((3,2)\) \((3,5)\) \((4,3)\) \((4,6)\) \((5,4)\) \((5,6)\)
\(1\) \(2\) \(2\) \(5\) \(2\) \(3\) \(3\) \(5\) \(5\) \(3\)
\(2\) \(0\) \(0\) \(0\) \(2\) \(0\) \(8\) \(5\) \(3\) \(1\)
\(3\) \(0\) \(0\) \(0\) \(2\) \(0\) \(8\) \(4\) \(3\) \(0\)
\(4\) \(0\) \(0\) \(0\) \(2\) \(0\) \(8\) \(0\) \(3\) \(-4\)

  • Iterazione \(1\). I costi ridotti sono i costi. I nodi in deficit \(4\) e \(6\) sono a distanza \(7\) e \(8\): \(t=4\), e \(\delta=\min\{5,3,4,4\}=3\). Il nodo \(6\) è più lontano di \(t\) e il suo potenziale diminuisce di \(7\), non di \(8\).

  • Iterazione \(2\). Gli archi \((1,2)\), \((2,4)\) del primo cammino hanno ora costo ridotto \(0\), e così i loro archi all'indietro. Il cammino \(1,3,5,6\) ha costo ridotto \(1\) e costo \(8\); \(\delta=\min\{2,4,4,4,2\}=2\) è fissato da \(e_1\) e da \(u_{56}\).

  • Iterazione \(3\). \(s=2\), e \(d(1)=0\) attraverso l'arco all'indietro \((2,1)\). Il cammino \(2,4,6\) usa l'ultima unità di \((2,4)\).

  • Iterazione \(4\). Il cammino \(2,1,3,5,4,6\) usa l'arco all'indietro \((2,1)\): un'unità che andava da \(1\) a \(2\) viene deviata da \(1\) attraverso \(3\), \(5\) e \(4\). La figura mostra \(G(\vet{x})\) con \(r_{ij}\) e il costo ridotto su ogni arco, e il cammino in blu.

Figura 3

Dopo l'iterazione \(4\) gli squilibri sono nulli e \(\vet{x}=\tilde{\vet{x}}\), di costo \(60\). Traslati di \(15\), i potenziali diventano \((15,13,13,5,10,0)\): i potenziali del Capitolo 4.

  • Qui i costi \(7,8,10,13\) dei cammini crescono da un'iterazione all'altra: le unità successive viaggiano lungo cammini più costosi, e il costo totale è \(3 \cdot 7+2 \cdot 8+10+13=60\).

  • Qui bastano quattro iterazioni, mentre il limite del Teorema 6.17 è \(D=7\).

Dijkstra ha bisogno dei costi ridotti

Nell'iterazione \(4\) gli archi \((2,1)\), \((3,1)\), \((4,2)\), \((5,3)\), \((6,4)\), \((6,5)\) di \(G(\vet{x})\) sono archi all'indietro con costi \(c^x_{ij}\) negativi, e l'algoritmo di Dijkstra con lunghezze negative può sbagliare (Capitolo 3). I potenziali rendono non negative tutte le lunghezze senza cambiare i cammini minimi.

L'algoritmo dei cammini minimi successivi manda flusso da un nodo in eccesso a un nodo in deficit lungo un cammino minimo di \(G(\vet{x})\), trovato dall'algoritmo di Dijkstra sui costi ridotti. L'aggiornamento \(\pi_i:=\pi_i-\min\{d(i),d(t)\}\) mantiene non negativi i costi ridotti, quindi il flusso finale è ottimo e i potenziali lo certificano.

6.8 Errori tipici

Attenzione

  • Dare all'arco all'indietro il costo \(+c_{ij}\). Un arco all'indietro diminuisce \(x_{ij}\), quindi risparmia \(c_{ij}\) per unità: il suo costo è \(-c_{ij}\), e la sua capacità residua è \(x_{ij}-l_{ij}\).

  • Aumentare di più di \(r(W)\). Qualche arco del ciclo uscirebbe dai suoi limiti; \(\theta=r(W)\) è il passo più lungo possibile.

  • Eseguire Bellman–Ford da un solo nodo. Un ciclo negativo non raggiungibile da quel nodo sfugge; le etichette partono da \(0\) su ogni nodo.

  • Scambiare la passeggiata per il ciclo. La passeggiata con \(n\) archi letta dalla tabella contiene un ciclo negativo, ma non è essa stessa un ciclo: il ciclo è il tratto tra due occorrenze dello stesso nodo.

  • Eseguire l'algoritmo di Dijkstra sui costi \(c^x_{ij}\). Gli archi all'indietro possono avere costi negativi; le lunghezze sono i costi ridotti \(c^x_{ij}-\pi_i+\pi_j\).

  • Aggiornare i potenziali con il segno sbagliato. Con \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\) l'aggiornamento è \(\pi_i:=\pi_i-\min\{d(i),d(t)\}\); i nodi più lontani di \(t\) diminuiscono solo di \(d(t)\).

  • Prendere per ottimo il flusso massimo del Passo 0. La rete ausiliaria non ha costi: il suo flusso massimo è ammissibile, e ottimo solo per caso.

6.9 In sintesi

In sintesi

  • La rete residua \(G(\vet{x})\) ha un arco in avanti \((i,j)\) con \(r_{ij}=u_{ij}-x_{ij}\) e costo \(c_{ij}\), e un arco all'indietro \((j,i)\) con \(r_{ji}=x_{ij}-l_{ij}\) e costo \(-c_{ij}\); aumentare lungo un ciclo \(W\) cambia il costo di \(\theta\,c(W)\).

  • Una circolazione si scompone in cicli; la differenza di due flussi ammissibili è una circolazione su \(G(\vet{x})\).

  • Un flusso ammissibile è ottimo se e solo se \(G(\vet{x})\) non ha cicli negativi, se e solo se esistono potenziali che danno costi ridotti non negativi su \(G(\vet{x})\); sugli archi di \(A\): \(\bar{c}_{ij}>0 \Rightarrow x_{ij}=l_{ij}\), \(\bar{c}_{ij}<0 \Rightarrow x_{ij}=u_{ij}\).

  • Un flusso massimo da una super sorgente a un super pozzo trova un flusso ammissibile o dimostra che non ne esistono.

  • Cancellazione dei cicli: Bellman–Ford da etichette \(0\) trova un ciclo negativo, aumentare di \(r(W)\) lo cancella; al più \(\vet{c}'\vet{x}^0-z(\mathrm{MCF})\) iterazioni con dati interi.

  • Cammini minimi successivi: Dijkstra sui costi ridotti da un nodo in eccesso al nodo in deficit più vicino, \(\pi_i:=\pi_i-\min\{d(i),d(t)\}\); al più \(D\) iterazioni.

La rete di riferimento in breve.

flusso più costoso \(\vet{x}^0=(1,4,4,1,4,1,3,3,1)\), costo \(80\)
cancellazione dei cicli da \(\vet{x}^0\) cicli \(4,5,3,4\); \(6,4,5,6\); \(3,1,2,3\): costi \(80,69,62,60\)
cammini minimi successivi cammini \(1,2,4\); \(1,3,5,6\); \(2,4,6\); \(2,1,3,5,4,6\): costi \(21,37,47,60\)
primo flusso ammissibile flusso massimo di valore \(7\); su \(A\) è \(\tilde{\vet{x}}\)
flusso ottimo \(\tilde{\vet{x}}=(2,3,4,0,3,0,2,1,2)\), \(z(\mathrm{MCF})=60\)
potenziali (\(\pi_6=0\)) \(\vet{\pi}=(15,13,13,5,10,0)\)


Esercizi su questo capitolo: Flusso di costo minimo