Açgözlü algoritmalar nedir ve ne zaman çalışır?

Question

Accepted Answer

**Açgözlü algoritma**, her adımda **yerel olarak optimal seçimi** yapar ve bunun global optimuma yol açacağını umar. Basit ve hızlıdır, ancak yalnızca problem **açgözlü seçim özelliğine** ve **optimal alt yapıya** sahip olduğunda doğrudur.

## Fikir

Geçmiş seçimleri asla yeniden düşünme — en iyi anlık seçeneğe bağlı kal ve devam et.

## Örnek: kanonik madeni paralarla sikke değiş tokuş

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

Bu, ABD madeni paraları için optimaldir, ancak {1, 3, 4} gibi kümeler için **başarısız olur** (açgözlü 6 için 3+3 yerine 4+1+1 verir).

## Açgözlü ne zaman çalışır

- **Optimal alt yapı:** optimal bir çözüm optimal alt çözümleri içerir.
- **Açgözlü seçim özelliği:** yerel optimum, global optimumun bir parçasıdır.

Çalışan örnekler: Dijkstra, Kruskal/Prim (MST), Huffman kodlaması, aralık planlama.

## Karmaşıklık

Genellikle hızlı — sıralamadan sonra sıklıkla O(n log n).

## Tuzaklar

Açgözlü **her zaman doğru değildir**. Açgözlü seçim özelliğini kanıtla veya buna güvenmeden önce brute-force/DP temeli karşısında test et.

## Neden önemli

Açgözlü geçerli olduğunda, DP veya brute force'tan çok daha basit ve daha hızlıdır.

Ne zaman geçerli olduğunu bilmek — ve ne zaman sessizce yanlış cevaplar verdiğini — algoritmik olgunluğun bir işaretidir.

Birçok temel grafik algoritması kalbi itibariyle açgözlüdür.