Greedy Algoritmalar: Ne Zaman İşe Yarar, Ne Zaman Yanıltır

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır.

Önce Tahmin Et

Kasada para üstü veren bir kod düşün. Akla gelen ilk algoritma, kasiyerlerin de yaptığı şey: en büyük bozuk parayla başla, sığdığı kadar ver, sonra bir küçüğüne geç.

// En büyük bozuk para önce. Yalnız "canonical" para sistemlerinde optimal
public static List<int> GreedyChange(int[] coins, int amount)
{
    List<int> used = [];
    foreach (int coin in coins.OrderDescending())
    {
        while (amount >= coin)
        {
            amount -= coin;
            used.Add(coin);
        }
    }

    return amount == 0 ? used : [];
}

Türk lirasının bozuk paralarıyla (1, 5, 10, 25, 50 kuruş ve 1 lira) bu algoritma her zaman en az sayıda parayı mı verir? Peki elindeki paralar yalnız 1, 3 ve 4 birimlik olsaydı ve 6 birim para üstü vermen gerekseydi, kaç para verirdi ve bu en az mı olurdu?

Greedy Nedir ve Ne Zaman Doğrudur

Greedy (açgözlü) algoritma, her adımda o an en iyi görünen seçimi yapar ve bir daha asla geri dönmez. Serinin 19. yazısındaki backtracking'in tam tersi: orada bütün dalları deneyip umutsuz olanları budadık, burada her adımda tek bir dal seçip diğerlerini hiç açmıyoruz. Bu yüzden greedy algoritmalar genellikle çok hızlıdır, çoğu zaman bir sıralama artı tek bir geçiş: O(n log n).

Hız bedava gelmez. Greedy'nin doğru cevap vermesi için problemin iki özelliği olmalı. Greedy choice property: o an en iyi görünen seçimi içeren bir optimal çözüm her zaman vardır. Optimal substructure: o seçimi yaptıktan sonra kalan problem aynı türden daha küçük bir problemdir ve onun optimal çözümü bütünün optimal çözümünün parçasıdır. İkincisini serinin 21. yazısında dynamic programming için de göreceğiz; greedy'yi ondan ayıran birincisi.

Greedy choice property'yi göstermenin klasik yolu exchange argument: optimal bir çözüm al, greedy'nin yaptığı seçimle değiştir ve sonucun kötüleşmediğini göster. Bunu bir örnek üzerinde yapalım.

Interval Scheduling: Tek Odada En Çok Toplantı

Bookstore ofisinde tek bir toplantı odası var ve gün içinde şu toplantılar istenmiş. Çakışmadan en çok kaç toplantı yapılabilir?

public sealed record Meeting(string Title, int Start, int End);

// Activity selection: her zaman en erken biten toplantıyı al. O(n log n).
public static List<Meeting> MaxNonOverlapping(IEnumerable<Meeting> meetings)
{
    List<Meeting> chosen = [];
    int freeAt = int.MinValue;
    foreach (Meeting m in meetings.OrderBy(m => m.End))
    {
        if (m.Start >= freeAt)
        {
            chosen.Add(m);
            freeAt = m.End;
        }
    }

    return chosen;
}

Meeting[] day =
[
    new("Standup", 9, 10), new("Pricing", 9, 12), new("Catalog", 10, 11),
    new("Review", 11, 13), new("Lunch talk", 12, 13), new("Retro", 13, 14),
];

one room: Standup 9-10, Catalog 10-11, Review 11-13, Retro 13-14

Kural "en erken biten toplantıyı al". Neden doğru olduğuna exchange argument ile bakalım. Optimal bir program al ve içindeki ilk toplantıya X de. Greedy'nin seçtiği G, bütün toplantılar arasında en erken biten olduğu için G, X'ten daha geç bitemez. X'i programdan çıkarıp yerine G'yi koy: G, X'ten erken ya da aynı anda bittiği için X'ten sonraki hiçbir toplantıyla çakışmaz ve toplantı sayısı aynı kalır. Yani G ile başlayan bir optimal program her zaman var. Geri kalanı, G bittikten sonra başlayan toplantılar üzerinde aynı problem; tümevarımla greedy optimal.

Sezgiye yatkın başka kurallar bu testten geçemez. "En kısa toplantıyı al" kuralını üç toplantılık bir günle deneyelim:

// Yanlış greedy: önce en kısa toplantı
Meeting[] trap = [new("A", 9, 12), new("B", 11, 13), new("C", 12, 15)];
List<Meeting> shortestFirst = [];
foreach (Meeting m in trap.OrderBy(m => m.End - m.Start))
{
    if (shortestFirst.All(x => m.End <= x.Start || m.Start >= x.End)) shortestFirst.Add(m);
}

shortest first: B; earliest end: A, C

En kısa toplantı B (2 saat) diğer ikisiyle de çakışıyor; onu seçmek A ve C'yi birlikte yapma şansını yok ediyor. "En erken başlayanı al" ya da "en az çakışanı al" kuralları için de karşı örnek bulunabilir. Greedy'de seçim kuralı her şeydir ve sezgi yeterli bir kanıt değildir.

Toplantı Odası Sayısı: Min-Heap ile

Soru değişiyor: bütün toplantıları yapmak için en az kaç oda gerekir? Bu kez toplantıları başlangıç saatine göre sıralıyoruz ve dolu odaların bitiş saatlerini bir min-heap'te tutuyoruz (serinin 13. yazısı). Yeni toplantı başlarken en erken boşalacak oda boşalmışsa onu kullanıyoruz, boşalmamışsa yeni bir oda açıyoruz:

// En az oda: başlangıca göre sırala, kullanımdaki odaların bitiş saatleri min-heap'te
public static int MinRooms(IEnumerable<Meeting> meetings)
{
    PriorityQueue<Meeting, int> busyUntil = new();
    int rooms = 0;
    foreach (Meeting m in meetings.OrderBy(m => m.Start))
    {
        if (busyUntil.TryPeek(out _, out int earliestEnd) && earliestEnd <= m.Start)
        {
            busyUntil.Dequeue(); // o oda boşaldı: tekrar kullan
        }

        busyUntil.Enqueue(m, m.End);
        rooms = Math.Max(rooms, busyUntil.Count);
    }

    return rooms;
}

rooms needed for all: 2

Heap'in boyu her an aynı anda süren toplantı sayısı; gün boyunca ulaştığı en büyük değer gereken oda sayısı. 9 ile 10 arasında Standup ve Pricing, 12 ile 13 arasında Review ve Lunch talk aynı anda sürüyor; hiçbir anda üç toplantı çakışmıyor. Maliyet sıralama için O(n log n), her toplantıda bir heap işlemi için O(log n).

Huffman Coding'e Kısa Bakış

Greedy'nin en zarif örneklerinden biri David Huffman'ın 1952'de yayımladığı sıkıştırma kodu. Fikir: sık görülen karakterlere kısa, nadir olanlara uzun bit dizileri ver ve hiçbir kod başka bir kodun başı (prefix) olmasın ki çözerken ayraç gerekmesin. Greedy adım: her zaman en hafif iki tree'yi birleştir.

private sealed record Node(char? Symbol, int Weight, Node? Left = null, Node? Right = null);

// Greedy: her zaman en hafif iki tree'yi birleştir. Prefix-free bir kod tablosu döner
public static Dictionary<char, string> BuildCodes(string text)
{
    PriorityQueue<Node, (int Weight, int Order)> queue = new();
    int order = 0;
    foreach (IGrouping<char, char> g in text.GroupBy(c => c).OrderBy(g => g.Key))
    {
        queue.Enqueue(new Node(g.Key, g.Count()), (g.Count(), order++));
    }

    while (queue.Count > 1)
    {
        Node a = queue.Dequeue();
        Node b = queue.Dequeue();
        Node parent = new(null, a.Weight + b.Weight, a, b);
        queue.Enqueue(parent, (parent.Weight, order++));
    }

    Dictionary<char, string> codes = [];
    Walk(queue.Dequeue(), "");
    return codes;

    void Walk(Node node, string prefix)
    {
        if (node.Symbol is char c)
        {
            codes[c] = prefix.Length > 0 ? prefix : "0";
            return;
        }

        Walk(node.Left!, prefix + "0");
        Walk(node.Right!, prefix + "1");
    }
}

'o' x5 -> 11
'b' x2 -> 010
'k' x2 -> 011
'r' x1 -> 000
's' x2 -> 100
't' x1 -> 001
' ' x1 -> 1010
'e' x1 -> 1011
bits: Huffman=42, 8-bit=120

"bookstore books" metninde en sık karakter olan "o" 2 bitle, nadir olanlar 3-4 bitle kodlanıyor; toplam 42 bit, karakter başına 8 bitlik kodlamanın 120 bitine karşı. Priority'ye bir sıra numarası eklememizin sebebi serinin 13. yazısındaki FIFO (First-In-First-Out) tuzağı: eşit ağırlıkta hangi tree'nin önce çıkacağı belirsiz olursa kod tablosu her çalıştırmada değişebilir. Huffman bugün de DEFLATE (zip ve gzip'in kullandığı sıkıştırma formatı) gibi formatların bir parçası olarak yaşıyor.

Greedy'nin Yanıldığı Yer: Bozuk Paralar

Açılıştaki soruya dönelim. 1, 3 ve 4 birimlik paralarla 6 birim:

{1,3,4} amount 6: greedy=[4, 1, 1] optimal coins=2

Greedy önce 4'ü alıyor, kalan 2 için iki tane 1 veriyor: üç para. Oysa 3 + 3 iki parayla aynı işi görüyor. Exchange argument burada çöküyor: "en büyük parayı al" seçimini içeren bir optimal çözüm yok. Optimali bulmak için her alt tutarın en iyi cevabını hesaplayan bir yöntem gerekiyor:

// Küçük tutarlar için kesin minimum; karşı örnek aramak için kullanılıyor
public static int OptimalCoinCount(int[] coins, int amount)
{
    int[] best = new int[amount + 1];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
        foreach (int c in coins)
            if (c <= a && best[a - c] != int.MaxValue)
                best[a] = Math.Min(best[a], best[a - c] + 1);
    return best[amount];
}

Bu küçük tablo dynamic programming'in ta kendisi; nasıl çalıştığını bir sonraki yazıda ayrıntısıyla göreceğiz. Burada onu bir hakem olarak kullanıyoruz.

Karşı Örnek Aramak

Bir greedy çözümün doğruluğunu ispat edemiyorsan, en azından yanlışlığını sistemli olarak ara. Küçük bir kesin çözücü (ya da kaba kuvvet) ile greedy'yi bir aralıktaki her input için karşılaştırmak, sezgiden çok daha güvenilir:

public static int? FindCounterexample(int[] coins, int maxAmount)
{
    for (int amount = 1; amount <= maxAmount; amount++)
    {
        List<int> greedy = GreedyChange(coins, amount);
        int optimal = OptimalCoinCount(coins, amount);
        if (optimal != int.MaxValue && (greedy.Count == 0 || greedy.Count > optimal))
        {
            return amount;
        }
    }

    return null;
}

{1,5,10,25,50,100}: no counterexample up to 1000
{1,2,5,10,20,50}: no counterexample up to 1000
{1,3,4}: fails at 6: greedy 3 coins, optimal 2
{1,15,25}: fails at 30: greedy 6 coins, optimal 2
{1,7,10}: fails at 14: greedy 5 coins, optimal 2

Türk lirasının kuruş sistemi (1, 5, 10, 25, 50, 100) ve 1, 2, 5, 10, 20, 50'lik sistem 1.000'e kadar hiç yanılmıyor. Bu tür sistemlere canonical denir ve kasiyerin greedy algoritması onlarda optimaldir. {1, 15, 25} sisteminde 30 birim için greedy 25 + 1 + 1 + 1 + 1 + 1 (altı para) verirken 15 + 15 iki para. Gerçek dünyada bunun karşılığı, bir kampanya için "indirim kuponu" ya da "puan" sistemi tasarlarken değerleri gelişigüzel seçmek: kasa yazılımı greedy çalışıyorsa müşteri fark etmeden fazla kupon harcar.

Testler hem doğru hem yanlış durumları sabitliyor; karşı örnek bulunamayan sistem için null bekliyoruz:

[Theory]
[InlineData(new[] { 1, 5, 10, 25, 50 }, null)]
[InlineData(new[] { 1, 3, 4 }, 6)]
[InlineData(new[] { 1, 15, 25 }, 30)]
public void FindCounterexample_FindsSmallestFailingAmount(int[] coins, int? expected) =>
    Assert.Equal(expected, Greedy.FindCounterexample(coins, 200));

Test run summary: Passed!
  total: 8
  failed: 0
  succeeded: 8
  skipped: 0
  duration: 445ms

"1.000'e kadar karşı örnek yok" bir ispat değildir. Bir para sisteminin canonical olup olmadığını kesin olarak söyleyen polinom zamanlı testler var, ama pratikte sınırlı bir aralıkta kesin çözücüyle karşılaştırmak çoğu yanlış sistemi hemen yakalar: karşı örnekler genellikle küçük tutarlarda çıkar.

Üretimde Dikkat

Greedy'yi hızı için seçiyorsan, doğruluğunu bir hakemle test et. Production'a giren her greedy kararı (kargo paketleme, kupon uygulama, kampanya önceliklendirme) için küçük input'larda kaba kuvvet ya da dynamic programming ile karşılaştıran bir test yaz. Testin işi greedy'nin optimal olduğunu ispatlamak değil, optimal olmadığı durumları bilinçli kılmak.

Bazen yaklaşık cevap yeterlidir. Kutulara kitap yerleştirme (bin packing) gibi problemlerde kesin çözüm çok pahalıdır; "en büyükten başla, sığdığı ilk kutuya koy" (first-fit decreasing) gibi greedy kurallar kesin optimalden en fazla belli bir oranda kötüdür ve milisaniyeler içinde çalışır. Bu durumda karar "greedy doğru mu?" değil, "bu sapma iş için kabul edilebilir mi?" sorusudur ve ölçülerek verilmelidir.

Seçim kuralını dokümante et ve isimlendir. OrderBy(m => m.End) satırı algoritmanın kalbi; biri onu OrderBy(m => m.Start) ile "sadeleştirirse" kod derlenir, testlerin çoğu geçer ve sonuç sessizce kötüleşir. Kuralın neden o olduğunu yorumla ve trap örneği gibi kuralı kıran bir testi kalıcı yap.

Sık Düşülen Tuzaklar

"Çalışıyor gibi görünen" greedy çözümü counterexample aramadan production'a almak. Kasiyer algoritması TL ile kusursuz çalışır; aynı kod farklı değerli kuponlarla 30 birim için 6 kupon harcatır. Testteki örnek verilerin şanslı olması algoritmanın doğru olduğunu göstermez.

Yanlış ölçüte göre sıralamak. Activity selection'da en kısa, en erken başlayan ya da en az çakışan; hepsi makul görünür, yalnız en erken biten doğrudur. Sıralama ölçütü bir ispat ya da en azından bir hakem testiyle seçilmeli.

Eşitlik durumlarını belirsiz bırakmak. Huffman'da ve heap kullanan her greedy'de eşit öncelikli elemanların sırası tanımsızsa çıktı çalıştırmadan çalıştırmaya değişebilir. Sonuç hâlâ optimal olabilir, ama testler ve cache'ler deterministik çıktı bekler.

Greedy'den geri dönüş beklemek. Greedy bir kararı geri almaz; çıkmaza girerse (bozuk para örneğinde 1'lik para yoksa ve kalan tutar verilemiyorsa) çözüm bulamaz, çözüm varken bile. GreedyChange bu yüzden boş liste dönüyor; {3, 4} ile 6 için greedy 4'ü alıp 2'de takılır, oysa 3 + 3 mümkün. Bu durumu da bir testle sabitledik:

[Fact]
public void GreedyChange_NoOneCoin_GetsStuck()
{
    Assert.Empty(Greedy.GreedyChange([3, 4], 6));
    Assert.Equal(2, Greedy.OptimalCoinCount([3, 4], 6));
}

Küçük Bir Deneme

★☆☆ MinRooms'u her toplantının hangi odaya atandığını da döndürecek şekilde değiştir (heap'te oda numarasını tut). Bookstore'un toplantı günü için oda planını yazdır.

★★☆ Activity selection için kendi hakem testini yaz: rastgele 10 toplantılık 1.000 gün üret, her gün için bütün subset'leri deneyen kaba kuvvetle (serinin 19. yazısındaki Subsets) en çok toplantı sayısını bul ve greedy ile karşılaştır. Sonra kuralı "en kısa önce" yap ve testin kaç günde kırıldığını say.

★★★ FindCounterexample'ı kullanarak üç paralı (1, a, b; a < b ≤ 30) bütün sistemleri tara ve hangilerinin 200'e kadar canonical olduğunu listele. Canonical olanlarda b ile a arasında bir ilişki görüyor musun?

Bozuk para örneği greedy'nin sınırını gösterdi: bazı problemlerde her alt problemin en iyi cevabını bilmeden doğru seçimi yapamazsın. Bir sonraki yazıda tam olarak bunu yapan yönteme geçiyoruz: dynamic programming. Fibonacci'nin exponential versiyonundan başlayıp memoization ve tabulation ile aynı hesabı doğrusal zamana indireceğiz.