--- title: 'Açgözlü Algoritmalar' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/acgozlu-algoritmalar' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:27+00:00' license: 'CC BY-SA 4.0' --- # Açgözlü Algoritmalar Açgözlü seçimin kanıtlanmadıkça yordam olmadığı: dört değerli 969 para sisteminin 827'sinde açgözlü gerekenden fazla para veriyor, oran 0,8535 ve en büyük fazlalık 16 para; aynı yanılgı 50 yerine 10 tutara kadar sınandığında sistemlerin yalnız 85'inde görülüyor. 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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.