|
|
Dato un grafo orientato G = (N,A) con pesi cij sugli archi (i,j) appartenenti ad A, e dato un nodo r appartenete a N trovare un cammino da r a u, per ogni nodo u appartenente a N, tale che la somma dei pesi sugli archi del cammino sia la più piccola possibile. Il concetto di “peso” cij modella, generalmente, distanze o lunghezze tra punti diversi di una rete. Denoteremo con: Pru, un cammino dal nodo r al nodo u e con C(Pru), il costo del cammino Pru che sarà:
Vediamo un esempio:
Una soluzione ammissibile per SPT è sicuramente composta da n-1cammini da r a u. Affinché esista almeno una soluzione ammissibile, occorre che ogni nodo u sia raggiungibile da r con un cammino. Si osserva che in presenza di cicli di costo negativo (poiché sono ammesse lunghezze negative), la soluzione non potrebbe avere una soluzione ottima. In tal caso infatti, la lunghezza minima di un qualsiasi cammino che includa un nodo di tale ciclo non sarebbe inferiormente limitata (il che va contro la definizione di algoritmi ottimi). Occorre quindi che non esistano cicli di lunghezza negativa. Si noti inoltre che due cammini differenti possono coincidere nella loro parte iniziale dal nodo r. Viceversa, non possono coincidere nella parte finale: se così fosse esisterebbero due cammini distinti che raggiungono gli stessi nodi, mentre il problema ne richiede uno solo. Pertanto, una soluzione ammissibile è un albero di copertura T di G, radicato in r, che include un cammino da r ad u. Introduciamo un’etichetta du sul generico nodo u appartenete a N, in modo che du indichi la distanza di u dal nodo r in T.
Il teorema di Bellman afferma che una soluzione ammissibile T è ottima se e solo se per ogni arco (i,j) appartenete ad A valgono le seguenti condizioni :
Si dimostra che se T è albero ottimo allora valgono (a) e (b). Supponiamo, per assurdo, che (b) non sia vera, allora esiste un cammino alternativo a quello in T che arriva nel nodo j con costo inferiore a dj. Il Teorema di Bellman ci fornisce una caratterizzazione matematica della soluzione e permette la formulazione di un algoritmo per la soluzione di SPT. Lo schema di algoritmo si basa sulla verifica, arco per arco, delle condizioni di Bellman, con conseguente sostituzione degli archi che violano le condizioni.
Passo cruciale dell’algoritmo è quindi la selezione dell’arco (i,j) che viola le condizioni di Bellman. Questo può essere fatto con l’impiego di un insieme S di nodi inizializato ad r (inizialmente contiene solo r). Al generico passo, si estrae u appartenente a S e si visitano tutti gli archi (u,v) con v appartenete all’ insieme di adiacenza A(u), verificando l’eventuale violazione. Per ogni arco (u,v) che viola le condizioni, si aggiorna l’etichetta dv perché migliorata e v viene inserito in S. Rappresentiamo la soluzione T come un albero dei padri. In linguaggio C avremo qualcosa di questo tipo:
T è inizializato ad un albero fittizio con tutti i nodi figli della radice r. Le etichette du sono inizializate a valori molto alti, ad esempio il massimo int. La procedura appena presentata è corretta e risolve il problema di SPT, ma non è però efficiente. La sua efficienza dipende essenzialmente dal numero massimo di inserzioni del medesimo nodo in S e dal numero massimo di miglioramenti delle distanze. Per ottenere una procedura efficiente, non basta che la struttura dati S utilizza sia un generico “insieme” con un’ altrettanto generica operazione “leggi”, ma occorre specializzarla ulteriormente. Se l’insieme S è una coda di priorità realizzata come una lista non ordinata, si ottiene l’algoritmo di Dijkstra (1959). Se l’insieme S è una coda di priorità realizzata con uno heap, si ottiene l’algoritmo di Johnson (1977). Se l’insieme S è una coda, si ottiene un algoritmo di complessità polinomiale. Se l’insieme S è una pila, la complessità dell’algoritmo diventa superpolinomiale (vedi cammino minimo con coda e con pila). Per saperne di più consultai seguenti approfondimenti:
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.