Ugrás a tartalomhoz

dynamic programming

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

dynamic programming (tsz. dynamic programmings)

  1. (informatika) dinamikus programozás

A dinamikus programozás (DP) egy optimalizálási technika, amelyet olyan problémák megoldására használnak, amelyek több, egymásra épülő részproblémára bonthatók. A lényege, hogy ne számoljuk ki többször ugyanazt a részmegoldást, hanem elmentjük (memorizáljuk) a már kiszámolt eredményeket, és újra felhasználjuk őket.

Az ötlet Richard Bellmantől származik az 1950-es évekből, aki ezt a módszert „optimalitás elve” alapján alkotta meg:

„Az optimális megoldás mindig optimális részmegoldásokból épül fel.”

2. Mikor alkalmazzuk?

A dinamikus programozás akkor alkalmazható, ha egy probléma rendelkezik az alábbi két tulajdonsággal:

🔁 Átfedő részproblémák

A probléma megoldása során ugyanazokat a részfeladatokat többször kiszámolnánk.

🌿 Optimális részstruktúra

Az egész probléma megoldása az alproblémák optimális megoldásain alapul.


3. Megközelítések

a) Felülről lefelé (Top-Down)

Ez egy rekurzív megközelítés, ahol a főproblémából indulunk ki, és fokozatosan bontjuk le az alproblémákra. Az ismétlődő számításokat memorizálással (memoization) kerülhetjük el.

b) Alulról felfelé (Bottom-Up)

Ebben az esetben a kisebb alproblémák megoldásával fokozatosan építjük fel a végső megoldást. Itt általában táblázatot használunk (pl. egy tömböt), amelybe minden részmegoldást elmentünk.


4. Klasszikus példák

🧮 1. Fibonacci számok

A Fibonacci-sorozat:

Naiv rekurzió (exponenciális idő):
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Dinamikus programozással (lineáris idő):
def fib_dp(n):
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

🎒 2. 0–1 hátizsák probléma

Adott tárgyak halmaza, mindegyikhez tartozik egy súly és érték. A cél, hogy kiválasszuk a tárgyakat úgy, hogy az összsúly ne lépje túl a hátizsák kapacitását, miközben az érték maximális.

Dinamikus programozási megoldás:
def knapsack(w, v, W):
    n = len(w)
    dp = [[0] * (W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(W+1):
            if w[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][W]

🧵 3. Leghosszabb közös részszekvencia (LCS)

Két karakterlánc leghosszabb közös részszekvenciáját keressük.

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    return dp[n][m]

5. Táblázat vagy memória?

  • 2D-táblázat: ha a probléma két változós (pl. LCS, hátizsák)
  • 1D tömb: ha az eredmény csak az előző értékektől függ (pl. Fibonacci)
  • Memorization (dict): kényelmes Pythonban rekurzív megközelítéshez


6. Hol alkalmazzák a gyakorlatban?

  • Bioinformatika: DNS-elemzés, szekvencia-illesztés
  • Pénzügy: árfolyamok optimalizálása
  • Szövegfeldolgozás: szerkesztési távolság, szövegek hasonlósága
  • Robotika, AI: pályatervezés, stratégiai döntések
  • Játékok: optimális lépéssorozat keresése (pl. sakkvégjáték)
  • Fordítóprogramok: szintaktikai elemzés (pl. CYK-algoritmus)


7. Előnyök és hátrányok

✅ Előnyök:

  • Sok problémát hatékonyan old meg (polinomiális idő)
  • Rekurzív vagy iteratív módon is megoldható
  • Könnyen átlátható táblázatos formában

❌ Hátrányok:

  • Nagy memóriaigény (főleg 2D DP esetén)
  • Nehéz felismerni, hogy mikor alkalmazható
  • Nem mindig triviális a részproblémák megfogalmazása


8. Tipikus DP problémák típusai

Típus Példa
Sorozatproblémák Fibonacci, LCS, LIS (leghosszabb növekvő szekvencia)
Hátizsák típusú 0–1 Knapsack, Partition, Subset Sum
Útkeresés Grid-pályák, minimális költség
Játékelmélet Nim-játék, Grundy számok
Sztringfeldolgozás Edit Distance, Regex illesztés
Szétosztás Étel, erőforrás, idő, stb. optimalizálása


9. Optimalizált DP (tér-idő csere)

Gyakran a teljes 2D tömb helyett elegendő csak 1 sor vagy oszlop, így csökkenthető a memóriahasználat.

Példa: LCS probléma → csak 2 sor kell a számításokhoz, nem az egész mátrix.


10. Összefoglalás

A dinamikus programozás egy rendkívül hatékony és sokoldalú eszköz optimalizálási és döntési problémák megoldására:

  • Ismétlődő részproblémákra épül
  • Részmegoldásokat tárol → időmegtakarítás
  • A programozási versenyek és ipari megoldások alapköve

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=dynamic_programming&oldid=3494657”