DINAMIKUS PROGRAMOZÁS: JELLEMZŐK, PÉLDA, ELŐNYÖK, HÁTRÁNYOK - TECHNOLÓGIA - 2026

A dinamikus programozás egy olyan algoritmus, amely egy komplex problémát oly módon old meg, hogy részproblémákra osztja, és az eredményeket tárolja, hogy elkerülje az eredmények újraszámítását.

Ezt az ütemtervet akkor használják, ha problémái vannak, amelyeket hasonló alproblémákra lehet felosztani, hogy eredményeiket újra felhasználhassák. Leginkább ezt az ütemtervet használják optimalizálásra.

Dinamikus programozás. A Fibonacci szekvenciában egymásra helyezett alproblémák. Forrás: Wikimedia commons, en: Felhasználó: Dcoatzee, a felhasználó nyomon követi: Stannered / public domain

A rendelkezésre álló alprobléma megoldása előtt a dinamikus algoritmus megpróbálja megvizsgálni a korábban megoldott alproblémák eredményeit. Az alproblémák megoldásait egyesítik a legjobb megoldás elérése érdekében.

Ahelyett, hogy ugyanazt az alproblémát újra és újra kiszámította volna, a megoldást valamilyen memóriában tárolhatja, amikor először találkozik ezzel az alproblémával. Ha ez újra megjelenik egy másik alprobléma megoldásakor, akkor a memóriában már tárolt megoldást megteszik.

Ez egy csodálatos ötlet a memória idejének rögzítéséhez, ahol további hely felhasználásával javíthatja a megoldás megtalálásához szükséges időt.

A dinamikus programozás jellemzői

A következő alapvető jellemzőkkel kell szembenéznie, hogy a dinamikus programozás alkalmazható legyen:

Optimális alszerkezet

Ez a jellemző azt fejezi ki, hogy az optimalizálási probléma megoldható az azt tartalmazó másodlagos problémák optimális megoldásainak kombinálásával. Ezeket az optimális alszerkezeteket rekurzióval írjuk le.

Például egy gráfban egy optimális alszerkezetet mutatunk be az r legrövidebb úton, amely az s csúcsról a t csúcsra megy:

Vagyis ezen a legrövidebb úton bármely i közbenső csúcs felvehető. Ha r valóban a legrövidebb út, akkor azt fel lehet osztani az r1 (s-től i-ig) és r2 (i-től t-ig) alútvonalakká, így ezek a legrövidebb útvonalak a megfelelő csúcsok között.

Ezért a legrövidebb utak megtalálásához a megoldás könnyen rekurzív módon megfogalmazható, és ezt a Floyd-Warshall algoritmus is elvégzi.

Átfedő alproblémák

Az alprobléma helyének kicsinek kell lennie. Vagyis bármely rekurzív algoritmusnak, amely egy problémát megold, új és újra ugyanazokat a részproblémákat kell megoldania, nem pedig új alproblémákat generálni.

Például a Fibonacci sorozat előállításához ezt a rekurzív összetételt vehetjük figyelembe: Fn = F (n - 1) + F (n - 2), az alapesegként véve, hogy F1 = F2 = 1. Akkor lesz: F33 = F32 + F31 és F32 = F31 + F30.

Mint láthatja, az F31 feloldódik az F33 és az F32 rekurzív alfestékébe. Bár az alproblémák száma nagyon kicsi, ha egy ilyen rekurzív megoldást alkalmaz, akkor újra és újra megoldja ugyanazokat a problémákat.

Ezt a dinamikus programozás veszi figyelembe, tehát az egyes alproblémákat csak egyszer oldja meg. Ez kétféle módon valósítható meg:

Felülről lefelé irányuló megközelítés

Ha valamely probléma megoldása rekurzívan megfogalmazható alproblémáinak megoldásával, és ha ezek az alproblémák átfedésben vannak, akkor az alproblémák megoldásai könnyen memorizálhatók vagy táblázatban tárolhatók.

Minden alkalommal, amikor új alprobléma megoldást keres, a táblázatot ellenőrizni fogják, hogy korábban megoldódtak-e. Abban az esetben, ha egy oldatot tárolnak, akkor azt újra kiszámítás helyett fogják használni. Ellenkező esetben a részprobléma megoldódik, a megoldást a táblázatban tárolva.

Alulról felfelé építkező megközelítés

Miután egy probléma megoldását rekurzívan fogalmazták meg alproblémái szempontjából, meg lehet próbálni a problémát felfelé formázni: először megpróbáljuk megoldani az alproblémákat, és azok megoldásait felhasználva a nagyobb alproblémákra megoldást találni.

Ez általában táblázatos formában történik, ismételten generálva a nagyobb és nagyobb alproblémákhoz megoldásokat kisebb alproblémák megoldásainak felhasználásával. Például, ha az F31 és F30 értéke már ismert, akkor az F32 értéke közvetlenül kiszámítható.

Összehasonlítás más technikákkal

A dinamikus programozással megoldandó probléma egyik jelentős vonása az, hogy az átfedő alproblémák legyenek. Ez az, ami megkülönbözteti a dinamikus programozást a split és conquer technikától, ahol nem szükséges a legegyszerűbb értékeket tárolni.

Ez hasonló a rekurzióhoz, mivel az alapesetek kiszámításakor a végső érték induktív módon meghatározható. Ez az alulról felfelé építkező megközelítés jól működik, ha egy új érték csak az előzőleg kiszámított értékektől függ.

Példa

Minimális lépések az 1 eléréséhez

Bármely "e" pozitív egész szám esetén a következő három lépés bármelyike ​​végrehajtható.

- Kivonjon 1-t a számból. (e = e-1).

- Ha osztható 2-vel, akkor osztható 2-del (ha e% 2 == 0, akkor e = e / 2).

- Ha osztható 3-mal, akkor osztja 3-val (ha e% 3 == 0, akkor e = e / 3).

A fenti lépések alapján meg kell találni ezeknek a lépéseknek a minimális számát, hogy az e-t 1-re tegyék. Például:

- Ha e = 1, akkor eredmény: 0.

- Ha e = 4, akkor eredmény: 2 (4/2 = 2/2 = 1).

- Ha e = 7, eredmény: 3 (7-1 = 6/3 = 2/2 = 1).

Fókusz

Gondolhatunk arra, hogy mindig olyan lépést választunk, amely az n-et a lehető legalacsonyabbá teszi, és így folytatjuk, amíg el nem éri az 1-et. Látható azonban, hogy ez a stratégia itt nem működik.

Például, ha e = 10, akkor a lépések a következők: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 lépés). Az optimális forma azonban: 10-1 = 9/3 = 3/3 = 1 (3 lépés). Ezért meg kell próbálnunk minden lehetséges lépést, amely elvégezhető minden egyes n értékre, és kiválasztjuk a lehetőségek minimális számát.

Minden rekurzióval kezdődik: F (e) = 1 + perc {F (e-1), F (e / 2), F (e / 3)}, ha e> 1, alapesetként véve: F (1) = 0. A visszatérési egyenlet alapján elkezdi kódolni a rekurziót.

Látható azonban, hogy átfedő alproblémái vannak. Ezenkívül az adott bemenet optimális megoldása az alproblémáinak optimális megoldásától függ.

A memorizáláshoz hasonlóan, ahol a megoldatott alproblémák megoldásait későbbi felhasználásra tárolják. Vagy a dinamikus programozáshoz hasonlóan, az alulról indul, és az adott e-ig halad. Akkor mindkét kód:

memorization

Dinamikus alulról felfelé történő programozás

Előny

A dinamikus programozás használatának egyik fő előnye, hogy felgyorsítja a feldolgozást, mivel a korábban kiszámított referenciákat használják. Mivel ez egy rekurzív programozási technika, csökkenti a kód sorait a programban.

Zavaró algoritmusok vs dinamikus programozás

A kapzsi algoritmusok hasonlóak a dinamikus programozáshoz, mivel mindkettő optimalizálási eszköz. A kapzsi algoritmus azonban optimális megoldást keres minden egyes helyi lépésben. Vagyis kapzsi választást keres, abban a reményben, hogy globális optimumot talál.

Ezért a kapzsi algoritmusok olyan feltételezést tehetnek, amely akkoriban optimálisnak tűnik, ám a jövőben drága lesz, és nem garantálja a globális optimált.

Másrészről, a dinamikus programozás megtalálja az optimális megoldást az alproblémákra, majd megalapozott döntést hoz az alproblémák eredményeinek egyesítésével, hogy valóban megtalálja a legoptimálisabb megoldást.

hátrányok

- Nagyon sok memóriára van szükség az egyes részproblémák kiszámított eredményének tárolásához anélkül, hogy garantálhatnánk, hogy a tárolt értéket felhasználjuk-e.

- Sokszor a kimeneti értéket tárolja anélkül, hogy végrehajtás közben felhasználnánk a következő alproblémákban. Ez felesleges memóriafelhasználást eredményez.

- A dinamikus programozás során a funkciókat rekurzívan hívják. Ez a veremmemória folyamatosan növekszik.

Rekurzió vs dinamikus programozás

Ha korlátozott memória van a kód futtatásához, és a feldolgozási sebesség nem jelent gondot, használhatja a rekurziót. Például, ha egy mobil alkalmazást fejlesztett, akkor a memória nagyon korlátozott az alkalmazás futtatásához.

Ha azt akarja, hogy a program gyorsabban futjon, és nincs memóriakorlátozása, akkor előnyösebb a dinamikus programozás.

Alkalmazások

A dinamikus programozás olyan hatékony megoldási módszer, amelyet rendkívül nehéznek tűnhet ésszerű időn belül megoldani.

A dinamikus programozási paradigmán alapuló algoritmusokat a tudomány sok területén alkalmazzák, beleértve a mesterséges intelligencia számos példáját, a problémamegoldástól a beszédfelismerésig.

Dinamikus programozáson alapuló algoritmusok

A dinamikus programozás meglehetősen hatékony és nagyon sokféle probléma esetén kiválóan működik. Számos algoritmus mohó algoritmusalkalmazásnak tekinthető, például:

- Fibonacci szám sorozat.

- Hanoi tornyai.

- Az összes pár rövidebb útvonal a Floyd-Warshall-n keresztül.

- Hátizsákkal kapcsolatos probléma.

- A projekt ütemezése.

- A legrövidebb út a Dijkstrán.

- Repülésirányítás és robotikavezérlés.

- Matematikai optimalizálási problémák.

- Időben megosztott használat: a CPU használatának maximalizálása érdekében ütemezze a munkát.

Fibonacci szám sorozat

A Fibonacci számok a következő sorrendben találhatók: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 stb.

A matematikai terminológiában a Fibonacci-szám Fn sorozatát a visszatérési képlet határozza meg: F (n) = F (n -1) + F (n -2), ahol F (0) = 0 és F (1) = 1.

Felülről lefelé irányuló megközelítés

Ebben a példában az összes kezdeti értékkel rendelkező keresési tömb -1-vel kezdődik. Ha valamely alprobléma megoldására van szükség, először ezt a keresési mátrixot kell keresni.

Ha a számított érték ott van, akkor az érték visszaadódik. Ellenkező esetben úgy számítják ki, hogy az eredmény a keresési tömbben tárolódik, hogy később újra felhasználható legyen.

Alulról felfelé építkező megközelítés

Ebben az esetben ugyanahhoz a Fibonacci-sorozathoz először f (0), majd f (1), f (2), f (3) és így tovább kell kiszámítani. Így az alproblémák megoldásait alulról felfelé építik.

Irodalom

1. Vineet Choudhary (2020). Bevezetés a dinamikus programozásba. Fejlesztő bennfentes. Feltöltve: developerinsider.co.
2. Alex Allain (2020). Dinamikus programozás C ++ formátumban. C programozás. Forrás: cprogramming.com.
3. Akadémia után (2020). A dinamikus programozás ötlete. Forrás: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dinamikus programozás és rekurzió - különbség, előnyök a példával. CSE verem. Feltöltve: csestack.org.
5. Code Chef (2020). Oktatóprogram a dinamikus programozáshoz. Forrás: codechef.com.
6. Programiz (2020). Dinamikus programozás. Forrás: programiz.com.