Dynamisk programmering

Dynamisk programmering (DP) er en teknikk for å løse en bred klasse problemer^[klargjør] effektivt. Metoden innebærer å dele opp et komplisert problem, for så å løse de overlappende delproblemene på en måte slik at hvert delproblem kun blir løst en gang. Dynamisk programmering er en av de mest brukte og viktigste generelle teknikkene for å utvikle gode algoritmer til dataprogrammer.

Overblikk

Dynamisk programmering er en generell teknikk, men implementering på hvert enkelt problem kan være svært annerledes. Dynamisk programmering fungerer kun dersom den underliggende kombinatoriske strukturen er sortert på en eller annen måte. Problemet må kunne deles opp i mindre delproblemer, og disse problemene må overlappe. Dersom delproblemene ikke overlapper kalles teknikken for en splitt og hersk algoritme.

For å implementere dynamisk programmering må man:

1. Identifisere en rekursjon som løser problemet
2. Starte med å løse de enkleste tilfellene
3. Bygge opp løsningen i en rekkefølge slik at ingen delproblemer blir løst mer enn en gang

Ofte blir utregninger lagret i en tabell, slik at de kan hentes senere. En slik tabell kan være en en-dimensjonal liste, to-dimensjonal matrise, og så videre.

Eksempler

Nedenfor er et eksempel.

Fibonacci-tallene

Fibonacci-tallene er ${\displaystyle 0,1,1,2,3,5,8,\ldots }$, der hvert tall er lik summen av de 2 forrige tallene. Dynamisk programmering kan brukes til å regne ut ${\displaystyle F_{n}}$ raskere enn en naiv implementasjon. Første skritt er å finne den rekursive sammenhengen mellom Fibonacci-tallene. Den er gitt ved:

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

Å implementere dette direkte vil føre til eksponentiell kjøretid ${\displaystyle {\mathcal {O}}(\alpha ^{n})}$, der ${\displaystyle \alpha }$ er en konstant. En direkte, naiv implementasjon er ikke ideell fordi delproblemer blir løst flere ganger. Etter å ha funnet den rekursive sammenhengen er neste skritt å løse initial-problemene:

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1}$

Dersom vi løser ${\displaystyle F_{n-1}}$ før ${\displaystyle F_{n}}$ for alle ${\displaystyle n}$, vil kjøretiden være ${\displaystyle {\mathcal {O}}(n)}$. Man starter med å løse ${\displaystyle F_{2}}$, deretter ${\displaystyle F_{3}}$, og så videre. Dette krever lineær tid i ${\displaystyle n}$, og man trenger heller ikke mye plass i minnet.

Binominalkoeffisientene

Binominalkoeffisientene er koeffisientene man får dersom man utvider uttrykket ${\displaystyle \left(a+b\right)^{n}}$, og skrives som ${\displaystyle {\tbinom {n}{r}}}$. Eksempelvis er ${\displaystyle {\tbinom {3}{2}}=3}$, fordi det andre leddet i ${\displaystyle \left(a+b\right)^{3}=a^{3}+3a^{2}b+3ab^{2}+b^{3}}$ har koeffisienten ${\displaystyle 3}$. Sagt på en annen måte teller ${\displaystyle {\tbinom {n}{r}}}$ antall måter vi kan velge ${\displaystyle r}$ elementer fra en samling med ${\displaystyle n}$ elementer. En naiv implementasjon ville vært å bruke formelen:

${\displaystyle {\binom {n}{r}}={\frac {n!}{(n-r)!r!}}}$

Problemet er at man potensielt gjør store utregninger av ${\displaystyle n!}$ som er tidkrevende for en datamaskin. ${\displaystyle {\tbinom {n}{n}}=1}$, men en datamaskin må utføre ${\displaystyle n}$ multiplikasjoner for å regne dette ut. Et bedre utgangspunkt er den rekursive formelen:

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$

med startverdier

${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$

Dette gir utgangspunktet for en implementasjon ved hjelp av dynamisk programmering. Delproblemene overlapper, med dersom vi løser de i riktige rekkefølge vil kjøretiden være ${\displaystyle {\mathcal {O}}(nr)}$ addisjoner.

Referanser

• Dasgupta, Sanjoy (2008). Algorithms. McGraw Hill. ISBN 978-0-07-352340-8. 
• Steve S. Skiena (2009). The Algorithm Design Manual (2nd ed. utg.). Springer. ISBN 978-1-84996-720-4. CS1-vedlikehold: Ekstra tekst (link)