Dynamisk programmering

Dynamisk programmering (DP) er en teknikk for å løse en bred klasse problemer 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:
 Identifisere en rekursjon som løser problemet
 Starte med å løse de enkleste tilfellene
 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 , der hvert tall er lik summen av de 2 forrige tallene. Dynamisk programmering kan brukes til å regne ut  raskere enn en naiv implementasjon. Første skritt er å finne den rekursive sammenhengen mellom Fibonacci-tallene. Den er gitt ved:

Å implementere dette direkte vil føre til eksponentiell kjøretid , der  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:

Dersom vi løser  før  for alle , vil kjøretiden være . Man starter med å løse , deretter , og så videre. Dette krever lineær tid i , og man trenger heller ikke mye plass i minnet.

 Binominalkoeffisientene 
Binominalkoeffisientene er koeffisientene man får dersom man utvider uttrykket , og skrives som . Eksempelvis er , fordi det andre leddet i  har koeffisienten . Sagt på en annen måte teller  antall måter vi kan velge  elementer fra en samling med  elementer. En naiv implementasjon ville vært å bruke formelen:

Problemet er at man potensielt gjør store utregninger av  som er tidkrevende for en datamaskin. ,
men en datamaskin må utføre  multiplikasjoner for å regne dette ut. Et bedre utgangspunkt er den rekursive formelen:

med startverdier

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  addisjoner.
Referanser

Kategori:Optimeringsalgoritmer og -metoder