3.2 Condizioni e potenziali di ottimalità¶
Parte 2 · Alberi e cammini · Capitolo 3 · Capitolo 3: Cammini minimi · Dispensa, volume 2 (PDF) · Esercizi: Cammini minimi · App: Cammini minimi: Dijkstra, Bellman–Ford, grafi aciclici
Definizione 3.7: potenziali e costi ridotti
Un vettore \(\vet{\pi} \in \R^n\) fornisce un potenziale \(\pi_i\) ad ogni nodo \(i \in N\). costo ridotto dell'arco \((i,j)\) rispetto a \(\vet{\pi}\) è
I potenziali sono ammissibile se \(\bar{c}_{ij} \ge 0\) per ogni arco \((i,j) \in A\), e un arco con \(\bar{c}_{ij}=0\) è stretto.
-
Dati etichette \(d(j)\), lunghezze di cammino da \(s\) a \(j\), utilizziamo i potenziali \(\pi_i=-d(i)\). Poi \(\bar{c}_{ij}=d_{ij}+d(i)-d(j)\) e i potenziali sono ammissibili se e solo se \(d(j) \le d(i)+d_{ij}\) per ogni arco.
-
Lungo una passeggiata \(W=i_0,i_1,\dots,i_k\) il telescopio dei potenziali:
\[ d(W)=\sum_{t=1}^{k} \bar{c}_{i_{t-1}i_t} \;+\; \pi_{i_0}-\pi_{i_k} . \]
Teorema 3.8: potenziali come certificato di ottimalità
Sia \(\vet{\pi}\) un potenziale ammissibile e sia \(P\) un percorso da \(s\) a \(t\) i cui archi siano tutti stretti. Allora \(P\) è un percorso più breve da \(s\) a \(t\) e \(d(P)=\pi_s-\pi_t\). Inoltre, \(G\) non ha ciclo negativo.
Dimostrazione
Usiamo la formula telescopica sopra.
-
Gli archi di \(P\) hanno \(\bar{c}_{ij}=0\), quindi \(d(P)=\pi_s-\pi_t\).
-
Per ogni percorso \(Q\) da \(s\) a \(t\), \(d(Q)=\sum_{(i,j) \in Q}\bar{c}_{ij}+\pi_s-\pi_t \ge \pi_s-\pi_t=d(P)\).
-
Per ogni ciclo \(C\) il primo e l'ultimo nodo coincidono, quindi \(d(C)=\sum_{(i,j) \in C}\bar{c}_{ij} \ge 0\). □
Corollario 3.9: condizioni di ottimalità per le etichette
Lasciamo che le etichette \(d(j)\), \(j \in N\) siano finite con \(d(s)=0\) e assumiamo che
-
(i) \(d(j) \le d(i)+d_{ij}\) per ogni arco \((i,j) \in A\);
-
(ii) per ogni \(j \neq s\) esiste un percorso da \(s\) a \(j\) di lunghezza \(d(j)\).
Quindi \(d(j)=\tilde{d}(j)\) per ogni \(j \in N\).
Dimostrazione
Per (i) i potenziali \(\pi_i=-d(i)\) sono ammissibili, quindi ogni percorso \(Q\) da \(s\) a \(j\) ha \(d(Q) \ge \pi_s-\pi_j=d(j)\) con l'argomento Teorema 3.8. Per (ii) il valore \(d(j)\) si raggiunge tramite un percorso, quindi \(d(j)=\tilde{d}(j)\). □
Esempio 3.4: un certificato sul grafo di riferimento
Con le distanze di Esempio 3.1 i potenziali sono \(\vet{\pi}=-\tilde{\vet{d}}=(0,-5,-2,-8,-10, -13)\), and the reduced costs \(\bar{c}_{ij}=d_{ij}-\pi_i+\pi_j\) sono:
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(d_{ij}\) | \(7\) | \(2\) | \(3\) | \(3\) | \(8\) | \(1\) | \(5\) | \(2\) | \(7\) |
| \(\bar{c}_{ij}\) | \(2\) | \(0\) | \(0\) | \(0\) | \(0\) | \(7\) | \(0\) | \(4\) | \(4\) |
-
Tutti i costi ridotti sono non negativi e gli archi stretti sono gli archi dell'albero del percorso più breve. Il percorso \(1,3,2,4,6\) è stretto, quindi è il più corto, con lunghezza \(\pi_1-\pi_6=13\).
-
L'albero della ricerca in ampiezza, \((1,2)\), \((1,3)\), \((2,4)\), \((3,5)\), \((4,6)\), fornisce le etichette \((0,7,2,10,10,15)\). Con i loro potenziali, \(\bar{c}_{32}=3-(-2)+(-7)=-2<0\): i potenziali non sono realizzabili e entrando nel nodo \(2\) attraverso \((3,2)\) si accorcia il suo percorso di \(2\).
I potenziali ammissibili (\(\bar{c}_{ij}=d_{ij}-\pi_i+\pi_j \ge 0\) su ogni arco) e un percorso fatto di archi stretti lo dimostrano il percorso è più breve. Con etichette, \(\pi_i=-d(i)\), e la fattibilità recita \(d(j) \le d(i)+d_{ij}\).