Cammini di costo minimo Flashcards
Definisci il problema del cammino minimo da r a t su un grafo orientato e pesato G = (N, A) dove ad ogni arco è associato un costo cij
Per ogni cammino P in G il costo C(P) è dato dalla somma dei costi degli archi che lo costituiscono. Il problema del cammino minimo vuole minimizzare il costo di ciascuno dei cammini che dalla radice vanno agli altri nodi.
Il problema dei cammini minimi può essere inferiormente illimitato?
Sì, succede quando nel grafo esiste un ciclo di costo negativo.
Esprimi il problema dei cammini minimi in termini di alberi.
Il problema SPT (Shortest Path Tree) consiste nel determinare in G un albero dei cammini minimi.
Nel problema dell’albero di cammini minimi, cosa rappresenta il vettore d?
E’ un vettore di etichette di nodi, d, che rappresenta il costo del cammino nell’albero dalla radice ad ogni singolo nodo.
Come trovare il vettore d nel problema dei cammini minimi?
Si può trovare facilmente attraverso una procedura di visita dell’albero a partire dalla radice.
Quali sono le condizioni di Bellman?
di + cij >= dj, per ogni nodo del grafo.
Se il vettore di etichette dei nodi verifica le condizioni di Bellman,
allora di è una valutazione inferiore del costo del cammino minimo da r a i.
T è un albero dei cammini minimi di radice r se e solo se…
il suo d verifica le condizioni di Bellman
Quali sono i passi dell’algoritmo SPT?
Mediante una visita del grafo si determina un albero di copertura radicato in r, e le relative etichette d.
Si controlla se esiste un arco (i, j) nel grafo originale che non soddisfa le condizioni di Bellman. Se esiste, si inserisce l’arco, nell’albero. Se non esiste abbiamo dimostrato che l’albero è ottimo.
L’algoritmo SPT è un algoritmo di…
ricerca locale
In quali modi si può implementare l’algoritmo SPT?
Q può essere implementato come coda di priorità o come lista.
Cosa è una coda di priorità?
E’ un insieme in cui ogni elemento ha associato uun valore (chiave) e la scelta dell’elemento da estrarre avviene sulla base di questo valore.
Cosa vuol dire quando Q è implementato come una lista?
In una lista, la scelta dell’elemento da estrarre dipende dalla posizione dell’elemento nella lista.
Come si implementa SPT con Q coda di priorità?
La chiave di priorità è il vettore delle etichette d, e la priorità cresce al decrescere di di.
SPT.S
SPT.S è la versione di SPT in cui ad ogni iterazione si estrae da Q l’elemento di etichetta minima. S sta per shortest first, e viene implementato con coda di priorità.
L’algoritmo SPT.S, a code di priorità, o algoritmo di Dijkstra…
ha un funzionamento per cui ogni nodo verrà inserito in Q al più una volta, purché non ci siano costi negativi. Pertanto ha complessità polinomiale.
L’algoritmo di Dijkstra, o SPT.S, a coda di priorità ha complessità esponenziale…
solo se ci sono archi di costo negativo.
Gli algoritmi SPT in cui Q viene implementato come una lista sono detti SPT.L. In questi algoritmi…
L’inserimento può avvenire in testa o in coda, ma la rimozione può avvenire solo in testa.
Quali tipi di liste ci sono?
fila (FIFO), o queue, l’inserzione avviene in coda e la rimozione in testa.
pila (LIFO), o stack, l’inserzione e la rimozione vengono effettuate in testa.
deque, lista a doppio ingresso.
