Differenze tra programmazione dinamica e Dijkstra
Clicca QUI per vedere il messaggio nel forum |
| Snakethesniper |
| Quali sono le differenze tra il calcolo dei cammini minimi con programmazione dinamica e con Dijkstra? A parte la modalità di esecuzione, il problema e la soluzione sono gli stessi? Ce n'è uno che conviene? |
| Cronovirus |
La differenza è che risolvono due problemi diversi:
- programmazione dinamica: calcola i cammini minimi tra ogni coppia di nodi
- Dijkstra: cammini minimi che partono dalla sorgente di un grafo |
| Snakethesniper |
Originally posted by Cronovirus
La differenza è che risolvono due problemi diversi:
- programmazione dinamica: calcola i cammini minimi tra ogni coppia di nodi
- Dijkstra: cammini minimi che partono dalla sorgente di un grafo
ma un side effect di dijkstra non è quello di trovare anche i cammini minimi tra le coppie di nodi? |
| Cronovirus |
| Attenzione io ho specificato che in dijkstra parti da una sorgente, questa è la differenza sostanziale; mentre se fai la programmazione dinamica avrai i risultati per ogni coppia di nodi e avrai al suo interno anche il risultato che ottieni con dijkstra per un nodo radice (credo). Quindi ok credo che concordiamo! Tuttavia vorrei sottolineare che all'orale non gli devi dire che sono uguali perché NON lo sono! |
| Snakethesniper |
Originally posted by Cronovirus
Attenzione io ho specificato che in dijkstra parti da una sorgente, questa è la differenza sostanziale; mentre se fai la programmazione dinamica avrai i risultati per ogni coppia di nodi e avrai al suo interno anche il risultato che ottieni con dijkstra per un nodo radice (credo). Quindi ok credo che concordiamo! Tuttavia vorrei sottolineare che all'orale non gli devi dire che sono uguali perché NON lo sono!
no no che sono diversi lo so, però appunto le slide dicevano che risolvono entrambi lo stesso problema, ovvero quello dei cammini minimi.
Se quindi ad esempio voglio trovare il cammino minimo tra due nodi specifici, mi conviene usare Dijkstra usando uno dei due nodi come sorgente, piuttosto che calcolarli con la programmazione dinamica ? |
| Cronovirus |
| La risposta è nella complessità dei due algoritmi: dijkstra è chiaramente migliore! |
|
|
|
