Forum Informatica Unict

Vecchi ordinamenti ad esaurimento => Algoritmi 2 => Topic started by: James on 10-02-2010, 18:38:24



Title: dubbio su programmazione dinamica
Post by: James on 10-02-2010, 18:38:24
Bene gente, si parla di programmazione dinamica e  più precisamente: della schedulazione di una linea d'assemblaggio. Nella slide 19, c'è la procedura M-OPT, di che si tratta? Qualcuno potrebbe spiegarmi il funzionamento? E perchè è più conveniente rispetto alla semplice OPT?
Grazie mille

Saluti


Title: Re:dubbio su programmazione dinamica
Post by: Slayer on 10-02-2010, 18:45:52
Se dai un'occhiata agli alberi di ricorsione di OPT e M-OPT (slides 20-21) noterai che l'albero relativo a M-OPT contiene meno nodi dell'albero relativo a OPT, ovvero, eseguendo M-OPT, si controllla se il valore M[i,j] è stato già calcolato ed eventualmente lo restituisce, senza effettuare chiamate di funzione ridondanti. Spero di esserti stato d'aiuto. Ciao


Title: Re:dubbio su programmazione dinamica
Post by: James on 10-02-2010, 18:57:06
Ma questo valore M[i,j] esattamente cos'è?


Title: Re:dubbio su programmazione dinamica
Post by: Slayer on 10-02-2010, 19:06:09
M[i,j] è il minimo tempo per attraversare la linea di assemblaggio dall'inizio fino alla stazione Si,j e viene definito ricorsivamente. Se j=1 (caso base), quindi si prende in considerazione la prima stazione, allora M[i,1] è uguale al tempo necessario per avviare la linea di assemblaggio (ei) più il tempo che viene speso all'interno della stazione Si,1 (ai,1). Altrimenti, se j>=2, allora viene assegnato a M[i,j] il tempo minore tra quello che si avrebbe se la precedente linea di assemblaggio fosse nella stessa linea in cui ci si trova (sarebbe a dire i) o quello che si avrebbe se la precedente linea di assemblaggio fosse nella linea opposta (sarebbe a dire 3-i).


Title: Re:dubbio su programmazione dinamica
Post by: James on 10-02-2010, 19:07:16
Tutto molto chiaro. Grazie mille, gentilissimo.


Title: Re:dubbio su programmazione dinamica
Post by: Slayer on 10-02-2010, 19:09:34
Figurati.