Bevezetés az algoritmusokba: Dinamikus programozás

Tegyük fel, hogy számításokat végez megfelelő bemenetsorozattal. Minden esetben elvégeznek bizonyos számításokat valamilyen eredmény megszerzéséhez. Nem tudja, hogy ugyanazzal a kimenettel találkozott, amikor ugyanazt a bemenetet adta meg . Tehát olyan, mintha újra kiszámolná egy olyan eredményt, amelyet korábban a saját kimenetéhez adott bemenettel ért el.

De mi a probléma itt? A helyzet az, hogy értékes idődet pazaroljuk. Itt könnyen megoldhatja a problémát, ha nyilvántartást vezet, amely leképezi a korábban kiszámolt eredményeket. Ilyen például a megfelelő adatstruktúra használata. Például tárolhatja az inputot kulcsként, a outputot pedig értékként (a leképezés része).

Azok, akik nem emlékeznek a múltra, el vannak ítélve, hogy megismételjék. ~ Dinamikus programozás

Most a probléma elemzésével tárolja a bemenetét, ha új (vagy nincs az adatszerkezetben) a megfelelő kimenettel. Egyébként ellenőrizze a beviteli kulcsot, és az eredő kimenetet kapja meg annak értékéből. Így, ha elvégez egy kis számítást, és ellenőrzi, hogy létezik-e ez a bemenet az adatstruktúrában, akkor közvetlenül megkapja az eredményt. Így ezt a megközelítést összekapcsolhatjuk a dinamikus programozási technikákkal.

Búvárkodás a dinamikus programozásba

Dióhéjban elmondhatjuk, hogy a dinamikus programozást elsősorban a problémák optimalizálására alkalmazzák, ahol meg akarjuk találni a „legjobb” módszert valamire.

Egy bizonyos forgatókönyv olyan, hogy vannak olyan ismétlődő részproblémák, amelyeknek viszont vannak saját kisebb részproblémáik. A dinamikus programozás ahelyett, hogy megpróbálná megoldani ezeket az újra megjelenő részproblémákat, újra és újra a kisebb részproblémák megoldását javasolja. Ezután rögzíti az eredményeket egy táblázatba, amelyből megoldást lehet találni az eredeti problémára.

Például a Fibonacci-számoknak 0,1,1,2,3,5,8,13,…egyszerű leírása van, ahol minden kifejezés összefügg az előtte lévő két kifejezéssel. Ha ennek a sorozatnak F(n)a harmadik nfutamideje, akkor megvan F(n) = F(n-1) + F(n-2). Ezt rekurzív képletnek vagy megismétlődési relációnak nevezzük . A későbbi kifejezés kiszámításához korábbi kifejezésekre van szükség.

A dinamikus programozási problémák többsége két típusba sorolható:

  1. Optimalizálási problémák.
  2. Kombinációs problémák.

Az optimalizálási problémák elvárják, hogy kiválasszon egy megvalósítható megoldást, hogy a szükséges függvény értéke minimalizálva vagy maximalizálva legyen. A kombinatorikus problémák azt várják tőled, hogy kitaláld a cselekvés számos módját, vagy valamilyen esemény bekövetkezésének valószínűségét.

Megoldandó megközelítés: felülről lefelé vagy alulról felfelé

A probléma megoldásának két fő különböző módja van:

Felülről lefelé: Felülről indul, a problémát azáltal, hogy lebontja. Ha látja, hogy a probléma már megoldódott, akkor csak adja vissza a mentett választ. Ezt Memoizálásnak nevezik.

Alulról felfelé: Ön közvetlenül kezdi meg a kisebb részproblémák megoldását, felfelé haladva, hogy levezesse az egyetlen nagy probléma végső megoldását. Ebben a folyamatban garantált, hogy az alproblémák megoldódnak a probléma megoldása előtt. Ezt nevezhetjük Tabulációnak ( tábla kitöltő algoritmus ).

Az iteráció vs rekurzió vonatkozásában az alulról felfelé az iterációt, a felülről lefelé pedig a rekurziót használja.

Itt van egy összehasonlítás a naiv és a DP megközelítés között. A különbséget mindkettő időbeli összetettsége alapján láthatja.

Memorizáció: Ne felejtsd el

Jeff Erickson megjegyzéseiben leírja a Fibonacci-számokat:

A rekurzív algoritmus sebességhiányának nyilvánvaló oka az, hogy ugyanazokat a Fibonacci-számokat számolja ki újra és újra.

Jelentősen felgyorsíthatjuk rekurzív algoritmusunkat, ha csak felírjuk a rekurzív hívásaink eredményeit. Aztán újra megkereshetjük őket, ha később szükségünk van rá.

A memória a gyorsítótárba helyezés és a korábban kiszámított eredmények újrafelhasználásának technikájára utal.

Ha memoizálást használ a probléma megoldására, akkor azt a már megoldott részproblémák térképének karbantartásával kell megtennie (ahogy korábban a kulcs és az érték leképezéséről beszéltünk ). „ Felülről lefelé ” csinálja, abban az értelemben, hogy először a „felső” problémát oldja meg (amely általában visszatér az alproblémák megoldásához).

Pszeudokód a memóriához :

Tehát rekurzióval ezt extra rezsi memóriával (azaz itt kereséssel) hajtjuk végre az eredmények tárolására. Ha a keresésben van érték, akkor azt közvetlenül visszaküldjük, vagy hozzáadjuk az adott index kereséséhez.

Ne feledje, hogy van egy kompromisszum a többletköltségekről a táblázatos módszerrel kapcsolatban.

Ha azonban további vizualizációkat szeretne a memóriához, akkor javaslom, hogy nézze meg ezt a videót.

Táblázatok: táblázatos formában történő kitöltés

De ha látjuk, hogy a tömb (memoizált megoldás) kitöltődik, akkor a rekurziót egy egyszerű ciklussal helyettesíthetjük, amely szándékosan kitölti a tömböt a sorrendben, ahelyett, hogy a bonyolult rekurzióra hagyatkoznánk, hogy „véletlenül” megtegye helyettünk.

A táblázatkezelés „alulról felfelé” módon történik. Ez inkább egyenesen halad előre, minden értéket kiszámít. Kevesebb általános költséget igényel, mivel nem kell fenntartania a feltérképezést, és az adatokat táblázatos formában tárolja az egyes értékekhez. Szükségtelen értékeket is kiszámíthat. Ez akkor használható, ha csak annyit szeretne, hogy kiszámolja a probléma összes értékét.

Pszeudokód a táblázatozáshoz:

Amint az álkódot (jobb oldalon) láthatja a képen, iterációt hajt végre (azaz egy tömb végéig hurcol). Egyszerűen a fib (0), a fib (1), a fib (2) szavakkal kezdődik ... A táblázatos megközelítéssel tehát kiküszöbölhetjük a rekurzió szükségességét, és egyszerűen visszaadhatjuk az eredményt az elemek átkapcsolásával.

Visszatekintés a történelembe

Richard Bellman állt a koncepció mögött. Ezt akkor találta ki, amikor az 1950-es évek közepén a RAND Corporationnél dolgozott. A „dinamikus programozás” elnevezés oka az volt, hogy elrejtse a matematikai munkát, amelyet e kutatás érdekében végzett. Attól félt, hogy főnökei bármilyen matematikai kutatást elleneznek vagy nem szeretnek.

Oké, szóval a „programozás” szó csupán utalás annak tisztázására, hogy ez régimódi tervezés vagy ütemezés volt, általában egy táblázat kitöltésével (nem pedig lineáris módon, hanem dinamikus módon) az idő helyett egyszerre.

Csomagolás

Ez az. Ez a tavaly elkezdett algoritmussorozat 2. része. Előző bejegyzésemben arról beszéltünk, hogy mi az algoritmusok keresése és rendezése. Bocsánat, hogy ezt nem sikerült rövidebb idő alatt átadni. De hajlandó vagyok az elkövetkező hónapokban gyorsabbá tenni a dolgokat.

Remélem tetszett neked, és hamarosan keresem a sorozat harmadik részét. Boldog kódolást!

Erőforrások:

Bevezetés a dinamikus programozásba 1 oktatóanyagok és megjegyzések | Algoritmusok HackerEarth

A fenti kép sokat elmond a dinamikus programozásról. Tehát megismétli azokat a dolgokat, amelyekhez már rendelkezik a www.hackerearth.com közösséggel - Versenyképes programozás - Versenyképes programozási oktatóanyagok - Dinamikus programozás: -tól

Közösség - Versenyképes programozás - Versenyképes programozási oktatóanyagok - Dinamikus programozás: A kezdőtől a haladóig www.topcoder.com

//www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Különleges kellékek Jeff Ericksonhoz és jegyzetei az algoritmushoz - //jeffe.cs.illinois.edu/