Algoritmo di Bellman Ford
Buongiorno!
Questa ricerca operativa mi sta facendo impazzire ^^
devo trovare un percorso minimo da v0 a v6 avendo una tabella testa coda di questo tipo
------v0------v1-----v2------v3-----v4-----v5-----v6-----
v0 | 0 | 5 | -1 | 10 | - | - | -
v1 | -1 | 0 | - | - | -2 | -1 | -
v2 | 4 | - | 0 | 8 | - | - | -
etc etc fino a v6
la tabella risolutiva indica a ogni passo il percorso min
passo v0 v1 v2 v3 v4 v5 v6
1 [0,v0] etc etc etc
2 [0,v0] [5,v0]
Il problema è che non riesco a capire come utilizzare la tabella data dall'esercizio, visto che so risolvere il problema solo se al posto della tabella testa coda,ho un grafo.
qualcuno saprebbe spiegarmi come fare o indicarmi risorse dalle quali attingere in rete?
Questa ricerca operativa mi sta facendo impazzire ^^
devo trovare un percorso minimo da v0 a v6 avendo una tabella testa coda di questo tipo
------v0------v1-----v2------v3-----v4-----v5-----v6-----
v0 | 0 | 5 | -1 | 10 | - | - | -
v1 | -1 | 0 | - | - | -2 | -1 | -
v2 | 4 | - | 0 | 8 | - | - | -
etc etc fino a v6
la tabella risolutiva indica a ogni passo il percorso min
passo v0 v1 v2 v3 v4 v5 v6
1 [0,v0] etc etc etc
2 [0,v0] [5,v0]
Il problema è che non riesco a capire come utilizzare la tabella data dall'esercizio, visto che so risolvere il problema solo se al posto della tabella testa coda,ho un grafo.
qualcuno saprebbe spiegarmi come fare o indicarmi risorse dalle quali attingere in rete?
Risposte
Semplicissimo!
La tabella è anche detta matrice delle adiacenze e rappresenta il grafo come potrebbe vederlo un computer, ad esempio
Se a te viene più semplice risolvere l'esercizio facendo uso del grafo puoi ricavarlo tranquillamente dalla tabella.
- Disegni in ordine sparso i vertici (in questo cado da v 0 a v6)
- dove leggi uno 0 e gli indici riga e colonna della matrice sono uguali ciò ti sta semplicemente dicendo che per raggiungere un dato vertice vi da vi stesso il costo è 0 (che scoperta ;P).
- dove leggi un numero, i due vertici sono collegati ed il ramo ha quel costo (ad esempio dalla prima riga si evince che v0 e v1 sono collegati e con costo 5 oppure v0 e v3 sono collegati con costo 10)
- dove leggi un tratto significa che quei due vertici non sono direttamente raggiungibili (sempre dalla prima riga v0 risulta non collegato a v4,5,6).
Il gioco è fatto
Se invece stai chiedendo di risolvere il problema senza passare per il grafo fammi sapere!
La tabella è anche detta matrice delle adiacenze e rappresenta il grafo come potrebbe vederlo un computer, ad esempio
Se a te viene più semplice risolvere l'esercizio facendo uso del grafo puoi ricavarlo tranquillamente dalla tabella.
- Disegni in ordine sparso i vertici (in questo cado da v 0 a v6)
- dove leggi uno 0 e gli indici riga e colonna della matrice sono uguali ciò ti sta semplicemente dicendo che per raggiungere un dato vertice vi da vi stesso il costo è 0 (che scoperta ;P).
- dove leggi un numero, i due vertici sono collegati ed il ramo ha quel costo (ad esempio dalla prima riga si evince che v0 e v1 sono collegati e con costo 5 oppure v0 e v3 sono collegati con costo 10)
- dove leggi un tratto significa che quei due vertici non sono direttamente raggiungibili (sempre dalla prima riga v0 risulta non collegato a v4,5,6).
Il gioco è fatto
Se invece stai chiedendo di risolvere il problema senza passare per il grafo fammi sapere!
Grazie ZaC!
Si avevo pensato di convertirlo, anche se facendolo il grafo viene un po grandicello e sconfusionato..
passiamo al piano B: risolverlo senza passare dal grafo?
Si avevo pensato di convertirlo, anche se facendolo il grafo viene un po grandicello e sconfusionato..
passiamo al piano B: risolverlo senza passare dal grafo?
Dunque, non è semplicissimo riportare in un forum i vari passaggi...
Proviamo, se poi non ti è chiaro fammi sapere.
Dunque, scrivi in ordine lessiografico (o un altro ordine se diversamente specificato dall'esercizio) i vari archi:
v0v1
v0v2
v0v3
v1v0
v1v4
v1v5
v2v0
v2v3
.....
(da esempio)
Disegni due tabelle, una dei costi ed una dei collegamenti con righe pari ai vari vertici e colonne pari al numero di vertici -1 (si dimostra che se l'algoritmo converge entro n-1 passi allora esiste una soluzione altrimenti c'è un loop negativo, ed anche che se per due passi consecutivi non vi è alcun miglioramento l'algoritmo si può considerare concluso)
Nella tabella dei costi al passo 0 metti zero nel vertice di partenza ed infinito in tutti gli altri
In quella dei collegamenti metti NIL (Not In Link) per tutti i vertici. (Consiglio di usare una matita, visto che dovrai modificare spesso le tabelle)
Adesso scorri la lista degli archi precedentemente stilata, e ti fermi al primo arco che interessa il vertice di partenza (poniamo il caso che il vertice di partenza sia v1, allora sceglierai l'arco v1v0).
Nella tabella dei costi in v0 metterai il valore presente nella matrice delle adiacenze alla riga v1 e nella colonna v0 mentre nella tabella dei collegamenti alla riga v0 metterai l'arco v1v0.
Procedi nello scorrere la lista ed aggiornando di conseguenza la tabella, ovviamente se un vertice è già stato raggiunto, ne modifichi il costo ed il relativo collegamento solo se questo porta un miglioramento (costo precedente link> costo attuale link).
Seguendo l'esempio dovrai aggiornare nei costi v4 e nei collegamenti aggiungere l'arco v1v4 e così via.
Conclusa la prima lettura della lista si conclude anche il passo 0 e si prosegue col passo 1,2,3,4 ammenocché per due passi consecutivi non vi sia alcun cambiamento, allora l'algoritmo si può considerare concluso.
Spero sia chiaro, se mi posti il testo per intero posso risolverlo in modo da mostrarti meglio i vari passaggi.
Fammi anche sapere i tuoi dubbi
Proviamo, se poi non ti è chiaro fammi sapere.
Dunque, scrivi in ordine lessiografico (o un altro ordine se diversamente specificato dall'esercizio) i vari archi:
v0v1
v0v2
v0v3
v1v0
v1v4
v1v5
v2v0
v2v3
.....
(da esempio)
Disegni due tabelle, una dei costi ed una dei collegamenti con righe pari ai vari vertici e colonne pari al numero di vertici -1 (si dimostra che se l'algoritmo converge entro n-1 passi allora esiste una soluzione altrimenti c'è un loop negativo, ed anche che se per due passi consecutivi non vi è alcun miglioramento l'algoritmo si può considerare concluso)
Nella tabella dei costi al passo 0 metti zero nel vertice di partenza ed infinito in tutti gli altri
In quella dei collegamenti metti NIL (Not In Link) per tutti i vertici. (Consiglio di usare una matita, visto che dovrai modificare spesso le tabelle)
Adesso scorri la lista degli archi precedentemente stilata, e ti fermi al primo arco che interessa il vertice di partenza (poniamo il caso che il vertice di partenza sia v1, allora sceglierai l'arco v1v0).
Nella tabella dei costi in v0 metterai il valore presente nella matrice delle adiacenze alla riga v1 e nella colonna v0 mentre nella tabella dei collegamenti alla riga v0 metterai l'arco v1v0.
Procedi nello scorrere la lista ed aggiornando di conseguenza la tabella, ovviamente se un vertice è già stato raggiunto, ne modifichi il costo ed il relativo collegamento solo se questo porta un miglioramento (costo precedente link> costo attuale link).
Seguendo l'esempio dovrai aggiornare nei costi v4 e nei collegamenti aggiungere l'arco v1v4 e così via.
Conclusa la prima lettura della lista si conclude anche il passo 0 e si prosegue col passo 1,2,3,4 ammenocché per due passi consecutivi non vi sia alcun cambiamento, allora l'algoritmo si può considerare concluso.
Spero sia chiaro, se mi posti il testo per intero posso risolverlo in modo da mostrarti meglio i vari passaggi.
Fammi anche sapere i tuoi dubbi
grazie^^
mi sto esercitando,
non appena mi blocco ti dico dov'è il problema, sperando di non averne
Ti ringrazio ancora per i chiarimenti
mi sto esercitando,
non appena mi blocco ti dico dov'è il problema, sperando di non averne
Ti ringrazio ancora per i chiarimenti
Ciao Zac, ho lo stesso problema! Devo risolvere un esercizio con l'algoritmo di Bellman Ford e non riesco ad interpretare questa tabella. Ho letto l'esempio in questa discussione ma ho molti dubbi 
Potresti mettere se ti è possibile un esercizio svolto e spiegato? In rete non riesco a trovare niente.
I miei esercizi sono sul quaderno e se è utile posso scriverlo qui.
Grazie.
Potresti mettere se ti è possibile un esercizio svolto e spiegato? In rete non riesco a trovare niente.
I miei esercizi sono sul quaderno e se è utile posso scriverlo qui.
Grazie.
Baroncella, mi dispiace per il ritardo (di più di un anno) con cui rispondo, ma non avevo visto questa tua richiesta d'aiuto... ormai sarà tutto superato, se hai bisogno batti un colpo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo