1.Greedy Algoritması nedir?
Sonraki adım üzerinde durulmadan ve hesaba katılmadan optimal çözüm arayışında mevcut şartlar üzerinden yaklaşımda bulunmaya greedy yani açgözlü algoritma denir. Amacı en iyi çözümü top down yaklaşım ile modellemektir.
2.Greedy Algoritması nasıl oluşturulur?
Çözüm bulmak istediğimiz problemin odak noktasına göre elimizdeki set öncelikle sortlanmalıdır. Sortlanan bu set üzerinden problemin odağına göre set tamamından azaltarak dibe doğru gidercesine tekrarlı halde işlem yapılmalıdır. Örneğin maximum gelir elde edilebilecek halde çanta doldurma istendiyse, ürünler değerleri en yüksekten aza doğru sıralanır ve sıradan çantaya kapasitemiz bazında doldurulmaya başlanır.Örneğin aktivite sıralaması istendiyse aktiviteler bitiş sürelerine göre sortlanabilir bu bağlamda öncelikli olanlar erken bitiş süreleri olanlar olacağı için bitiş süresi en erkenden en geç olana doğru sıralama yapılabilir. Bunun için bir Açgözlü yaklaşım karar değişkeni tutulur ve işlemler yapılır, bu bağlamda bir giyim fabrikasının maksimum verimle ürün dağıtımı da modellenebilir, bir süt fabrikasının maksimum süt litresi elde etme mantığı da modellenebilir. Verileri sortladıktan/sıraladıktan sonra talep edilen kondisyon üzerinden eldeki set ile işlem yapılmalıdır.
3.Bazı bilinen Greedy Yaklaşımları
En çok kullanılan Greedy algoritmaları şu şekilde söylenebilir: Knapsack, Dijkstra, Huffman, Activity Selection, Prims and Kruskal Algoritmaları. Bunlardan bazılarını bir nebze daha detaylı açıklayalım. Öncelikle Aktivite Seçme Problemine geliştirilen Açgözlü yaklaşım algoritmasından bahsedelim. Bu problemde birtakım aktiviteler vardır ve bu aktivitelerin başlangıç ve bitiş saatleri bilinir. Aynı zamanda tek aktivite seçilebilecek şekilde maksimum aktiviteyi nasıl seçebiliriz sorusu üzerinde durulmaktadır. Açgözlü yaklaşımın bizden talep ettiği üzere, elimizdeki setten en yakın bitiş zamanlı aktiviteyi çıkardığımızda elimizde kalan değişikliğe uğramış setimizin yine optimize çözümünü aramalıyız. Yani göstermek gerekirse S setimiz olsun a da en erken zamanlı bitiş saatine sahip etkinlik ve B de optimize çözümümüz, böylece S – a = S’ setini oluşturacaktır ve S nin optimize çözümü B aynı zamanda S’ + a nın da çözümü olacaktır. Yani S – a kümesinin de aynı zamanda optimize çözümüdür.Bu şekilde elimizde aktivite kalmayana kadar ilerleyebilecek şekilde optimize çözümümüzü yorumlayabiliriz. Pseudocode yani taslak kodunu yorumlamak gerekirse eğer, bir loop içerisinde gezinerek aktivitelerin başlangıç ve bitiş sürelerini kıyaslayarak setimizle oynama yaparak optimal aktiviteleri maksimum sayıda olacak şekilde modelleyebiliriz.İkinci olarak Knapscak problemine Açgözlü yaklaşımdan bahsedelim. Dinamik programlamada da bahsi geçen temeli çantamıza/torbamıza/kutumuza nesneleri doldurmak olan Knapsack problemi Açgözlü Algoritmada yaklaşımsal farklılıklar içermektedir. Dinamik programlamada binary(0-1) Knapsack modeli varken Açgözlüde fractional yani parçalı nesnelerle işlem yapılır. Buna örnek olarak çantama kum,altın tozu gibi malzemeleri doldurmaya çalıştığım durumlar düşünülebilir. Bu gibi durumlarda maksimum değerdeki malzemeyi dolduracak şekilde ilerlenilir. Bunun için bize karşılaştırma yapabileceğimiz veriler gereklidir, her ürünü değeri/kütlesi üzerinden kolayca sıralayabiliriz.Sıralamayla başladığımız açgözlü yaklaşımda sıralanmış ürünler üzerinden doldurmaya başlarız kapasitemizin dolup dolmadığını da if kondisyonu üzerinden kontrol ederiz. Ürünleri doldurdukça kazancımızı ve kapasitemizi revize ederiz biri artarken diğeri azalacaktır. Sonunda kapasitemiz yetersiz hale geldiğinde elimizde sıralamaya göre doldurulmuş yani maksimum kazancı elde edebileceğimiz bir algoritma olmuş olacaktır. Son olarak Huffman kod algoritması üzerinde durabiliriz. Huffman kodu temsili veri sayılarını azaltmak böylece verimli veri sıkıştırılması yapılmasına olanak sağlamak amaçlı kullanılan bir algoritmadır. Normalde sayıları temsil etmek için binary taban üzerinden bit sayı hesabı yapılırken Huffman kodunda kullanım sıklıkları üzerinden temelinde bir ağaç üzerinden bit hesabına dahil etmeyi tavsiye edilir. Bu süreç şu şekilde işler, bir dosya düşünelim bu dosyada k karakteri 45bin kez, l karakteri 13bin kez, m karakteri 9bin kez, n karakteri 16bin kez,t karakteri 5bin kez, p karakteri de 12bin kez geçmekte.Normalde bu 6 karakteri binary hesapla bit hesabına eklemek için minimum 3 bite ihtiyaç duyarız(2^3 = 8 sayı tutulabilir, 000,001,010… şeklinde). Bu da (13bin + 12bin + 9bin + 5bin + 45bin + 16bin) * 3 bit = 300bit ihtiyacına denk gelir. Ancak huffman kod kullanarak 45,13,12,16,9,5 sıklıklarını eşleştirerek ağaca yerleştirirsek bir sıklık ağacı elde etmiş oluruz bunun içinde genelde sol kola 0 sağ kola 1 verilerek sayıların Huffman temsili bit sayıları bulunur.Bu örnek için en sıktan en seyreğe, 0, 111, 101, 100, 1101, 1100 olacaktır bunlar da sıklıklarıyla çarpıldığında 300bin bitten daha az yer tutacaktır.
Huffman kodu için örnek görseli bu şekilde verilebilir.
4.Greedy Algoritması ve Dinamik Programlama yorumlaması
Açgözlü ve Dinamik Programlama karşılaştırmasında, ikisinde de optimal çözüm aranmaktadır. Açgözlü yaklaşımda bir seçim elemanı tutulur bu durum dinamik programlamada yoktur. Bu eleman optimal çözüm için karar değişkenini temsil eder. Değişken üzerinden seçim yapıldıktan sonra alt problemler çözülerek devam edilir. Dinamik programlamada ise her adımda seçim vardır ve bu seçim alt problemlerin optimal çözümlerini etkileyebilir. Ancak açgözlü yaklaşımda ise bu durum asla gelecek adımların seçimlerine ya da çözümlerine bağlı olamaz çünkü bu şekilde dizayn edilmez. Dinamik programlama memoization bazlı konuşmadan tam anlamıyla bir bottom up stratejisine sahiptir, açgözlü yaklaşım ise tam dersi top down stratejiye sahiptir. Yani açgözlü seçim değişkeni her adımda artırımlıdır ve bütün üzerinden indirgeyerek hesaplanır, dinamik programlamada bu durum tersinir işlemektedir. Özetle açgözlü yaklaşım top down stratejiye sahipken dinamik programlama bottom up stratejiye sahiptir.