InfoC adventi naptár

Dinamikus programozás

A laboron azt tapasztaltuk, hogy a rekurzióval működő Fibonacci számsor kiszámító program borzalmasan lassú: a negyvenedik szám előállításán már több másodpercet gondolkodik a gép. Ez azonban nem azt jelenti, hogy a rekurzív megvalósítás hibás, azt pedig főleg nem, hogy általában a rekurzió lassú lenne.

Szedjük elő egy kicsit az említett programot! A rekurzív fib() függvény így nézett ki:

#include <stdio.h>

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

int main() {
    int i;
    
    for (i=0; i<45; ++i)
        printf("fib(%d) = %d\n", i, fib(i));
    
    return 0;
}

Ez a nagy számokra a program egyre lassabb lesz. Bár minden sorban csak az előző két kiírt szám összegét kellene kiszámolni és kiírni, mégis egyre többet kell várni a megjelenő számokra. Ennek egyik oka az, hogy a kiírt nagy számok tulajdonképpen nullák és egyek összegeként állnak elő. Vegyük észre: csak n=0 és n=1 esetén tér vissza a függvény konkrét értékkel, minden más érték számítás eredményeként jön ki:

#include <stdio.h>

void fibkiir(int n) {
    if (n<2)
        printf("%d", n);
    else {
        fibkiir(n-1);
        printf("+");
        fibkiir(n-2);
    }
}

int main() {
    fibkiir(10);
    
    return 0;
}

Másik oka pedig – vagy ugyanez az ok, másképpen megközelítve – az, hogy nem használja fel az algoritmus a már kiszámolt részeredményeket. Amikor a kérdés fib(45), akkor fib(44) és fib(43) újra kiszámolódik, hiába történt meg ez a kettő éppen az előbb. Sőt fib(44)-hez kell fib(43) is, úgyhogy a fib(43) értéke is többször kérdés, sőt kisebb számokra még rosszabb a helyzet.

Vagyis az oszd meg és uralkodj módszerünk, miszerint a fib(45) problémát egyszerűbb, fib(44) és fib(43) részfeladatokra bontottuk, itt nem túl hatékony. Mégpedig azért nem, mert a részfeladatoknak közös részfeladatai is vannak, és ezt nem veszi figyelembe.

Mi itt a az ötlet? Megtehetjük azt például, hogy eltároljuk a már kiszámolt értékeket. Nem csak azért, mert esetleg újra kérdezhetik ugyanazt (és a számsor 44. tagja mindig ugyanannyi lesz), hanem mert a rekurzió során a függvény magától is mindig ugyanazokat a számokat kérdezi. A tároló itt lehet egyszerűen egy tömb, amely kezdetben 0 értékekkel van kitöltve. Természetesen ez nem lehet a függvény automatikus, lokális változója, hiszen akkor elveszne az értéke. Globális kell legyen, vagy ami a legjobb: egy statikus lokális.

#include <stdio.h>
#include <assert.h>

int fib(int n) {
    /* statikus: megőrzi az értékét! */
    static int fibszam[46] = {0};
    
    /* ha triviális */
    if (n<2)
        return n;
    /* a tároló véges, bár lehetne mallocolni */
    assert(n<46);
    /* amúgy már kiszámoltuk? ha nem, számoljuk ki! */
    if (fibszam[n]==0)
        fibszam[n] = fib(n-1)+fib(n-2); // eltárolódik!
    /* adjuk vissza */
    return fibszam[n];
}

int main() {
    int i;
    
    for (i=0; i<45; ++i)
        printf("fib(%d) = %d\n", i, fib(i));
    
    return 0;
}

A lényeg a jelölt sorban van: amit egyszer már kérdeztek a függvénytől, az arra kapott választ eltárolja a tömbben, és legközelebb már számítás nélkül visszatér vele. Látszik, hogy ez így ugyanolyan gyors, mint az iteratív megoldás.

A vázolt technikát dinamikus programozásnak nevezik (dynamic programming – memoization, tabulation). Ezt az „elágazó” problémáknál, ahol a részfeladatok közösek, gyakran alkalmazzák, mivel legtöbbször egyszerűbb a részfeladatok eredményeit egy táblázatban eltárolni, és onnan kikeresni, mintsem egy új, sokkal bonyolultabb algoritmust tervezni a megoldásra, amely más úton gondolkozik, és elkerüli a részfeladatok ismétlését.

Nézzük meg újra a rekurziós gyak pénzváltós feladatát is ilyen szempontból! Ott az volt a kérdés, hányféleképpen fizethetünk ki 100 forintot úgy, hogy 5, 10, 20, 50 forintosokat használunk. Ha egy kicsit átírjuk ezt, hogy 2000 forintot kelljen fizetni, 100-asokkal és 200-asokkal is, máris látjuk, hogy nagyon lassú a program:

#include <stdio.h>
#include <stdlib.h>
 
int penzvalto(int mennyit, int *fajtak, int hanyadiktol) {
    if (mennyit==0)
        return 1;
    if (fajtak[hanyadiktol]==-1 || mennyit<0)
        return 0;
 
    return penzvalto(mennyit-fajtak[hanyadiktol], fajtak, hanyadiktol)
           + penzvalto(mennyit, fajtak, hanyadiktol+1);
}
 
int main() {
    int fajtak[]={5, 10, 20, 50, 100, 200, -1};
    
    printf("Összesen: %d lehetőség\n", penzvalto(2000, fajtak, 0));
    
    return 0;
}

Ennek ugyanaz a gondja, mint az első, fibonaccis programnak. Egy csomóféle úton eljut oda, hogy már csak a maradék 100 forint a kérdés, és újra meg újra megoldja ugyanezt a részfeladatot. A válasz viszont mindig ugyanaz, így gyorsabb lenne eltárolni!

Tekintsük fixnek a használható pénzérméket: ilyenkor a függvénynek csak két paramétere marad, hogy mennyit kell fizetni, és hogy a használható érmék közül hányfélével dolgozhat még. A kiszámolt válaszokat betehetnénk pl. egy láncolt listába, vagy valami más, trükkösebb adatszerkezetbe is. Az egyszerűség kedvéért maradjunk egy egyszerű tömbnél: a megoldasok[][] kétdimenziós tömb tárolja azt, hogy mennyit pénzt hanyadiktol fajtákkal hányféleképpen lehet kifizetni: megoldasok[mennyit/5][hanyadiktol]. (Azért /5, mert úgyis 5 forint a legkisebb egység.)

#include <stdio.h>
#include <stdlib.h>

int fajtak[]={5, 10, 20, 50, 100, 200};
 
int penzvalto(int mennyit, int hanyadiktol) {
    /* megoldasok[mennyit/5][hanyadiktol] */
    static int megoldasok[2000/5+1][6];
    static int elso = 1;

    /* triviális megoldások */
    if (mennyit==0)
        return 1;
    if (hanyadiktol==6 || mennyit<0)
        return 0;

    /* első futtatáskor inicializáljuk a tömböt csupa -1-re,
     * mert itt nem jó a 0-s kezdeti érték */
    if (elso) {
        int m, h;
        for (m = 0; m<2000/5+1; m+=1)
            for (h = 0; h<6; h+=1)
                megoldasok[m][h] = -1;
        elso = 0;
    }
    
    if (megoldasok[mennyit/5][hanyadiktol]==-1) // kiszámoltuk már ezt?
        megoldasok[mennyit/5][hanyadiktol] =
            penzvalto(mennyit-fajtak[hanyadiktol], hanyadiktol)
             + penzvalto(mennyit, hanyadiktol+1);
 
    return megoldasok[mennyit/5][hanyadiktol];
}
 
int main() {
    printf("Összesen: %d lehetőség\n", penzvalto(2000, 0));
    
    return 0;
}

Látszik, hogy az átalakítás szinte triviális, és az eredeti algoritmus is változatlan formában szerepelhet a programban. Ez más algoritmusoknál sincs így: csak létre kell hozni egy (kérdés;válasz) elemeket tartozó táblázatot, és a számítás előtt mindig megnézni, hogy kiszámoltuk-e már valamikor azt, ami éppen most is a kérdés.