2.1. Flusso di costo minimo e cammini minimi.

1 . Alg o r it m i p e r p r o b le m i d i flu s s o s u r e t i
ROC-00/01 Capitolo 1
1.1. Il problema di flusso di costo minimo
Questi appunti sono da considerare una evoluzione degli appunti di Programmazione
Matematica; pertanto si eviterà di ripetere definizioni e concetti già contenuti negli altri appunti,
salvo quando necessario per garantire una chiarezza espositiva
1.1.1
Un esempio
Si assuma che un dato progetto sia decomponibile in un insieme di n attività, i=1,…,n. È dato il
tempo di che l'attività i richiede per essere eseguita. Inoltre, per ogni attività i sono noti gli
insiemi P(i) e S(i) delle attività che rispettivamente precedono e seguono i nel progetto, cioè che
devono terminare prima che inizi l'attività i e che non possono iniziare prima che sia completata
l'attività i. Si vogliono determinare i tempi di inizio delle attività in modo che il tempo di
completamento del progetto sia minimo. Senza ledere la generalità, si può assumere che l'attività
1 non sia preceduta da alcuna attività e che la attività n non sia seguita da altre attività del
progetto; infatti, in caso contrario, è sufficiente aggiungere due attività fittizie di durata nulla, una
che precede e l'altra che segue tutte le attività del progetto. Il problema può essere formulato
come problema di PL nel seguente modo.
(1.1.1)
min πn - π1
πj - πi ≥ di,
j ∈ S(i ),
i =1,…,n,
dove πi indica il tempo di inizio della attività i. Infatti i vincoli del problema implicano che la
attività i sia conclusa prima dell'inizio delle attività che la seguono (πi + di ≤ πj, j ∈ S(i )). La
funzione obiettivo, a meno della costante dn, rappresenta la durata del progetto. Indicando con xij
la variabile duale associata al vincolo di indici i, j, il duale del problema (1.1.1) è:
max∑
n
∑ dixij
i=1 j∈S(i)
(1.1.2)
-1,

∑ xji - ∑ xij =  1,
j∈P(i)
j∈S(i)
 0,
xij ≥ 0
i =1,
i =n,
altrimenti,
i = 1,…, n,
j ∈ S(i ),
Poiché, come è immediato verificare, la relazione di precedenza costituisce un ordinamento
parziale sull'insieme delle attività, si può associare al problema il grafo orientato G = (N, A), dove
il nodo i ∈ N corrisponde alla attività i, i = 1,…, n e: ak = (i,j) ∈ A ⇒ l'attività i precede l'attività j
(l'attività j segue l'attività i ). Assumiamo che sia |A | = m.
In figura 1.1 è mostrata una istanza del problema, la relativa coppia di problemi duali e il grafo
associato.
Il problema (1.1.2) è detto problema di flusso. Infatti le variabili x ij possono essere
interpretate come flussi per unità di tempo di beni (messaggi, passeggeri, litri di acqua,...)
interpretando il grafo G come una rete (di comunicazione, di trasporto, idraulica,...).
È immediato verificare (vedi figura 1.1.1) che la matrice dei vincoli del problema (1.1.2) è
la matrice di incidenza E = [eik] del grafo G. I vincoli del problema implicano che il flusso
entrante nel nodo i (Σj∈P(i) xji) sia uguale al flusso uscente dal nodo i (Σj∈S(i) xij). Si osservi
che per il nodo origine (i = 1) e per il nodo destinazione (i = n) l'offerta e la domanda sono
uguali a 1, mentre tutti gli altri nodi sono di trasferimento. Il problema consiste nel determinare
un flusso ammissibile di costo massimo.
4
ROC-00/01 Capitolo 1
x
Attività
1
2
3
4
Durata Attività che
seguono
3
4
2
0
(1,2) (1,3) (2,3)
2,3
3,4
4
π 2
∅
4
1
3
-1
1
0
0
-1
0
1
0
3
3
max
min
(2,4) (3,4)
0
-1
1
0
0
-1
0
1
0
0
-1
1
4
4
2
∨/
=
-1
0
0
1
2
4
3
1
4
1
3
4
1
2
3
Figura 1.1.1
Il problema (1.1.1), duale del problema di flusso, è detto anche problema di potenziale. Si
tratta di determinare un potenziale πi per ogni nodo del grafo in modo che la differenza di
potenziale di ogni coppia di nodi che corrispondono ad un arco di G non sia inferiore al costo
dell'arco. Si vuole minimizzare la differenza di potenziale tra il nodo destinazione e il nodo
origine. Nella letteratura il problema di flusso è usualmente indicato come problema primale e il
problema di potenziale come duale. Nel seguito adotteremo questa convenzione.
1.1.2 Formulazione del problema di flusso di costo minimo
Sia G = (N, A), con |N| = n e |A| = m, un grafo orientato e pesato; associati a G vi sono i vettori
di bilancio b = [bi], di costo c = [cij] e di capacità superiore u = [uij]. Inoltre, con E = [eik]
indichiamo la matrice di incidenza e con FS(i) e BS(i) rispettivamente la stella uscente e la stella
entrante del nodo i, i = 1 ,…, n.
Il problema (primale) di flusso di costo minimo è allora:
(P)
(1.1.3)
Min cx
Ex = b
0≤x≤u
e il suo duale (problema di potenziale) è:
(D)
Max
(1.1.4)
πb - µu
πE - µ ≤ c
µ≥0
o, in forma estesa:
(D)
Max ∑ πibi i∈N
∑ µijuij
(i,j)∈A
πj - πi - µij ≤ cij,
µij
≥ 0,
per ogni (i,j) ∈ A
per ogni (i,j) ∈ A.
5
ROC-00/01 Capitolo 1
1.1.3 Trasformazione in formulazioni equivalenti
Nel corso di Programmazione Matematica si è visto come è sempre possibile trasformare un
problema di flusso di costo minimo, senza perdita di generalità, per ottenere un problema con
capacità inferiori nulle, oppure con singola origine e singola destinazione, o anche come
problema di circolazione.
Nel seguito mostriamo altre due trasformazioni che risultano utili in particolari casi.
Uguaglianza tra domanda ed offerta
Si supponga che il problema che si vuole rappresentare abbia una domanda globale diversa
dall'offerta globale. Si studia cioè un problema in cui, se la domanda è maggiore dell'offerta, si
intende soddisfare al massimo la domanda, lasciandone una parte insoddisfatta a causa di
carenze dell'offerta. Analogamente, per il caso opposto in cui si ha un'offerta maggiore della
domanda, si intende soddisfare tutta la domanda non utilizzando la parte di offerta eccedente.
Una diretta formulazione del problema in termini di problema di flusso di costo minimo su
un grafo G sarebbe:
(P1)
Min cx
E ix
≤ bi,

= bi,
se bi >0,
altrimenti,
per ogni i∈N
0≤x≤u
dove eb = Σi∈N bi > 0, se si ha eccesso di domanda; oppure il problema:
(P2)
Min cx
E ix
≥ bi,

= bi,
se bi <0,
altrimenti,
per ogni i∈N
0≤x≤u
dove eb = Σi∈N bi < 0, in caso contrario. Si vuole trasformare (P1) o (P2) in un problema di
flusso equivalente (P') con la proprietà che eb' = 0:
(P')
(1.1.5)
Min c'x'
E'x' = b'
0 ≤ x' ≤ u'
Si trasforma G in un grafo ampliato G' con un nodo fittizio n+1 il cui bilancio è dato da:
b'n+1 = - ∑ bi.
i∈N
Inoltre:
- per il problema (P 1 ) il nodo n+1 è un origine (b'n +1 < 0) ed è connesso con ogni
destinazione i mediante un arco fittizio (n+1,i);
- per il problema (P2) il nodo n+1 è una destinazione (b'n +1 > 0) ed è connesso con ogni
origine i mediante un arco fittizio (i,n+1).
Gli archi fittizi hanno capacità superiore +∞ e costo nullo. Sia E' la matrice di incidenza di
G'; siano inoltre c', u' e b' i dati associati agli archi ed ai nodi di G'. Indicando con x' il vettore
dei flussi su G' si ottiene la formulazione (1.1.5); ovviamente eb' = 0.
Esempio 1.1.1
Il grafo originario sbilanciato ed il grafo ampliato:
6
ROC-00/01 Capitolo 1
4
Σ bi = -11 < 0
−10
(1,2)
a1
1
(3,4)
a2
(0,+∞)
2
a3
−5
−10
3
b3
4
(0,+∞)
(1,2)
a1
1
(3,4)
(2,3)
11
a2
2
a3
−5
(2,3)
3
4
( cij ,uij )
Figura 1.1.2
Esercizio 1.1.1
Dimostrare che il problema (P') è equivalente ai problemi (P1) e (P2).
Forte connessione del grafo
Dato un grafo G non fortemente connesso su cui è definito un problema di flusso (P), è
possibile ampliare G in un grafo fortemente connesso G' su cui è definito un problema di flusso
(P') equivalente a (P). Per ottenere G' è sufficiente aggiungere un nodo fittizio n+1 ed una
coppia di archi fittizi (i,n+1) e (n+1,i) per ciascun nodo i. Il nodo fittizio è un nodo di
trasferimento, gli archi fittizi hanno capacità +∞ e costo M, con M maggiore del costo di
qualunque cammino semplice (ad esempio M = 1 + (n-1)cmax, dove cmax è il massimo costo
degli archi originari). Il problema di flusso (P') sul grafo ampliato G' è equivalente al problema
(P) su G. Infatti, se (P) è non vuoto (esiste almeno una soluzione ammissibile), allora qualunque
soluzione ammissibile per (P) è ammissibile per (P') e qualunque soluzione ammissibile per (P')
che non utilizzi gli archi fittizi è ammissibile anche per (P) e ha lo stesso valore della funzione
obiettivo. Pertanto se la soluzione ottima per (P') non utilizza gli archi fittizi allora essa è ottima
anche per (P), altrimenti, cioè se almeno un arco fittizio è utilizzato, (P) è vuoto.
Esercizio 1.1.2
Dimostrare le asserzioni fatte.
Esercizio 1.1.3
Dimostrare l'equivalenza tra i due problemi (P) e (P').
Esercizio 1.1.4
Nel caso che (P) sia vuoto, quale interpretazione può essere data alla soluzione ottima di (P')?
1.1.4 Matrice di base ed albero di base
Nel seguito tratteremo il caso del problema di flusso con capacità inferiori nulle (1.1.3); la
generalizzazione al problema di flusso con capacità inferiori qualsiasi è facilmente deducibile.
Consideriamo la coppia di problemi duali di flusso e di potenziale definita su un grafo
orientato G = (N, A), |N |=n, |A |=m, formulati in (1.1.3) e in (1.1.4) e che riscriviamo; il
problema (primale) di flusso di costo minimo e il problema (duale) di potenziale sono:
(P)
Min cx
Ex = b
0≤x≤u
(D) Max πb - µu
πE - µ ≤ c
µ≥0
Assumeremo nel seguito, senza ledere la generalità, che il grafo G sia connesso e cioè che
esista un albero di copertura.
Sia B ⊆ {1, 2, …, m} un sottoinsieme dell'insieme degli indici di colonna di E, tale che |B|
= n-1 e che il grafo parziale TB = (N, AB) sia un albero. L'albero è un albero di copertura ed è
detto albero di base. Indicheremo con EB la matrice di incidenza di TB; ovviamente EB è una
sottomatrice di E, formata dalle n righe e da n-1 colonne della matrice E.
7
ROC-00/01 Capitolo 1
Teorema 1.1.1
EB ha rango massimo: r(EB) = n-1.
Dim.
Si consideri una funzione di visita posticipata vp su TB. Si costruisca la matrice ÊB, permutando
le righe e le colonne di EB, in base all'ordinamento dei nodi e degli archi indotto da vp e cioè gli
indici delle righe di ÊB sono Vp[r], Vp[Vp[r]], Vp[Vp[Vp[r]]], … , e gli indici delle colonne
(P[Vp[r]],Vp[r]), (P[Vp[Vp[r]]],Vp[Vp[r]),…(1).
Siano i e (i,P[i]) rispettivamente l'indice della riga e della colonna k-esima di Ê B. La
colonna k-esima conterrà nelle posizioni da 1 fino a k-1 elementi nulli, poiché i corrispondenti
nodi precedono i nella visita. L'elemento k sarà +1 o -1 a seconda dell'orientamento dell'arco
(cioè se P[i] > 0 o P[i] < 0). Di conseguenza la matrice ÊB è una matrice triangolare inferiore.
Osserviamo infine che se si rimuove l'ultima riga di ÊB, cioè quella corrispondente al nodo r, si
ottiene una matrice quadrata, di ordine n-1, triangolare inferiore con gli elementi della diagonale
non nulli. Pertanto, r(EB) = r(ÊB) = n-1. ♦
Esempio 1.1.2
Si considerino l'albero e la visita posticipata in figura 1.3:
1
2
4
3
5
7
8
6
9
N va -1
1 8
2 7
3 1
4 2
5 4
6 3
7 9
8 5
9 6
Figura 1.1.3
Le matrici EB e ÊB sono:
N (1,2) (1,3) (2,4) (2,5) (3,6) (3,7) (5,8) (6,9)
1 -1
-1
2
1
-1
-1
3
1
-1
-1
4
1
EB = 5
1
-1
6
1
-1
7
1
8
1
9
1
N (5,8) (2,5) (2,4) (1,2) (3,7) (6,9) (3,6) (1,3)
8 1
5 -1
1
(1) Ricordiamo che se, ad esempio, P[Vp[r]] < 0, allora l'arco e conseguentemente l'indice della colonna è
(Vp[r]),P[Vp[r]]).
8
ROC-00/01 Capitolo 1
4
2
ÊB = 7
9
6
3
1
1
-1
-1
1
1
1
-1
1
-1
-1
-1
1
-1
Esercizio 1.1.5
Dato il grafo in figura 1.1.4, determinare un albero di copertura TB, la sua matrice di incidenza EB e la matrice
permutata ÊB.
-3
2
(8,9)
−10
(1,3)
1
(3,14)
(3,6)
3
5
(cij , u ij)
(2,12)
4
8
Figura 1.1.4
Corollario 1.1.2
Il rango della matrice E è uguale a n-1.
Dim.
È infatti immediato osservare che la somma delle righe di E è il vettore nullo.♦
Osservazione 1.1.1
Il grafo può essere ampliato in modo tale che la matrice di incidenza E' del grafo ampliato sia di rango n. È
sufficiente aggiungere un particolare arco artificiale (0,r), la cui coda sia un nodo non esistente e la testa sia un
nodo che verrà assunto come radice degli alberi di copertura. L'aggiunta di (0,r) corrisponde all'aggiunta alla
matrice E della colonna er =[0,0,…,1,0,…,0], avente la sola componente r-esima = 1. Ogni albero di copertura
TB conterrà l'arco artificiale (0,r) e la corrispondente matrice di incidenza E'B è una matrice quadrata di ordine e di
rango n. Pertanto, la matrice ampliata E' = [E,er ] è di rango n.
Alternativamente la matrice E può essere ridotta ad una nuova matrice E", eliminando una riga, ad esempio
la riga r, al fine di far coincidere il numero di righe (n-1) con il suo rango. Ogni albero di copertura TB avrà il
nodo r come radice e la corrispondente matrice di incidenza E"B è una matrice quadrata di ordine e di rango n-1.
Teorema 1.1.3
Vi è corrispondenza biunivoca tra gli alberi di copertura del grafo ampliato TB e le matrici di
base E'B = [EB,er].
Dim.
Abbiamo mostrato che ad ogni albero di copertura TB corrisponde una matrice E'B = [EB,er]
quadrata e di ordine e rango n: cioè una matrice di base per il problema di flusso corrispondente.
Mostriamo ora che, data una matrice di base E'B = [E B,er], ad essa corrisponde un albero di
copertura T B . Consideriamo il grafo parziale G B = (N,A B ) associato ad E'B ; tale grafo ha
esattamente n nodi ed n archi, compreso l'arco fittizio (0,r). Supponiamo per assurdo che G
contenga un ciclo C formato dagli archi di indice i1, i2, …, ih. Con EC indichiamo la matrice di
incidenza formata da tutte e sole le colonne corrispondenti agli archi di C. Inoltre, dato
arbitrariamente un verso di percorrenza del ciclo, siano C+ e C- i due sottoinsiemi degli indici
degli archi di C rispettivamente concordi e discordi con il verso di percorrenza. Si ponga il valore
del moltiplicatore λj, per j=1, 2, …, h, nel seguente modo:
9
ROC-00/01 Capitolo 1

λj = 

1, se l'arco di indice j appartiene a C+,
-1, se l'arco di indice j appartiene a C-.
Il prodotto EC λ = 0 (è infatti facile verificare, per ogni riga i di EC, e cioè per ogni nodo i
del ciclo C, che esistono due sole componenti non nulle che indichiamo con j e k, che
corrispondono ai due archi incidenti in i, quando moltiplicate per i rispettivi coefficienti λj e λk,
forniscono due valori unitari ma di segno opposto); pertanto E C è formata da h colonne
linearmente dipendenti. Ciò implica che E'B non può essere una matrice di base e che pertanto
GB è un albero. ♦
Soluzioni di base complementari
Nel calcolo delle soluzioni di base complementari associate ad una matrice di base E'B e più in
generale nelle operazioni che vengono svolte dall'algoritmo del simplesso nelle sue diverse
versioni, svolge un ruolo particolarmente importante la soluzione di sistemi del tipo:
(1.1.6)
(1.1.7)
EBx = ξ,
π EB = η,
dove ξ e η sono due vettori di termini noti. Data la loro struttura, tali sistemi sono risolvibili in
modo efficiente attraverso una visita posticipata (1.1.6) e anticipata (1.1.7).
Iniziamo con il sistema (1.1.6). Interpretando il vettore ξ come vettore di bilancio ed il
vettore x come flusso, si tratta di determinare un flusso sull'albero TB che soddisfi il particolare
vettore di bilancio ξ.
Osserviamo che se u è un nodo foglia (in particolare il primo nodo di una visita
posticipata), allora esiste un unico arco incidente in u. Il valore del flusso su tale arco è dato per
(1.1.6) da:
xp(u),u = ξu,
se p(u)>0,
xu,-p(u) = -ξu, se p(u)<0.
Ai fini del calcolo del flusso sugli altri archi è sufficiente aggiornare la componente del
vettore corrispondente al nodo come segue:
ξ|p(u)| := ξ|p(u)| + ξu,
e proseguire selezionando il nodo successivo nella visita. Si osservi che in questo modo esisterà
sempre un unico arco incidente nel nodo selezionato il cui flusso deve ancora essere
determinato. La procedura, la cui complessità è O(n) poiché ogni nodo di TB viene esaminato
una sola volta, può essere formalizzata come segue:
Procedura Flusso_di_base (TB,r,P,Vp,ξ,x):
begin
u:=Vp[r];
while u≠r do
begin if P[u] >0 then x[P[u],u]:= ξ[u] else x[u,-P[u]]:= -ξ[u];
ξ[|P[u]|] = ξ[|P[u]|] + ξ[u]; u:=Vp[u] end
end.
Figura 1.1.5 - La procedura Flusso_di_base
Consideriamo adesso il sistema (1.1.7). Se attribuiamo alle componenti di η il significato
di differenza di potenziale sui corrispondenti archi di TB, il vettore π può essere interpretato
come un vettore di potenziali da assegnare ai nodi dell'albero in modo da realizzare le richieste
10
ROC-00/01 Capitolo 1
differenze di potenziale sugli archi. Osserviamo che avendo in questo caso il sistema n variabili
ed n-1 vincoli, si ha un grado di libertà che può essere eliminato ponendo ad esempio πr = 0. Il
sistema può essere risolto mediante una visita anticipata di TB come mostrato dalla seguente
procedura, di complessità O(n):
Procedura Potenziale_di_base (TB,r,P,Va,c,π):
begin
π[r]:=0; u:=Va[r];
while u≠r do begin if P[u] >0 then π[u]:=π[P[u]] + c[P[u],u] else π[u]:=π[-P[u]] - c[u,-P[u]];
u:=Va[u] end
end.
Figura 1.1.6 - La procedura Potenziale_di_base
Soluzione di base primale
Essendo il problema di flusso (1.1.3) un problema di P.L. a variabili limitate, una base per la
coppia di problemi duali (1.1.3) e (1.1.4) è individuata dalla partizione degli indici degli archi di
A in (B,L,U), dove B individua l'albero di copertura TB e (L,U) è una partizione degli indici degli
archi fuori base tali che:
 0, se h ∈ L,
xh = 
uh, se h ∈ U.
La soluzione di base primale associata è quindi:
(1.1.8)
 x_B 
_ _ 
x = x 
L
 x_ 
U
_
_
_
_
dove x L = 0, x U = uU e x B è soluzione di EB x B = b - EUuU.
_
Per il calcolo della soluzione di base primale o flusso di base, x , corrispondente alla
matrice di base EB è sufficiente applicare la procedura Flusso_di_base con ξ = b – EUuU. La
_
soluzione x così determinata è un flusso e, per costruzione, soddisfa i vincoli di conserva-zione
del flusso e, per gli archi fuori base , cioè {ah: h ∈ L ∪ U}, soddisfa anche i vincoli di capacità.
_
Il flusso di base x è ammissibile se sono soddisfatti anche i vincoli di capacità per gli archi in
base:
_
(1.1.9)
0 ≤ x B ≤ u B.
Esempio 1.1.3
Sia B = {2, 3, 6, 7}, L = {1, 4}, U = {5} la base del grafo in figura 1.1.7 dove:
c = [ 2 3 5 -3 -1 2 4],
 45
1
u =  2,
 47
3
11
 -50
b = -6
 38
ROC-00/01 Capitolo 1
(cij , u ij)
a
(2,4)
a
3
a5
(5,1)
1
7
3
(4,3)
(-1,4)
a
5
a 2 (3,5)
-6
TB
1
3
4
a2
a1
-5
a4
(-3,2)
2
n =5, m=7
3
(2,7)
a6
5
8
r =1
a3
6
2
a7
4
Figura 1.1.7 - La procedura Potenziale_di_base
_
_
_
Il valore del flusso sugli archi fuori base è x 12 = x 24 = 0, x 34 = u34 = 4. Infine, ξ = b -E U uU è dato da
ξ i = b i, i = 1, 2, 5; ξ 3 = b 3 + u34 = -2; ξ 4 = b 4 - u 34 = -1. L'applicazione della procedura Flusso_di_base
fornisce:
_
_
x 23 = -ξ2 = 0;
ξ3 = -2;
x 45 = -ξ4 = 1;
ξ5 = 8 - 1 = 7;
_
_
x 35 = ξ 5 = 7;
ξ3 = -2 + 7 = 5;
x 13 = ξ 3 = 5;
ξ1 = -5 + 5 = 0.
Si ha quindi:
_
xB =
 5
 0 _
  ; x =  0 ; x_ = [4];
 7 L  0 U
 
 1
_
0 ≤ x B ≤ uB, pertanto il flusso è ammissibile.
 05
0
_
x =  0 ;
 47
1
Soluzione di base duale
__
_
La soluzione di base duale associata alla base (B, L, U ), è data da (π,µ) dove π è soluzione del
sistema :
_
(1.1.10) π EB = cB,
_ _ _ _
e µ = (µB, µL, µU ) è data da:
_
_
_
_
µB = µL = 0,
µU = πEU - cU
_
Per il calcolo di π, indicato come potenziale di base, è sufficiente applicare la procedura
Potenziale_di_base con η = cB. Ricordiamo che è necessario fissare il potenziale di un nodo (ad
_
_
es. πr = 0) perché π sia univocamente determinato.
__
Affinché la soluzione (π,µ) sia ammissibile devono essere verificate le condizioni:
_
_
(1.1.11) π EL - µL ≤ cL,
_
_
(1.1.12) µU = πEU - cU ≥ 0.
__
_
Poiché µL = 0, la soluzione (π,µ) è ammissibile se e solo se sono verificati i vincoli:
_ _
π j - πi ≤ cij;
per ogni ah = (i,j) tale che h ∈ L;
_ _
π j - πi ≥ cij;
per ogni ah = (i,j) tale che h ∈ U.
_ _
_
Chiameremo c ij = cij + πi - πj il costo ridotto dell'arco (i,j). Si osservi che il costo ridotto
degli archi in base, cioè {ah: h ∈ B}, è nullo per costruzione. Quindi, la soluzione duale di base
è ammissibile se e solo se per gli archi fuori base valgono le seguenti relazioni:
12
ROC-00/01 Capitolo 1
(1.1.13)
_
c ij ≥ 0
_
c ij ≤ 0
per ogni ah = (i,j) tale che h ∈ L;
per ogni ah = (i,j) tale che h ∈ U.
_
Poiché
la componente µ della soluzione duale di base è determinata univocamente dato il
_
vettore π, nel seguito_ le soluzioni duali di base verranno indicate semplicemente per mezzo del
vettore di potenziale π.
Esempio 1.1.3 (continua)
Applicando la procedura Potenziale_di_base al problema fornito in figura 1.1.7 si ha:
_
_
_
_
_
π 1 = 0;
π 3 = π1 + c13 = 0 + 3 = 3;
π 5 = π3 + c35 = 3 + 2 = 5;
_
_
_
_
π 4 = π5 - c45 = 5 - 4 = 1;
π 2 = π3 - c23 = 3 - 5 = -2.
Inoltre, i costi ridotti degli archi fuori base sono:
_
_
c 12 = 2 + 0 + 2 = 4;
c 24 = -3 - 2 - 1 = -6;
_
essendo (2,4)∈ L e c 24 < 0, la soluzione duale non è ammissibile.
_
c 34 = -1 + 3 - 1 = 1;
I problemi di flusso di costo minimo costituiscono una classe importante dei problemi di
PL in quanto, se i dati sono interi, anche le soluzioni di base complementari hanno componenti
intere come mostrato dal seguente teorema.
Teorema 1.1.4
Se i costi, le domande e le capacità del grafo sono valori interi, allora ogni coppia di soluzioni di
base complementari ha componenti a valori interi.
Dim
La dimostrazione segue immediatamente osservando che la matrice di base ha determinante ±1
o, equivalentemente, osservando che le operazioni aritmetiche effettuate nelle procedure
Flusso_di_base e Potenziale_di_base sono solo somme e sottrazioni. ♦
1.1.5 Intorno di una base
È possibile individuare, nell'intorno di una base di un problema di flusso di costo minimo
primale (duale) ammissibile, una base adiacente primale (duale) ammissibile che migliora la
funzione obiettivo (o, in caso di degenerazione, con uguale valore della funzione obiettivo).
Sviluppiamo in termini di operazione su alberi sia l'individuazione delle basi adiacenti, sia il
calcolo delle soluzioni di base complementari corrispondenti alla base adiacente per mostrare
come la particolare struttura del problema renda più efficienti alcune di queste operazioni. Alla
fine del paragrafo saranno fornite le indicazioni necessarie per ottenere le basi adiacenti.
Flusso adiacente ammissibile
Assumiamo che (B, L, U) definisca un flusso di base ammissibile e un potenziale di base non
ammissibile. La non ammissibilità del potenziale di base implica che esiste un indice k tale che:
_
(1.1.14) o ∃ ak = (p,q) e k ∈ L
con c pq < 0,
_
(1.1.15) oppure ∃ ak = (p,q) e k ∈ U
con c pq > 0.
L' indice k è l'indice dell'arco entrante in base. L'aggiunta di ak a TB determina un ciclo C.
Si fissa un verso sul ciclo (vedi figura 2.4.9) come segue:
- se k ∈ L, il verso del ciclo è concorde con quello di ak;
13
ROC-00/01 Capitolo 1
-
se k ∈ U, il verso del ciclo è discorde con quello di ak.
ak
ak
k∈U
k∈L
Figura 1.1.8
Indichiamo con C + e C - gli indici degli archi del ciclo C che sono concordi e,
rispettivamente, discordi con il verso fissato. Si consideri il flusso x(θ) definito da:
_
+
 x_ij + θ, se (i,j) ∈ C ,
xij (θ) =  x ij - θ, se (i,j) ∈ C-,
 x_ ,
se (i,j) ∉ C,
ij
dove θ è un reale non negativo.
È immediato verificare che x(θ) soddisfa, per ogni θ, i vincoli di conservazione del flusso.
Consideriamo la funzione obiettivo:
_
cx(θ)=c x + θ ( ∑ cij - ∑ cij ) .
(i,j)∈C+ (i,j)∈COsserviamo che è
_ _
cij = πj - πi,
∀(i,j) ∈ C \ {(p,q)};
_
infatti C \{(p,q)} ⊆ AB e πEB = cB. Si ha quindi sostituendo:
_ _
_
c
+
π
π
=
c
se k ∈ L,
 pq
p
q
pq,
∑ c+ij - ∑ - cij = -c - _π + π_ =- c_ , se k ∈ U.
 pq p
q
pq
(ij)∈C
(ij)∈C
_
Quindi il costo ridotto c pq fornisce la variazione di costo del flusso al seguito di una
variazione unitaria di flusso sul ciclo C. Dalle (1.1.14) e (1.1.15) si ha allora che:
_
cx(θ) ≤ c x ,
∀θ ≥0.
Affinché x(θ) sia ammissibile devono
_ essere verificati i vincoli 0 ≤ xij(θ) ≤ uij, (i,j) ∈ C. I
vincoli precedenti sono soddisfatti se θ ≤ θ = min{θ1,θ2}, dove
_
_
θ1 = min{uij - x ij , (i,j) ∈ C+};
θ2 = min{ x ij , (i,j) ∈ C-}.
Infatti θ ≤ θ1 impedisce che il flusso violi la capacità superiore negli archi del ciclo concordi col
verso fissato, e θ ≤ θ2 impedisce che il flusso assuma valori negativi negli archi del ciclo discordi
col verso fissato(1). Il flusso
_
(1) Si noti che per problemi di flusso con capacità illimitata può risultare θ=+∞. In tal caso il problema di flusso
non è inferiormente limitato e il problema di potenziale è vuoto.
14
ROC-00/01 Capitolo 1
(1.1.16)
_
x' = x(θ)
è un flusso di base. Infatti ad esso è associata la base (B', L', U') adiacente a (B, L, U) determinata
come segue. _
_
Il valore θ corrisponde ad almeno un arco ah= (i,j) del ciclo C per cui xij(θ) assume valore
uguale a zero o alla capacità superiore. L'arco ah è l'arco uscente dalla base.
Posto B'= B \ {h} ∪ {k} si ha che TB' è per costruzione
un albero. Si osservi che se h = k
_
+
allora T B' = T B . Inoltre se a h ∈ C , allora_ x ij(θ ) = u ij e quindi h dovrà essere aggiunto
all'insieme U; altrimenti, se ah ∈ C-, allora xij(θ) = 0 e quindi h dovrà essere aggiunto all'insieme
L. L'indice della variabile entrante in base dovrà essere eliminato da L o da U a seconda che si
verifichi il caso (1.1.14) o il_ caso (1.1.15). Riassumendo,
_
_ una base adiacente (B', L', U') che
individua la soluzione x' = x(θ) ammissibile con cx(θ) ≤ c x è data da:
B' = B \ {h} ∪ {k}
(1.1.17)
(L ∪ {h} \ {k},U ), se k ∈L e h ∈C-,

(L,U ∪ {h} \ {k}),
(L',U') = 
(L \ {k},U ∪ {h}),
(L ∪ {h},U \ {k}),
se k ∈U e h ∈C+,
se k ∈L e h ∈C+,
se k ∈U e h ∈C_
_
_
Si osservi che se θ > 0, allora cx(θ ) < c x e la nuova base è una base distinta dalla
precedente, cui
_ dalla funzione obiettivo; questo accade in
_ corrisponde un valore inferiore
particolare se x è non degenere. Altrimenti, se θ = 0, (B',
_ L', U') è una base distinta da (B, L, U) a
cui corrisponde la stessa soluzione di base degenere x .
Determiniamo adesso la soluzione duale e cioè il potenziale (π',µ') o equivalentemente
(π',c') associato a (B', L', U'). Ovviamente π' può essere calcolato applicando la procedura
Potenziale_di_base. Mostriamo che è possibile ottenere π' mediante l'aggiornamento di π.
Cominciamo con l'osservare che la rimozione di ah da TB, causa la separazione di TB in
due alberi, che indicheremo con T' = (N', A') e T" = (N", A"); nel seguito denoteremo con T'
l'albero che contiene la radice r. La partizione (N', N") di N è un taglio del grafo G; A(N', N") è
l'insieme degli archi del taglio mentre A+(N', N") e A-(N', N") rappresentano gli insiemi degli
archi rispettivamente diretti e inversi del taglio.
Per costruzione ah ∈ A(N', N"). Poiché l'aggiunta di ak a TB forma il ciclo C contenente ah,
allora ak ∈ A(N', N"). Consideriamo la trasformazione
_
_
π + δ, se i ∈ N",
(1.1.18) πi (δ) =  πi,
se i ∈ N'.

i
dove il reale δ è detto variazione di potenziale.
Consideriamo l'effetto della trasformazione (1.1.18) sui vincoli del problema di potenziale;
per far questo, come abbiamo visto, possiamo equivalentemente valutare i costi ridotti cij(δ)
relativi alla soluzione π(δ). Si ha:
_
 c ij + δ, se (i,j) ∈ A-(N', N"),
_
_
(1.1.19)
c ij (δ) = cij + πi (δ) - πj (δ) =  c ij - δ, se (i,j) ∈ A+(N', N"),
_
 c ij,
altrimenti.
15
ROC-00/01 Capitolo 1
Allora, posto:
_
_  c pq, se ak =(p,q) ∈ A+(N', N"),
δ = _
− c pq, se ak =(p,q) ∈ A (N', N")
_
_
_
è immediato verificare
che
c
(δ
)
=
0,
c
(δ
_
pq
ij ) = c ij = 0,_∀(i,j) ∈B' \ {k }.
Pertanto π'=π(δ), ottenuto dalla (1.1.18) per δ = δ, è soluzione di
π'EB'= cB'
e quindi π' è il potenziale di base associato a (B', L', U').
Il seguente teorema riassume i risultati e caratterizza l'intorno di un flusso di base
ammissibile.
Teorema 1.1.5
_ _
Sia data
una
base
(B,
L,
U)
e
la
corrispondente
coppia
di
soluzioni
di
base
complementari
(
x
, π),
_
_
dove x è un flusso ammissibile e π è un potenziale non ammissibile. È possibile determinare
una base adiacente (B', L', U') data da (1.1.17) a cui corrispondono
la coppia di soluzioni
_
_
complementari x', data da (1.1.16), e π', data dalla (1.1.18) per δ = δ, per cui risulta cx' ≤ c x .
Esempio 1.1.3 (continua)
_
Proseguendo l'esempio, l'arco a4 = (2,4) è fuori base alla capacità inferiore, cioè 4 ∈ L e c 24 = -6 < 0. Pertanto
k = 4 e l'inserimento di a4 forma il ciclo C = {(2,4), (4,5), (3,5), (2,3)} (vedi figura 1.1.9).
Il verso di_C è concorde
_ con (2,4) e gli archi concordi con il verso di C: sono (2,4), (4,5); quindi
θ 1 = min{u 24 - x 24 , u 45 - x 45} = min{2, 2} = 2.
_
_
Gli archi
_ discordi con il verso di C sono (3,5) e (2,3); θ 2 = min{ x 3 5 , x 23 } = min{7, 0} = 0. Di
conseguenza θ = min{θ1, θ2} = min{2, 0} = 0. L'arco uscente
_ è _l'arco a3= (2,3); h =_ 3.
_
Poiché l'arco entrante (2,4) ∈ A-(N',N") si ha che δ = - c 24 = 6. Essendo θ = 0 si ha x' = x . Il nuovo
potenziale di base e i nuovi costi ridotti sono ottenuti per aggiornamento:
_
_
_
_
_
_
π'2= π 2 + δ = -2 + 6 = 4;
c12
' = c 12 - δ = 4 - 6 = -2;
c23
' = c 23 + δ = 0 + 6 = 6.
La base (B', L', U') è data da
B' = B \{h}∪{k} = {2,3,6,7} \{3}∪{4} = {2,4,6,7};
L' = L \{k}∪{h} = {1,4} \{4}∪{3} = {1,3};
U' = U = {5};
Poiché c12
' = -2 < 0, a1 = (1,2) con 1 ∈ L', la base (B', L', U') non è duale ammissibile.
T'
1
1
a2
a2
3
a6
5
a7
3
a
3
a6
5
2
2
T"
a7
a4
4
4
Figura 1.1.9
Potenziale adiacente ammissibile
_
Assumiamo ora che
(B,
L,
U)
individui
un
potenziale
di
base
ammissibile,
π, ed un flusso di base
_
_
_
non ammissibile, x . Poiché il potenziale è ammissibile si ha c L ≥ 0 e c U ≤ 0, mentre per la non
ammissibilità del flusso dovrà esistere almeno un indice h ∈ B tale che l'arco ah = (v,w) abbia
_
_
flusso x vw < 0 oppure x vw > uvw.
16
ROC-00/01 Capitolo 1
Si vuole studiare l'operazione di passaggio dalla base individuata da (B, L, U) ad una nuova
base adiacente ottenuta scegliendo l'arco ah come arco uscente. La rimozione di ah individua il
taglio (N', N") causando la separazione del albero TB in due sottoalberi, T' = (N', A') e T" = (N",
A"). Assumiamo che la radice r sia la radice di T'.
Sia a k = (p,q) l'arco entrante in base (assumiamo per ora di conoscere già tale arco,
affrontando solo successivamente il problema della sua determinazione). Dovrà naturalmente
essere ak ∈ A(N', N") e quindi esso formerà in TB un ciclo contenente ah. Nella figura 1.1.10
sono stati indicati i quattro casi possibili; in essa non è stato indicato il verso di ak, non essendo
per ora rilevante.
r
r
x vw > u vw
xvw <0
w
v
T'
v
T'
ah
w
ah
C
C
i
j
ak
j
a)
i
ak
T"
T"
b)
r
r
x vw > uvw
xvw <0
T'
T'
v
w
w
ah
v
ah
C
C
i
ak
j
j
ak
T"
c)
i
T"
d)
Figura 1.1.10
_
Osserviamo
che
il
verso
scelto
per
il
ciclo
C
è
concorde
con
l'arco
a
se
è
x
h
vw < 0 e
_
discorde se è x vw > uvw. Nella nuova base (B', L', U') l'indice h apparterrà ad L' o a U' e di
conseguenza il flusso sull'arco ah = (v,w) dovrà essere nullo, h ∈ L', oppure uguale a uvw, h ∈
U'.
Il nuovo flusso di base, x', è dato per ogni arco (i,j) ∈ A da:
_
_
x
+
θ
 _ij _, se (i,j)∈C+,
x'ij =  x ij − θ, se (i,j)∈C-,
 x_ ,
altrimenti;
ij
dove si è posto:
17
ROC-00/01 Capitolo 1
_
_  − x vw,
θ =  _
 x vw - uvw,
_
se x vw < 0,
_
se x vw > uvw.
Consideriamo ora l'aggiornamento della soluzione duale, cioè del vettore dei potenziali π.
Secondo quanto già visto nel caso di basi adiacenti primali ammissibili, il nuovo vettore dei
potenziali π' ha componenti:
_
_
πi + δ, se i∈N",
π'i = _
se i∈N';
π ,
i
dove
_
c pq, se ak=(p,q)∈A+(N',N"),
_ 
δ = 
_
 − c pq, se ak=(p,q)∈A-(N',N").
Osserviamo che il costo ridotto di (i,j) ∈ A viene così modificato:
_
_
c
−
δ
, se (i,j)∈A+(N',N"),
ij

_ _
_
(1.1.20)
c ij' =  c ij + δ, se (i,j)∈A-(N',N"),
 c_ ,
altrimenti.
ij
Osserviamo che per l'ammissibilità di π' dovrà essere, per l'arco ah = (v,w):
_
≥0, se x vw < 0 cioè h∈L',
_
_

c vw
' = c vw +π'v- π'w 
_
≤0, se x vw>uvw cioè h∈U'.
_
Pertanto, siccome c vw = 0, dovrà essere:
_
_
≤0, se x vw<0 e ah∈A+(N',N") oppure x vw>uvw e ah∈A-(N',N"),
_ 
δ 
_
_
≥0, se x vw<0 e ah∈A-(N',N") oppure x vw>uvw e.ah∈A+(N',N").
_
Supponiamo di essere nel primo caso, δ ≤ 0. Chiaramente gli unici archi il cui costo ridotto
viene modificato sono quelli appartenenti al taglio (N',N"). Volendo mantenere l'ammissibilità
_
duale, siccome il costo ridotto degli archi inversi diminuirà secondo la (1.1.20), il valore δ dovrà
risultare:
_
_

c ij, ∀(i,j)∈A+(N',N") per cui x ij = uij,
_ 
δ ≥ 
_
_
 − c ij, ∀(i,j)∈A-(N',N") per cui x ij = 0.
Indichiamo i due sottoinsiemi degli archi in questione
AL− = {ai∈A−(N',N"): i∈L}.
_
Per l'ammissibilità basta allora porre (si ricorda che δ≤0):
_
_
_
+
(1.1.21) δ = max{{ c ij: (i,j)∈AU
}∪{− c ij: (i,j)∈AL− }}.
+
AU
= {ai∈A+(N',N"): i∈U}
e
18
ROC-00/01 Capitolo 1
Come arco ak = (p,q) entrante in base al posto
degli archi)
_
_di ah scegliamo l'arco_ (o uno
_
per cui è verificata la (1.1.21), per cui si_verifica δ = c_pq se k ∈ U, oppure δ = − c pq, se k ∈ L.
Analogo è il caso in cui si debba avere δ ≥ 0; il valore δ è posto:
_
_
_
−
(1.1.22) δ = min{{ c ij: (i,j)∈AL+ }∪{− c ij: (i,j)∈AU
}},
dove
AL+ = {ai∈A+(N',N"): i∈L}
−
AU
= {ai∈A−(N',N"): i∈U}.
e
L'arco entrante in base, ak, è determinato di conseguenza. Se
nella
_ nella (1.1.21) (oppure
_
+
−
+
−
(1.1.22)) l'insieme AU ∪ AL = Ø, (oppure AL ∪ A U = Ø), si pone δ = −∞ (oppure δ = +∞). Si
ha allora che il problema
di potenziale è non limitato e quindi che il problema di flusso è vuoto.
_
Nel caso si abbia δ finito la nuova base (B', L', U') è data da:
B'=B\{h}∪{k},
k∈L
L'=L\{k}∪{h}
U'=U
L'=L\{k}
U'=U∪{h}
_
x vw<0
_
x vw>uvw
k∈U
L'=L∪{h}
U'=U \{k}
L'=L
U'=U \{k}∪{h}
Esempio 1.1.4 (continua)
Si consideri la base B = {1, 3, 4, 7}, L = {5, 6}, U = {2}_ e la coppia di soluzioni di base_complementari associate
T
(vedi figura 1.1.11):
_ il flusso di base non_ammissibile x = [0 5 -11 11 0 0 8] : x 23 < 0; il potenziale di
base ammissibile π = [0 2 7 -1 3], c = [0 -4 0 0 7 6 0]. L'arco uscente di base è a 3 , quindi h = 3.
Consideriamo gli archi candidati ad entrare in base. Il caso in esame corrisponde al caso 1).
TB
1
a1
2
3
a3
TB
1
T'
a1
a2
2
a4
4
T"
a7
3
a
3
a5
a4
4
a7
a6
5
5
Figura 1.1.11
_
_
_
_
δ1 = min{- c 13} = 4, δ2 = min{ c 34 , c 35} = 6. Pertanto δ = -4 e a2 è l'arco entrante, cioè k =2.
Esercizio 1.1.6
Completare l'esempio precedente
Osservazione 1.1.2: basi adiacenti
Si può verificare formalmente che i criteri per il passaggio a basi adiacenti ammissibili introdotti nel corso del
paragrafo, coincidano con i criteri applicati negli algoritmi del Simplesso Primale e Duale per problemi di PL a
variabili limitate. Per procedere in questa direzione è necessario calcolare EB-1 e EB-1E.
E B -1 è una matrice a valori (0, -1, 1) le cui righe sono associate agli archi di T B e le cui colonne sono
associate ai nodi di TB. Il valore eij-1, associato all'arco ai ed al nodo j è determinato dalla posizione di ai rispetto
al cammino Prj dalla radice r al nodo j su TB:
 0,
1,
eij-1 = 
 -1,
a i ∉ P rj,
a i = (p(j),j) ∈ P rj,
a i = (j,-p(j)) ∈ P rj;
19
ROC-00/01 Capitolo 1
pertanto, gli elementi non nulli della riga Ei-1 corrispondono ai nodi del sottoalbero di TB di radice j; gli elementi
j
non nulli della colonna (E-1) individuano gli archi appartenenti a Prj, il segno determina il loro orientamento.
Anche la matrice F = EB-1E è a valori (0, -1, 1); le righe sono associate agli archi di TB mentre le colonne
sono associate agli archi di G. L'interpretazione del valore fij è legata alla relazione tra ai e aj rispetto a TB = (N,
AB); ovviamente, se aj ∈ AB, allora:
 0, se j ≠ i,
fij = 
 1 , se j = i.
Supponiamo ora che j ∉ B. L'arco aj induce su TB un ciclo C ed un verso; allora:
 0, a i ∉ C ,
1 , a i ∈ C ed ha verso opposto,
fij = 
 -1,
a i ∈ C ed ha verso uguale.
Una analoga interpretazione può essere fatta considerando i due alberi T' e T" in cui viene separato TB
rimuovendo l'arco ai; si noti che ai definisce un orientamento tra T' e T"; allora:
 0, a j non riconnette T' e T",
1 , a j riconnette T' e T" ed ha orientamento uguale,
fij = 
 -1,
a j riconnette T' e T" ed ha orientamento opposto.
Pertanto, per j ∉ B, gli elementi non nulli di Fj individuano gli archi che formano un ciclo sull'albero a
causa dell'inserimento di aj, ed il segno indica il verso sul ciclo (discorde se +1, concorde se -1) rispetto a quello
di a j; inoltre, gli elementi non nulli di F i individuano gli archi che riconnettono T' e T", ed il segno indica
l'orientamento tra gli alberi (uguale se +1, opposto se -1) rispetto a quello di ai.
Esempio 1.1.4
Dato il grafo in figura 1.1.12, la sua matrice di incidenza E e la base B = {2, 3, 5}:
2
2
a1
a4
TB
a3
1
4
a2
a3
1
a2
a5
4
a5
3
3
Figura 1.1.12


E = 


-1 -1 0 0 0
1 0 -1 -1 0
0 1 1 0 -1
0 0 0 1 1


EB-1 = 


0 1
0 -1
0 0
1 1
1
0
0
1
1
0
1
1
1
0
0
0














EB = 




F = EB-1E = 


-1 0 0
0 -1 0
1 1 -1
0 0 1
1
-1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0






0
0
1
0
0
0
0
1






1.1.6 Algoritmi del simplesso su reti
Algoritmo primale del simplesso su reti
Un algoritmo del simplesso per i problemi di flusso è facilmente descrivibile (vedi figura
1.1.13). La procedura riceve in input una base primale ammissibile e le strutture dati
caratterizzanti l'albero di base (Visita anticipata, Visita posticipata, Predecessore).
20
ROC-00/01 Capitolo 1
Procedure Simplesso_per_flusso(c,u,b,B,L,U,TB,r,Va,Vp,P,x,π):
begin
ottimo := true; Flusso_di_base(u,b,B,L,U,TB,r,Vp,P,x); Potenziale_di_base(c,B,TB,r,Va,P,π);
repeat
Potenziale_Ammissibile(c,L,U,π,k,ottimo);
if not ottimo then
_
begin Trova_Ciclo(u,T
,P,k,z,x,θ
,h,verso);
B
_
_
if θ > 0 then Aggiorna_Flusso(TB,P,verso,k,z,θ,x);
Aggiorna_Potenziale(c,k,h,π,δ); Aggiorna_base(B,L,U,h,k) end
until ottimo
end.
Figura 1.1.13
Esercizio 1.1.7
Proseguire l'applicazione del simplesso per flussi al problema dell'esempio 1.1.3 sino a determinare la soluzione
ottima.
Algoritmo duale del simplesso su reti
Un algoritmo del simplesso per i problemi di potenziale è facilmente descrivibile (vedi figura
1.1.14). La procedura riceve in input una base duale ammissibile e le strutture dati caratterizzanti
l'albero di base (Visita anticipata, Visita posticipata, Predecessore).
Procedure Simplesso_per_potenziale(c,u,b,B,L,U,TB,r,Va,Vp,P,x,π):
begin
ottimo := true; potenziale_illimitato := false;
Flusso_di_base(u,b,B,L,U,TB,r,Vp,P,x); Potenziale_di_base(c,B,TB,r,Va,P,π);
repeat
Flusso_Ammissibile(u,B,x,h,ottimo);
if not ottimo then
begin
_
Trova_delta(c,L,U,h,δ,k,potenziale_illimitato);
if not potenziale_illimitato then _
_
begin Trova_Ciclo(u,T
B,P,k,z,x,θ,h,verso); Aggiorna_Flusso(T
B,P,verso,k,z,θ,x);
_
_
if δ ≠ 0 then Aggiorna_Potenziale(c,k,h,π,δ);
Aggiorna_base(B,L,U,h,k) end
end
until ottimo or potenziale_illimitato
end.
Figura 1.1.14
Esercizio 1.1.8
Proseguire l'esempio 1.1.3 sino a determinare la coppia di soluzioni ottime.
Determinazione di basi ammissibili iniziali
Nel caso di problemi di flusso, la determinazione di una base ammissibile iniziale è facilmente
effettuabile sia per il problema di flusso che per il problema di potenziale.
Una base primale ammissibile, artificiale, è ottenibile ampliando il grafo con un nodo
fittizio n+1 e con n archi fittizi: un arco (i,n+1) per ogni nodo i origine o di trasferimento ed un
arco (n+1,j) per ogni nodo j destinazione. Agli archi del tipo (i,n+1) si attribuisce una capacità
uin+1 = -bi e costo M opportunamente grande mentre per gli archi del tipo (n+1,i) si attribuisce
una capacità un+1j = bj e costo nullo. Gli archi fittizi individuano un albero di copertura per il
problema ampliato; la base (B, L, U) si ottiene ponendo gli indici degli archi del grafo originario
in L, gli indici degli archi fittizi in B e ponendo U= ∅. A (B, L, U) corrisponde un flusso
21
ROC-00/01 Capitolo 1
ammissibile per il problema ampliato. Inoltre se il problema di partenza è non vuoto, allora il
flusso ottimo per il problema ampliato è ammissibile per il problema originario. Altrimenti, se il
problema originario è vuoto, allora il flusso ottimo per il problema ampliato è non nullo in
almeno due archi fittizi.
Esercizio 1.1.9
Scrivere la formulazione del problema ampliato e del suo duale.
La individuazione di una base cui corrisponde un potenziale ammissibile può essere
effettuata senza ampliare il problema, e pertanto senza modificare la struttura del grafo. Infatti,
dato un qualsiasi albero di copertura T B , è immediato determinare una partizione (L, U)
dell'insieme degli indici degli archi fuori base tale che (B,L,U) sia una base duale ammissibile.
_
Infatti è sufficiente calcolare con una visita anticipata su T B il vettore dei potenziali π e,
_
successivamente il vettore dei costi ridotti c . Quindi si assegnano gli indici degli archi fuori base
ad L o ad U in modo che risulti cL ≥ 0 e cU < 0. La base (B,L,U) risultante è duale ammissibile
per costruzione.
Esercizio 1.1.10
Determinare una base duale ammissibile per il problema dell'esempio 1.1.3.
Esercizio 1.1.11
Descrivere una procedura che in O(m) determina un albero di base ed una base duale ammissibile.
22
ROC-00/01 Capitolo 1
1.2 Il problema dei cammini minimi
In questo capitolo approfondiremo alcuni aspetti del problema della determinazione dell'albero
dei cammini minimi essenzialmente per problemi implementativi e per la valutazione della relativa
complessità computazionale. Non ripeteremo quindi quanto riportato negli appunti di Ricerca
Operativa.
Introdurremo inoltre alcune varianti delle condizioni di Bellman per la risoluzione di
problemi di cammino quando la misura del cammino stesso non è necessariamente la somma
delle misure sugli archi.
1.2.1 Formulazione del problema dell'albero dei cammini minimi
Il problema è un particolare problema di flusso dove la radice r è l'unica origine di n-1 unità di
flusso, ciascun altro nodo i essendo destinazione di una unità di flusso. I flussi sugli archi sono
vincolati solo ad essere non negativi (pertanto il problema è a capacità illimitata). Il problema ha
quindi la seguente formulazione:
(1.2.1)
(P) Min cx
Ex = b
x≥ 0
dove b è:

bi = 

-(n-1), se i = r,
1,
altrimenti.
Il duale del problema (P) è:
(1.2.2)
(D) Max πb
πE ≤ c
o, in forma estesa:
(D) Max
∑
πi
i∈N \{r}
- (n-1)πr
πj
- πi
≤ cij,
∀ (i,j) ∈ A
Essendo le righe della matrice di incidenza E linearmente dipendenti, si può porre senza
perdere di generalità πr = 0. Il problema
duale (D) ha una diretta interpretazione in termini di
_
costi dei cammini. Un potenziale π è ammissibile se la differenza di potenziale tra i nodi estremi
_
di ciascun arco non eccede il costo dell'arco stesso. Interpretando la differenza di potenziale πi _
π r come il costo del cammino dalla radice r ad i, l'obiettivo è massimizzare la somma dei costi
degli n-1 cammini da r agli altri nodi sotto il vincolo che la differenza di potenziale tra i nodi
estremi di ciascun arco non ecceda il costo dell'arco stesso.
1.2.2 Le condizioni di Bellman
Si ricorda che il costo C(Pxy) di un cammino Pxy è dato dalla somma dei costi degli archi che
formano il cammino:
C(Pxy) =
∑
ca.
a∈A xy
23
ROC-00/01 Capitolo 1
Senza perdere di generalità si può presupporre che esista almeno un cammino da r a
ciascun altro nodo i.
Sia Tr = (N,Ar) un albero di copertura radicato in r e orientato, cioè gli archi dell'albero
sono tutti orientati dai padri verso i figli; inoltre sia di un valore reale, detto etichetta del nodo i,
che rappresenta un'approssimazione per eccesso del costo dell'unico cammino da r a i in Tr. Le
seguenti condizioni sono dette condizioni di Bellman:
(1.2.3)
di + cij ≥ dj,
∀ (i ,j)∈A.
Si noti che le condizioni di Bellman (1.2.3) non sono altro che i vincoli del problema duale
quando si utilizzano le etichette al posto dei potenziali. Si può dimostrare che la procedura SPT
non è altro che una implementazione efficiente dell'algoritmo del simplesso per la risoluzione
della coppia di problemi (1.2.1) e (1.2.2).
Vale il seguente teorema:
Teorema 1.2.1
Se il grafo G contiene un ciclo negativo, cioè un cammino orientato chiuso il cui costo è
negativo, allora il problema dell'albero dei cammini minimi è mal posto in quanto esistono
cammini (non semplici) il cui costo non è limitato inferiormente.
Nel seguito supporremo che il problema di cammino minimo abbia ottimo, e pertanto che il
grafo sia privo di cicli negativi. L'ipotesi non è restrittiva in quanto, si ricorda, è possibile
verificare in tempo polinomiale se un grafo contiene un ciclo negativo.
1.2.3 Algoritmo SPT
Si riporta qui la procedura SPT (Shortest Path Tree) già descritta negli appunti di
Programmazione Matematica.
Procedure SPT(r, P, d):
begin
for i := 1 to n do begin P[i] := r; d[i] := M end; P[r] := nil; d[r] := 0; Q := {r};
repeat
select u from Q; Q := Q \ {u};
for each (u,v) ∈ FS(u) do
if d[u] + c[u,v] < d[v] then
begin d[v] := d[u] + c[u,v]; P[v] := u;
if v ∉ Q then Q := Q ∪ {v} end
until Q = ø
end.
Figura 1.2.1 - La procedura SPT
La correttezza della procedura è mostrata dal seguente teorema.
Teorema 1.2.2
La procedura SPT è corretta.
Dim.
Mostriamo che essa termina in un numero finito di passi. Ricordiamo che il valore dell'etichetta
del nodo v, dv, è il costo di un cammino del grafo da r a v. Osserviamo inoltre che il nodo v è
inserito in Q quando la sua etichetta dv diminuisce. Poiché il numero di cammini da r a v è finito,
dv può diminuire un numero finito di volte e quindi il nodo v potrà essere inserito in Q un
24
ROC-00/01 Capitolo 1
numero finito di volte. Di conseguenza il ciclo repeat…until è ripetuto un numero finito di volte,
quindi, la procedura termina in un numero finito di passi.
Si noti che, alla generica iterazione k della procedura, può esistere un arco (i,j) con i=p(j)
tale che dj >di + cij. Ciò si verifica quando il nodo i, successivamente alla sua estrazione da Q
che ha determinato l'assegnazione i=p(j), viene inserito nuovamente in Q, poiché la sua etichetta è
stata migliorata. Pertanto, per ogni arco (i,j) dell'albero corrente, vale la condizione dj ≥di + cij.
Mostriamo adesso che al termine della procedura l'albero Tr definito da p(.) è un albero dei
cammini minimi. I nodi i ≠ r tali che di < M sono stati inseriti (almeno una volta) in Q e quindi è
stato individuato almeno un cammino da r a i. Assumiamo che, al termine della procedura, esista
almeno un nodo j tale che dj = M. Allora non esistono cammini di G da r a j di lunghezza
minore di M o, in altre parole, l'unico cammino è rappresentato dall'arco artificiale (r,j). Infatti, se
per assurdo un tale cammino esistesse, allora la procedura a partire da r attribuirebbe al nodo j,
attraverso l'inserimento in Q dei nodi del cammino, una etichetta dj < M. Possiamo quindi
limitarci a considerare il grafo G' = (N', A') di G indotto dai nodi i ∈ N: dj < M; sia T'r l'albero di
G' definito da p(.) applicata ai nodi di N' (T'r è l'albero restituito dalla procedura privato degli
eventuali nodi con etichetta M e degli archi incidenti in tali nodi). Per ogni arco (i,j) dell'albero,
cioè p(j) = i, si ha dj =di + cij, quindi le etichette dei nodi rappresentano i costi dei cammini
dell'albero. Essendo verificate le condizioni di Bellman per tutti gli archi del grafo, non esiste
nessun cammino di costo inferiore al cammino dell'albero da r al nodo i, per ogni i ∈ N'.
Pertanto T'r è l'albero dei cammini minimi di radice r del grafo G'. ♦
Indicate rispettivamente con:
γsel il numero di selezioni di nodi da Q,
γmax il massimo numero di selezioni dello stesso nodo da Q,
γcon il numero di controlli delle condizioni di Bellman, e pertanto il massimo numero di
possibili inserimenti in Q,
si hanno le seguenti condizioni:
- γsel ≤ n γmax,
(ogni nodo selezionato non più di γmax volte),
- γmax ≥ 1,
(ogni nodo selezionato almeno una volta),
- γcon ≤ n γsel,
(num. controlli per selezione = num. archi stella uscente ≤n),
- γcon ≤ m γmax,
(num. controlli per arco = num. selez. del nodo coda ≤γmax),
- γcon ≤ min{nγsel,mγmax}, (dalle due condizioni precedenti).
Supponendo che sia il controllo di appartenenza di un elemento a Q sia il controllo se Q è
vuoto si possono effettuare in tempo O(1), senza fare ulteriori ipotesi sulla scelta implementativa
di Q indichiamo le complessità delle operazioni elementari per la sua gestione, rispettivamente
con:
- qinit la complessità dell'inizializzazione di Q,
- qsel la complessità della selezione e rimozione di un elemento da Q,
- qcon la complessità dell'inserimento di un elemento in Q (e suo eventuale
riordinamento).
Allora la complessità di SPT può essere espressa da:
-
(1.2.4)
-
O(qinit + γsel qsel + γcon qcon).
In generale si possono fare due scelte implementative per l'insieme Q:
la coda di priorità:
(non ordinata, ordinata, parzialmente ordinata),
la lista:
(fila, pila, liste a doppio ingresso).
25
ROC-00/01 Capitolo 1
Studiamo separatamente le due scelte.
1.2.4 Algoritmi a selezione del nodo di etichetta minima (Shortest-first)
L'insieme Q viene implementato come coda di priorità. Ad ogni elemento è cioè associata una
chiave di priorità e le operazioni elementari eseguibili in Q sono:
- inserimento di un elemento con associata chiave di priorità,
- modifica della chiave di priorità di un elemento di Q di cui si conosca la posizione in Q,
- selezione dell'elemento con chiave di priorità migliore e sua rimozione da Q.
Per il problema dell'albero dei cammini minimi la chiave di priorità di un nodo i è l'etichetta
di; l'elemento di priorità migliore è il nodo di etichetta minima:
(1.2.5)
u = argmin{di: i ∈ Q}.
Vale il seguente Teorema di Dijkstra (1959):
Teorema 1.2.3
Se in SPT si implementa Q come coda di priorità e se i costi sono non negativi, allora ogni nodo
verrà inserito in Q (e rimosso da esso) una ed una sola volta.
Dim.
Basta osservare che, essendo i costi non negativi, le etichette dei nodi selezionati durante le varie
iterazioni di SPT formano una sequenza non decrescente; infatti, tutti i nodi inseriti
successivamente all'estrazione di un nodo i avranno un'etichetta ≥ di. Pertanto, affinché il nodo i
sia reinserito in Q a causa della riduzione della propria etichetta, sarebbe necessario che esistesse
un arco incidente in i con costo negativo. Dalla non negatività dei costi segue la tesi. ♦
Corollario 1.2.4
γmax = 1.
Indichiamo con SPT_S le versioni di SPT nelle quali è adottata la selezione del nodo ad
etichetta minima, cioè le versioni in cui Q è implementato come coda di priorità. Dal Corollario
1.2.4 si ha che: γsel = n, γcon = m; pertanto la complessità di SPT_S è:
(1.2.6)
O(qinit + n qsel + m qcon).
Osservazione 1.2.1 Se si hanno costi negativi, si ha γcon = O(2n ), γsel = O(2n ) [D.B. Johnson, 1973].
Studiamo ora due realizzazioni della coda di priorità Q: la lista non ordinata e lo heap
binario, già presentate nel corso di Programmazione Matematica.
Algoritmo SPT_S_Dijkstra
La coda di priorità Q è realizzata mediante una lista non ordinata (ad
vettore a puntatori); le operazioni elementari comportano:
- inizializzazione della lista Q con la sola radice r:
- selezione del nodo di etichetta minima: scansione della lista Q
- rimozione del nodo di etichetta minima selezionato
- inserzione di un nodo (ad esempio, in testa) o modifica dell'etichetta
pertanto si ha: qinit = O(n), qsel = O(n), qcon = O(1).
esempio mediante un
⇒ O(n),
⇒ O(n),
⇒ O(1),
⇒ O(1);
Corollario 1.2.5
La procedura SPT_S_Dijkstra, su grafi con costi non negativi, ha complessità O(n 2).
26
ROC-00/01 Capitolo 1
Algoritmo SPT_S_heap
La coda di priorità Q è realizzata mediante un heap binario con dizionario; le operazioni
elementari comportano:
- inizializzazione dello heap Q con la sola radice r
⇒ O(n),
- selezione del nodo di etichetta minima: la radice dello heap Q
⇒ O(1),
- rimozione del nodo radice dello heap Q e riordinamento di Q
⇒ O(logn),
- inserzione di un nodo o modifica dell'etichetta
⇒ O(logn);
pertanto si ha: qinit = O(n), qsel = O(logn), qcon = O(logn).
Corollario 1.2.6
La procedura SPT_S_heap, su grafi con costi non negativi, ha complessità O(mlogn).
1.2.5 Algoritmi a selezione su lista (List search)
L'insieme Q viene implementato come una lista, cioè una sequenza di elementi su cui possono
essere effettuate operazioni di rimozione ed inserzione alle estremità della sequenza, chiamate
rispettivamente testa e coda della lista. Si distinguono diversi tipi di liste:
- la fila:
l'inserzione viene effettuata in coda e la rimozione dalla testa (regola FIFO);
- la pila: l'inserzione e la rimozione vengono effettuate in testa (regola LIFO);
- la deque (double-ended queue) o lista a doppio ingresso: l'inserzione viene effettuata sia
in testa sia in coda e la rimozione solo dalla testa.
Le operazioni elementari sulle liste sono:
- inserimento di un elemento come nuova testa della lista,
- inserimento di un elemento come nuova coda della lista,
- rimozione dell'elemento testa dalla lista.
Le liste possono essere realizzate in diversi modi (liste a puntatori, vettori di puntatori,
lineari o circolari, semplici o doppie, ecc.). È sempre possibile realizzare una lista in modo tale
che le operazioni elementari e le operazioni di controllo di appartenenza di un elemento alla lista
e di controllo se la lista è vuota abbiano tutte complessità costante: O(1).
Indichiamo con SPT_L le versioni di SPT nelle quali l'insieme Q è implementato come
lista. Dalla formula di complessità per SPT (1.2.4) si ha che: qinit = O(n), qsel = O(1), qcon =
O(1); pertanto la complessità di SPT_L, anche nel caso di costi negativi è:
(1.2.7)
O(n + γsel + γcon) = O(γcon).
Q può essere realizzata mediante un vettore circolare di puntatori Q[.], ad n+1 componenti;
Q[n+1] punta al primo elemento della lista Q. Inoltre, il puntatore last individua l'elemento di
coda di Q (Q = Ø ⇒ last = n+1 e Q[n+1] = n+1).:
 j,
se j segue i in Q,

se i ∉ Q,
Q[i] =  0,
n+1, se i è l'ultimo elemento di Q.
-
Le operazioni elementari di gestione di Q sono realizzate nel seguente modo:
inizializzazione (Q := {r}):
for i := 1 to n do Q[i] := 0; Q[n+1] := last := r; Q[r] := n+1;
controllo se j ∉ Q :
if Q[j] = 0 then… ;
controllo se Q = Ø:
if last = n+1 then… ;
inserimento di j in coda a Q :
Q[last] := j; Q[j] := n+1; last := j;
inserimento di j in testa a Q :
Q[j] := Q[n+1]; Q[n+1] := j; if last = n+1 then last := j;
27
ROC-00/01 Capitolo 1
-
rimozione di i dalla testa di Q :
i := Q[n+1]; Q[n+1] := Q[i]; Q[i] := 0;
if last = i then last := n+1;
Studiamo ora tre diverse realizzazioni della lista Q: la fila o queue, la lista a doppio
ingresso o deque ed una trasformazione della deque detta 2queue.
Algoritmo SPT_L_queue
La lista Q è realizzata mediante una fila: l'inserzione dei nodi avviene in coda e la rimozione dalla
testa (regola FIFO); si noti che l'aggiornamento dell'etichetta di un nodo appartenente a Q non
influisce sulla posizione dell'elemento nella fila. Analizziamo la complessità di SPT_L_queue; si
può dimostrare che la particolare struttura della fila garantisce che, in assenza di cicli negativi,
nessun nodo sarà inserito più di n-1 volte in Q. Pertanto:
Teorema 1.2.7
La procedura SPT_L_queue ha complessità O(m n).
Dim.
Da quanto appena affermato si ha γmax ≤ n. Quindi γsel ≤ n 2 e γcon ≤ min{nγsel,mγmax } ≤
min{n3,mn} = mn. Dalla (1.2.7) segue la tesi.♦
Osservazione 1.2.2
La procedura SPT_L_queue può essere utilizzata per controllare se un grafo orientato possiede cicli negativi.
Infatti per il teorema 1.2.7 è sufficiente contare le iterazioni eseguite: se dopo n(n-1)/2+1 iterazioni Q risulta non
vuota, allora tutti i nodi presenti in Q appartengono a cicli di costo negativo.
La limitazione discende dal fatto che se si ottenesse un albero Tr dei cammini minimi ogni nodo i sarebbe
estratto da Q non più di γ i-1 volte, dove γ i è il livello di i su T r , salvo per la radice per cui γ r =1. Nel caso
peggiore si ha Tr formato da un cammino con un nodo per ogni livello j=0,1,...,n-1; pertanto si ha
Σ i∈N γi
≤
n(n-1)
+ 1.
2
Algoritmo SPT_L_deque
La lista Q è realizzata mediante una lista a doppio ingresso, o deque; i nodi vengono inseriti in
coda la prima volta (cioè quando l'etichetta scende dal valore M ad un valore finito) ed in testa le
volte successive; la rimozione avviene dalla testa. Questa politica differenziata di inserzione è
dovuta alla seguente osservazione; quando l'etichetta di un nodo i già esaminato viene
ulteriormente migliorata, non sono stati effettuati miglioramenti per le etichette dei nodi
discendenti di i nell'albero corrente: essi pertanto hanno un'etichetta strettamente superiore al
costo del cammino corrente, si inserisce pertanto il nodo i in testa al fine di anticipare la sua
selezione da Q e quindi la correzione delle etichette dei discendenti. Si ottiene pertanto una
politica ibrida LIFO-FIFO.
Si noti che la lista Q può essere interpretata come una coppia di liste Q' e Q" connesse in
serie, vedi figura 1.2.2; Q' conterrà solo i nodi reinseriti in Q mentre Q" conterrà solo i nodi
inseriti per la prima volta in Q.
Q'
Q"
last
Figura 1.2.2
Si rimuoverà il nodo testa di Q" solo se Q'=Ø, pertanto Q' è una pila (stack) e Q" è una
fila (queue). Si può dimostrare che il numero di inserimenti in Q' è esponenziale, cioè che:
28
ROC-00/01 Capitolo 1
γsel = O(2n) e γcon = O(n2n).
Teorema 1.2.8
La procedura SPT_L_deque ha complessità O(n2n).
È possibile riorganizzare Q affinché Q' sia implementata come fila; basta infatti mantenere
un puntatore all'ultimo elemento della porzione Q' di Q, vedi figura 1.2.3. I nodi verranno
inseriti, la prima volta, in coda a Q" (che coincide con la coda di Q), le altre volte in coda a Q'. La
struttura è conosciuta come doppia coda (o 2queue).
Q'
Q"
last of Q'
last of Q"
Figura 1.2.3
Si può dimostrare che il massimo numero di inserimenti dello stesso nodo in Q' è:
γmax = O(n2) e γcon = O(m.n2).
Teorema 1.2.9
La procedura SPT_L_2queue ha complessità O(m.n2).
L'importanza dell'algoritmo SPT_L_deque risiede nel fatto che, pur se la complessità
computazionale nel caso peggiore è esponenziale, su grafi sparsi ha una efficienza
computazionale migliore di molti algoritmi polinomiali. L'algoritmo SPT_L_2queue ha le stesse
prestazioni sperimentali di SPT_L_deque pur avendo una complessità polinomiale.
Nella letteratura scientifica degli ultimi venti anni si possono trovare migliaia di versioni
diverse di algoritmi per il problema dell'albero dei cammini minimi. La maggior parte di essi
sono semplici realizzazioni dell'algoritmo SPT nelle due possibili classi SPT_S e SPT_L; le
maggiori differenze risiedono nel tipo di strutture di dati che vengono utilizzate per realizzare
l'insieme (lista o coda di priorità) Q.
1.2.6 Un algoritmo distribuito per il calcolo dei cammini minimi
Il seguente sistema è conosciuto come equazioni di Bellman:
(1.2.8)
 0,
se j = r,
+c
:
(i,j)
∈
BS(j)},
altrimenti.
min{d

i ij
dj = 
È facilmente dimostrabile che se il grafo è privo di cicli negativi o nulli, la soluzione del
sistema (1.2.8) fornisce i costi minimi dei cammini; inoltre, si possono scegliere gli archi che
forniscono i valori minimi in modo opportuno affinché formino un albero di cammini minimi.
(1)
(1)
Sia d(k)
i il valore dell'etichetta del nodo i all'iterazione k (inizialmente si ha d r = 0 e d i =
M, per ogni i ≠ r); Il processo iterativo dovuto alle equazioni di Bellman è dato, per ogni j ≠ r da:
(1.2.9)
(k)
d(k+1)
j = min{d i +cij: (i,j) ∈ BS(j)};
quando k=n-1 si ha la soluzione delle equazioni (1.2.8). Il processo iterativo si può arrestare
appena si ha, per un k qualsiasi che d(k+1) = d(k).
29
ROC-00/01 Capitolo 1
Le (1.2.9) suggeriscono una computazione parallela di tipo sincrono in cui l'etichetta di
ogni nodo viene calcolata separatamente dalle altre. In generale gli algoritmi di tipo sincrono
sono abbastanza inefficienti e richiedono un coordinamento temporale tra processori per lo
scambio delle informazioni (nel nostro caso il nuovo stato delle etichette).
È possibile organizzare, in modo molto semplice un calcolo distribuito e asincrono dei
cammini minimi. Si supponga di avere a disposizione un processore per ogni nodo del grafo; il
processore P(i), associato al nodo i ∈ N, conosce la porzione di grafo relativa alla BS(i) con i
relativi costi, ed è in comunicazione con tutti i nodi j immediati successori di i stesso, cioè i nodi
terminali degli archi della FS(i).
Inizialmente di = M e il processore P(i) è inattivo, salvo per il processore P(r) che è attivo e
per il quale si ha dr = 0. Il processore P(r) attivo non fa altro che inviare il messaggio <r,dr> ai
processori associati ai suoi immediati successori e si disattiva (si noti che P(r) ha finito la sua
computazione e non si riattiverà più).
Quando un processore P(j) riceve un messaggio <i,di> da un processore P(i), blocca la
coda di arrivo dei messaggi e effettua il normale controllo di rispetto della condizione di
Bellman: se essa è rispettata, il processore riattiva la coda dei messaggi per recepirne, se c'è, uno
nuovo. Se invece si ha che d j > d i+cij, allora pone d j := d i+cij, p j := i e riattiva la coda dei
messaggi.
Appena la coda dei messaggi è vuota, P(j), se ha effettuato almeno un cambiamento di
etichetta, invia il messaggio <j,dj> a tutti i processori associati ai suoi immediati successori e si
disattiva; altrimenti si disattiva senza alcun invio di messaggi.
Pertanto, l'algoritmo associato al processore P(j) può essere riassunto come:
Procedure Distributed_SP_for_j:
begin
if messagequeue ≠ Ø then
begin flag := false;
repeat
select&remove <i,d[i]> from messagequeue;
if d[i] + c[i,j] < d[j] then begin d[j] := d[i] + c[i,j]; P[j] := i; flag := true end
until messagequeue = Ø;
if flag then for each (j,h) ∈ FS(j) do sendmessage(P(h),<j,d[j]>) end
end.
Figura 1.2.4 - La procedura Distributed_SP
Al termine, un processore centrale raccoglie i dati relativi all'etichetta e al predecessore di
ciascun nodo per fornire l'albero dei cammini minimi e i relativi costi minimi.
Temi per progetti
Sono a disposizione i seguenti temi.
- Utilizzo dei costi ridotti nella riottimizzazione di cammini minimi;
- Cammini minimi in reti dinamiche;
- Buckets, Radix heaps e Fibonacci heaps per la classe SPT_S;
- Valori soglia, riordinamenti parziali e altre politiche di inserzione per la classe SPT_L.
30