Adventi naptár
Czirkos Zoltán · 2021.08.24.
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ó.