LCS

Jeg sliter litt med LCS. Jobber en seg bakover eller framover? Ut ifra notatene fra forelesningen forstod jeg det slik at vi sammenligner de to siste elementene. Om de er ulike, kutter vi av en av dem fra en av sekvensene, og sammenligner så på nytt (og gjentar inntil vi finner to like). Men når vi da har funnet to like, går vi til de nest siste elementene i begge sekvensene?

Og hva er kjøretiden? \(O(m + n)\) (hvor \(m\) og \(n\) er antallet elementer i de to sekvensene, eller \(O(mn)\)?

Basert på et Piazza-spørsmål fra 2015

Du må jobbe deg fremover. Som med alle andre problemer, må du løse delproblemen før du kan løse hovedproblemet. Men, også som med alle andre problemer: Du kan løse problemet rekursivt, og da «ser det ut som om» du løser det fra slutten. Du vil løse hovedproblemet, og ber rekursivt om svaret på delproblemene. Når svarene kommer, kombinerer du dem. Men da har jo rekursjonen alt jobbet bak i kulissene, og gått helt tilbake til start, og funnet de grunnleggende svarene først. Så om du jobber iterativt eller rekursivt så vil det se helt forskjellig ut – men egentlig være akkurat det samme.

Dvs., vi «kutter av» de siste elementene, og løser resten rekursivt. Rekursjonen betyr ikke at vi «går videre» – det betyr at vi løser disse først, før vi er i stand til å løse hele problemet. Dvs.:

Hvis de to siste bokstavene er like: Løs problemet rekursivt der disse to er kuttet av, og bruk dette svaret \(+\, 1\).

Hvis de ikke er like: Løs to varianter rekursivt, der du enten har kuttet av den ene eller den andre. Bruk den beste av disse løsningene.

Men du trenger ikke gjøre det rekursivt. Hvis du alt har løst problemet for alle tidligere prefix-kombinasjoner, kan du bare slå opp disse tre tilfellene direkte i tabellen med svarene. Da har du bare kommet rekursjonen i forkjøpet, på en måte.

Det er et konsept det er nyttig/viktig å forstå grundig, så jeg anbefaler at du ser nærmere på det. Her er et enkelt eksempel i Python:

>>> def f(n):
...     if n == 0:
...         return
...     f(n-1)
...     print("Bygger løsning", n, "basert på løsning", n-1)

Funksjonen er rekursiv, og det kan se ut som om man «jobber seg bakover». Men la oss se hva som skjer hvis vi jobber oss bakover fra f(5), for eksempel:

>>> f(5)
Bygger løsning 1 basert på løsning 0
Bygger løsning 2 basert på løsning 1
Bygger løsning 3 basert på løsning 2
Bygger løsning 4 basert på løsning 3
Bygger løsning 5 basert på løsning 4

Som du ser, den jobber seg fremover uansett, akkurat som om vi hadde hatt en for-løkke som gikk frem mot n.

Det er samme logikk i LCS. Vi definerer svaret på lcs(a, b) ut fra svarene på lcs(a[:-1], b), lcs(a, b[:-1]) og lcs(a[:-1], b[:-1]). Disse løses rekursivt, så det kan se ut som om vi jobber oss bakover fra de siste bokstavene i a og b, men saken er at dette trinnet utføres sist, etter de rekursive kallene, og det oppfører seg akkurat som funksjonen over (bare med to parametre, da).

Her er den rekursive versjonen fra Python Algorithms:

def rec_lcs(a,b):                               # Longest common subsequence
    @memo                                       # L is memoized
    def L(i,j):                                 # Prefixes a[:i] and b[:j]
        if min(i,j) < 0: return 0               # One prefix is empty
        if a[i] == b[j]: return 1 + L(i-1,j-1)  # Match! Move diagonally
        return max(L(i-1,j), L(i,j-1))          # Chop off either a[i] or b[j]
    return L(len(a)-1,len(b)-1)                 # Run L on entire sequences

Det er viktig at den rekursive funksjonen er memoisert, siden vi ellers ville få eksponentiell kjøretid. (Definisjonen av @memo finner du i Python Algorithms. Du kan evt. bruke @lru_cache fra standardbiblioteket, med None som maks-størrelse.)

Så der ser du altså en implementasjon som ser ut til å jobbe seg bakover – men om du satte inn print-setninger, så ville du se at den egentlig jobbet seg fremover. Hele poenget er jo nettopp at de rekursive kallene må utføres først, så vi har løsningene klare på delproblemene først.

Den algoritmen er ekvivalent med denne, ikke-rekursive varianten:

def lcs(a,b):
    n, m = len(a), len(b)
    pre, cur = [0]*(n+1), [0]*(n+1)             # Previous/current row
    for j in range(1,m+1):                      # Iterate over b
        pre, cur = cur, pre                     # Keep prev., overwrite cur.
        for i in range(1,n+1):                  # Iterate over a
            if a[i-1] == b[j-1]:                # Last elts. of pref. equal?
                cur[i] = pre[i-1] + 1           # L(i,j) = L(i-1,j-1) + 1
            else:                               # Otherwise...
                cur[i] = max(pre[i], cur[i-1])  # max(L(i,j-1),L(i-1,j))
    return cur[n]                               # L(n,m)

Den løser de samme delproblemene i samme rekkefølge. Den gjør det bare litt mer «gjennomsiktig», med for-løkker som helt opplagt går «fremover».

Hvert delproblem kan løses i konstant tid, så den asymptotiske kjøretiden blir lik antall delproblemer. Og antall delproblemer er lik antall kombinasjoner av prefikser av de to sekvensene, altså \(\Theta(mn)\). Det er kanskje lettere å se ut fra den iterative løsningen, siden vi har én løkke som går fra \(1\) til \(n\) inne i én som går fra \(1\) til \(m\).