Açgözlü algoritma nedir ve problem çözümünde nasıl…

Greedy algoritma, her adımda yerel olarak en iyi kararı alan, bunun küresel olarak en iyi çözüme yol açacağı umuduyla kullanılan heuristik bir yaklaşımdır.

Uygulamalar:

Aktivite Seçim Problemi:

Problem: Verilen bir kümeden zaman açısından çakışmayan maksimum aktivite sayısını seçmek.
Greedy çözüm: Aktivite bitiş zamanına göre artan sıralama yapın. Her adımda, daha önce seçilenlerle çakışmayan en küçük bitiş zamanına sahip aktiviteyi seçin.

# Aktivite Seçimi örneği
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Bitiş zamanına göre sıralama

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Para Bozdurma Problemi (Coin Change Problem) kanonik madeni para setleri için:
- Problem: Belirli bir toplamı en az sayıda madeni para kullanarak ödemek.
- Greedy çözüm: En büyük nominaldeki madeni parayı mümkün olan en fazla kullanın, toplam ödenene kadar. Sadece belirli madeni para setleri için çalışır (örneğin, 1, 5, 10, 25).
```
# Para bozdurma örneği (kanonik madeni paralar için)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Kruskal algoritması ile en küçük yayılım ağacı (Minimum Spanning Tree):
- Problem: Bağlantılı, ağırlıklı, yönsüz bir grafikte, tüm düğümleri en düşük toplam ağırlıkla bağlayan kenar kümesini bulmak.
- Greedy çözüm: Tüm kenarları ağırlıklarına göre artan sırayla sıralayın. Daha sonra, döngü oluşturmayan kenarları seçerek, n-1 kenar eklenene kadar devam edin (n, düğüm sayısıdır).

Greedy algoritmalar kolayca uygulanabilir, ancak her zaman rastgele problemlerde küresel olarak en iyi çözümü bulmazlar. Bazı problemler (örneğin, herhangi bir madeni para setiyle bozuk para problemi, genel sırt çantası problemi) için greedy yaklaşım optimal değildir. Optimalliği veya daha iyi bir yaklaşımı garanti etmek için dinamik programlama veya diğer yöntemler gerekebilir. Greedy algoritma uygulanmadan önce, uygun olup olmadığını doğrulamak önemlidir.

Açgözlü algoritma nedir ve problem çözümünde nasıl kullanılır?