Açgözlü Algoritmalar

Böl ve yönet problemi parçalıyor ve bütün parçaları çözüyordu. Bu dersin kalıbı daha cesur davranır: her adımda o an en iyi görünen seçimi yapar, yaptığı seçimi bir daha sorgulamaz ve geriye hiç dönmez. Kalıbın adı açgözlü (greedy) ve çekiciliği açıktır — geri dönüş olmadığı için adım sayısı küçüktür.

Cesaretin bir bedeli var. Böl ve yönette ön koşul birleştirmeye ilişkindi ve gözle görülüyordu. Burada ön koşul çok daha örtüktür: yerel olarak en iyi olan seçimin, küresel olarak en iyi çözümün parçası olması gerekir. Bu, girdiye bakarak anlaşılmaz; kanıtlanır ya da yanlıştır. Bu ders kanıtın ne olduğunu kurar ve kanıt olmadığında ne kadar yanıldığını sayar.

• TY20. Ölçülen problem: verilen tutarı bir para sisteminde en az sayıda parayla ödemek.
• TY21. Para sistemi $(1, a, b, c)$ biçimindedir. 1’in bulunması her tutarın ödenebilir olmasını güvenceye alır, yani “ödenemez” durumu ölçümü kirletmez.
• TY22. Açgözlü yordam en büyük paradan başlar ve geri dönmez. Bir adım, bir paranın kalandan düşülmesidir.
• TY23. Kâhin kaba kuvvettir: bütün para bileşimlerini sayar. Alttan yukarı çözüm kâhin yerine kullanılmadan önce kâhinle sınanır.
• TY24. Tarama, 2 ile 20 arasındaki bütün üçlüleri kapsar — 969 sistem — ve her sistemde 1’den 50’ye kadar bütün tutarları dener.
• TY25. Ayrılan girdi burada bir sistemdir: açgözlünün en az bir tutarda fazla para verdiği sistem sayılır.
• TY26. Fazlalık, açgözlünün kullandığı para sayısından en azının çıkarılmasıdır.
• TY27. M01/K04’ün açgözlü yordamları — Dijkstra algoritması, minimum kapsayan ağaç algoritmaları ve Huffman kodlaması — tekrarlanmaz; yalnız neden yanılmadıkları yazılır.
• TY28. İkinci dağarcık 20260219 tohumuyla üretilen beş değerli sistemlerdir.

Açgözlü Seçim ve Kanıt Yükümlülüğü

Açgözlü bir yordam, çözümü adım adım kurar ve her adımda bir ölçüte göre en iyi görünen adayı alır. Ölçüt sabittir, seçim geri alınmaz. Böyle bir yordamın doğru olması için tek bir şeyin gösterilmesi yeterlidir: her adımda yapılan seçimin, en iyi çözümlerden en az birinde bulunması. Buna açgözlü seçim özelliği denir ve gösterilme biçimi neredeyse her zaman aynıdır — bir değiş tokuş akıl yürütmesi.

Algoritmalar kursu bu akıl yürütmenin üç örneğini kurdu ve kanıtladı. Minimum kapsayan ağaç dersinde kesme özelliği, bir kesmeyi geçen en hafif kenarın bir en iyi ağaçta bulunduğunu gösteriyordu: o kenarı içermeyen bir ağaca kenar eklenince oluşan çevrimden, aynı kesmeyi geçen daha ağır bir kenar çıkarılabiliyordu. Huffman kodlaması dersinde aynı yapı, en seyrek iki simgenin kardeş yapılabileceğini gösteriyordu. Dijkstra algoritmasında ise seçim, kesinleşmemiş düğümler arasında en küçük tahminli olanın artık kesinleşmiş olmasıydı ve bu, kenar ağırlıklarının negatif olmamasına dayanıyordu.

Üçünün ortak yanı, seçimin güvenliğinin gösterilmiş olmasıdır. Bu ders o yordamları tekrarlamaz; sorduğu soru şudur: kanıt yoksa ne olur. Yanıt, sayılabilir bir şeydir.

Kâhini Doğrulamak

Para üstü probleminde en az para sayısını veren yordam, alttan yukarı çözümdür. Ama bu kursun kuralı kâhinin kaba kuvvet olmasını ister. Bu yüzden alttan yukarı çözüm, geniş taramada kullanılmadan önce kâhinle sınanır.

# Ortak cerceve: adim sayaci (onceki derslerden aynen).
from itertools import combinations


class Sayac:
    def __init__(self):
        self.adim = 0

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


def acgozlu_para(sistem, tutar, s):
    """En buyuk paradan baslar, geri donmez."""
    kalan, adet = tutar, 0
    for p in sorted(sistem, reverse=True):
        while kalan >= p:
            s.say()
            kalan -= p
            adet += 1
    return adet if kalan == 0 else None


def dp_para(sistem, tutar, s):
    """Alttan yukari tam cozum."""
    en_az = [0] + [10**9] * tutar
    for t in range(1, tutar + 1):
        for p in sistem:
            if p <= t:
                s.say()
                if en_az[t - p] + 1 < en_az[t]:
                    en_az[t] = en_az[t - p] + 1
    return en_az[tutar] if en_az[tutar] < 10**9 else None


def kahin_kaba_para(sistem, tutar, s):
    """Butun para bilesimlerini sayar. Hakem budur."""
    en_az = None

    def gez(i, kalan, adet):
        nonlocal en_az
        s.say()
        if kalan == 0:
            if en_az is None or adet < en_az:
                en_az = adet
            return
        if i == len(sistem):
            return
        p = sistem[i]
        for k in range(kalan // p + 1):
            gez(i + 1, kalan - k * p, adet + k)
    gez(0, tutar, 0)
    return en_az


ORNEK = [(1, 3, 7, 12), (1, 4, 9, 16), (1, 5, 10, 25), (1, 18, 19, 20)]
ayrilan, sk, sd = 0, Sayac(), Sayac()
for sistem in ORNEK:
    for tutar in range(1, 26):
        if kahin_kaba_para(sistem, tutar, sk) != dp_para(sistem, tutar, sd):
            ayrilan += 1
print("dogrulama: ", len(ORNEK), "sistem x 25 tutar =", len(ORNEK) * 25, "girdi")
print("kahin (kaba kuvvet) adim:", sk.adim, "| alttan yukari adim:", sd.adim,
      "| oran:", round(sk.adim / sd.adim, 2))
print("kahinden ayrilan girdi:", ayrilan)

dogrulama:  4 sistem x 25 tutar = 100 girdi
kahin (kaba kuvvet) adim: 13584 | alttan yukari adim: 2785 | oran: 4.88
kahinden ayrilan girdi: 0

Yüz girdinin hiçbirinde ayrılma yok; kaba kuvvet 13.584 adım, alttan yukarı çözüm 2785 adım harcıyor. Bu, alttan yukarı çözümün doğru olduğunu kanıtlamaz — sınamak kanıt değildir — ama onu 969 sistemlik taramada kâhin yerine kullanmayı ölçülmüş bir zemine oturtur. Kaba kuvvetin doğrudan kullanılmamasının nedeni de görünüyor: 4,88 katlık fark 100 girdide zararsızdır, 969 sistem ve 50 tutar için ise taramayı gereksiz yere büyütür.

Dokuz Yüz Altmış Dokuz Sistem

Asıl ölçüm, dört değerli bütün sistemleri tarar.

# Onceki blogun uzerine: Sayac, acgozlu_para, dp_para ve combinations oradan gelir.
def acgozlu_tarama(ust=20, tutar_ust=50):
    """Butun {1,a,b,c} sistemleri: acgozlu kac sistemde ve kac tutarda fazla veriyor."""
    bozuk, toplam_sistem, en_buyuk_fark, ornek = 0, 0, 0, None
    for a, b, c in combinations(range(2, ust + 1), 3):
        sistem = (1, a, b, c)
        toplam_sistem += 1
        s = Sayac()
        kotu = 0
        fark_en = 0
        for t in range(1, tutar_ust + 1):
            ac = acgozlu_para(sistem, t, s)
            dp = dp_para(sistem, t, s)
            if ac is not None and dp is not None and ac > dp:
                kotu += 1
                if ac - dp > fark_en:
                    fark_en = ac - dp
        if kotu:
            bozuk += 1
            if fark_en > en_buyuk_fark:
                en_buyuk_fark = fark_en
                ornek = (sistem, kotu, fark_en)
    return {"sistem": toplam_sistem, "bozuk": bozuk,
            "oran": round(bozuk / toplam_sistem, 4),
            "en_buyuk_fark": en_buyuk_fark, "ornek": ornek}


T = acgozlu_tarama()
print("taranan sistem:", T["sistem"], "| acgozlunun fazla verdigi:", T["bozuk"],
      "| oran:", T["oran"])
print("en buyuk fazlalik:", T["en_buyuk_fark"], "| ornek sistem:", T["ornek"])

taranan sistem: 969 | acgozlunun fazla verdigi: 827 | oran: 0.8535
en buyuk fazlalik: 16 | ornek sistem: ((1, 18, 19, 20), 2, 16)

969 sistemin 827’sinde açgözlü, gerekenden fazla para veriyor. Oran 0,8535, yani dört değerli para sistemlerinin yaklaşık altıda beşi açgözlü için uygun değil. En büyük fazlalık 16 paradır ve $(1, 18, 19, 20)$ sisteminde görülüyor.

Bu sayının hakkını vermek gerekir. Açgözlü seçim, para üstü probleminde herkesin sezgisine uyar: en büyük parayı ver, kalanı küçült. Sezgi yanlış değildir — 142 sistemde gerçekten doğru yanıtı verir. Yanlış olan, sezginin yordam yerine geçmesidir. Açgözlü seçim sezgiseldir; kanıtlanmadıkça yordam değildir.

Nerede ve Ne Kadar Yanılıyor

En büyük fazlalığın nerede ortaya çıktığı, yanılgının biçimini gösterir.

# Onceki bloklarin uzerine: Sayac, acgozlu_para, dp_para oradan gelir.
SISTEM = (1, 18, 19, 20)
s = Sayac()
print("sistem", SISTEM, "- acgozlunun fazla verdigi tutarlar")
for tutar in range(1, 51):
    ac = acgozlu_para(SISTEM, tutar, s)
    dp = dp_para(SISTEM, tutar, s)
    if ac > dp:
        print(f"  tutar {tutar:2d}: acgozlu {ac:2d} para, en az {dp:2d} para,"
              f" fazlalik {ac - dp:2d}")
print()
print("tarama siniri  bozuk sistem  oran")
for tutar_ust in (10, 20, 50, 100):
    T = acgozlu_tarama(tutar_ust=tutar_ust)
    print(f"{tutar_ust:14d} {T['bozuk']:13d} {T['oran']:6.4f}")

sistem (1, 18, 19, 20) - acgozlunun fazla verdigi tutarlar
  tutar 36: acgozlu 17 para, en az  2 para, fazlalik 15
  tutar 37: acgozlu 18 para, en az  2 para, fazlalik 16

tarama siniri  bozuk sistem  oran
            10            85 0.0877
            20           466 0.4809
            50           827 0.8535
           100           827 0.8535

36 tutarında en az çözüm iki paradır: 18 artı 18. Açgözlü ise 20’yi alır, kalan 16’yı bir tek birlerle ödeyebilir ve 17 para kullanır. 37’de aynı şey olur: en az çözüm 18 artı 19, açgözlünün çözümü 20 artı on yedi birlik. Yanılgının kaynağı görünüyor — en büyük parayı almak, geriye ödenmesi pahalı bir kalan bırakıyor. Açgözlü bu kalanı görmez, çünkü seçimi yaparken yalnız o anki en büyük değere bakar.

Alt tablo daha rahatsız edici bir şey söylüyor. Aynı 969 sistem yalnız 10’a kadar sınandığında 85 sistem bozuk görünüyor, oran 0,0877. 20’ye kadar sınandığında 466 sistem, oran 0,4809. 50’ye kadar sınandığında 827, oran 0,8535. 100’e çıkmak sonucu değiştirmiyor. Yani bu sistem ailesinde yanılgıların tamamı 50’nin altında ortaya çıkıyor, ama 10’a kadar sınayan biri sistemlerin yüzde 91’ini temiz sanırdı. Sınamanın kapsamı sonucun kendisini belirliyor; bir kalıbın “sınandı” denmesi, neye kadar sınandığı yazılmadıkça bir şey ifade etmez.

Sınanabilir Bir Yeter Koşul

Kanıtın yerini bir sezgi alamıyorsa, en azından sınanabilir bir koşul aranabilir. Para sistemleri için akla ilk gelen aday, değerlerin bir bölünme zinciri oluşturmasıdır: her değerin bir sonrakini bölmesi.

# Onceki bloklarin uzerine: Sayac, acgozlu_para, dp_para, combinations oradan gelir.
zincir_saglam, zincir_bozuk, digeri_saglam, digeri_bozuk = 0, 0, 0, 0
saglam_ornek = []
for a, b, c in combinations(range(2, 21), 3):
    sistem = (1, a, b, c)
    s = Sayac()
    bozuk = any(acgozlu_para(sistem, t, s) > dp_para(sistem, t, s)
                for t in range(1, 51))
    zincir = b % a == 0 and c % b == 0            # her deger bir sonrakini boluyor mu
    if zincir and bozuk:
        zincir_bozuk += 1
    elif zincir:
        zincir_saglam += 1
    elif bozuk:
        digeri_bozuk += 1
    else:
        digeri_saglam += 1
        if len(saglam_ornek) < 4:
            saglam_ornek.append(sistem)
print("bolunme zinciri olan  : saglam", zincir_saglam, "| bozuk", zincir_bozuk)
print("bolunme zinciri olmayan: saglam", digeri_saglam, "| bozuk", digeri_bozuk)
print("zinciri olmayan saglam sistemlerden ornekler:", saglam_ornek)

bolunme zinciri olan  : saglam 13 | bozuk 0
bolunme zinciri olmayan: saglam 129 | bozuk 827
zinciri olmayan saglam sistemlerden ornekler: [(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 3, 6), (1, 2, 3, 7)]

Bölünme zinciri taşıyan 13 sistemin 13’ü de sağlam; bu koşul altında açgözlü hiçbir tutarda fazla vermiyor. Ama zincirin bulunmadığı sistemlerin 129’u da sağlam. Koşul yeterlidir, gerekli değildir: sağladığında güvence verir, sağlamadığında hiçbir şey söylemez. $(1, 2, 3, 4)$ sistemi zincir taşımaz — 3, 2’yi bölmez — ama açgözlü orada da yanılmaz.

Bu ayrım bu kursun neden kâhini bırakmadığını açıklar. Yeter koşul, 969 sistemin 13’ünde ölçüme gerek bırakmaz. Kalan 956 sistem için tek bilgi kaynağı kâhindir; koşulun sağlanmaması bir kalıbı ne aklar ne mahkûm eder. Sınanabilir bir koşul, ölçümün yerine değil önüne geçer.

İkinci Dağarcık

Ölçüm, dört değerli sistemlerin ötesine taşınır: beş değerli ve daha geniş aralıklı sistemler iki tohumla üretilir.

# Onceki bloklarin uzerine: Sayac, acgozlu_para, dp_para oradan gelir.
def uretec(tohum):
    d = tohum

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


def bes_degerli_dagarcik(tohum, n=40):
    """Bes degerli {1,a,b,c,d} sistemler; degerler 2..40 arasinda ve artan."""
    r = uretec(tohum)
    kume = []
    while len(kume) < n:
        d = sorted({2 + r(39) for _ in range(4)})
        if len(d) == 4:
            kume.append((1, *d))
    return kume


for ad, tohum in (("birinci dagarcik (20260218)", 20260218),
                  ("ikinci  dagarcik (20260219)", 20260219)):
    sistemler = bes_degerli_dagarcik(tohum)
    bozuk, en_fark = 0, 0
    for sistem in sistemler:
        s = Sayac()
        kotu = max((acgozlu_para(sistem, t, s) - dp_para(sistem, t, s))
                   for t in range(1, 61))
        if kotu > 0:
            bozuk += 1
            en_fark = max(en_fark, kotu)
    print(ad, "| bozuk sistem", bozuk, "/ 40 | oran", round(bozuk / 40, 4),
          "| en buyuk fazlalik", en_fark)

birinci dagarcik (20260218) | bozuk sistem 39 / 40 | oran 0.975 | en buyuk fazlalik 21
ikinci  dagarcik (20260219) | bozuk sistem 40 / 40 | oran 1.0 | en buyuk fazlalik 21

Beş değerli sistemlerde oran 0,9750 ve 1,0000; iki dağarcık arasındaki bir sistemlik fark çözünürlüğün altındadır. Değer sayısını artırmak açgözlüyü düzeltmiyor, kötüleştiriyor — daha çok değer, en büyük parayı aldıktan sonra kalanı ödemenin daha çok yolu ve dolayısıyla açgözlünün kaçırabileceği daha çok çözüm demektir. En büyük fazlalık da 16’dan 21’e çıkıyor.

Bu, K04’ün üç açgözlü yordamıyla arasındaki farkı tamamlar. Orada seçimin güvenli olduğu kanıtlanmıştı ve kanıt, girdinin bir özelliğine dayanıyordu: kesmeyi geçen en hafif kenar, en seyrek iki simge, negatif olmayan kenar ağırlığı. Para sisteminde böyle bir özellik sistemin kendisine bağlıdır ve çoğu sistemde yoktur. Açgözlü kalıbı seçmek, o özelliğin var olduğunu varsaymaktır; varsayım yazılmadığında yordam sessizce fazla para verir.

Özet

• Açgözlü yordam her adımda en iyi görüneni alır ve geri dönmez; doğru olması için seçimin en iyi çözümlerden birinde bulunduğunun değiş tokuş akıl yürütmesiyle gösterilmesi gerekir.
• Alttan yukarı çözüm, geniş taramada kullanılmadan önce kaba kuvvetle sınandı: 100 girdide 0 ayrılma, kaba kuvvet 13.584 adım, alttan yukarı 2785 adım.
• Dört değerli 969 sistemin 827’sinde açgözlü fazla para veriyor; oran 0,8535 ve en büyük fazlalık 16 para, $(1, 18, 19, 20)$ sisteminde 36 ve 37 tutarlarında.
• Yanılgının kaynağı, en büyük parayı almanın geriye ödenmesi pahalı bir kalan bırakmasıdır; açgözlü o kalanı seçim anında görmez.
• Aynı tarama 10’a kadar yapılsaydı bozuk sistem sayısı 827 değil 85 çıkardı; sınamanın kapsamı sonucu belirler ve “sınandı” demek neye kadar yazılmadıkça bir şey söylemez.
• Beş değerli sistemlerde oran 0,9750 ve 1,0000’e çıkıyor; değer eklemek açgözlüyü düzeltmiyor, en büyük fazlalığı 16’dan 21’e taşıyor.

Sonraki Adım

Açgözlü, kalanı görmediği için yanılıyordu. Bunun bir çaresi var: kalanı da çözmek, yani her alt problemin en iyi çözümünü hesaplayıp saklamak. Bu dersteki alttan yukarı çözüm zaten bunu yapıyordu ve hiç yanılmadı. Sonraki ders o yordamın adını koyar ve iki koşulunu ölçer — alt problemlerin örtüşmesi ve en iyi çözümün alt problemlerin en iyi çözümlerinden kurulabilmesi. Örtüşme olmadığında saklamanın hiçbir şey kazandırmadığı, ama yine de yer tuttuğu sayıyla gösterilecek.