Dinamikus programozás

Dinamikus programozás (DP; ang. dynamic programming, DP) — összetett optimalizálási feladatok megoldásának módszere, amely az eredeti feladat egyszerűbb részfeladatok sorozatára való bontásán alapul. A módszer többlépéses döntéshozatali folyamatokra alkalmazható, ahol a teljes feladat optimális megoldása a részfeladatok optimális megoldásaiból építhető fel.

A fogalmat Richard Bellman amerikai matematikus vezette be az 1950-es években. Ebben az összefüggésben a „programozás" szó „tervezés" vagy „optimális cselekvési terv összeállítása" értelemben szerepel, nem pedig számítógépes kód írását jelenti.

Kulcstulajdonságok és tételek

A dinamikus programozás alkalmazhatóságát egy feladatra két alapvető tulajdonság megléte határozza meg.

Bellman optimalitási elve

A módszer központi fogalma a Bellman-féle optimalitási elv (ang. Bellman's principle of optimality). Ez kimondja: bármilyen legyen is a kezdeti állapot és a kezdeti döntés, a további döntéseknek optimális stratégiát kell alkotniuk az első döntés eredményeként kapott állapotra nézve.

Más szóval, az optimális trajektória bármely része önmagában is optimális. Ez a tulajdonság lehetővé teszi, hogy az általános feladatot egyszerűbb részfeladatok sorozatára bontsuk, és azokat rekurzívan oldjuk meg.

Átfedő részfeladatok

Egy feladatnak átfedő részfeladatok (ang. overlapping subproblems) tulajdonsága van, ha rekurzív megoldása során ugyanazok a részfeladatok többször is előfordulnak. A DP lehetővé teszi az ismételt számítások elkerülését azáltal, hogy elmenti a már megoldott részfeladatok eredményeit (ezt a technikát memoizációnak vagy táblázatosításnak nevezik), ami jelentősen növeli a hatékonyságot a naiv rekurzív felsoroláshoz képest.

Bellman-egyenlet

Az optimalitási elvből következik a módszer alapvető rekurrens összefüggése — a Bellman-egyenlet. Ez összekapcsolja az aktuális állapot „értékét" (optimális nyereségét vagy költségét) a következő állapotok értékeivel. Additív célfüggvényű determinisztikus többlépéses folyamat esetén általános alakja:

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

ahol:

• $k$ — a lépés sorszáma ($m$-tól 1-ig);
• $x$ — a rendszer állapota a $k-1$. lépésben;
• $y$ — a $k$. lépésben hozott irányított döntés;
• ${\phi }_k(x,y)$ — a k-adik lépésen elért nyereség (vagy költség);
• $f_k(x,y)$ — a rendszer új állapotát meghatározó függvény;
• $V_k(s)$ — a célfüggvény optimális értéke a $k$. lépéstől $s$ állapotban induló részfeladatra.

Az egyenletet sorban, általában „a végéről" oldják meg, az utolsó lépéstől visszafelé haladva az első felé.

Alkalmazási példák

• Legrövidebb út keresése gráfban: Ez a feladat rendelkezik az optimális részstruktúra tulajdonságával, mivel a legrövidebb út bármely szakasza maga is legrövidebb. A Bellman–Ford- és a Floyd–Warshall-algoritmus klasszikus példája a DP alkalmazásának e feladat megoldásában.
• Hátizsák-feladat: A feladat egy korlátozott kapacitású hátizsák optimális feltöltéséről szól, különböző értékű és súlyú tárgyakkal. A DP lehetővé teszi e feladat megoldását úgy, hogy a tárgyakat sorban veszi figyelembe, és minden lépésben kiszámítja a maximális értéket a maradék kapacitás összes lehetséges értékére.
• Erőforrás-elosztási feladat: Korlátozott erőforrás (pl. befektetések) elosztása több projekt között az összesített hatás maximalizálása céljából.

Korlátok

A módszer fő korlátja a dimenzionalitás átka (ang. curse of dimensionality) — Bellman által bevezetett fogalom, amely az állapotok számának, és következésképpen a számítási bonyolultságnak exponenciális növekedését jelöli a rendszer állapotát leíró változók számának növekedésével. Ez korlátozza a pontos DP gyakorlati alkalmazhatóságát nagyon nagy méretű feladatokra.

Kapcsolódó fogalmak

• Operációkutatás
• Optimális irányítás elmélete
• Markov-döntési folyamat (sztochasztikus általánosítás)
• Hamilton–Jacobi–Bellman-egyenlet (folytonos idejű analóg)

Megjegyzések

</references>