Greedy Algoritma Nedir? Activity Selection ve Huffman’ı Görün

Greedy algoritmalar, her adımda o anda en iyi görünen seçimi yaparak çözüme ilerler. Bu yaklaşım kısa ve hızlı kodlar üretir; fakat yerel olarak iyi bir seçim her problemde global optimumu garanti etmez. Asıl beceri, greedy’nin çalıştığı problemi tanımak ve doğruluğunu gerekçelendirmektir.

Websoftik Academy Greedy Optimization Lab; Activity Selection, Huffman Coding ve karşı örnekler üzerinden seçim, kalan problem, kanıt ve complexity ilişkisini aynı trace üzerinde gösterir.

Greedy yöntem, çözümü geri dönmeden art arda seçimlerle kurar. Her adımda bir candidate set, feasibility kuralı ve “en iyi” adayı belirleyen selection function bulunur. Seçim kalıcıdır; dynamic programming’deki gibi bütün alt durumlar saklanmaz, backtracking’deki gibi karar ağacı yeniden gezilmez.

Bu nedenle greedy kodu çoğu zaman sorting ile başlar ve tek geçişle devam eder. Ancak hız tek başına doğruluk değildir. Problem hem greedy choice property hem optimal substructure taşıyorsa yerel seçimler optimum çözüme dönüşebilir.

Greedy Optimization Lab, problemi input, ordered candidates, current solution ve rejected candidates katmanlarına ayırır. Bir adım ilerlediğinizde hangi adayın değerlendirildiği, neden kabul veya reddedildiği ve objective değerinin nasıl değiştiği görünür.

Lab’in önemli tarafı yalnızca başarılı örnekleri göstermemesidir. Aynı seçim kuralını küçük bir counterexample üzerinde çalıştırıp local optimum ile global optimum arasındaki farkı karşılaştırabilirsiniz.

Greedy choice property, en az bir optimal çözümün greedy seçimi içerdiğini söyler. Başka bir ifadeyle ilk kararı güvenle sabitleyebilir, geri kalan problemde optimumu aramaya devam edebiliriz. Bu, “mantıklı görünüyor” sezgisi değil, probleme özel ispatlanması gereken bir özelliktir.

Selection kriteri değiştiğinde özellik de kaybolabilir. Activity Selection’da en erken başlayan ya da en kısa süren aktiviteyi seçmek cazip görünür; fakat genel durumda optimumu garanti eden kriter en erken bitiş zamanıdır.

Optimal substructure, optimal çözümün içinde kalan alt problemin çözümünün de optimal olmasıdır. Greedy seçim yapıldıktan sonra uyumsuz adaylar elenir; geriye aynı yapıda, daha küçük bir problem kalır.

Bu özellik dynamic programming’de de vardır. Ayrım şudur: DP birbiriyle yarışan çok sayıda alt durumu değerlendirirken greedy tek bir güvenli seçimi sabitler. Bu yüzden greedy’nin ek olarak choice property’ye ihtiyacı vardır.

Amaç, başlangıç ve bitiş zamanları verilen aktivitelerden çakışmayan en büyük kümeyi seçmektir. Aktiviteler bitiş zamanına göre sıralanır. İlk aktivite seçilir; ardından başlangıcı son seçilen aktivitenin bitişine eşit veya büyük olan ilk aday kabul edilir.

Sorting sonrası tek geçiş yeterlidir. Lab timeline üzerinde accepted aktiviteleri yeşil, overlap nedeniyle elenenleri ayrı renkte tutar. Böylece feasibility kontrolü ile objective’in “aktivite sayısını büyütmek” olduğu birbirine karışmaz.

En erken biten uyumlu aktivite, kalan zaman aralığını olabildiğince geniş bırakır. Bir optimal çözüm başka bir aktiviteyle başlıyorsa ilk aktiviteyi greedy seçimle değiştirebiliriz; greedy aktivite daha geç bitmediği için sonraki aktiviteler hâlâ uyumludur.

Bu exchange işlemi çözüm sayısını azaltmaz ve greedy seçimi içeren bir optimal çözüm üretir. Kanıtın gücü, tüm olasılıkları denemeden ilk seçimin güvenli olduğunu göstermesidir.

Huffman Coding, karakter frekanslarına göre prefix-free ve minimum ağırlıklı code tree üretir. Her turda frekansı en küçük iki node çıkarılır, toplam frekanslı yeni bir parent altında birleştirilir ve yapı tekrar aday kümesine eklenir.

Sık karakterler root’a yakın, seyrek karakterler daha derinde kalır. Lab her merge sonrasında forest’ı, oluşan code tree’yi ve toplam bit maliyetini günceller. Sol edge için 0, sağ edge için 1 verilmesi kodu değiştirir fakat optimal maliyeti değiştirmez.

Her Huffman turunda en küçük iki frekansa erişmek gerekir. Unsorted array ile bu seçim her tur O(n) tarama ister. Min-priority queue, iki extract-min ve bir insert işlemini O(log n) zamanda yapar; toplam construction maliyeti O(n log n) olur.

Priority Queue’nun array-tree representation’ını önce Heap & Priority Queue rehberinde inceleyebilirsiniz. İki Lab birlikte çalışıldığında veri yapısı seçiminin algoritmanın maliyetini nasıl değiştirdiği açıkça görülür.

Lab, optimal solution ve greedy solution satırlarını yan yana göstererek exchange adımını soyut bir cümle olmaktan çıkarır. Kanıt her problemde aynı kalıp değildir; değiştirilen öğe ve korunan invariant açıkça yazılmalıdır.

Coin Change’de her zaman en büyük parayı seçmek bazı denomination kümelerinde optimum değildir. Örneğin para değerleri 1, 3 ve 4 iken 6 için greedy 4+1+1 seçer; optimum 3+3’tür. Local choice property bulunmadığı için geri dönmemek çözümü kilitler.

Bir greedy strateji önermeden önce küçük exhaustive örnekler üretmek iyi bir testtir. Counterexample bulmak stratejiyi çürütür; bulamamak ise tek başına doğruluk kanıtı değildir.

Fractional Knapsack’te öğeler bölünebilir. Değer/ağırlık oranı en yüksek öğeden başlayarak kapasiteyi doldurmak optimumdur. Son öğenin yalnızca gereken kısmı alınabilir; exchange argument bu stratejiyi destekler.

0/1 Knapsack’te öğe ya tamamen alınır ya alınmaz. Aynı oran stratejisi kapasite içinde daha iyi bir kombinasyonu kaçırabilir. Bu sürüm genellikle dynamic programming veya problem boyutuna göre başka arama teknikleri gerektirir.

Backtracking akışını karşılaştırmak için Recursion & Backtracking rehberine geçebilirsiniz. En iyi yaklaşım bazen hibrittir: greedy bound, daha büyük bir arama veya optimizasyon algoritmasının pruning kararını güçlendirebilir.

Greedy algoritmanın maliyeti çoğunlukla ön işleme ve candidate seçimine bağlıdır. Activity Selection sıralı input’ta O(n), sıralama gerekiyorsa O(n log n)’dir. Huffman, min heap ile O(n log n) çalışır.

Yalnızca ana loop’u saymak sorting veya data structure maliyetini gizler. Time complexity yanında space complexity, tie-break davranışı ve output’un deterministik olup olmadığı da analiz edilmelidir.

Greedy Optimization Lab’i açın ve ilk seçimi yapmadan önce sonucu tahmin edin. Graph problemlerinde greedy kullanımını görmek için Graph Algorithms rehberini inceleyin.