Greedy Algoritması

Greedy Algoritması

Greedy Algoritması yani bir diğer adı ile açgözlü algoritmalar, optimizasyonlar sırasında yaşanan problemleri ortadan kaldırmak adına kullanılan basit, uygulanması oldukça kolay olan ve sezgisel  olarak oluşturulmuş algoritmalara verilen  isimdir. Yalnızca optimizasyon problemleri için kullanılmalarına karşın genel olarak bir tasarım tekniği olarak da görülüyor. Bu nedenle de büyük bir önem taşıyor. Açgözlü algoritmalar ile problem çözümü gerçekleştirmekte kullanılan bu temel teknik,  problemin oldukça küçük bir alt kümesindeki çözümü oluşturmak ve bu çözümü genel bir çözüm haline getirmeyi sağlıyor. Algoritmada sağlanan çözümü elde etmek için kullanılan seçimler en başta doğru gibi görünse de zaman içerisinde olumsuz ve yanlış olabiliyor. 'Greedy ne demek?' sorusuna bu şekilde yanıt verilebiliyor.  Bu açıklamaya bağlı olarak da Greedy algoritmasında çeşitli tekniklerden yararlanılıyor. En çok tercih edilen açgözlü algoritmalar ise aşağıdaki şekilde sıralanıyor;

• Knapsack Problemi
• Kruskal Algoritması
• Prims Algoritması
• Huffman Kodu
• Dijkstra Algoritması

'Greedy algoritması ne demek?' sorusu da özetle bu şekilde yanıtlanabiliyor.  Peki, Greedy algoritması nasıl oluşturulur?  İşte tam olarak bu kısımda ise  algoritmaların nasıl çalıştığı hakkında bilgi sahibi olunması gerekiyor. Aksi bir durumda nasıl bir yol izleneceği hakkında doğru kararlar alınması mümkün olmuyor.  Algoritmaların örneklerine bakılması, nasıl işlendiklerinin öğrenilmesi, avantajları ve dezavantajları, nasıl uygulandıklarının bilinmesi daha profesyonel bir şekilde ilerlenmesini sağlıyor. Bu şekilde istenilen maksimum verime daha kısa süre içerisinde ulaşım sağlanabiliyor ve maksimum verim elde edilmesi mümkün oluyor.

Greedy Algoritması Nasıl Oluşturulur?

Greedy algoritmasını oluşturmak için ilk olarak çözüm bulunmasını istediğiniz probleme odaklamanız gerekiyor. Çözüm bulunmak istenilen noktaya odaklandıktan sonra elde bulunan setin sortlanması gerçekleştiriliyor.  Sortlama işleminin gerçekleştirildiği bu set aracılığıyla probleme odaklanılıyor ve setin geneline bakılarak en detaya inene kadar tekrarlı bir şekilde işlem gerçekleştiriliyor.

Örnek  verilmesi gerekirse; maksimum gelir sağlanacak olan çanta doldurmak isteniyorsa elde bulunan ürünlerin değerleri değerlendiriliyor. Değerlendirme işlemi sonrasında değerler en yüksekten en aza doğru sıralanıyor ve çanta kapasitesine göre doldurma işlemi gerçekleştiriliyor. Örneğin aktivite olarak sıralama gerçekleştirilecek ise aktivitelerin bitiş zamanına göre sortlanması bu noktada önem taşıyor. Bu noktada zamanı erken bitecek olanların öne alınması ve zamanı uzun olanlara göre sıralama yapılması öneriliyor. Açgözlü yaklaşım göz önünde bulundurularak sıralanıyor ve işlemler gerçekleştiriliyor.

Bu duruma göre bir tekstil fabrikasının maksimum verim ile ürün dağıtımı modellemesi yapması, bir süt fabrikasının ise maksimum süt elde etme mantığıyla hareket etmesi örnek verilebiliyor. Greedy algoritması örnekleri de aşağıdaki şekilde sıralanabiliyor. Böylece elde edilen örnekler doğrultusunda ilerleme sağlanabiliyor.

Greedy Algoritması Örnekleri

En çok tercih edilen Greedy algoritması çeşitleri şu şekilde sıralanabiliyor: Knapsack, Huffman, Activity Selection,  Dijkstra,  Prims ve Kruskal Algoritmaları en çok tercih edilen Greedy algoritmaları arasında bulunuyor. Bu algoritmaların detaylı olarak öğrenilmesi kullanım açısından pek çok avantaj sağlıyor.

İlk olarak aktivite seçme problemi için geliştirilmiş olan açgözlü yaklaşım algoritmasından bahsedilmesi gerekiyor. Yalnızca bir aktivite seçilebiliyor olarak görülse de maksimum aktivitenin oluşturulması için olanak sağlanıyor.  Açgözlü yaklaşımın yani Greedy Algoritması verilen algoritmanın kullanıcılardan talep ettiği gibi, elde bulunan setten en yakın zamanlı aktivite çıkarıldığında elde kalan değişikliğe uğramış kısmın yine optimize çözümünün aranması gerekiyor.  Yani ifade etmek gerekirse elimizde bir S seti 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şturuyor ve S nin optimize edilmiş olan çözümü B, aynı zamanda S’ + a’nın da çözümü oluyor. Bu duruma göre  S – a kümesinin de aynı anda çözüme kavuşturulduğu görülüyor. Bu duruma göre edilde bulunan aktivite kalmayana kadar ilerleme sağlanıyor ve optimize çözümümüzü yorumlanabiliyor.

Pseudocode adı verilen taslak kodunun da yorumlanması verilebilecek örnekler arasında yer alıyor. Örnek vermek gerekirse, herhangi bir loop içerisinde gezinme ile elde edilecek olan aktivitelerin başlangıç ve bitiş süreleri kıyaslanıyor ve elde bulunan veriler üzerinde  değişiklikler yapılarak tüm aktiviteleri maksimuma çıkacak şekilde modellemek mümkün oluyor. İkinci adımda ise Knapscak problemine göre açgözlü yaklaşım incelenebiliyor. Açgözlü yaklaşımın örneklerinin net bir şekilde algılanabilmesi için Knapscak probleminin göz önünde bulundurulması büyük önem taşıyor. Dinamik programlamada da ismi geçen ve temelinin depolarda duran nesnelerin doldurulması olduğu Knapsack probleminin yaklaşımsal olarak farklılıkları oluyor.

Dinamik programlamaya bakıldığında binary(0-1) Knapsack modeli bulunurken açgözlü yaklaşımda parçalı nesneler ile işlemler gerçekleştirilebiliyor. Bu duruma örnek olarak çanta içerisinde altın tozu ve benzeri maddelerin doldurulmaya çalışıldığı örnek verilebiliyor. Maksimum sayıda nesnenin çanta içerisinde eklenebilmesi için ise yeni yöntemlerin bulunması gerekiyor. Karşılaştırılmış olan verilen bu aşamada oldukça fazla öne taşıyor. Her nesne kütlesine, ağırlığına göre karşılaştırılıyor ve ‘Greedy algoritması nedir?’ sorusunun cevabı da bu aşamada verilebiliyor. Nesnelerin sıralanmaya ve karşılaştırılmaya başlanıldığı açgözlü yaklaşımda nesnelere uygun kapasitesinin bulunup bulunmadığına bakılıyor ve if kondisyonu hesaplanıyor. Ürünler sepete eklendikçe kazanç ve kapasite değerlendiriliyor ve gerekli revizeler gerçekleştiriliyor. Bu aşama aç gözlü yaklaşım için büyük önem taşıyor. Gerekli revizelerin yapılmasının ardından çanta kapasitesinin yetersiz hale gelmesi durumunda verilerden elde edilen sıralama doğrultusunda maksimum kazancın elde edilebileceği bir algoritma oluşuyor.

Açgözlü algoritma örnekleri arasında verilebilecek olan bir diğer algoritma örneği ise Huffman oluyor. Huffman kodu adı verilen bu örnek temsili olarak verileri azaltmak ve bu azaltma sonucunda verimli verileri elde tutmak için gerçekleştirilen bir algoritma olarak görülüyor. Normal durumlarda sayıları temsil etmesi için binary tabandan sayı hesabı gerçekleştiriliyor ancak Huffman kodunda ise kullanım sıklığına bakılarak bit hesabı gerçekleştiriliyor. Bu hesaplama süreci ise şu şekilde gerçekleştiriliyor;

Örneğin bir dosya göz önüne getiriliyor ve  bu dosyada A karakteri en az 45 bin kez, B karakteri 13 bin kere, C karakteri ise 9 bin kere , D karakteri 16 bin kere , E  karakteri 5 bin kere, F karakteri de 12 bin kere geçiyor. Normalde bu 6 karakterin  binary hesaplaması ile  bit hesabına eklemek için minimum 3 bite ihtiyaç duyulduğu görülüyor.

(2^3 = 8 sayı tutulabiliyor, 000,001,010…). Bu durum da  (13 bin + 12 bin + 9 bin + 5 bin + 45 bin + 1 6bin)x3 bit = 300 bit sonucunu meydana getiriyor. Ancak Huffman koduna bakıldığında ve bu kod kullanıldığında 45,13,12,16,9,5 şıkları eşleştiriliyor ve Huffman kodu ile bit sayıları bulunuyor. Bu örnek göz önünde bulundurulduğunda en sıkıştıktan en seyreğe doğru bir sıralama yapıldığında, 0, 111, 101, 100, 1101, 1100 oluyor ve bu sonuçlar da sıklıklarıyla çarpıldığında 300 bin bitten daha az yer tuttuğu görülüyor. Greedy parametresi nedir sorusunun cevabı ise bu örnekler oluyor.

Greedy Algoritmasının Avantajları Nelerdir?

Greedy algoritması, yaklaşım algoritmaları arasında yer alan algoritmalardan bir tanesi olarak karşımıza çıkıyor. Bu algoritmanın kendi içerisinde pek çok avantajı bulunuyor. Kullanıcılar algoritmayı hangi alanda kullanıyor olursa olsun maksimum verimi almak için kullanıyor. Bu sayede verilere dayanarak pek çok alanda maksimum verime ulaşılabiliyor. Matematiksel bir algoritma olması da yaşanabilecek olumsuzlukların önüne geçilmesini ve en az riskin alınmasını sağlıyor. Greedy Algoritması tipik temsilcisi de bu aşamada önem taşıyor.

Bu algoritmanın avantajları arasında ilk sırada hata yapma oranını en aza indirgemesi yer alıyor. Algoritmanın püf noktalarına dikkat edilmesi durumunda sorunsuz bir şekilde işlem yapılabiliyor ve özellikle örnekler üzerinden ilerleme sağlanabiliyor.

Algoritma matematiksel bir temele dayandığı için alan fark etmeksizin her türlü alanda maksimum verim alınması mümkün hale geliyor. Örnek vermek gerekirse bir süt fabrikasında sütten maksimum verim alınması bu algoritma ile hesaplanabiliyorken aynı zamanda bir tekstil fabrikasının da maksimum verimi bu algoritma ile hesaplanabiliyor. Kısaca alan ve sektör fark etmeksizin her türlü alanda kullanımı gerçekleştirilebiliyor.

Greedy algoritmasının avantajları arasında yer alan bir diğer avantaj ise şüphesiz ki ücretsiz bir uygulama olması yer alıyor. Kolay bir şekilde hesaplama gerçekleştirilebildiği için bu uygulama için ekstra ücretler ödenmesine gerek kalmıyor. Bireysel olarak hesaplama yapılabiliyor ve bu algoritmaya göre bir yol izlenebiliyor.

Açgözlü algoritmaların bir diğer avantajı ise optimal çözümlerin sağlanması oluyor. Diyelim ki sıkışmış bir andasınız ve kısıtlı bir zamanınız bulunuyor. Bu kısıtlı zaman içerisinde anında çözüm bulmak ve sorunun ortadan kalkmasını sağlamak için açgözlü algoritmasını kullanmanız büyük avantaj sağlıyor. Basit bir çözüm olarak görülse de bu algoritma sayesinde küçük bir alanda başlayan çözüm genel bir çözüme dönüşebiliyor. Ancak bu noktada unutulmaması gereken kısım; küçük bir alandayken çözüm gibi görülen durumun zaman içerisinde çözüm için yetersiz olduğu görülebiliyor.  Bu nedenle dikkatli bir şekilde ilerlenmesi gerekiyor.

Greedy Algoritması ve Dinamik Programlama Karşılaştırması

Açgözlü algoritma ve dinamik programlama karşılaştırılması gerçekleştirildiğinde, her iki algoritmanın da sorunlara karşı optimal çözüm için kullanıldığı görülüyor. Ancak her iki algoritmada da birbirinden farklı özellikler yer alıyor. Kullanıcıların bu özelliklere dikkat etmesi ve farkları bildikten sonra uygulamayı gerçekleştirmesi gerekiyor.

Bu iki sık kullanılan algoritma arasındaki ilk fark açgözlü yaklaşımda seçim elemanı tutulması olurken dinamik programlamada ise herhangi bir seçim elemanı bulunmaması oluyor. Seçilen eleman optimal çözümde meydana gelebilecek olan karar değişimini temsil ediyor. Değişkene bakılarak seçim gerçekleştirildikten sonra alt problemlerden başlanılarak çözümler üretiliyor. Dinamik programlamaya bakıldığında ise her bir adımda bir seçim gerçekleştirildiği ve bu seçimler doğrultusunda alt problemlere optimal çözümler eklendiği görülüyor.

Ancak açgözlü yaklaşıma bakıldığında ise bu durumun dinamik programlamanın aksine gelecek adımlara göre bir seçim yapılmadığı ve çözümler üretilmediği görülüyor. Temelde bu şekilde bir dizayn gerçekleştirilmiyor ve her bir adımda bir çözüm üretilmiyor. Dinamik programlamada memoization bazlı konuşma yani  tam anlamıyla bir bottom up stratejisi kullanıldığı görülüyor. Açgözlü yaklaşım ise tam tersine top down stratejisi ile çalışıyor. Açgözlü olan stratejide genellikle değişim her bir adımda artırılıyor ve indirgemeler üzerinden hesaplama gerçekleştiriliyor. Ancak dinamik programlamaya bakıldığında bu programlamada ise bu durumun tam tersinin uygulandığı görülüyor.  Özetlemek gerekirse aç gözlü yaklaşımda top down stratejisi uygulanırken dinamik programlamada  bottom up stratejisi uygulanıyor. Programlama yöntemlerini kullanacak olan kişilerin ise iki programlama türünün arasındaki farkı bilmesi ve bu bilgi doğrultusunda hareket etmesi gerekiyor.