In deze tutorial leer je wat dynamisch programmeren is. Ook vind je de vergelijking tussen dynamisch programmeren en hebzuchtige algoritmen om problemen op te lossen.
Dynamisch programmeren is een techniek in computerprogrammering die helpt bij het efficiënt oplossen van een klasse van problemen met overlappende subproblemen en optimale substructuureigenschappen.
Dergelijke problemen omvatten het herhaaldelijk berekenen van de waarde van dezelfde subproblemen om de optimale oplossing te vinden.
Dynamisch programmeervoorbeeld
Neem het geval van het genereren van de fibonacci-reeks.
Als de reeks F (1) F (2) F (3) … F (50) is, volgt deze de regel F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46) …
Merk op hoe er overlappende subproblemen zijn, we moeten F (48) berekenen om zowel F (50) als F (49) te berekenen. Dit is precies het soort algoritme waar Dynamic Programming uitblinkt.
Hoe dynamisch programmeren werkt
Dynamisch programmeren werkt door het resultaat van subproblemen op te slaan, zodat wanneer hun oplossingen nodig zijn, deze voorhanden zijn en we ze niet opnieuw hoeven te berekenen.
Deze techniek om de waarde van subproblemen op te slaan, wordt memoisatie genoemd. Door de waarden in de array op te slaan, besparen we tijd voor berekeningen van deelproblemen die we al zijn tegengekomen.
var m = map (0 → 0, 1 → 1) functie fib (n) als sleutel n niet in kaart is mm (n) = fib (n - 1) + fib (n - 2) retourneer m (n)
Dynamisch programmeren door middel van memo is een top-down benadering van dynamisch programmeren. Door de richting waarin het algoritme werkt om te keren, dwz door te vertrekken vanuit het basisscenario en toe te werken naar de oplossing, kunnen we ook dynamisch programmeren bottom-up implementeren.
functie fib (n) if n = 0 retourneer 0 else var prevFib = 0, currFib = 1 herhaal n - 1 keer var newFib = prevFib + currFib prevFib = currFib currFib = newFib retourneer currentFib
Recursie versus dynamische programmering
Dynamisch programmeren wordt meestal toegepast op recursieve algoritmen. Dit is geen toeval, de meeste optimalisatieproblemen vereisen herhaling en dynamisch programmeren wordt gebruikt voor optimalisatie.
Maar niet alle problemen die recursie gebruiken, kunnen Dynamic Programming gebruiken. Tenzij er sprake is van overlappende subproblemen zoals in het fibonacci-sequentieprobleem, kan een recursie de oplossing alleen bereiken met een verdeel en heersbenadering.
Dat is de reden waarom een recursief algoritme als Merge Sort geen gebruik kan maken van Dynamic Programming, omdat de subproblemen op geen enkele manier overlappen.
Hebzuchtige algoritmen versus dynamische programmering
Greedy Algorithms zijn vergelijkbaar met dynamisch programmeren in de zin dat ze beide tools zijn voor optimalisatie.
Hebzuchtige algoritmen zoeken echter naar lokaal optimale oplossingen of met andere woorden, een hebzuchtige keuze, in de hoop een globaal optimum te vinden. Daarom kunnen hebzuchtige algoritmen een gok maken die er op dat moment optimaal uitziet, maar later duur wordt en geen wereldwijd optimum garanderen.
Dynamisch programmeren daarentegen vindt de optimale oplossing voor subproblemen en maakt vervolgens een weloverwogen keuze om de resultaten van die subproblemen te combineren om de meest optimale oplossing te vinden.
