Açgözlü Algoritma ( Greedy Algorithm ) - 2

Açgözlü algoritmalar optimizasyon problemleri için kullanılır. Her adımda, şu anda en iyi görünen bir seçim yapabiliriz ve tüm problemin optimal çözümünü elde ederiz.
Özel DP Problemleri için Açgözlü Algoritmalar

Kesirli Sırt Çantası Problemi(Fractional Knapsack Problem)
Coin Exchange Problem

Kesirli Sırt Çantası Problemi

Kesirli Sırt Çantası (knapsack) Problemi

Bir çantamız var ve bu çantanın içine belirli bir miktarda ürün konulabiliyor.

Örneğin; limiti 100 olan 50, 40, 30, 20 limitlik ürünler var. Bir de bu ürünlerin değerleri var. Ürünler sırasıyla 80, 70, 30, 10 lira değerindedirler.

1. Adım: Birim değerleri hesaplanır.

80/50=1.6 70/40=1.75 30/30=1 10/20=0.5

2.Adım: İlk olarak değeri en yüksek olan alınır. Kalan yerlere sırasıyla yüksekten küçüğe yerleştirilir.

40 ve 50 birimlik ürünler alındığında 100 birimlik limit aşılmadan tamamlanmış olur.

Para Üstü Problemi (Coin Changing Problem)

Örneğin para üzeri verilmesi için açgözlü yaklaşımının kullanılmasını düşünelim. Bu problemde bir satıcı kendisinden alışveriş yapan kişiye para üzeri vermektedir. Ödenmesi gereken miktar bu örnekte 24 olsun ve para birimlerimiz 20, 19, 5, 1 olsun.

Açgözlü yaklaşımına göre satıcı 24’ü tamamlamak için elindeki para birimlerinden sonuca en çok yaklaştıran 20lik birimi seçecektir. Daha sonra geriye kalan boşluğu (24-20=4) doldurmak için elindeki tek imkan olan 4 tane 1lik birimle dolduracaktır ve toplamda 5 adet bozuk parayı müşteriye geri verecektir. Oysaki aynı problem bir 19luk bir de 5lik bozuk paralar ile çözülerek 2 bozuk para vermek mümkün olabilirdi.

Bu da aç gözlü yaklaşımın zafiyetini oluşturuyor. İlk görülen sonuç seçilince daha iyi sonuçların görülmesi engelleniyor. Bu tür Doğrusal Programlama problemlerinde verimli çalışmayan Greedy(Açgözlü) Algoritmalar Graflarda son derece iyi sonuçlar vermektedir.