Dynamisk programmering

Memoisering (memoization) og dynamisk programmering (dynamic programming / DP) er to ganske like teknikker for å designe algoritmer, og de kan brukes på mange forskjellige problemstillinger. Selve teknikken er relativt enkel, men den kan anvendes på mange kreative måter, så det krever mye oppgavetrening å bli vant med det.

Idéen bak teknikkene illustreres fint av problemet med å regne ut Fibonacci-tall. Fibonacci-tallene er en tallrekke som begynner med to ettall, og deretter er hvert tall summen av de to forrige: 1, 1, 2, 3, 5, 8, 13, 21, … Dette kan defineres rekursivt slik:
f(0) = 1
f(1) = 1
f(n) = f(n – 1) + f(n – 1) når n > 1
Dette implementerer vi enkelt i C++:

long long fib(int n) {
    if (n < 2)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

Med unntak av at selv long long (64-bits heltall) fort blir en for liten datatype fordi Fibonacci-tallene blir svært store ganske fort, har denne fremgangsmåten et problem som blir åpenbart når vi prøver å mate inn større og større verdier: allerede for så små verdier som 40 blir den uholdbart treg, og det vil vise seg at hver gang man øker n med 1, vil kjøretiden øke med en faktor på ca. 1.6. Hva skyldes dette, når det er en så enkel beregning?

Hvis vi tegner opp en call graph, vil vi se hva som går galt: f.eks. må fib(5) regnes ut ved hjelp av fib(4) og fib(3). Men fib(4) må regnes ut ved hjelp av fib(3) og fib(2), så hele utregningen av fib(3) gjøres to ganger – og det blir bare verre og verre jo lenger ned man går:

fib(5)
    fib(4)
        fib(3)
            fib(2)
                fib(1)
                fib(0)
            fib(1)
        fib(2)
            fib(1)
            fib(0)
    fib(3)
        fib(2)
            fib(1)
            fib(0)
        fib(1)

Løsningen på dette er å innføre memoisering (uten r – ordet kommer fra “memo”, altså huskelapp, ikke fra memorisering), som går ut på å bruke et array eller et hashmap til å holde rede på svarene underveis etterhvert som man finner dem, slik at man slipper å gjøre nye utregninger av svar man allerede har funnet. (Et hashmap er et slags dynamisk array hvor indeksene kan være hva som helst, også f.eks. strenger (så det kalles nøkler i stedet for indekser), og hvor man kan sette inn nøkler ved behov. I C++ er hashmap implementert i klassen map.) Det første den rekursive funksjonen da må gjøre er å slå opp i arrayet / hashmap’et for å sjekke om svaret allerede er regnet ut. Dersom man bruker et array må man preallokere det til rett størrelse (pass på off-by-one-feil – hvis du trenger arrayindekser opp til og med n, må arrayet ha størrelse n + 1) og fylle ut elementene med sentinel-verdier (verdier som ikke er gyldige svar, og som man da kan bruke til å detektere at plassen ikke er fylt ut ennå). Enten man bruker array eller hashmap må man også starte med å legge inn basetilfellene.

Memoisering med array:

#include <iostream>

using namespace std;

const long long EMPTY = -1;

long long fib(int n, long long * mem) {
    if (mem[n] != EMPTY) // Har vi svaret fra før av?
        return mem[n];
    long long result = fib(n - 1, mem) + fib(n - 2, mem);
    mem[n] = result; // Husk å lagre resultatet i arrayet!
    return result;
}

int main() {
    int n;
    cin >> n;
    // Allokering
    long long * mem = new long long[n + 1];
    // Initialisering med sentinel-verdier
    for (int i = 0; i < n + 1; ++i) {
        mem[i] = EMPTY;
    }
    // Basetilfeller
    mem[0] = 1;
    if (n > 1) //...ellers er ikke arrayet stort nok
        mem[1] = 1;
    cout << fib(n, mem) << endl;
    return 0;
}

Man kunne godt ha hatt arrayet som en global variabel – det ville ha gått marginalt raskere, men kan bli rotete i store programmer.

Memoisering med hashmap:

#include <iostream>
#include <map>

using namespace std;

long long fib(int n, map<int, long long> & mem) { // Viktig å sende map'et som referanse for å unngå kopiering
    if (mem.find(n) != mem.end()) // Har vi svaret fra før av?
        return mem[n];
    long long result = fib(n - 1, mem) + fib(n - 2, mem);
    mem[n] = result; // Husk å lagre resultatet i arrayet!
    return result;
}

int main() {
    int n;
    cin >> n;
    // Allokering (sentinel-verdier trengs ikke i et map)
    map<int, long long> mem;
    // Basetilfeller
    mem[0] = 1;
    mem[1] = 1;
    cout << fib(n, mem) << endl;
    return 0;
}

Dersom man hadde printet et mellomresultat hver gang man fant det, ville man ha sett at resultatene dukker opp nedenfra og opp, selv om vi angrep problemet ovenfra og ned. Dette kan man utnytte til å lage en marginalt mer effektiv løsning som ikke bruker rekursjon (og som dermed også vil fungere i situasjoner hvor n kan være stor), ved at man bare itererer over tabellen og fyller den ut:

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    long long * mem = new long long[n + 1];
    mem[0] = 1;
    if (n > 1)
        mem[1] = 1;
    for (int i = 2; i <= n; ++i) { // Husk <= i stedet for den vanlige <
        mem[i] = mem[i - 1] + mem[i - 2];
    }
    cout << mem[n] << endl;
    return 0;
}

Dersom man ikke er interessert i mellomresultatene, trenger man ikke arrayet en gang:

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n < 2) {
        cout << 1 << endl;
        return 0;
    }
    long long previous = 1;
    long long current = 1;
    long long next;
    for (int i = 2; i <= n; i++) {
        next = current + previous;
        previous = current;
        current = next;
    }
    cout << current << endl;
    return 0;
}

I praksis bruker man vanligvis DP, med mindre man er i en situasjon hvor man vet at ikke alle mellomresultatene vil være nødvendig å beregne – da vil memoisering gå raskere fordi den aldri regner ut mellomresultater som ikke vil trenges senere.

DP brukes ofte når man er i en situasjon hvor man har et problem hvor løsningen består av en sekvens med handlinger, og det gjelder å finne den optimale sekvensen (ut fra en eller annen definisjon av “optimal sekvens), og hvor man i hvert steg kan velge mellom flere forskjellige handlinger – men hvor man ikke kan forutsi hvilken handling som er best. La oss betrakte myntutdelingsproblemet: man har n kroner som skal deles ut ved hjelp av færrest mulig mynter og sedler. Løsningen er altså en sekvens av valører (mynt- og seddelverdier). Med det norske myntsystemet kan man bruke en grådig algoritme: del hele tiden ut den største valøren som er mindre enn eller lik det gjenværende beløpet. Men med noen myntsett fungerer ikke dette: hvis myntsettet f.eks. består av enkroninger, firekroninger og femkroninger, vil den grådige algoritmen dele ut åtte kroner som én femmer og tre enkroninger, mens den optimale løsningen er to firekroninger. Nå er vi altså i en situasjon hvor man ikke kan forutsi hvilken handling som er best. Løsningen er å prøve alle mulige handlinger og se hva som skjer. La oss si at man skal dele ut 13 kroner. Den beste måten å gjøre det på vil enten være å først dele ut en enkroning og så dele ut 12 kroner på best mulig måte, eller å først dele ut en firekroning og så dele ut 9 kroner på best mulig måte, eller å først dele ut en femkroning og så dele ut 8 kroner på best mulig måte. Hvilken av disse som er best, vet vi ikke – så vi prøver alle sammen, og løser først delproblemene med å dele ut hhv. 12, 9 eller 8 kroner. Disse vil føre til nye delproblemer, som etterhvert vil begynne å overlappe – dermed trenger man memoisering eller DP.

OPPGAVE: Skriv et program som løser myntutdelingsproblemet med DP. Inputen består av først en linje med to tall n og k: og antallet valører og antallet beløp som skal deles ut. Deretter kommer en linje med n heltall, som er valørene (1 vil alltid være inkludert, men tallene er ikke nødvendigvis sortert – bruk og sort() til å sortere en vector), og så kommer k linjer med ett tall på hver: beløpene som skal deles ut. For hvert beløp, skriv ut det optimale antallet mynter.

Eksempelinput:

3 2
1 5 4
8
13

Eksempeloutput:

2
3

OPPGAVE: Andre ganger er problemstillingen todimensjonal, slik som i følgende IOI-oppgave fra 2004: http://olympiads.win.tue.nl/ioi/ioi2004/contest/day2/phidias.pdf . Løs denne også.

I myntutdelingsproblemet og i Phidias antar man at man har ubegrenset tilgang på mynter av de forskjellige valørene. Faktisk er det en forutsetning for DP at det ikke finnes delte ressurser som spises opp av løsningen, for da er det ikke sikkert at en løsning på et delproblem kan brukes (siden delproblemløsningen pluss måten vi kom oss frem til det delproblemet til sammen bruker for mye ressurser). Men noen ganger kan man håndtere slike delte ressurser ved å innføre en ekstra dimensjon. La oss si at du skal på bilferie, og har lagt opp en rute som går innom n byer (og dermed består av n – 1 veistrekninger mellom disse byene). Avstanden mellom hver by er et heltallig antall mil. I hver by finnes det en bensinstasjon, hvor bensinprisen er et heltallig antall kroner per liter. Bilen er en SUV som sluker eksakt én liter per mil. Hvordan kan man komme seg fra start til slutt på billigst mulig måte, gitt at man starter med tom tank som rommer et gitt, heltallig antall liter og ikke er interessert i å ha noe bensin igjen på tanken når man ankommer den siste byen? For å klare dette, holder det ikke å løse problemet “hva er billigste måte å komme seg til by i på?” ved å løse problemet “hva er billigste måte å komme seg til by i – 1 på?”, fordi billigste måte å komme seg til en by på involverer å kjøre tanken tom akkurat når man ankommer byen, noe som ikke er smart dersom bensinen er kjempedyr i den byen. Vi er nødt til å innføre mengden gjenværende bensin på tanken som en dimensjon (dvs. som et parameter) i problemstillingen, slik at vi kan løse problemet “hva er billigste måte å komme seg til by i på dersom jeg skal ha j liter igjen på tanken når jeg kommer dit?” ved å løse problemet “hva er billigste måte å komme seg til by i – 1 på dersom jeg skal ha k liter igjen på tanken når jeg kommer dit?” for forskjellige verdier av k og se hvilken som er billigst. Problemet er altså todimensjonalt her også, men uten at det er åpenbart fra oppgaven.

OPPGAVE: Skriv et program som løser bensinstasjonproblemet med DP. Første linje inneholder n og t: antall byer og kapasiteten til tanken; andre linje inneholder n – 1 heltall som er avstandene mellom de forskjellige byene; tredje linje inneholder n – 1 heltall som er bensinprisene i de forskjellige byene unntatt den siste (fordi prisen der er uinteressant siden man ikke skal fylle der). Output er prisen for den billigste måten å klare det på.

Eksempelinput:

5 25
5 22 10 15
40 10 30 22

Eksempeloutput:
(Kommer)

(Merk: Denne oppgaven kan muligens løses grådig også, men vi har ikke bevist at den grådige løsningsmetoden er korrekt.)

Til sist: merk at noen ganger er det flere potensielle sluttilstander, og man kan ikke forutsi hvilken som er best – da må løse for alle disse, og så avslutte med å løpe gjennom alle de potensielle sluttilstandene for å finne den beste.