Algoritmi greedy e Programmazione Dinamica PDF

Preview

Summary

Appunti presi a lezione sugli algoritmi greedy e programmazione dinamica...

Description

Programmazione dinam dinamica ica La programmazione dinamica permette di andare a risolvere i problemi scomponendoli in sotto problemi, ma a differenza del metodo divide et impera, questi devono essere dipendenti tra di loro. Per andare a risolvere i vari sotto problemi viene utilizzata la metodologia bottom-up. Questa permette di andare a risolvere il problema andando ad ordinare i sotto problemi dal più piccolo al più grande. In questo caso viene seguita l’idea che andando a risolvere quelli più piccoli allora sarà più facile andare a risolvere quelli più grandi in quanto dipendenti. Altra differenza con il metodo ricorsivo è il fatto che i risultati verranno calcolati una sola volta e inseriti all’interno di una tabella. Nel caso in cui un sottoproblema dovesse ripresentarsi non verrà ricalcolato ma il risultato verrà preso dalla tabella precedentemente riempita. Il tempo di esecuzione di un problema di programmazione dinamica è dato dal prodotto del numero di sottoproblemi da dover risolvere e il numero di scelte da considerare per ogni problema. Esistono diverse tipologie di problemi di programmazione dinamica, i più noti sono: LCS e Zaino 0-1 (o intero).

LCS (Longest Commo Common n Subsequence) Il problema della LCS è un problema molto comune nel campo della bio-informatica e viene utilizzato per andare a vedere quanto due organismi siano simili date due stringhe di DNA in input. Date quindi due stringhe X e Y verrà prodotta una stringa Z contente la sotto sequenza più lunga in comune tra le due. Il tempo di esecuzione sarà pari a O(nW) a differenza di un algoritmo di brute force il quale andrebbe ad effettuare un confronto tra gli elementi raggiungendo una complessità esponenziale.

Zaino 0-1 Il problema dello zaino 0-1 è un problema di ottimizzazione che consiste nel massimizzare il profitto andando a prendere un insieme di elementi. Il problema vede uno zaino di capacità C e un insieme di elementi ai quali è associato un peso e un profitto. Si andrà quindi a scegliere se prendere o meno l’oggetto se il peso di quest’ultimo è minore o al massimo uguale della capacità dello zaino. Nel caso in cui questo vincolo non venga violato allora si deciderà se prendere l’elemento andando a sommare il profitto, diminuendo la capacità dello zaino con il peso dell’oggetto e andando a diminuire la dimensione dell’array, oppure passare semplicemente all’elemento successivo. Nel caso in cui, invece, il vincolo non venga rispettato si passerà semplicemente all’elemento successivo. Il problema è semi polinomiale, questo perché all’aumentare dell’input aumenterà anche la complessità di calcolo. 0 𝑠𝑒 𝑖 == 𝐷𝑖𝑚 𝑧𝑎𝑖𝑛𝑜[𝑖, 𝑗] = {max(𝑧𝑎𝑖𝑛𝑜[𝑖 − 1, 𝑗], 𝑧𝑎𝑖𝑛𝑜[𝑖 − 1, 𝑖]) 𝑠𝑒 𝐶𝑎𝑝𝑎𝑐𝑖𝑡à 𝑧𝑖𝑎𝑛𝑜 ≥ 𝑖𝑡𝑒𝑚[𝑖] 𝑧𝑖𝑎𝑛𝑜[𝑖 − 1, 𝑗] 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 j...