I denne vejledning lærer du, hvad dynamisk programmering er. Du finder også sammenligningen mellem dynamisk programmering og grådige algoritmer for at løse problemer.
Dynamisk programmering er en teknik i computerprogrammering, der hjælper med effektivt at løse en klasse af problemer, der har overlappende underproblemer og optimal underkonstruktionsegenskab.
Sådanne problemer involverer gentagne gange beregning af værdien af de samme underproblemer for at finde den optimale løsning.
Eksempel på dynamisk programmering
Tag sagen om at generere Fibonacci-sekvensen.
Hvis sekvensen er F (1) F (2) F (3)… F (50), følger den reglen 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)…
Bemærk hvordan der er overlappende delproblemer, vi skal beregne F (48) for at beregne både F (50) og F (49). Dette er nøjagtigt den slags algoritme, hvor dynamisk programmering skinner.
Sådan fungerer dynamisk programmering
Dynamisk programmering fungerer ved at gemme resultatet af underproblemer, så når deres løsninger er nødvendige, er de lige ved hånden, og vi behøver ikke at genberegne dem.
Denne teknik til lagring af værdien af underproblemer kaldes memoization. Ved at gemme værdierne i arrayet sparer vi tid til beregninger af delproblemer, vi allerede er stødt på.
var m = kort (0 → 0, 1 → 1) funktion fib (n) hvis tast n ikke er i kort mm (n) = fib (n - 1) + fib (n - 2) returnerer m (n)
Dynamisk programmering ved memoization er en top-down tilgang til dynamisk programmering. Ved at vende den retning, som algoritmen fungerer, dvs. ved at starte fra basissagen og arbejde hen imod løsningen, kan vi også implementere dynamisk programmering på en bottom-up måde.
funktion fib (n) hvis n = 0 returnerer 0 andet var prevFib = 0, currFib = 1 gentag n - 1 gange var newFib = prevFib + currFib prevFib = currFib currFib = newFib returstrømFib
Rekursion vs dynamisk programmering
Dynamisk programmering anvendes hovedsageligt til rekursive algoritmer. Dette er ikke en tilfældighed, de fleste optimeringsproblemer kræver rekursion, og dynamisk programmering bruges til optimering.
Men ikke alle problemer, der bruger rekursion, kan bruge dynamisk programmering. Medmindre der er tilstedeværelse af overlappende delproblemer som i Fibonacci-sekvensproblemet, kan en rekursion kun nå løsningen ved hjælp af en divide and conquer-tilgang.
Det er grunden til, at en rekursiv algoritme som Merge Sort ikke kan bruge dynamisk programmering, fordi underproblemerne ikke overlapper hinanden.
Grådige algoritmer vs dynamisk programmering
Grådige algoritmer ligner dynamisk programmering i den forstand, at de begge er værktøjer til optimering.
Imidlertid ser grådige algoritmer efter lokalt optimale løsninger eller med andre ord et grådigt valg i håb om at finde et globalt optimalt. Derfor kan grådige algoritmer give et gæt, der ser optimalt ud på det tidspunkt, men bliver dyrt ned ad linjen og ikke garanterer et globalt optimalt.
På den anden side finder dynamisk programmering den optimale løsning på underproblemer og træffer derefter et informeret valg for at kombinere resultaterne af disse underproblemer for at finde den mest optimale løsning.
