DAA - Açgözlü Yöntem

Tüm algoritmik yaklaşımlar arasında en basit ve anlaşılır yaklaşım Greedy yöntemidir. Bu yaklaşımda, karar, mevcut kararın gelecekteki etkisinden endişe edilmeksizin mevcut mevcut bilgiler temelinde alınır.

Açgözlü algoritmalar, bir sonraki parçayı anında fayda sağlayacak şekilde seçerek parça parça bir çözüm oluşturur. Bu yaklaşım, daha önce alınan seçimleri asla yeniden değerlendirmez. Bu yaklaşım esas olarak optimizasyon problemlerini çözmek için kullanılır. Açgözlü yöntemin uygulanması kolaydır ve çoğu durumda oldukça etkilidir. Dolayısıyla, Greedy algoritmasının, global optimal çözümü bulma umuduyla her adımda yerel optimal seçimi takip eden sezgiselliğe dayalı bir algoritmik paradigma olduğunu söyleyebiliriz.

Pek çok problemde, makul bir sürede yaklaşık (optimuma yakın) bir çözüm verse de optimal bir çözüm üretmez.

Açgözlü Algoritmanın Bileşenleri

Açgözlü algoritmalar aşağıdaki beş bileşene sahiptir -

A candidate set - Bu setten bir çözüm oluşturulur.
A selection function - Çözüme eklenecek en iyi adayı seçmek için kullanılır.
A feasibility function - Bir adayın çözüme katkıda bulunmak için kullanılıp kullanılamayacağını belirlemek için kullanılır.
An objective function - Bir çözüme veya kısmi çözüme bir değer atamak için kullanılır.
A solution function - Tam bir çözüme ulaşılıp ulaşılmadığını belirtmek için kullanılır.

Uygulama alanları

Açgözlü yaklaşım, birçok sorunu çözmek için kullanılır.

Dijkstra algoritmasını kullanarak iki köşe arasındaki en kısa yolu bulmak.
Prim / Kruskal algoritması vb. Kullanarak bir grafikte minimum yayılma ağacını bulmak.

Açgözlü Yaklaşım Başarısız Olduğunda

Pek çok problemde, Greedy algoritması en uygun çözümü bulamaz, üstelik en kötü çözümü de üretebilir. Seyahat Eden Satıcı ve Sırt Çantası gibi sorunlar bu yaklaşım kullanılarak çözülemez.