Dynamisk programmering

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk

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[rediger | rediger kilde]

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[rediger | rediger kilde]

Nedenfor er et eksempel.

Fibonacci-tallene[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]