Lexiq

Dinamikus programozás

A dinamikus programozás elnevezés egy számítógépes programozás során használt problémamegoldási módszert jelöl, aminek lényege, hogy egy nagyobb problémát kisebb, rekurzív algoritmussal megoldható részproblémákra bontunk, és a részproblémák megoldásait eltároljuk, hogy ismétlődés esetén ne kelljen újraszámolni őket.

Ezzel a módszerrel jelentősen felgyorsulhat az algoritmus, például a Fibonacci‑sorozat kiszámítására írt exponenciális időkomplexitású rekurzív algoritmus lineáris időkomplexitásúvá válhat. Az algoritmus például így néz ki Python nyelven optimalizálás nélkül:

def fib(n):
    if n < 2:
        return n
    return fib(n-1)+fib(n-2)

Ez a megoldás a rekurzív hívások során többször is kiszámolja ugyanazt az értéket, ahelyett, hogy az első alkalommal eltárolná az eredményt, és azt használná fel, amikor másodszor van szükség rá. Ezt teszi az alábbi megoldás:

def fib(n, m = {}): //m-ben tároljuk a már kiszámolt részmegoldásokat
    if n in m: return m[n] //ha el van tárolva, nem számoljuk ki újra
    if n < 2:
        return n
    m[n] = fib(n-1, m)+fib(n-2, m) //eltároljuk az eredményt
    return m[n]

Publikálva: 2021. október 10.