Algoritmer og datastrukturerHjem

CMD + K

Tilbake til Algoritmer og datastrukturer

TDT4120 · Dynamisk programmering

Fyll DP-tabellen

Hver celle er ett delproblem, løst én gang. Følg avhengighetene som hvert svar bygges fra — og spor så den optimale løsningen tilbake ut.

Rader = streng Y · kolonner = streng X.
NåAvhenger avLøsning
∅
A
G
C
A
T
∅
0
0
0
0
0
0
G
0
A
0
C
0
1 / 23Grunntilfelle: et tomt prefiks har LCS-lengde 0 — fyll rad 0 og kolonne 0.
RekurrensX = AGCAT · Y = GAC
c[i][j] = 0 if i=0 or j=0 = c[i−1][j−1] + 1 if X[j] = Y[i] = max(c[i−1][j], c[i][j−1]) otherwise
—

Lær mer

En DP-tabell fylles bunn-opp: hver celle kombinerer noen få allerede løste delproblemer (avhengighetene, markert i blått) til en ny optimal delløsning. Den aktive cellen glør i fagfargen.

Når hele tabellen er fylt, leses løsningen ut ved å følge avhengighetene baklengs fra det optimale hjørnet — traceback-stien lyser opp underveis. LCS arver diagonalen ved treff (ellers maks av over/venstre); redigeringsavstand og ryggsekk velger det beste blant tidligere celler.

Relaterte kapitler

6Dynamisk programmering