--- title: "Dinamikus programozás" source: "https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s" wiki: "systems-analysis.info/int" article: "Dinamikus_programozás" language: "hu" categories: - "Category:Hungarian" - "Category:Operations research" revision_id: 1691 wiki_created_at: 2026-09-06T22:52:32Z wiki_modified_at: 2026-09-06T22:52:32Z downloaded_at: 2026-09-07T22:47:16Z --- # 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[\[1\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-bigenc-dp-1)[\[2\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-ru-wiki-dp-2). 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[\[3\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-rechetnikov-dp-3). 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[\[4\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-en-wiki-dp-4). ## 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[\[3\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-rechetnikov-dp-3). 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**[\[1\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-bigenc-dp-1). 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) = \max\limits_{y \in U(x)}\{\varphi_{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; - $\varphi_{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[\[5\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-mit-amp-5). - **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[\[6\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-ru-wiki-curse-6)[\[7\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-utexas-ormm-7). 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 [\[1\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-bigenc-dp-1) [\[2\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-ru-wiki-dp-2) [\[3\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-rechetnikov-dp-3) [\[4\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-en-wiki-dp-4) [\[5\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-mit-amp-5) [\[6\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-ru-wiki-curse-6) [\[7\]](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_note-utexas-ormm-7) \ 1. ↑ [1.0](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-bigenc-dp_1-0) [1.1](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-bigenc-dp_1-1) [1.2](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-bigenc-dp_1-2) "Динамическое программирование". *Большая российская энциклопедия*. [1] 2. ↑ [2.0](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-ru-wiki-dp_2-0) [2.1](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-ru-wiki-dp_2-1) "Динамическое программирование". *Википедия*. [2] 3. ↑ [3.0](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-rechetnikov-dp_3-0) [3.1](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-rechetnikov-dp_3-1) [3.2](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-rechetnikov-dp_3-2) Решетников А. Н., Коченков А. В., Пиров Д. М., Рябоконь Д. А. (2011). *Динамическое программирование. Примеры применения*. Учебное пособие, ННГУ им. Лобачевского (ВМиК). [3] 4. ↑ [4.0](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-en-wiki-dp_4-0) [4.1](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-en-wiki-dp_4-1) "Dynamic programming". *Wikipedia*. [4] 5. ↑ [5.0](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-mit-amp_5-0) [5.1](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-mit-amp_5-1) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. [5] 6. ↑ [6.0](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-ru-wiki-curse_6-0) [6.1](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-ru-wiki-curse_6-1) "Проклятие размерности". *Википедия*. [6] 7. ↑ [7.0](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-utexas-ormm_7-0) [7.1](https://systems-analysis.info/int/Dinamikus_programoz%C3%A1s#cite_ref-utexas-ormm_7-1) Jensen P. A. (2004). *Dynamic Programming – Models*. Operations Research Models and Methods, Univ. of Texas. [7]