I denne veiledningen lærer du hva dynamisk programmering er. Du vil også finne sammenligningen mellom dynamisk programmering og grådige algoritmer for å løse problemer.
Dynamisk programmering er en teknikk innen dataprogrammering som hjelper til effektivt å løse en klasse problemer som har overlappende underproblemer og optimal underkonstruksjonsegenskap.
Slike problemer innebærer gjentatte ganger å beregne verdien av de samme delproblemene for å finne den optimale løsningen.
Eksempel på dynamisk programmering
Ta saken med å generere Fibonacci-sekvensen.
Hvis sekvensen er F (1) F (2) F (3)… F (50), følger den regelen 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) …
Legg merke til hvordan det er overlappende delproblemer, vi må beregne F (48) for å beregne både F (50) og F (49). Dette er nøyaktig den typen algoritme der dynamisk programmering skinner.
Hvordan fungerer dynamisk programmering
Dynamisk programmering fungerer ved å lagre resultatet av delproblemer, slik at når løsningene deres kreves, er de tilgjengelig, og vi trenger ikke å beregne dem på nytt.
Denne teknikken for å lagre verdien av delproblemer kalles memoization. Ved å lagre verdiene i matrisen sparer vi tid for beregninger av underproblemer vi allerede har kommet over.
var m = kart (0 → 0, 1 → 1) funksjon fib (n) hvis nøkkel n ikke er i kart mm (n) = fib (n - 1) + fib (n - 2) retur m (n)
Dynamisk programmering ved memoization er en top-down tilnærming til dynamisk programmering. Ved å snu retningen algoritmen fungerer i, dvs. ved å starte fra basissaken og jobbe mot løsningen, kan vi også implementere dynamisk programmering på en bunn-opp-måte.
funksjon fib (n) hvis n = 0 returnerer 0 annet var prevFib = 0, currFib = 1 gjenta n - 1 ganger var newFib = prevFib + currFib prevFib = currFib currFib = newFib returstrømFib
Rekursjon vs dynamisk programmering
Dynamisk programmering brukes hovedsakelig til rekursive algoritmer. Dette er ikke tilfeldig, de fleste optimaliseringsproblemer krever rekursjon og dynamisk programmering brukes til optimalisering.
Men ikke alle problemer som bruker rekursjon, kan bruke dynamisk programmering. Med mindre det er tilstedeværelse av overlappende delproblemer som i Fibonacci-sekvensproblemet, kan en rekursjon bare nå løsningen ved hjelp av en deling og erobringsmetode.
Det er grunnen til at en rekursiv algoritme som Merge Sort ikke kan bruke dynamisk programmering, fordi underproblemene ikke overlapper på noen måte.
Grådige algoritmer vs dynamisk programmering
Grådige algoritmer ligner på dynamisk programmering i den forstand at de begge er verktøy for optimalisering.
Grådige algoritmer ser imidlertid etter lokale optimale løsninger eller med andre ord et grådig valg, i håp om å finne et globalt optimalt. Derfor kan grådige algoritmer gi en gjetning som ser optimal ut den gangen, men blir kostbar nedover linjen og ikke garanterer et globalt optimalt.
Dynamisk programmering, derimot, finner den optimale løsningen på underproblemer, og tar deretter et informert valg for å kombinere resultatene av disse underproblemene for å finne den mest optimale løsningen.
