Nederlands
Menu

Wat is Dynamisch programmeren (dynamic programming)?

Ontwerpmethode voor algoritmen die een probleem opsplitst in kleinere deelproblemen en de antwoorden daarop in een tabel vastlegt om ze opnieuw te gebruiken, zodat dezelfde berekening niet herhaald wordt. Ze wordt gebruikt voor het knapzakprobleem, het minimale aantal munten, de langste gemeenschappelijke deelreeks, kortste paden en meer.

Japanse benaming: 動的計画法

“Dynamisch programmeren (dynamic programming)” komt voor in 3 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Het idee: elk overlappend deelprobleem één keer oplossen

Wie Fibonaccigetallen rechtstreeks met recursie uit fib(n) = fib(n−1) + fib(n−2) berekent, berekent dezelfde waarden steeds opnieuw, zodat het aantal aanroepen exponentieel groeit (ongeveer 2,69 miljoen voor fib(30)). Dynamisch programmeren legt het antwoord op elk deelprobleem vast zodra het is gevonden en zoekt het daarna alleen nog op, zodat fib(n) werk kost dat evenredig is met n. De methode is toepasbaar als de optimale oplossing van een groot probleem kan worden opgebouwd uit optimale oplossingen van kleinere deelproblemen (optimale deelstructuur) en dezelfde deelproblemen vaak terugkomen (overlappende deelproblemen).

Memoisatie en tabellen invullen

Er zijn twee manieren om het te implementeren: memoisatie (top-down), die de vorm met recursie behoudt maar berekende resultaten onthoudt, en de bottom-upaanpak, die een tabel invult vanaf de kleinste deelproblemen. Bij het 0/1-knapzakprobleem bevat de tabel bijvoorbeeld „de maximale waarde die haalbaar is met voorwerpen tot en met i binnen capaciteit c”, en wordt ze ingevuld door telkens het grootste van wel of niet meenemen van elk voorwerp te kiezen. Voor n voorwerpen en capaciteit W kost dit O(nW). Het probleem van het minimale aantal munten kan op dezelfde manier worden opgelost door voor elk bedrag van 0 tot het doelbedrag het minimale aantal munten in een tabel te zetten.

Verschil met gretige algoritmen, en toepassingen

Een gretig algoritme kiest gewoon de keuze die op elk moment het beste lijkt en gaat verder, dus het is snel, maar voor sommige problemen niet optimaal. Bij het betalen van 8 yen met munten van 1, 4 en 6 yen gebruikt het gretige algoritme drie munten, 6 + 1 + 1, terwijl dynamisch programmeren er twee vindt, 4 + 4. Dynamisch programmeren wordt breed toegepast, bijvoorbeeld voor de bewerkingsafstand en de langste gemeenschappelijke deelreeks van tekenreeksen (zoals in het diff-commando), het uitlijnen van DNA-sequenties, het viterbialgoritme in spraakherkenning en het algoritme van Floyd-Warshall voor kortste paden tussen alle paren knopen.

Nu oefenen: vragen over Dynamisch programmeren (dynamic programming)

Een functie fib(n) voor Fibonaccigetallen is met recursie gedefinieerd als „als n kleiner dan of gelijk aan 1 is, geef n terug; geef anders fib(n−1) + fib(n−2) terug”. Hoe vaak wordt fib aangeroepen als fib(5) wordt aangeroepen, de eerste aanroep meegerekend?

  1. A6
  2. B9
  3. C15
Antwoord en toelichting tonen

Antwoord: C. 15

Stel dat C(n) het aantal aanroepen voor fib(n) is. Dan geldt C(0) = C(1) = 1 en C(n) = 1 + C(n−1) + C(n−2), dus C(2) = 3, C(3) = 5, C(4) = 9 en C(5) = 15. Omdat dezelfde waarden steeds opnieuw worden berekend, groeit het aantal exponentieel met n; fib(30) doet ongeveer 2,69 miljoen aanroepen. Met memoisatie (een vorm van dynamisch programmeren), die berekende waarden in een tabel bewaart, worden alleen de zes waarden fib(0) tot fib(5) berekend en daalt het aantal aanroepen tot 9 (2n − 1). 6 is het aantal verschillende argumenten, en 9 het aantal aanroepen met memoisatie.

Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?

  1. AOok het gretige algoritme bereikt het minimum van 2 munten
  2. BHet gretige algoritme gebruikt 3 munten en mist het minimum van 2
  3. CHet gretige algoritme gebruikt 3 munten, en dat is het minimum
Antwoord en toelichting tonen

Antwoord: B. Het gretige algoritme gebruikt 3 munten en mist het minimum van 2

Het gretige algoritme neemt eerst één munt van 6 yen en betaalt de resterende 2 yen met twee munten van 1 yen: 3 munten. Maar twee munten van 4 yen betalen het bedrag met slechts 2. Omdat een gretig algoritme alleen telkens de keuze opstapelt die op dat moment het beste lijkt, is het voor sommige muntstelsels niet optimaal. Dynamisch programmeren, dat een tabel vult met het minimale aantal munten voor elk bedrag van 0 tot 8 yen, van klein naar groot, vindt altijd het minimum. Voor muntstelsels zoals de Japanse munten van 1, 5, 10, 50, 100 en 500 yen geeft het gretige algoritme altijd het minimum.

Veelgestelde vragen

Wat is het verschil tussen dynamisch programmeren en verdeel-en-heers?

Beide splitsen een probleem op in deelproblemen, maar bij verdeel-en-heersalgoritmen zoals mergesort overlappen de deelproblemen niet, dus hoeven antwoorden niet te worden vastgelegd. Dynamisch programmeren verschilt doordat het antwoorden vastlegt en hergebruikt als dezelfde deelproblemen vaak terugkomen.

Wat zijn de zwakke punten van dynamisch programmeren?

Het vraagt geheugen en werk in verhouding tot de grootte van de tabel. De O(nW) van het knapzakprobleem is evenredig met de waarde van de capaciteit W, dus het wordt onpraktisch als W heel groot is. Geheugen kan worden bespaard door alleen vast te leggen wat nodig is of alleen de vorige rij van de tabel te bewaren.

“Dynamisch programmeren (dynamic programming)” in de toelichting

Vragen met “Dynamisch programmeren (dynamic programming)” (3)

  1. Een functie fib(n) voor Fibonaccigetallen is met recursie gedefinieerd als „als n kleiner dan of gelijk aan 1 is, geef n terug; geef anders fib(n−1) + fib(n−2) terug”. Hoe vaak wordt fib aangeroepen als fib(5) wordt aangeroepen, de eerste aanroep meegerekend?
  2. Je betaalt 8 yen met munten van 1 yen, 4 yen en 6 yen. Welke uitspraak over het aantal munten dat een gretig algoritme kiest (dat eerst zoveel mogelijk van de grootste munt gebruikt), vergeleken met het minimale aantal munten, is juist?
  3. Een knapzak met capaciteit 8 wordt gevuld met voorwerpen gekozen uit vier voorwerpen met (gewicht, waarde) (2, 3), (3, 4), (4, 5) en (5, 6). Van elk voorwerp is er maar één, en voorwerpen kunnen niet worden gesplitst. Wat is de maximale totale waarde bij een totaal gewicht van hoogstens 8?

Verwante termen

Gretig algoritme (greedy algorithm) Recursie Argument Algoritme van Dijkstra Binair zoeken (binary search) Binaire heap (binary heap) Binaire zoekboom (binary search tree) Breedte-eerst zoeken (breadth-first search) Diepte-eerst zoeken (depth-first search) Gelinkte lijst (linked list)

Naar de woordenlijst