Açgözlü algoritma nedir ve hangi durumlarda kullanılır?

Ağırlıklı algoritma, her adımda en iyi yerel çözümü (mevcut an açısından en avantajlı seçeneği) seçen ve bu dizinin küresel olarak en iyi çözüme yol açacağı umuduyla kullanılan bir optimizasyon yaklaşımıdır. Bu, mevcut seçimin gelecekteki adımlar üzerindeki olası sonuçlarını dikkate almaz.

Özellikler:

• Basitlik: Genellikle dinamik programlama veya diğer optimizasyon yöntemlerinden daha kolay uygulanabilir.
• Hız: Genellikle daha düşük hesaplama karmaşıklığına sahiptir.
• Optimalite garantisi: Her zaman küresel olarak en iyi çözümü bulduğunu garanti etmez. Sadece belirli problem sınıfları için garanti sağlar.

Her adımda yerel olarak en iyi seçimi yapmanın küresel olarak en iyi çözüme götürdüğü gösterilen problemlerde kullanılır. Örnekler:

• Aktivite Seçim Problemi: Zaman açısından çakışmayan en fazla aktiviteyi seçmek.
• Sırt çantası problemi (öğelerin bölünebilirliği ile): Öğeler bölünebiliyorsa. Aksi takdirde, bu dinamik programlama problemidir.
• Prim ve Kruskal algoritmaları: Bir grafikte minimum yayılım ağacı bulmak için.
• Dijkstra algoritması: Negatif olmayan kenar ağırlıklarıyla en kısa yolu bulmak için.
• Huffman kodlaması: Optimum ön ek kodu oluşturmak için.

Aktivite seçim algoritması için pseudocode örneği:

Fonksiyon SeçAktiviteleri(aktivite):
  Aktiviteyi bitiş zamanına göre sırala
  seçilen_aktivite = boş liste
  son_bitis_zamanı = 0

  Her aktivite için:
    Eğer aktivite.start_time >= son_bitis_zamanı ise:
      Aktiviteyi seçilenlere ekle
      son_bitis_zamanı = aktivite.finish_time

  Döndür seçilen_aktivite

Greedy algoritmasının belirli bir probleme uygulanabilir olup olmadığını kontrol etmek önemlidir, çünkü aksi takdirde alt-optimal bir çözüm verebilir.