Açgözlü Algoritmalar
Açgözlü (Greedy) algoritmalar, her adımda en iyi görünen seçimi yaparak global optimum çözüm arayan problem çözme yaklaşımıdır.
Fractional Knapsack
Nesneleri ağırlık/değer oranına göre sıralayarak çantaya yerleştiren, nesnelerin bölünebilir olduğu çanta problemi çözümü.
Huffman Coding
Karakterlerin frekanslarına göre değişken uzunluklu kodlar atayan, veri sıkıştırma için kullanılan algoritma.
Açgözlü Algoritmalar Hakkında
Açgözlü algoritmalar, optimizasyon problemlerini çözmek için kullanılan bir algoritma tasarım yaklaşımıdır. Bu yaklaşımda, algoritma her adımda mevcut durumda en iyi görünen seçimi yapar, gelecekteki sonuçları dikkate almadan ilerler. Bu nedenle "açgözlü" (greedy) olarak adlandırılır.
Açgözlü algoritmaların temel özellikleri:
- Yerel Optimizasyon: Her adımda mevcut durumda en iyi görünen seçimi yapar.
- Geriye Dönüş Yok: Bir kez karar verildikten sonra, bu karar değiştirilmez.
- Basitlik: Genellikle anlaşılması ve uygulanması kolaydır.
- Verimlilik: Çoğu durumda çok hızlı çalışır, genellikle O(n log n) veya daha iyi.
Açgözlü algoritmaların başarılı olması için gereken koşullar:
- Açgözlü Seçim Özelliği: Yerel optimum seçimler, global optimum çözüme yol açmalıdır.
- Optimal Alt Yapı: Problemin optimal çözümü, alt problemlerin optimal çözümlerini içermelidir.
Açgözlü algoritmaların her zaman optimal çözümü garanti etmediğini unutmamak önemlidir. Bazı durumlarda, yerel optimum kararlar, global optimum çözüme ulaşmayı engelleyebilir. Ancak, belirli problem türlerinde açgözlü yaklaşım optimal sonuç verir.
Açgözlü algoritmaların kullanıldığı yaygın problemler:
- Minimum Yayılma Ağacı (Kruskal ve Prim algoritmaları)
- Huffman Kodlama (veri sıkıştırma)
- Dijkstra En Kısa Yol Algoritması
- Kesirli Sırt Çantası Problemi (Fractional Knapsack)
- Etkinlik Seçim Problemi (Activity Selection)
- Para Üstü Problemi (Coin Change Problem - bazı durumlarda)
Açgözlü algoritmalar, dinamik programlama veya geri izleme gibi diğer yaklaşımlara göre genellikle daha hızlı ve daha az bellek kullanır. Ancak, her problem için uygun olmayabilir ve bazen alt-optimal sonuçlar üretebilir. Bu nedenle, problemi dikkatli bir şekilde analiz etmek ve açgözlü yaklaşımın uygun olup olmadığını belirlemek önemlidir.