Dinamikus Programozás�2024.10.02
Ismétlés
Oszd meg és uralkodj
Divide & Conquer (,,Oszd meg és uralkodj”) paradigma
Oszd meg és uralkodj
Felosztás: hogyan osztjuk a feladatot több részfeladatra
Uralkodás: a részfeladatokat rekurzív módon megoldjuk. Ha a részfeladatok mérete elég kicsi, akkor közvetlenül megoldja a részfeladatokat.
Összevonás: a részfeladatok megoldásait összevonjuk az eredeti feladat megoldásává
PL: vállalat adója ->részleg->munkások
Rekurzió
Faktoriális számítás: n! = n· (n - 1) · … · 2 · 1
Rekurzív összefüggés: n! = n · (n - 1)!
Alapeset: n = 1
Rekurzív eset: n > 1: n · (n - 1)!
Fibonacci
az első és a második elem értéke 1.
az N. elem az N-1 - edik és az N-2 - dik elemek összege.
Fibonacci
def fibo( n ) :
if (( n == 1 ) || (n == 0)):
return 1
else
return fibo(n-1) + fibo(n-2)
Lépcső
n=4
Lépcső
def P( n ) :
if ( n == 1 )
return 1
elseif ( n == 2 )
return 2
else
return P( n−1) + P( n−2)
Dinamikus programozás
Dinamikus programozás
Az eddigiekben egy-egy összetett feladat megoldására oszd-meg-és-uralkodj megoldást használtunk.
A rekurzív megoldás legnagyobb hátránya azonban az, hogy legtöbb esetben, ahogy növekszik az elemszámunk, vele együtt hatványozottan növekszik a megoldáshoz szükséges idő hossza és a lépések száma is.
Dinamikus programozás
Ennek a problémának a kiküszöbölésére ad hatékony megoldást a dinamikus programozás.
Ebben a tananyagban egy másik, szintén részproblémára bontáson alapuló, algoritmus családdal, a dinamikus programozással ismerkedünk meg.
Dinamikus programozás
A rekurzív algoritmusok sokszor azért lassúak, mert bizonyos részproblémákat többször is kiszámolnak.
Tipikusan ez történik, amikor optimalizálási feladatunk van és a megoldás kedvezményeket lépésről lépésre építjük fel.
Dinamikus programozás
Ezt úgy tudjuk elkerülni, ha az egyszer már kiszámolt rész megoldásokat eltároljuk, és később újra felhasználjuk azokat.
A több időt valójában most több tárra „cseréljük”, melynek eredményeként a rekurzív programok időkomplexitása drasztikusan csökkenthető.
Dinamikus programozás
A dinamikus programozás a részproblémákra bontás gyengeségeit két fő módszerrel próbálja orvosolni:
Az egyik módszer lényege, hogy programunk futása alatt
(TÁBLÁZATKITÖLTÉS módszere)
Dinamikus programozás
A második módszer:
Általában amikor a részproblémákat többször is szükséges megoldani, akkor az összes lehetséges „kis” részproblémát ki kell számolni, hogy az eredeti nagy probléma megoldása kiszámítható legyen.
Dinamikus programozás
Ezért a dinamikus programozásban tipikusan:
(LENTRŐL FELFELÉ ÉPÍTKEZÉS módszere).
Dinamikus programozás
Vegyük észre, hogy ez ellentétes az oszd-meg-és-uralkodj algoritmusok filozófiájával, ahol mindig az eredeti problémát bontjuk kisebb és kisebb problémákra
(FELÖLRŐL LEFELÉ ÉPÍTKEZÉS módszere)
Dinamikus programozás
A Dinamikus programozás gyakorlatilag „ugyanaz” mint a oszd meg és uralkodj módszer/rekurzió.
Ám még előzőekben sok egymásba ágyazás/időigény mellett dolgoztunk, most a memóriában történő tároláson van a hangsúly.
Dinamikus programozás
Nézzünk meg egy példát:
Rendezzük a következő számsort 8, 4, 1, 5, 3, 2, 6, 7 !
Próbáljunk oszd meg és uralkodj logikával gondolkodni
Dinamikus programozás
Összefésülő (merge)rendezés:
A tömböt két részre vágjuk (lehetőleg fele-fele arányban), a részeket külön-külön rendezzük (rekurzió!), majd a rendezett részeket összefésüljük.
Dinamikus programozás
Probléma: Rekurzív algoritmusok -> többször is kiszámolnak.
Megoldás: A részmegoldások -> eltároljuk es újra felhasználjuk.
A több időt több tárra ,,cseréljük" -> exponenciális idő -> polinomidő
Ehhez viszont el kell tároljuk a rész problémák megoldását.
Dinamikus programozás
A megoldás lépései általában:
Adjuk meg a rekurzív megoldást (alap- és rekurzív eset).
A rekurzió alapján építsük fel ,,lentről felfelé”: az algoritmus kezdjen az alapesettel, majd a teljes megoldásig egy jó sorrendben számolja ki a rész problémákat.
Fibonacci
def fib( n ) :
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
return result
Táblázatkitöltés
A részeredmények (TÁBLÁZATKITÖLTÉS) tárolásának módszere:
A részproblémára bontási algoritmusokat kibővítjük egy- vagy kétdimenziós tömbbel, melyet a részeredmények tárolására használunk fel.
Táblázatkitöltés
Amikor egy részproblémát kell megoldanunk először megvizsgáljuk, hogy a keresett érték megtalálható-e a részeredmények között.
Ha megtalálható, akkor felhasználjuk, egyébként kiszámoljuk, majd eltároljuk.
Fibonacci
def fib( n ) :
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
return result
Rendkívül gyenge a hatásfoka, nagyon sokáig fut.
Nézzünk egy példát: fib(5)
Fibonacci
Fibonacci
1
Fibonacci
1
Fibonacci
1
Fibonacci
1
Fibonacci
1 1 2
Fibonacci
1 1 2
Fibonacci
1 1 2 4
Fibonacci
1 1 2 4
Fibonacci
1 1 2 4 5
Fibonacci
1 1 2 4 5
Fibonacci
1 1 2 4 5
Fibonacci
1 1 2 4 5
Fibonacci
1 1 2 4 5
Fibonacci
Fibonacci
def fib( n, memo ) :
if memo[n] != null:
return memo[n]
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
memo = 1 1 2 3
T(n) = 2n + 1 …… O(n)
Fibonacci
def fib( n, memo ) :
if memo[n] != null:
return memo[n]
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
memo =
Fibonacci
def fib( n, memo ) :
if memo[n] != null:
return memo[n]
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
memo =
Fibonacci
def fib( n, memo ) :
if memo[n] != null:
return memo[n]
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
memo = 1
Fibonacci
Fibonacci
def fib( n, memo ) :
if memo[n] != null:
return memo[n]
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
memo = 1 1
Fibonacci
def fib( n, memo ) :
if memo[n] != null:
return memo[n]
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
memo = 1 1 2
Fibonacci
def fib( n, memo ) :
if memo[n] != null:
return memo[n]
if (( n == 2 ) || (n == 1)):
result = 1
else
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
memo = 1 1 2 3 5
Fibonacci
Alulról felfelé építkezés
A TÁBLÁZATKITÖLTÉSEN alapuló dinamikus programozási megoldásnál még gyorsabb lehet, ha nem FELÜLRŐL LEFELÉ, rekurzív módon töltjük ki a táblázatot, hanem az ALULRÓL FELFELÉ ÉPÍTKEZÉS módszerével:
Alulról felfelé építkezés
-Hozzuk létre a megfelelő méretű táblázatot, amiben minden cella egy része problémának felel meg.
-Töltsük az alapesetek megoldásait.
-„alulról felfelé” az alapesetekből kiindulva, a teljes megoldásig számoljuk ki a részproblémák megoldásait a már korábban kiszámolt megoldások alapján
Lépcső
Jelölje P(n) azt a számot, hányféleképpen mehetünk fel egy n lépcsőfokból álló lépcsőn, ha egyszerre csak 1 vagy 2 lépcsőfokot léphetünk.
Adjunk egy dinamikus programozási eljárást a P(n) érték kiszámítására!
P(6) = ?
Lépcső
Az előző órán a rekurzív algoritmushoz megadtuk az összefüggéseket:
Alapeset:
Rekurzív eset:
Lépcső
Ezek alapján a következő dinamikus programozási eljárást adhatjuk meg, ahol egy T tömböt töltünk ki, T[i] a P(i) értékét tartalmazza:
Lépcső
Nézzünk egy példát: egy 8 magas lépcsőre szeretnénk felmenni.
Sok lépést spórolunk meg az előző megoldáshoz képest!
Melyik a jobb…?
Melyik a jobb megoldás?
Melyik a jobb…?
Melyik a jobb megoldás?
Sakk
Jelölje R(k; n) azt a számot, hányféleképpen juthatunk egy k x n méretű sakktábla bal alsó sarokból a jobb felső sarkába, ha csak a jobbra vagy a felfelé szomszédos mezőre léphetünk. Adjunk meg két dinamikus programozási eljárást (egyet négyzetes, egyet lineáris táblázatkitöltéssel) az R(k; n) érték kiszámítására!
R(3,4) = ?
Sakk
Megoldás:
Az előző órán megadtuk a rekurzív algoritmusokhoz az összefüggéseket.
A következő összefüggések állnak fent:
Alapeset:
Rekurzív eset:
Sakk
Ezek alapján a következő dinamikus programozási eljárást adhatjuk meg, T[i, j] az R(i, j) értékét tartalmazza:
Sakk
Táblázat
Feladat
Adott egy k×n-es tábla. Minden mezőre meg van adva egy Cij pozitív szám, ami
a mezőről begyűjthető érték.
Egy játékos a bal alsó sarokból szeretne eljutni a jobb felső sarokba úgy, hogy csak jobbra és felfelé léphet a szomszédos mezőre.
Az útja során összegyűjtheti a mezőkről az értékeket.
Mennyi értéket tudunk összeszedni maximálisan?
Hogyan határoznánk meg ezt az utat, amin a maximális értéket szedhetjük össze?
j
i
?
Táblázat
Megoldás
Az előző algoritmust annyiban kell módosítanunk, hogy nem a lépések számát, hanem az addig összeszedhető maximum értéket kell eltároljuk.
Táblázat
Sakk vs Pontok
Ajánlott kitekintő