IF Notes

Dynamic Programming dan Memoization

6 min read

Back to IF5100 Pemrograman untuk Data Analitik

Dynamic Programming dan Memoization

Questions/Cues

  • Mengapa fib(n) rekursif biasa sangat boros, dan apa itu memoization?
  • Apa dua syarat agar dynamic programming bekerja (optimal substructure dan overlapping subproblems)?
  • Apakah 0/1 knapsack memenuhi kedua syarat itu, dan di mana subproblem yang tumpang tindih?
  • Apa yang menjadi key memo di fastMaxVal, dan mengapa len(toConsider) cukup?
  • Mengapa jumlah panggilan turun dari 65.536 ke sekitar 5.191 untuk 16 item?
  • Apakah dynamic programming “mukjizat” yang mematahkan sifat eksponensial?

Reference Points

  • IF5100 — Optimization Problems (Slides 31-47)

Fibonacci Rekursif dan Pekerjaan Berulang

def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

Pohon panggilan fib(6) = 13 menghitung fib(4), fib(3), dan seterusnya berkali-kali. Diverifikasi: fib(6) membuat 25 panggilan, fib(20) membuat 21.891 panggilan. Hasil fib(120) = 8.670.007.398.507.948.658.051.921 jelas tidak mungkin dihitung dengan cara ini.

Memoization

Ide: menukar waktu dengan ruang. Buat tabel (memo) untuk mencatat apa yang sudah dihitung. Sebelum menghitung fib(x), cek apakah sudah ada di tabel: jika ya, ambil; jika belum, hitung lalu simpan.

def fastFib(n, memo = {}):
    """Assumes n is an int >= 0, memo used only by recursive calls
       Returns Fibonacci of n"""
    if n == 0 or n == 1:
        return 1
    try:
        return memo[n]
    except KeyError:
        result = fastFib(n-1, memo) + fastFib(n-2, memo)
        memo[n] = result
        return result

Dengan memo, fastFib(6) hanya butuh 11 panggilan (dibanding 25), dan fastFib(120) selesai seketika.

Kapan Dynamic Programming Bekerja?

  • Optimal substructure: solusi optimal global dapat dibangun dari solusi optimal subproblem lokal. Contoh: fib(x) = fib(x-1) + fib(x-2) untuk x > 1.
  • Overlapping subproblems: mencari solusi optimal melibatkan penyelesaian subproblem yang sama berulang kali. Contoh: fib(x) dihitung berkali-kali.

Apakah 0/1 Knapsack Memenuhi?

Deck menunjukkan dengan menu kecil a(6,3), b(7,3), c(8,2), d(9,5) dan budget 5 kalori. Setiap node pada search tree berbentuk <taken, left, value, remaining>. Pertanyaan yang diselesaikan di tiap node: diberi sisa berat, maksimalkan nilai dengan memilih dari item yang tersisa. Himpunan item yang sudah dipilih (bahkan nilainya) tidak berpengaruh. Karena itu subproblem ditentukan hanya oleh pasangan (item tersisa, sisa kalori).

Overlap muncul, misalnya, pada node {a}, [c,d], sisa 2 dan {b}, [c,d], sisa 2 (keduanya “pilih dari [c,d] dengan sisa 2”), serta {a}, [d], sisa 2 dan {b}, [d], sisa 2. Perhatikan nilai himpunan yang berbeda (6 vs 7) tidak mengubah subproblem. Pada menu kecil ini maxVal melakukan 17 panggilan (17 node), sedangkan versi memo hanya 14 panggilan.

flowchart TD
    N0["0: {} | [a,b,c,d] | sisa 5"] --> N1["1: {a} | [b,c,d] | sisa 2"]
    N0 --> N6["6: {} | [b,c,d] | sisa 5"]
    N1 --> N2["2: {a} | [c,d] | sisa 2"]
    N6 --> N7["7: {b} | [c,d] | sisa 2"]
    N6 --> N11["11: {} | [c,d] | sisa 5"]
    N2 --> N4["4: {a} | [d] | sisa 2"]
    N7 --> N9["9: {b} | [d] | sisa 2"]
    N4 -.->|"subproblem sama: [d], sisa 2"| N9
    N2 -.->|"subproblem sama: [c,d], sisa 2"| N7

fastMaxVal: maxVal dengan Memo

  • Tambahkan memo sebagai argumen ketiga: def fastMaxVal(toConsider, avail, memo = {}).
  • Key memo adalah tuple (len(toConsider), avail); item yang tersisa cukup diwakili len(toConsider) karena selalu berupa sufiks dari list awal.
  • Pertama, body mengecek apakah jawaban optimal untuk key itu sudah ada di memo; terakhir, body memperbarui memo.
def fastMaxVal(toConsider, avail, memo = {}):
    if (len(toConsider), avail) in memo:
        result = memo[(len(toConsider), avail)]
    elif toConsider == [] or avail == 0:
        result = (0, ())
    elif toConsider[0].getCost() > avail:
        result = fastMaxVal(toConsider[1:], avail, memo)
    else:
        nextItem = toConsider[0]
        withVal, withToTake = fastMaxVal(toConsider[1:], avail - nextItem.getCost(), memo)
        withVal += nextItem.getValue()
        withoutVal, withoutToTake = fastMaxVal(toConsider[1:], avail, memo)
        if withVal > withoutVal:
            result = (withVal, withToTake + (nextItem,))
        else:
            result = (withoutVal, withoutToTake)
    memo[(len(toConsider), avail)] = result
    return result

Performa

Dari deck (menu acak, budget 750):

len(items)2**len(items)Jumlah panggilan fastMaxVal
247
41625
8256427
1665.5365.191
324.294.967.29622.701
6418.446.744.073.709.551.61642.569
128Big83.319
256Really Big176.614
512Ridiculously big351.230
1024Absolutely huge703.802

Verifikasi: 2**16 = 65.536. Jumlah panggilan bergantung pada menu acak; saat dijalankan ulang dengan seed 0, 1, dan 2 untuk 16 item saya mendapat 5.192, 4.329, dan 6.964 panggilan, jadi angka 5.191 pada deck cocok dengan orde besarnya (ribuan, bukan puluhan ribu). Untuk 128 item hasil run saya sekitar 150.000, lebih besar dari 83.319 pada deck, sehingga angka pada tabel hanya satu contoh acak.

Bukankah Itu Mukjizat?

Tidak. Masalahnya tetap eksponensial dalam kasus terburuk; yang terjadi adalah kompleksitas bisa halus. Waktu fastMaxVal ditentukan oleh jumlah pasangan berbeda <toConsider, avail>: nilai toConsider dibatasi len(items), dan nilai avail dibatasi jumlah jumlah berat yang berbeda. Bila berat berupa bilangan bulat kecil, pasangan berbeda jumlahnya terbatas sehingga cepat. Solusi selalu benar, dan cepat di bawah kondisi yang tepat.

Summary

Memoization menyimpan hasil subproblem dalam tabel agar tidak dihitung ulang (menukar waktu dengan ruang): fib(6) turun dari 25 ke 11 panggilan. Dynamic programming bekerja bila ada optimal substructure dan overlapping subproblems. 0/1 knapsack memenuhi keduanya karena subproblem hanya bergantung pada (item tersisa, sisa kalori), bukan item yang sudah dipilih; fastMaxVal memakai memo dengan key (len(toConsider), avail). Panggilan turun drastis (16 item: 2^16 = 65.536 vs sekitar 5 ribu), bukan karena masalah tak lagi eksponensial, melainkan karena waktu dibatasi oleh jumlah pasangan <toConsider, avail> yang berbeda. Greedy memberi solusi cepat tetapi belum tentu optimal; DP memberi solusi pasti benar dan sering cepat.

Graph View

Backlinks