A dinamikus programozás Richard Bellman matematikus és közgazdász által kidolgozott koncepció.
Abban az időben Bellman bonyolult optimalizálási problémák megoldásának módját kereste. Az optimalizálási problémák megkövetelik, hogy a lehetőségek közül a legjobb megoldást válassza.
Az optimalizálási problémára példa az Utazó értékesítő probléma. A cél az, hogy megtaláljuk a legrövidebb útvonalat, hogy az eladó pontosan egyszer meglátogassa az egyes városokat, és visszatérjen a kiinduló városba.
Bellman ezeket a problémákat úgy közelítette meg, hogy kisebb részproblémákra bontotta őket, és a részproblémákat a legkisebbtől a legnagyobbig oldotta meg. Ezután a részproblémák eredményeit eltárolta, és újra felhasználta nagyobb részproblémák megoldására. Ez a fő gondolat a dinamikus programozás mögött.
Tartalomjegyzék
Mi az a dinamikus programozás?
A dinamikus programozás úgy oldja meg az optimalizálási problémákat, hogy kisebb részproblémákra bontja őket, minden részproblémát egyszer megold, és eltárolja a megoldásaikat, hogy újra felhasználhatók legyenek és kombinálhatók legyenek a nagyobb probléma megoldására. A problémákat a legkisebbtől a legnagyobbig megoldják, lehetővé téve a megoldások újrafelhasználását.
Hogyan működik a dinamikus programozás?
Egy probléma megoldása dinamikus programozással a következő lépésekből áll:
Ennek működéséhez kiszámoljuk a 6. Fibonacci-számot, F(6), ezzel az eljárással.
Először határozza meg a megoldandó részproblémákat.
F(n) = F(n-1) + F(n-2) n > 1 esetén
Ezért: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
A második lépés az egyes részproblémák megoldása rekurzív függvény vagy iteratív folyamat segítségével. A részproblémákat a legkisebbtől a legnagyobbig oldjuk meg, a kisebb részproblémák eredményeit újra felhasználva. Ez a következőket adja nekünk:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Az egyes részproblémák megoldása során a megoldásokat egy tömbben vagy táblázatban tároljuk, hogy újra felhasználhatók legyenek nagyobb részproblémák megoldásában, például:
Ha az összes részprobléma megoldódott, a megoldásokat felhasználjuk az eredeti probléma megoldásának megalkotására.
Ebben az esetben az eredeti feladat megoldása a 6. Fibonacci-szám, amelyet a legnagyobb problémából azonosított F(5) és F(4) részfeladatok összegzésével kapunk. Az eredmény 8.
Hol és miért alkalmazzák a dinamikus programozást?
A dinamikus programozást olyan területeken alkalmazzák, ahol kisebb részproblémákra bontható problémáink vannak, és ezek megoldásait nagyobb problémák megoldására használják.
Ezek a területek közé tartozik a számítástechnika, a közgazdaságtan, a matematika és a mérnöki tudomány. A számítástechnikában sorozatokat, gráfokat és egész értékeket tartalmazó problémák megoldására, valamint a kompetitív programozásban használják.
A közgazdaságtanban a pénzügyi, termelési és erőforrás-elosztási optimalizálási problémák megoldására használják. A matematikában a dinamikus programozást a játékelméletben, a statisztikában és a valószínűségszámításban használják, ahol optimalizálási problémák megoldására használják.
A mérnöki tudományban az erőforrás-allokáció, ütemezés, gyártás, kommunikáció és vezérlőrendszerek problémáinak megoldására használják.
A dinamikus programozásnak számos előnye van az optimalizálási problémák megoldására:
Ha az optimalizálási problémák megoldásáról van szó, a dinamikus programozás nagyon hasznos eszköz a megoldások hatékonyságának biztosítására.
A dinamikus programozásban használt megközelítések
A dinamikus programozásban két megközelítést alkalmaznak az optimalizálási problémák megoldására. Ezek a felülről lefelé és az alulról felfelé irányuló megközelítések.
Felülről lefelé irányuló megközelítés
Ezt a megközelítést memoizációnak is nevezik. A memoizáció egy optimalizálási technika, amelyet elsősorban a számítógépes programok gyorsabbá tételére használnak azáltal, hogy a függvényhívások eredményeit a gyorsítótárban tárolják, és a gyorsítótárban lévő eredményeket a következő alkalommal visszaküldik, ahelyett, hogy újra kiszámolnák őket.
A felülről lefelé irányuló megközelítés rekurziót és gyorsítótárazást foglal magában. A rekurzió olyan függvényt tartalmaz, amely a probléma egyszerűbb változatait hívja meg argumentumaként. A rekurziót a probléma kisebb részproblémákra bontására és a részproblémák megoldására használják.
Ha egy részprobléma megoldódott, az eredményt a rendszer gyorsítótárba helyezi, és hasonló probléma esetén újra felhasználja. A felülről lefelé irányuló módszer könnyen érthető és megvalósítható, és csak egyszer oldja meg az alproblémát. Ennek azonban az a hátránya, hogy a rekurzió miatt sok memóriát foglal el. Ez verem túlcsordulási hibához vezethet.
Alulról felfelé építkező megközelítés
Az alulról felfelé irányuló megközelítés, más néven táblázatosítás, megszünteti a rekurziót, iterációval helyettesíti, így elkerüli a veremtúlcsordulási hibákat.
Ebben a megközelítésben egy nagy problémát kisebb részproblémákra bontunk, és a részproblémák megoldásait a nagyobb probléma megoldására használják fel.
A kisebb részproblémákat először a legnagyobbtól a legkisebbig oldjuk meg, eredményeiket pedig mátrixban, tömbben vagy táblázatban tároljuk, innen ered a névtáblázat.
A tárolt eredmények nagyobb problémákat oldanak meg, amelyek a részproblémáktól függenek. Az eredeti probléma eredményét ezután úgy találjuk meg, hogy a legnagyobb részproblémát az előzőleg kiszámított értékek felhasználásával megoldjuk.
Ennek a megközelítésnek az az előnye, hogy memória- és időhatékony, mivel megszünteti a rekurziót.
Példák dinamikus programozással megoldható problémákra
Íme néhány programozási probléma, amelyek dinamikus programozással megoldhatók:
#1. Hátizsák probléma
Forrás: Wikipédia
A hátizsák egy vászonból, nejlonból vagy bőrből készült táska, amelyet általában a hátára rögzítenek, és katonák és túrázók használnak kellékek szállítására.
A hátizsák-probléma során egy hátizsákot mutatunk be, és a teherbíró képessége miatt ki kell választania a tárgyakat, mindegyiknek megvan az értéke. A kiválasztásnak olyannak kell lennie, hogy a felvett tárgyak maximális összértékét kapja, és a tételek súlya kisebb vagy egyenlő legyen, mint a hátizsák kapacitása.
Az alábbiakban egy példa látható a hátizsák problémájára:
Képzelje el, hogy kirándulni készül, és van egy 15 kilogrammos hátizsákja. Van egy listája azokról a tárgyakról, amelyeket magával vihet, értékükkel és súlyukkal együtt, az alábbi táblázat szerint:
CikkÉrték Súly 2003Hálózsák1502Tűzhely501Étel1002Vizes palack100.5Elsősegélykészlet251
Válassza ki a behozni kívánt cikkek egy részhalmazát úgy, hogy a tárgyak összértéke maximalizálva legyen, miközben a teljes súly kisebb vagy egyenlő, mint a hátizsák kapacitása, amely 15 kilogramm.
A hátizsák-probléma valós alkalmazásai magukban foglalják a portfólióhoz hozzáadandó értékpapírok kiválasztását a kockázat minimalizálása és a profit maximalizálása érdekében, valamint a legkevésbé pazarló módszerek megtalálását a nyersanyagok csökkentésére.
#2. Ütemezési probléma
Az ütemezési probléma olyan optimalizálási probléma, amelyben a cél a feladatok optimális hozzárendelése egy erőforráskészlethez. Az erőforrások lehetnek gépek, személyzet vagy a feladatok elvégzéséhez használt egyéb erőforrások.
Az alábbiakban látható egy példa egy ütemezési problémára:
Képzelje el, hogy Ön egy projektmenedzser, aki olyan feladatok ütemezéséért felelős, amelyeket az alkalmazottak csapatának kell elvégeznie. Minden feladatnak van kezdési ideje, befejezési ideje, valamint azoknak az alkalmazottaknak a listája, akik alkalmasak a végrehajtására.
Itt van egy táblázat, amely leírja a feladatokat és azok jellemzőit:
Feladatkezdési időBefejezési idő Képzett alkalmazottak T1911A, B, CT21012A, CT31113B, CT41214A, B
Rendeljen hozzá minden feladatot egy alkalmazotthoz, hogy minimalizálja a teljes befejezési időt.
Az ütemezési problémával a feldolgozóiparban találkozhatunk, amikor megpróbálják optimalizálni az erőforrások, például a gépek, anyagok, szerszámok és munkaerő elosztását.
Az egészségügyben is találkozhatunk vele az ágyak, a személyzet és az egészségügyi felszerelések optimalizálásakor. Más iparágak, ahol ez a probléma előfordulhat, a projektmenedzsment, az ellátási lánc menedzsment és az oktatás.
#3. Utazó eladó probléma
Forrás: Wikipédia
Ez az egyik legtöbbet tanulmányozott optimalizálási probléma, amely dinamikus programozással megoldható.
Az utazó eladó probléma megadja a városok listáját és az egyes várospárok közötti távolságokat. Meg kell találnia a lehető legrövidebb útvonalat, amely minden várost pontosan egyszer meglátogat, és visszatér a kiindulási városba.
Az alábbiakban egy utazó eladó problémájára mutatunk be példát:
Képzelje el, hogy Ön egy eladó, akinek a lehető legrövidebb időn belül meg kell látogatnia egy sor várost. Az alábbi táblázatban látható a felkeresendő városok listája, valamint az egyes várospárok közötti távolságok listája:
CityABCDEA010152030B100352515C153503020D202530010E301520100
Az utazó eladó problémával találkozhatunk többek között a szabadidős iparban a turisták útvonaltervezésekor, a logisztikában az áruszállítás tervezésénél, a közlekedésben az autóbuszjáratok tervezésénél, valamint az értékesítési iparban.
Nyilvánvaló, hogy a dinamikus programozás számos valós alkalmazást tartalmaz, ami segít többet megtudni róla.
A dinamikus programozással kapcsolatos ismereteinek kifejtéséhez vegye figyelembe a következő forrásokat.
Erőforrások
Dinamikus programozás – Richard Bellman
A Dinamikus programozás Richard Bellman könyve, aki kitalálta a dinamikus programozást, és már korai szakaszában kifejlesztette azt.
A könyv könnyen érthető módon íródott, a szöveg megértéséhez csak alapvető matematikai és számítási ismeretekre van szükség. A könyvben Bellman bemutatja a többlépcsős döntési folyamat matematikai elméletét, amely kulcsfontosságú a dinamikus programozásban.
A könyv ezután megvizsgálja a többlépcsős gyártási folyamatok szűk keresztmetszeti problémáit, a létezési és egyediségi tételeket, valamint az optimális készletegyenletet.
A legjobb dolog a könyvben az, hogy Bellman számos összetett problémára kínál példákat olyan területeken, mint a logisztika, az ütemezéselmélet, a kommunikációelmélet, a matematikai közgazdaságtan és az irányítási folyamatok, és bemutatja, hogy a dinamikus programozás hogyan tudja megoldani a problémákat.
A könyv Kindle, keményfedeles és puhakötésű változatban is elérhető.
Dinamikus programozási algoritmusok mesterkurzusa
Ezt az Udemy dinamikus programozási algoritmusok mesterkurzusát Apaar Kamal, a Google szoftvermérnöke és Prateek Narang kínálja, aki szintén a Google-lal dolgozott.
A kurzus úgy lett optimalizálva, hogy segítse a tanulókat abban, hogy kitűnjenek a programozási versenyben, amely számos, dinamikus programozást igénylő problémát tartalmaz.
A programozó versenytársak mellett a kurzus ideális azoknak a programozóknak, akik szeretnének jobban megérteni az algoritmusokat, valamint a programozási interjúkra és online kódolási fordulókra készülőknek.
A több mint 40 órás kurzus a dinamikus programozást fedi le részletesen. A kurzus először olyan fogalmakról kínál felfrissítést, mint a rekurzió és a visszalépés.
Ezután számos egyéb fogalom mellett lefedi a dinamikus programozást a játékelméletben, a karakterláncokat, fákat és gráfokat, mátrix hatványozást, bitmaszkokat, kombinatorikát és részszekvenciákat, partíciós problémákat és többdimenziós dinamikus programozást.
Versenyképes programozási alapismeretek, mester algoritmusok
Az Udemy Prateek Narang és Amal Kamaar Competitive Programming Essentials kurzusát kínálja, amely dinamikus programozást, matematikát, számelméletet, valamint fejlett adatstruktúrákat és algoritmusokat tartalmaz oly módon, hogy az hasznos és releváns a versenytárs programozók számára.
A kurzus felfrissítést kínál az adatstruktúrákról és algoritmusokról, mielőtt belemerülne az összetettebb algoritmusokba és technikákba, amelyek jól jöhetnek a versenyprogramozásban.
A kurzus kiterjed a dinamikus programozásra, a matematikára, a játékelméletre, a mintaillesztésre, a bitmaszkolásra és számtalan fejlett algoritmusra, amelyeket programozási versenyeken használnak és teszteltek.
Az Udemy kurzus 10 modulból és 42 részből áll, és minden szakasz után rengeteg gyakorló kérdést tartalmaz. Ez a bestseller tanfolyam kötelező mindenkinek, aki érdeklődik a versenyprogramozás iránt.
Végső szavak
A dinamikus programozás minden programozó számára előnyös készség, hogy megtanulja javítani a valós problémák problémamegoldását. Ezért a programozóknak fontolóra kell venniük a javasolt források áttekintését, hogy ezt a kulcsfontosságú eszközt hozzáadhassák eszköztárukhoz.
Ezután megtekintheti az adattudományban használható programozási nyelveket.