Açgözlü Algoritmalar: Her Adımda "En İyi" Seçeneği Seçmek

Kasiyer ve bozuk para problemi

Bir müşterinize 47 kuruş para üstü vermeniz lazım. Madeni paralar: 25 kuruş, 10 kuruş, 5 kuruş, 1 kuruş. Mümkün olan en az sayıda madeni para kullanarak nasıl ödersiniz?

İçgüdüsel yaklaşım: en büyükten başla.

• 47 → 25 kullan, kalan 22
• 22 → 10 kullan, kalan 12
• 12 → 10 kullan, kalan 2
• 2 → 1 kullan, kalan 1
• 1 → 1 kullan, kalan 0

Toplam 5 madeni para. Bu yaklaşımın matematiksel adı: açgözlü algoritma (greedy algorithm). Her adımda en iyi yerel seçimi yap; ileriyi düşünme.

Türk parası için, ABD doları için, çoğu standart sistemde bu yaklaşım optimal'dir. Ama her zaman değil!

Açgözlü ne zaman başarısız olur

Hayal edin: madeni paralar 1, 7, 10. 15 kuruş vermeniz gerek.

Açgözlü: 10 → 1 → 1 → 1 → 1 → 1 = 6 paralı.
Optimal: 7 + 7 + 1 = 3 paralı.

Açgözlü burada büyük fark atar — 6 yerine 3. Çünkü "10 al" kararı, sonradan çok sayıda 1'e mecbur bıraktı. Daha düşük başlamak (7'den) hesabı kurtarıyordu.

Bu basit örnek açgözlü algoritmaların tehlikesini gösterir: yerel optimum, küresel optimumu garantilemez.

Açgözlü çalışan klasik problemler

Her şeye rağmen pek çok problemde açgözlü harikadır. Klasik örnekler:

1) Etkinlik seçme problemi (activity selection)

Bir günde birçok toplantı var, her birinin başlangıç-bitiş saati biliyor. Çakışmadan en çok kaç toplantıya katılabilirsin?

Açgözlü çözüm: Toplantıları bitiş saatine göre sırala; sırayla seç. Mevcut toplantıyla çakışmayan ilkini her zaman al. Bu yaklaşımın optimal olduğu kanıtlanabilir.

2) Kruskal'ın minimum yayılma ağacı algoritması

Bir grafte en az toplam ağırlıkla tüm düğümleri bağlayan ağaç (MST) bulmak. Açgözlü: kenarları ağırlıklarına göre sırala; sırayla seç (çevrim oluşturmayanı). Optimal.

3) Prim'in MST algoritması

Yine açgözlü. Bir düğümden başla, en hafif kenarı ekleyerek ağı genişlet.

4) Dijkstra'nın en kısa yol algoritması

Açgözlü stratejiyle çalışır: her adımda en yakın düğümü işle. Pozitif ağırlıklarla optimaldir.

5) Huffman kodlama

Verileri sıkıştırmak için harfler/karakterler için en az bit uzunluğunda kod atama. Açgözlü: en az frekanslı iki düğümü birleştir. Bu süreç optimum kodlamayı verir.

6) Kesirli sırt çantası problemi (fractional knapsack)

Bir hırsız sırt çantasını altın, gümüş, vs. parçalardan dolduruyor. Her birim ağırlık başına en yüksek değerli olanı tercih et (kesilebiliyorsa). Açgözlü ile optimal.

Açgözlü ne zaman başarısız olur (devamı)

Ama bazı problemler açgözlüye acımasızdır:

1) 0/1 sırt çantası problemi

Yukarıdaki kesirli versiyonun aksine, parçalar bölünemez — ya alırsın ya bırakırsın. Açgözlü yetersiz; dinamik programlama gerekir.

2) Gezgin satıcı problemi (TSP)

"En yakın komşuyu seç" açgözlü yaklaşımı TSP'de optimal değildir. NP-zor bir problem; açgözlü kötü tahminler verebilir.

3) Renklendirme problemleri (graph coloring)

Bir grafiği en az renkle boyamak için açgözlü yaklaşım (her düğümü mevcut komşularına uymayan en küçük renkle boya) her zaman optimal değildir; sıralamaya bağlı.

"Açgözlü oldu mu kanıtlamalı"

Bir problem için açgözlü algoritma önerirseniz, onun optimum olduğunu kanıtlamak zorundasınız. Standart kanıt teknikleri:

Değiştirme argümanı (exchange argument)

Açgözlü çözüm $G$ ile herhangi bir optimal çözüm $O$'yu karşılaştır. Bir konumda farklıysalar, $O$'nun bir parçasını $G$'ninki ile değiştir; hâlâ optimal kalır. Sonuçta tüm $O$ tıpkı $G$'ye dönüştürülebilir. Bu, $G = O$ veya $G$ de optimal demektir.

Matroid teorisi

Matroid denilen özel cebirsel yapılarda açgözlü her zaman optimaldir. Ağaç teorisi, lineer cebir, kombinatorik optimizasyon — matroid yapısı varsa açgözlü kesin çalışır.

Açgözlü ne zaman güvenle kullanılır

• Greedy choice property (açgözlü seçim özelliği): "Yerel optimum + alt-problemlerin optimumu = küresel optimum."
• Optimal substructure: Optimal çözüm, alt-problemlerin optimal çözümlerini içerir.

Bu iki özellik varsa, açgözlü kazanır. Yoksa dikkat: dinamik programlama, geri izleme (backtracking), brute force gibi alternatifler gerekebilir.

Hayat dersi: "anlık en iyi" ile "uzun vadeli en iyi"

Açgözlü algoritmalar günlük hayata mecazlı bir ders verir: anlık olarak en iyi görünen seçim, her zaman uzun vadede en iyi sonucu vermez.

Kariyer, yatırım, ilişki — bazılarında "şimdi al, sonra düşün" işe yarar; bazılarında felaket olur. Matematiksel olarak: "greedy çalışıyor mu?" sorusu hayatta da geçerli. Cevap kişiye, duruma, problemin yapısına bağlıdır.

Bir kasiyerin parmaklarındaki "önce en büyük" kuralı, bilgisayar biliminin en zarif algoritma stratejilerinden birinin doğum belgesidir. Sade, hızlı, çoğu zaman optimal — ama her zaman dikkatli kullanılmalı.