Flusso di costo minimo Flashcards
Descrivi il problema di flusso di costo minimo…
Data una rete, vogliamo trovare il flusso che costa di meno, soddisfando i bilanciamenti e rispettando le capacità degli archi.
Cosa è uno pseudoflusso?
E’ un vettore x che rispetta tutti i vincoli di capacità sugli archi.
Definiamo lo sbilanciamento di un nodo i rispetto ad x
la differenza tra il flusso entrante e il flusso uscente, meno il bilancio del nodo i.
Dx e Ox sono rispettivamente
L’insieme di tutti i nodi con eccedenza di flusso e di tutti i nodi con difetto di flusso.
Se non ci sono nodi sbilanciati,
allora il vettore x rispetta i vincoli di conservazione del flusso ed è pertanto un flusso ammissibile.
Lo sbilanciamento complessivo di uno pseudoflusso è
la somma degli sbilanciamenti di tutti i nodi con eccedenza di flusso, che è uguale alla somma degli sbilanciamenti dei nodi con difetto di flusso.
Inviare flusso lungo un cammino aumentante modifica
solamente il bilancio degli estremi, mentre lo sbilanciamento di tutti gli altri nodi rimane invariato.
Uno pseudoflusso è minimale se
è lo pseudoflusso di costo minimo tra quelli con lo stesso sbilanciamento.
Se uno pseudoflusso è minimale e ammissibile
allora è ottimo
Uno pseudoflusso minimale
non ammette cicli aumentanti di costo negativo.
La capacità di un cammino è
la minima capacità degli archi di P nel grafo residuo
Costo di un cammino
La somma dei costi degli archi del cammino nel grafo residuo
Ciclo aumentante
ciclo orientato nel grafo residuo
Algoritmo dei cammini minimi successivi
init: x pseudoflusso minimale
2) ricerca di un cammino aumentante di costo minimo
3) Se esiste stop
4) Altrimenti aumentare di theta unità il flusso lungo il cammino trovato.
3) Iterare
Complessità dell’algoritmo dei cammini minimi
Avviene un SPT.L Bellman-Ford per iterazione, e il numero massimo di iterazioni è lo sbilanciamento complessivo, quindi O(gmn) dove g è lo sbilanciamento.
L’algoritmo dei cammini minimi successivi…
mantiene ad ogni passo uno pseudoflusso minimale x, e determina un cammino aumentante di costo minimo tra un nodo s e un nodo t, per diminuire, al minor costo possibile, lo sbilanciamento di x.
L’uso di cammini aumentanti di costo minimo nei cammini minimi successivi mantiene la proprietà di
minimalità degli pseudoflussi.
Nel flusso di costo minimo, theta rappresenta
la maggiore diminuzione possibile dello sbilanciamento complessivo corrispondente al cammino P e allo pseudoflusso x.
Lo sbilanciamento e(i) di un nodo è
Il flusso che esce, meno il flusso che entra, meno il suo bilancio.
Se uno vuole ridurre lo sbilanciamento…
deve spedire il flusso da un nodo che ha eccesso ad un nodo che ha difetto.
