.dsy:it. - Differenze tra programmazione dinamica e Dijkstra

.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- Differenze tra programmazione dinamica e Dijkstra (http://www.dsy.it/forum/showthread.php?threadid=43694)

Posted by Snakethesniper on 12-02-2014 22:07:

Differenze tra programmazione dinamica e Dijkstra

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?

Posted by Cronovirus on 12-02-2014 22:20:

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

Posted by Snakethesniper on 13-02-2014 11:07:

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?

Posted by Cronovirus on 13-02-2014 12:08:

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!

Posted by Snakethesniper on 13-02-2014 12:37:

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 ?

Posted by Cronovirus on 13-02-2014 12:55:

La risposta è nella complessità dei due algoritmi: dijkstra è chiaramente migliore!

All times are GMT. The time now is 22:36.

Show all 6 posts from this thread on one page