Dinamik Programlama

Açgözlü yordam, aldığı en büyük parayı bir daha sorgulamadığı için geriye pahalı bir kalan bırakıyordu. Çare belliydi ve önceki derste zaten kullanıldı: kalanı da çözmek, yani her alt problemin en iyi çözümünü hesaplayıp saklamak. O yordamın adı dinamik programlama (dynamic programming).

Kalıbın çekiciliği, üstel bir aramayı sayılabilir bir tabloya indirmesidir. Bedeli ise iki ayrı ön koşuldur ve ikisi de sessizce bozulabilir. Birincisi optimal alt yapı: en iyi çözümün, alt problemlerin en iyi çözümlerinden kurulabilmesi. İkincisi örtüşen alt problem: aynı alt problemin birden çok kez sorulması. Birincisi bozulunca yanıt yanlış çıkar; ikincisi bozulunca yanıt doğru kalır ama saklamak hiçbir şey kazandırmaz. Bu ders ikisini de sayar.

• TY29. Ölçülen problem: bir dizide bitişik olmayan en çok üç eleman seçerek elde edilebilecek en büyük toplam. Boş seçim serbesttir, yani yanıt hiçbir zaman sıfırın altında olmaz.
• TY30. Kâhin bütün alt kümeleri görür: 12 elemanlı bir dizide 4096 alt küme.
• TY31. Bir adım, not almada bir özyineleme çağrısı, alttan yukarıda bir hücrenin hesaplanması, kâhinde bir alt kümenin denenmesidir.
• TY32. Not alma (memoization) özyinelemeli çözüme bir defter ekler; alttan yukarı çözüm aynı bağıntıyı özyinelemesiz kurar.
• TY33. Kalıbın ön koşulu: defterin anahtarı, alt problemi tek anlamlı belirleyen durumun tamamını taşımalıdır. Eksik anahtar yalnız bu ön koşulu bozar.
• TY34. İkinci ön koşul optimal alt yapıdır ve bu derste bozulmadan tutulur; onun bozulduğu durum klasik problemler konusuna aittir.
• TY35. Örtüşme ölçümü ortak tanımdan aynen alınır ve yeniden tanımlanmaz.
• TY36. Defter boyu giriş sayısıyla, tablo boyu hücre sayısıyla ölçülür.
• TY37. Her ölçüm 20260219 tohumlu ikinci dağarcıkta da koşturulur.

Örtüşme Sayılır

Not almanın kazancı, alt problemlerin kaç kez tekrarlandığına eşittir. Bu, tahmin edilecek bir şey değil sayılacak bir şeydir. Aşağıdaki iki yordam aynı $n$ için çalışır; birinde her alt problem iki kez sorulur, ötekinde her çağrı yeni bir alt problem üretir.

# Ortak tanimin ortusme olcumu: ayni n, iki farkli alt problem yapisi.
class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self, n=1):
        self.adim += n


def ortusen(n, notlu=True):
    """Ortusen alt problem: her deger iki kez cagriliyor."""
    s = Sayac()
    defter = {}

    def f(k):
        s.say()
        if k < 2:
            return k
        if notlu and k in defter:
            return defter[k]
        d = f(k - 1) + f(k - 2)
        defter[k] = d
        return d
    f(n)
    return {"cagri": s.adim, "deger": len(defter)}


def ortusmeyen(n, notlu=True):
    """Ortusmeyen alt problem: her cagri farkli bir alt problem."""
    s = Sayac()
    defter = {}

    def f(bas, son):
        s.say()
        if son - bas <= 1:
            return son - bas
        if notlu and (bas, son) in defter:
            return defter[(bas, son)]
        orta = (bas + son) // 2
        d = f(bas, orta) + f(orta, son)
        defter[(bas, son)] = d
        return d
    f(0, n)
    return {"cagri": s.adim, "deger": len(defter)}


print(" n  ortusen notlu  ortusen notsuz  ortusmeyen notlu  ortusmeyen notsuz  defter")
for n in (10, 15, 20):
    a, b = ortusen(n, True), ortusen(n, False)
    c, d = ortusmeyen(n, True), ortusmeyen(n, False)
    print(f"{n:2d} {a['cagri']:14d} {b['cagri']:15d} {c['cagri']:17d}"
          f" {d['cagri']:18d} {c['deger']:7d}")

 n  ortusen notlu  ortusen notsuz  ortusmeyen notlu  ortusmeyen notsuz  defter
10             19             177                19                 19       9
15             29            1973                29                 29      14
20             39           21891                39                 39      19

Örtüşen yapıda $n = 20$ için çağrı sayısı 21.891’den 39’a iniyor; kazanç 561 kat. Örtüşmeyen yapıda aynı $n$ için notlu ve notsuz sürüm ikisi de 39 çağrı yapıyor — defter bir kez bile isabet vermiyor — ama yine de 19 giriş tutuyor. İkinci satırın söylediği şey açıktır: not almanın koşulu örtüşmedir. Örtüşme yoksa defter yalnız yer tutar; yanıt doğru kalır, kazanç sıfırdır ve bellek boşa gider.

İki yapı arasındaki fark, bağıntının biçimindedir. Örtüşen yapıda iki dal aynı değerlere iniyor ve alt problem uzayı $n$ büyüklüğünde; örtüşmeyende her dal kendi aralığına iniyor ve alt problem uzayı çağrı sayısı kadar. Bir kalıbı seçmeden önce sorulacak soru budur: alt problem uzayı, çağrı sayısından küçük mü.

Defterin Anahtarı Durumun Tamamını Taşımalı

Not almanın ikinci ve daha sessiz ön koşulu deftere ilişkindir. Aşağıdaki problem iki değişkenli bir duruma sahiptir: hangi konumdayız ve kaç seçim hakkımız kaldı. Aynı yordam iki anahtarla koşturulur.

# Onceki blogun uzerine: Sayac oradan gelir.
TOHUM = 20260218
SECIM = 3          # en cok kac eleman secilebilir


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def dagarcik(tohum=TOHUM, n=40, uzunluk=12):
    r = uretec(tohum)
    return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]}
            for i in range(n)]


def kahin_secim(dizi, k, s):
    """Butun alt kumeleri gorur; bitisik olmayan ve en cok k elemanlilari deger."""
    en_iyi = 0
    for maske in range(1 << len(dizi)):
        s.say()
        if maske & (maske << 1):                  # bitisik iki secim var
            continue
        if bin(maske).count("1") > k:
            continue
        en_iyi = max(en_iyi, sum(dizi[i] for i in range(len(dizi))
                                 if maske >> i & 1))
    return en_iyi


def not_alan(dizi, k, s, anahtar="tam"):
    """anahtar='tam' -> defter (konum, kalan) ile; 'eksik' -> yalniz konum ile."""
    defter = {}

    def f(i, kalan):
        s.say()
        if i >= len(dizi) or kalan == 0:
            return 0
        ad = (i, kalan) if anahtar == "tam" else i
        if ad in defter:
            return defter[ad]
        d = max(f(i + 1, kalan), dizi[i] + f(i + 2, kalan - 1))
        defter[ad] = d
        return d
    sonuc = f(0, k)
    return sonuc, len(defter)


def olc(anahtar, kume):
    ayrilan, ak, ah, giris = [], 0, 0, 0
    for k in kume:
        s1, s2 = Sayac(), Sayac()
        deger, boy = not_alan(k["dizi"], SECIM, s1, anahtar)
        if deger != kahin_secim(k["dizi"], SECIM, s2):
            ayrilan.append(k["no"])
        ak += s1.adim
        ah += s2.adim
        giris += boy
    return {"ayrilan": len(ayrilan), "ayrilan_no": ayrilan[:6], "kalip_adim": ak,
            "kahin_adim": ah, "oran": round(ah / ak, 2), "defter_girisi": giris}


K = dagarcik()
print("kahin: dizi basina", 2 ** 12, "alt kume")
for anahtar in ("tam", "eksik"):
    print(f"defter anahtari {anahtar:6s}:", olc(anahtar, K))

kahin: dizi basina 4096 alt kume
defter anahtari tam   : {'ayrilan': 0, 'ayrilan_no': [], 'kalip_adim': 2440, 'kahin_adim': 163840, 'oran': 67.15, 'defter_girisi': 1200}
defter anahtari eksik : {'ayrilan': 39, 'ayrilan_no': [1, 2, 3, 5, 6, 7], 'kalip_adim': 1000, 'kahin_adim': 163840, 'oran': 163.84, 'defter_girisi': 480}

Üç sayı yan yana. Kâhin 40 girdide 163.840 adım harcıyor. Tam anahtarlı not alma 2440 adım harcıyor — kâhinin 67,15 katı azı — ve 40 girdinin hiçbirinde ayrılmıyor. Eksik anahtarlı not alma 1000 adım harcıyor, kâhinin 163,84 katı azı, ve 40 girdinin 39’unda kâhinden ayrılıyor.

Yanılgının mekanizması, önceki iki dersinkinden farklıdır ve daha tehlikelidir. Burada atlanan bir bölge yok; yordam bütün dalları geziyor. Sorun, deftere yazılan değerin yanlış soruya ait olmasıdır. Beşinci konumda üç seçim hakkıyla hesaplanan en iyi değer, aynı konuma bir seçim hakkıyla gelindiğinde geri veriliyor. Defter isabet ediyor, hesap atlanıyor, adım sayısı düşüyor — ve yanıt bozuluyor. Adım sayısının düşmesi burada bir hızlanma değil, yanlışın belirtisidir: 2440 yerine 1000 adım, defterin 1200 yerine 480 giriş tutması, hesaplanması gereken alt problemlerin yarıdan çoğunun hiç hesaplanmadığı anlamına gelir.

Not Alma ile Alttan Yukarı

Aynı bağıntı özyinelemesiz de kurulabilir. Bu, dinamik programlamanın ikinci biçimidir ve farkı ölçülebilir.

# Onceki bloklarin uzerine: dagarcik, Sayac, not_alan, kahin_secim ve K oradan gelir.
def alttan_yukari(dizi, k, s):
    """Ayni bagintiyi ozyinelemesiz kurar; butun (konum, kalan) hucreleri dolar."""
    n = len(dizi)
    tablo = [[0] * (k + 1) for _ in range(n + 2)]
    for i in range(n - 1, -1, -1):
        for kalan in range(1, k + 1):
            s.say()
            tablo[i][kalan] = max(tablo[i + 1][kalan],
                                  dizi[i] + tablo[i + 2][kalan - 1])
    return tablo[0][k], n * k


s1, s2, s3 = Sayac(), Sayac(), Sayac()
ayrilan, not_giris, tablo_hucre = 0, 0, 0
for k in K:
    a, boy = not_alan(k["dizi"], SECIM, s1, "tam")
    b, hucre = alttan_yukari(k["dizi"], SECIM, s2)
    kahin_secim(k["dizi"], SECIM, s3)
    if a != b:
        ayrilan += 1
    not_giris += boy
    tablo_hucre += hucre
print("kahin adim       :", s3.adim)
print("not alma adim    :", s1.adim, "| defter girisi:", not_giris)
print("alttan yukari    :", s2.adim, "| tablo hucresi:", tablo_hucre)
print("ikisinin ayrildigi girdi:", ayrilan, "/ 40")

kahin adim       : 163840
not alma adim    : 2440 | defter girisi: 1200
alttan yukari    : 1440 | tablo hucresi: 1440
ikisinin ayrildigi girdi: 0 / 40

İki biçim 40 girdide de aynı yanıtı veriyor, ama sayıları farklı. Alttan yukarı çözüm 1440 adım harcıyor, not alma 2440; aradaki fark özyineleme çağrılarının kendisidir. Buna karşılık not alma 1200 giriş tutuyor, alttan yukarı 1440 hücre. Yani dizi başına not alma 30 giriş, tablo 36 hücre.

Ödünleşim tam olarak buradadır. Alttan yukarı çözüm bütün hücreleri doldurur — erişilemeyecek olanları da — ve karşılığında çağrı yükü ödemez. Not alma yalnız gerçekten sorulan alt problemleri hesaplar, bu problemde 36 hücrenin 30’unu, ve karşılığında her alt problem için bir çağrı ödemesi yapar. Hangisinin kazandığı alt problem uzayının ne kadarının erişilebilir olduğuna bağlıdır; bu problemde uzayın altıda beşi erişilebilir olduğu için alttan yukarı öne geçiyor. Erişilebilir oran düştükçe not alma öne geçer.

Optimal Alt Yapı Sınanabilir Bir İddiadır

Yukarıdaki iki biçim de aynı bağıntıyı kullanıyor: bir konumdaki en iyi değer, ya o konumu atlayıp bir sonrakine geçmenin ya da o konumu seçip iki sonrakine geçmenin en iyisidir. Bu bağıntının doğruluğu optimal alt yapı varsayımına dayanır ve varsayım sınanabilir — bağıntının her hücresi ayrı ayrı kâhine sorulur.

# Onceki bloklarin uzerine: dagarcik, Sayac, kahin_secim, SECIM ve K oradan gelir.
def kahin_sonek(dizi, bas, kalan, s):
    """Sonekin en iyisini kaba kuvvetle bulur."""
    return kahin_secim(dizi[bas:], kalan, s)


hucre, uyusan, s = 0, 0, Sayac()
for k in K:
    dizi = k["dizi"]
    for i in range(len(dizi)):
        for kalan in range(1, SECIM + 1):
            hucre += 1
            atla = kahin_sonek(dizi, i + 1, kalan, s)           # i secilmiyor
            sec = dizi[i] + kahin_sonek(dizi, i + 2, kalan - 1, s)   # i seciliyor
            if max(atla, sec, 0) == kahin_sonek(dizi, i, kalan, s):
                uyusan += 1
print("sinanan hucre:", hucre, "| bagintinin kahinle uyustugu hucre:", uyusan)
print("kahin adimi  :", s.adim)

sinanan hucre: 1440 | bagintinin kahinle uyustugu hucre: 1440
kahin adimi  : 1719960

1440 hücrenin 1440’ında bağıntı kâhinle uyuşuyor. Sınamanın bedeli görülmelidir: 1.719.960 adım, yani çözümün kendisinin bin katından fazlası. Optimal alt yapıyı sınamak, problemi çözmekten pahalıdır ve bu şaşırtıcı değildir — her hücre için soneki baştan kaba kuvvetle çözmek gerekir.

Buradan iki şey çıkar. Birincisi, optimal alt yapı bir sezgi değil, sınanabilir bir iddiadır; bir bağıntı yazıldığında onun geçerliliği kâhine hücre hücre sorulabilir. İkincisi, bu sınama üretimde değil tasarım sırasında ve küçük girdide yapılır. Bağıntı bir kez doğrulandıktan sonra 40 girdide 1440 adımla çalışan bir çözüm kalır geriye; bir buçuk milyon adımlık sınama, o çözümün doğruluğunun bir defalık bedelidir.

İkinci Dağarcık

# Onceki bloklarin uzerine: dagarcik, olc oradan gelir.
for ad, tohum in (("birinci dagarcik (20260218)", 20260218),
                  ("ikinci  dagarcik (20260219)", 20260219)):
    kume = dagarcik(tohum)
    print(ad)
    for anahtar in ("tam", "eksik"):
        o = olc(anahtar, kume)
        print(f"  anahtar {anahtar:6s} ayrilan {o['ayrilan']:2d} / 40 | oran",
              round(o["ayrilan"] / 40, 4), "| kalip adim", o["kalip_adim"],
              "| defter girisi", o["defter_girisi"])

birinci dagarcik (20260218)
  anahtar tam    ayrilan  0 / 40 | oran 0.0 | kalip adim 2440 | defter girisi 1200
  anahtar eksik  ayrilan 39 / 40 | oran 0.975 | kalip adim 1000 | defter girisi 480
ikinci  dagarcik (20260219)
  anahtar tam    ayrilan  0 / 40 | oran 0.0 | kalip adim 2440 | defter girisi 1200
  anahtar eksik  ayrilan 37 / 40 | oran 0.925 | kalip adim 1000 | defter girisi 480

Adım ve defter sayıları iki dağarcıkta birebir aynı: 2440 ile 1200, 1000 ile 480. Beklenen sonuçtur, çünkü bu yordamların adımı dizinin değerlerine değil yalnız uzunluğuna ve seçim hakkına bağlıdır. Eksik anahtarın ayrılan girdisi 39’dan 37’ye iniyor; oran 0,9750’den 0,9250’ye. İki girdilik fark, çözünürlüğün anlamlı saydığı üç girdinin altındadır ve ölçülmemiş sayılır. Okuma iki dağarcıkta da aynıdır: eksik anahtar neredeyse her girdide yanlış yanıt verir.

Özet

• Dinamik programlamanın iki ön koşulu vardır: optimal alt yapı ve örtüşen alt problem; birincisi bozulunca yanıt, ikincisi bozulunca kazanç yok olur.
• Örtüşen yapıda $n = 20$ için çağrı 21.891’den 39’a iniyor; örtüşmeyen yapıda notlu ve notsuz sürüm ikisi de 39 çağrı yapıyor ve defter 19 girişi boşa tutuyor.
• Tam anahtarlı not alma kâhinin 67,15 katı az adım harcıyor ve 0 girdide ayrılıyor; eksik anahtarlı sürüm 163,84 katı az harcıyor ve 39 girdide ayrılıyor.
• Eksik anahtarda adım sayısının düşmesi bir hızlanma değil yanlışın belirtisidir; defter 1200 yerine 480 giriş tutuyor, yani alt problemlerin yarıdan çoğu hiç hesaplanmıyor.
• Alttan yukarı çözüm 1440 adımla not almanın 2440 adımından az harcıyor ama 1440 hücre tutuyor; not alma 1200 giriş tutuyor. Kazananı, alt problem uzayının erişilebilir oranı belirler.
• İkinci dağarcıkta adım ve defter sayıları birebir aynı; eksik anahtarın ayrılan girdisi 39 yerine 37 ve bu iki girdilik fark ölçülmemiş sayılır.

Sonraki Adım

Dinamik programlama, alt problem uzayını tümüyle dolaşıp saklıyordu. Bazı problemlerde uzay o kadar büyüktür ki tümünü dolaşmak seçenek değildir; orada tek yol, uzayın büyük bölümünün çözüm içermediğini kanıtlayıp kesmektir. Sonraki ders bu kesmeyi ölçer: budamalı arama yedi vezirlik tahtada 552 düğüm gezerken budamasız arama 960.800 düğüm geziyor, ve iki sayının oranı $n$ büyüdükçe artıyor.