[Algoritmi] esericizio cammini minimi
Salve a tutti,
è la prima volta scrivo qui ma sono in difficoltà con l'esame di ASD che devo dare a breve.
Devo rispondere a questa domanda usando non gli algoritmi standard (sul mio testo ho trovato gli algoritmi e gli ho capiti) ma usando la programmazione dinamica.
Il testo recita
Studiando ho capito che:
è la prima volta scrivo qui ma sono in difficoltà con l'esame di ASD che devo dare a breve.
Devo rispondere a questa domanda usando non gli algoritmi standard (sul mio testo ho trovato gli algoritmi e gli ho capiti) ma usando la programmazione dinamica.
Il testo recita
Illustrare e discutere l’algoritmo noto per costruire i cammini minimi tra tutte le coppie di vertici di un grafo orientato e pesato.
Studiando ho capito che:
[*:37vzrep3] Devo trovare la matrice dei pesi W[/*:m:37vzrep3]
[*:37vzrep3] Data questa matrice devo calcolare le matrici da 0 a m -1 dove m -1 è m è il numero di nodi[/*:m:37vzrep3]
[*:37vzrep3] Queste matrici le calcolando andando facendo moltiplicazioni tra matrici[/*:m:37vzrep3][/list:u:37vzrep3]
Ho un esercizio sul libro svolto ma non riesco a capire come effettuare le molitplicazioni tra matrici (ho visto la regola riga per colonna ma non ridà!) e soprattutto come moltiplicare i simboli (tra loro e con un numero) che inserisco quando non c'è un nodo tra due archi e quindi non ho un penso da scrivere.
Ho cercato online ma invano. Mi servirebbe capire come svolgere questa tipologia di esercizio.
Grazieee
Mi sapete aiutare?
Risposte
Ciao mattiadj 
Innanzitutto scusa il ritardo nella risposta, spero di essere ancora in tempo per aiutarti nella preparazione dell'esame. L'algoritmo che mi stai descrivendo è quello di Floyd-Warshall immagino. Questo ha complessità pari a $O(n^4)$, dove $n$ è il numero di vertici del grafo o (in maniera del tutto equivalente) il numero di righe/colonne della matrice dei pesi $W$. Il prodotto tra matrici è il classico prodotto righe per colonne e le condizioni per farlo relativamente al numero di righe/colonne della matrice sono banalmente rispettate avendo a che fare con una matrice quadrata. La complessità dell'algoritmo può essere ridotta, come credo tu abbia visto, mediante la tecnica della quadratura ripetuta (ed in tal caso se non ricordo male arriva ad essere $O(n^2)$).
Quello che non ho capito è i simboli di cui parli nel caso non vi siano archi tra un vertice e l'altro: in tal caso il peso sull'arco è banalmente zero e pertanto tale valore lo dovrai inserire nella cella della matrice corrispondente.
Innanzitutto scusa il ritardo nella risposta, spero di essere ancora in tempo per aiutarti nella preparazione dell'esame. L'algoritmo che mi stai descrivendo è quello di Floyd-Warshall immagino. Questo ha complessità pari a $O(n^4)$, dove $n$ è il numero di vertici del grafo o (in maniera del tutto equivalente) il numero di righe/colonne della matrice dei pesi $W$. Il prodotto tra matrici è il classico prodotto righe per colonne e le condizioni per farlo relativamente al numero di righe/colonne della matrice sono banalmente rispettate avendo a che fare con una matrice quadrata. La complessità dell'algoritmo può essere ridotta, come credo tu abbia visto, mediante la tecnica della quadratura ripetuta (ed in tal caso se non ricordo male arriva ad essere $O(n^2)$).
Quello che non ho capito è i simboli di cui parli nel caso non vi siano archi tra un vertice e l'altro: in tal caso il peso sull'arco è banalmente zero e pertanto tale valore lo dovrai inserire nella cella della matrice corrispondente.
Ti ringrazio per la risposta e si mi serve ancora aiuto.
Ciò che dici tu è ovviamente giusto ma io non devo usare quell'algoritmo, devo usare la programmazione dinamica.
Nello specifico ti allego ciò che ormai mi sta facendo dannare da giorni. Non riesco a capire come vengono generate le matrici da L2 a L4 dell'immagine che allego!
L1 = W dove W è la matrice di adiacenza del grafo pesato sopra rappresentato . W e L1 mi sono chiarissimi ma...da L2 a L4 come ci arrivo??? Ho seguito alla lettera il codice dell'algoritmo ESP che ti riporto in cima ma senza successo.
Puoi dirmi come arrivarci passo passo dicendomi come se stessi parlando a un deficiente
come ricavare i ckij? (nel forum cosa devo usare per scrivere bene ckij??)
Grazie
Ciò che dici tu è ovviamente giusto ma io non devo usare quell'algoritmo, devo usare la programmazione dinamica.
Nello specifico ti allego ciò che ormai mi sta facendo dannare da giorni. Non riesco a capire come vengono generate le matrici da L2 a L4 dell'immagine che allego!
L1 = W dove W è la matrice di adiacenza del grafo pesato sopra rappresentato . W e L1 mi sono chiarissimi ma...da L2 a L4 come ci arrivo??? Ho seguito alla lettera il codice dell'algoritmo ESP che ti riporto in cima ma senza successo.
Puoi dirmi come arrivarci passo passo dicendomi come se stessi parlando a un deficiente
come ricavare i ckij? (nel forum cosa devo usare per scrivere bene ckij??)Grazie
Sì, quello della programmazione dinamica è un algoritmo alternativo a quello di Floyd-Warshall, seppur meno performante. In realtà per determinare i valori dei vari elementi della matrice basta che segui passo passo l'algoritmo. Considera che devi ragionare come se stessi eseguendo un prodotto righe per colonne solo che anziché sommare i prodotti parziali tra gli elementi considerati determini di volta in volta le somme degli elementi delle matrici che stai scorrendo (ovviamente in base a riga e colonna correnti) ed il minimo di queste somme andrà a sostituire l'elemento corrente nella matrice risultante. In pratica l'operazione di prodotto che esegui nel prodotto righe per colonne diventa una somma e l'operazione di somma (nel prodotto righe per colonne) diventa il minimo (inteso sempre come operazione ovviamente).
Giusto per darti un'idea perché l'elemento $L_{13}^{(3)}$ diventa $-3$
In tal caso devi considerare la riga $1$ di $L^{(2)}$, ossia $(0, 3, 8, 2, -4)$ e la colonna $3$ di $L^{(1)} = W$, ossia $(8, \infty, 0, -5, \infty)$. Se esegui le somme di tali valori ottieni: $(8, \infty, 8, -3, \infty)$. Chiaramente il valore minimo è $-3$ che va riportato come elemento di $L^{(3)}$ in posizione $(1, 3)$.
Ovviamente ci sono dei trucchi per stare prima nel determinare le varie matrici, ad esempio avrai notato come gli elementi nella diagonale principale hanno sempre valori tali a $0$ per ovvie ragioni e pertanto qui non occorre perdere tempo con i calcoli.
Per scrivere $c_{ij}$ con il LaTeX (così come lo vedi qui) nei post in modo da visualizzare la formula in modo più ordinato il codice è:
Giusto per darti un'idea perché l'elemento $L_{13}^{(3)}$ diventa $-3$
In tal caso devi considerare la riga $1$ di $L^{(2)}$, ossia $(0, 3, 8, 2, -4)$ e la colonna $3$ di $L^{(1)} = W$, ossia $(8, \infty, 0, -5, \infty)$. Se esegui le somme di tali valori ottieni: $(8, \infty, 8, -3, \infty)$. Chiaramente il valore minimo è $-3$ che va riportato come elemento di $L^{(3)}$ in posizione $(1, 3)$.Ovviamente ci sono dei trucchi per stare prima nel determinare le varie matrici, ad esempio avrai notato come gli elementi nella diagonale principale hanno sempre valori tali a $0$ per ovvie ragioni e pertanto qui non occorre perdere tempo con i calcoli.
Per scrivere $c_{ij}$ con il LaTeX (così come lo vedi qui) nei post in modo da visualizzare la formula in modo più ordinato il codice è:
$c_{ij}$.
Ti ringrazio infinitamente e forse ho capito ma per es se voglio calcolare C1,4 di L2 ?
Poi quando dici
Devo considerare la riga 1 di L2 e colonna 3 di W perchè sto considerando L(3)1,3? Cioè 1 mi indica la riga e 3 la colonna?
Perchè scegli proprio la riga 1 e la colonna 3?
Tornado al mio esempio e seguendo la tua procedura. Se io voglio capire perchè L(2)1,4 = 2 faccio la somma tra:
- la riga 1 di L1 cioè (0 3 8 inf -4)
- la colonna 4 di W cioè (inf 1 inf 0 6)
Ma facendo questa somma mi viene (inf 4 8 inf 2) e quindi ho inf (il min tra inf e inf è inf!) e non 2!!
O anche se voglio sapere perchè L(3)2,5 = -1 io sommo:
- la riga 2 di L(2) cioè (3 0 -4 1 7)
- la colonna 5 di W cioè (-4 7 inf inf 0)
e il risultato è (-1 7 inf inf 7) ed anche qui dovrei confrontare il min tra 1 e inf che 1 e non -1!!!
Cosa sto sbagliando?
ps: scusa se non uso LaTex ma ancora capisco bene come usarlo in verità non ho neanche guardato bene perchè sto cercando di capire questo esercizio!
Ti ringrazio!
Poi quando dici
In tal caso devi considerare la riga 1 di L(2), ossia (0,3,8,2,−4) e la colonna 3 di L(1)=W, ossia (8,∞,0,−5,∞). Se esegui le somme di tali valori ottieni: (8,∞,8,−3,∞). Chiaramente il valore minimo è −3 che va riportato come elemento di L(3) in posizione (1,3).
Devo considerare la riga 1 di L2 e colonna 3 di W perchè sto considerando L(3)1,3? Cioè 1 mi indica la riga e 3 la colonna?
Perchè scegli proprio la riga 1 e la colonna 3?
Tornado al mio esempio e seguendo la tua procedura. Se io voglio capire perchè L(2)1,4 = 2 faccio la somma tra:
- la riga 1 di L1 cioè (0 3 8 inf -4)
- la colonna 4 di W cioè (inf 1 inf 0 6)
Ma facendo questa somma mi viene (inf 4 8 inf 2) e quindi ho inf (il min tra inf e inf è inf!) e non 2!!
O anche se voglio sapere perchè L(3)2,5 = -1 io sommo:
- la riga 2 di L(2) cioè (3 0 -4 1 7)
- la colonna 5 di W cioè (-4 7 inf inf 0)
e il risultato è (-1 7 inf inf 7) ed anche qui dovrei confrontare il min tra 1 e inf che 1 e non -1!!!
Cosa sto sbagliando?
ps: scusa se non uso LaTex ma ancora capisco bene come usarlo in verità non ho neanche guardato bene perchè sto cercando di capire questo esercizio!
Ti ringrazio!
"mattiadj":
Ti ringrazio infinitamente e forse ho capito ma per es se voglio calcolare C1,4 di L2 ?
[...]
Procedimento del tutto analogo. Con $L^{(2)}$ è più semplice perché basta che "moltiplichi" $L^{(1)}$ per sé stessa (che di fatto corrisponde esattamente a $W$). Io ora ho scritto per semplicità moltiplichi ma ricordiamoci che non è una vera moltiplicazione tra matrici poiché si effettuano le operazioni di somma e minimo come ti ho descritto in precedenza. Per l'elemento $C_{14}$ di $L^{(2)}$ dovrai considerare la prima riga di $L^{(1)}$ e la quarta colonna di $L^{(1)}$ (in questo caso le matrici che consideri solo le medesime ma non negli altri per ovvi motivi).
"mattiadj":
[...]
Poi quando dici
In tal caso devi considerare la riga 1 di L(2), ossia (0,3,8,2,−4) e la colonna 3 di L(1)=W, ossia (8,∞,0,−5,∞). Se esegui le somme di tali valori ottieni: (8,∞,8,−3,∞). Chiaramente il valore minimo è −3 che va riportato come elemento di L(3) in posizione (1,3).
Devo considerare la riga 1 di L2 e colonna 3 di W perchè sto considerando L(3)1,3? Cioè 1 mi indica la riga e 3 la colonna?
Perchè scegli proprio la riga 1 e la colonna 3?
Esattamente, gli indici ti dicono quali righe delle rispettive matrici (dove la prima è sempre quella che hai appena determinato e la seconda $W = L^{(1)}$) devi considerare.
"mattiadj":
[...]
Tornado al mio esempio e seguendo la tua procedura. Se io voglio capire perchè L(2)1,4 = 2 faccio la somma tra:
- la riga 1 di L1 cioè (0 3 8 inf -4)
- la colonna 4 di W cioè (inf 1 inf 0 6)
Ma facendo questa somma mi viene (inf 4 8 inf 2) e quindi ho inf (il min tra inf e inf è inf!) e non 2!!
[...]
No, perché
Il minimo tra $(\infty, 4, 8, \infty, 2)$ sarà $2$, no Il minimo tra $\infty$ ed una qualsiasi numero reale (nella fattispecie intero) sarà l'intero stesso, no Poi tra gli interi scegli quello con valore minimo..."mattiadj":
[...]
O anche se voglio sapere perchè L(3)2,5 = -1 io sommo:
- la riga 2 di L(2) cioè (3 0 -4 1 7)
- la colonna 5 di W cioè (-4 7 inf inf 0)
e il risultato è (-1 7 inf inf 7) ed anche qui dovrei confrontare il min tra 1 e inf che 1 e non -1!!!
Cosa sto sbagliando?
[...]
No, stesso errore fatto sopra... Non hai determinato il minimo di tale sequenza di interi/infiniti in maniera corretta. Ora hai capito il procedimento ma sei inciampato nell'ultimissima parte più facile
."mattiadj":
[...]
ps: scusa se non uso LaTex ma ancora capisco bene come usarlo in verità non ho neanche guardato bene perchè sto cercando di capire questo esercizio!
Ti ringrazio!
Tranquillo, pensa prima all'esercizio, LaTeX imparerai ad usarlo un po' alla volta facendo pratica. Spero ora ti sia tutto più chiaro, in caso chiedi pure
Ma quindi io devo trovare il minimo all'interno della sequenza che ottengo dalla somma???
Esattamente esatto, come del resto è descritto dall'algoritmo.
Scusa ma dove è scritta questa cosa nell'algoritmo?? Quando dice lij + wkg io mettevo k cioè il numero della matrice (per es nel caso di L2 mettevo il 2) per cercare all'interno della matrice L(m-1) il coefficiente con riga i colonna k e all'interno della matrice W il coeff di riga k e colonna j.
Sbagliavo ovviamente ma perchè?
Ti ringrazio sei stato sensazionale!
Sbagliavo ovviamente ma perchè?
Ti ringrazio sei stato sensazionale!
Allora, $k$ è l'indice con cui scorri la riga e la colonna che hai appena selezionato correntemente dalle rispettive matrici $L^{(m - 1)}$ e $W$ che ti servono (nell'algoritmo sono chiamate rispettivamente $L$ e $W$), $i$ e $j$ invece sono gli indici dell'elemento corrente della tua nuova matrice $L^{(m)}$ che stai generando e di cui vuoi appunto determinarne i valori che la compongono (nell'algoritmo è chiamata $L'$).
L'errore che commettevi te è dovuto al fatto che $k$ riparte da $1$ e va fino ad $n$ per ogni elemento della tua nuova matrice di cui vuoi determinare il valore. Come invece cercavi di selezionare gli elementi nella matrici $L^{(m - 1)}$ e $W$ andava bene.
Sensazionale Troppo gentile 
L'errore che commettevi te è dovuto al fatto che $k$ riparte da $1$ e va fino ad $n$ per ogni elemento della tua nuova matrice di cui vuoi determinare il valore. Come invece cercavi di selezionare gli elementi nella matrici $L^{(m - 1)}$ e $W$ andava bene.
Sensazionale
Troppo gentile
uhm e quando ho lik e wkj questo k assume nel primo caso il valore j della di l' che sarebbe L(m-1) e nel secondo caso il valore della i di W ?
Cioè non capisco cosa vuol dire lik e wkj o meglio quali coeff devo prendere che sono determinati da questi indici.
Spero di averti fatto capire la mia perplessità!
Cioè non capisco cosa vuol dire lik e wkj o meglio quali coeff devo prendere che sono determinati da questi indici.
Spero di averti fatto capire la mia perplessità!
No, $k$ è un indice a sé stante che va da $1$ a $n$ e, combinato appositamente con un secondo indice ed il nome della rispettiva matrice permette di selezionare la rispettiva cella. Dire "assume il valore della $i$/$j$" non è corretto.
Quindi lik e wkj quale coeff vanno ad identificare? Cioè non ho capito perchè tu prendi tutta la RIGA X e la COLONNA Y invece del singolo coefficiente.
Sto cercando di capire il codice dell'algoritmo sennò la soluzione per l'es ce l'ho Ma siccome sarà sicuramente una domanda di teoria sto cercando di capire cosi da saperlo riscrivere.
Grazie
Sto cercando di capire il codice dell'algoritmo sennò la soluzione per l'es ce l'ho
Ma siccome sarà sicuramente una domanda di teoria sto cercando di capire cosi da saperlo riscrivere.Grazie
"mattiadj":
Quindi lik e wkj quale coeff vanno ad identificare? Cioè non ho capito perchè tu prendi tutta la RIGA X e la COLONNA Y invece del singolo coefficiente.
[...]
Perché abbiamo da determinare i cammini minimi tra tutte le coppie in un grafo orientato, no
I vicini li trovi sia nella riga che nella colonna relativa alla cella in cui ti trovi (quella corrente). $L_{ik}$ puoi immaginarlo come il peso necessario per arrivare al vertice in cui ti trovi adesso dopo un tot di passi. Per sapere come muoverti nella maniera più conveniente devi identificare il percorso con peso minore (consultando pertanto $w_{kj}$) e da qui derivano tali operazioni di somma e minimo di cui parlavamo poiché difatti da quel punto in poi valuti tutti i possibili percorsi che puoi effettuare."mattiadj":
[...]
Sto cercando di capire il codice dell'algoritmo sennò la soluzione per l'es ce l'ho
Grazie
Di nulla. Consiglio: prova a fare un piccolo schema su carta mentre esegui l'algoritmo e vedrai che ti sarà più chiaro. Vedrai (o forse l'hai già vista) come questo passaggio è anche ottimizzato con l'algoritmo di Floyd-Warshall di cui ti parlavo.
E' un esame che ho fatto cinque anni fa questo ma lo ricordo come se fosse ieri e custodisco gelosamente il librone utilizzato per questo ed un altro corso
.
Allora il cammino di peso minimo per es da 1 a 2 è sempre 3 fino a L(3). C'è un arco che collega 1 e 2 perchè invece in L(4) diventa 1. Il meccanismo secondo il quale diventa 1 è chiaro ma perchè diventa 1?
Chiaro
In quale vertice devo arrivare?
Questi passi sono dati da k?
Come muovermi in che senso?
Per es: io so che il cammino minimo da 1 a 2 è 3! Deve essere 3 perchè c'è un arco! Perchè invece in L(4) diventa 1?
Quale "cammino" partendo da 1 per arrivare 2 fa sul grafo per addirittura farlo essere di peso 1??
Grazie ancora
I vicini li trovi sia nella riga che nella colonna relativa alla cella in cui ti trovi (quella corrente).
Chiaro
Lik puoi immaginarlo come il peso necessario per arrivare al vertice in cui ti trovi adesso dopo un tot di passi. Per sapere come muoverti nella maniera più conveniente devi identificare il percorso con peso minore (consultando pertanto wkj)
In quale vertice devo arrivare?
Questi passi sono dati da k?
Come muovermi in che senso?
Per es: io so che il cammino minimo da 1 a 2 è 3! Deve essere 3 perchè c'è un arco! Perchè invece in L(4) diventa 1?
Quale "cammino" partendo da 1 per arrivare 2 fa sul grafo per addirittura farlo essere di peso 1??
Grazie ancora
"mattiadj":
[...]
In quale vertice devo arrivare?
[...]
Da ciascun vertice vogliamo avere tutti i possibili cammini da questo agli altri vertici del grafo (tenendo conto che in alcuni casi potrebbero non esserci e questo giustifica l'introduzione del simbolo $\infty$). Pertanto potenzialmente vogliamo arrivare a tutti gli altri vertici (ove possibile).
"mattiadj":
[...]
Questi passi sono dati da k?
[...]
No, forse così ti ho messo io in confusione. Parlavo di passi in senso generico, avrei potuto dire semplicemente "dopo un po'". Chiedo venia
"mattiadj":
[...]
Come muovermi in che senso?
[...]
Nel senso di determinare il percorso più conveniente, meno "pesante"/"costoso".
"mattiadj":
[...]
Per es: io so che il cammino minimo da 1 a 2 è 3! Deve essere 3 perchè c'è un arco! Perchè invece in L(4) diventa 1?
Quale "cammino" partendo da 1 per arrivare 2 fa sul grafo per addirittura farlo essere di peso 1??
Grazie ancora
Questo accade perché abbiamo dei pesi negativi. Attenzione: il cammino con minor archi possibili non è detto che sia necessariamente quello più conveniente. Se noti infatti per andare da $1$ a $2$ puoi sì effettuare il cammino $1 \rightarrow 2$ (con peso pari a $3$) ma anche $1 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 2$ il cui peso totale è pari a $-4 + 6 - 5 + 4 = 1$
. Ovviamente della presenza di quest'ultimo cammino non puoi accorgertene subito ma solamente quando determini $L^{(4)}$.A te
Ti ringrazio! Ora è tutto moooooooooooolto più chiaro!! 
Mi rivedo tutto e se ho ancora qualche dubbio ti scrivo!
Grazieeeeee
Mi rivedo tutto e se ho ancora qualche dubbio ti scrivo!
Grazieeeeee
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo