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(void) {
    for (int 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ámítani é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(void) {
    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ámított részeredményeket. Amikor a kérdés fib(45), akkor fib(44) és fib(43) újra kiszámító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ámított é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);
    /* már kiszámítottuk? ha nem, akkor most! */
    if (fibszam[n] == 0)
        fibszam[n] = fib(n - 1) + fib(n - 2); // eltárolódik!
    /* adjuk vissza */
    return fibszam[n];
}

int main(void) {
    for (int 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(void) {
    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 itt is mindig ugyanaz, úgyhogy gyorsabb lenne eltárolva!

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ámított 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>
#include <stdbool.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 bool elso = true;

    /* 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) {
        for (int m = 0; m < 2000 / 5 + 1; m += 1)
            for (int h = 0; h < 6; h += 1)
                megoldasok[m][h] = -1;
        elso = false;
    }

    if (megoldasok[mennyit / 5][hanyadiktol] == -1) // kiszámítottuk már ezt?
        megoldasok[mennyit / 5][hanyadiktol] =
            penzvalto(mennyit - fajtak[hanyadiktol], hanyadiktol)
            + penzvalto(mennyit, hanyadiktol + 1);

    return megoldasok[mennyit / 5][hanyadiktol];
}

int main(void) {
    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 másképp: 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ámítottuk-e már valamikor azt, ami éppen most is a kérdés.

A dinamikus programozásról részletesen az Algoritmuselmélet c. tárgyban lesz szó.