Açgözlü algoritmalar: etkinlik seçimi, kesirli sırt çantası, para üstü

Greedy (açgözlü) algoritma her adımda o an en iyi görünen seçimi yapar ve bir daha o seçimi sorgulamaz. Geri dönüş yok, tüm olasılıkları deneme yok. Bu yüzden hızlıdır ve kodu kısadır. Sorun şu: her problemde doğru cevap vermez. Sınavda iki tip soru gelir. Biri “greedy’yi çalıştır, sonucu yaz” (etkinlik listesi, çanta değeri, madeni paralar). Diğeri “bu greedy kural yanlış, karşı örnek ver”.

Altın kurallar:

1. Greedy = yerel en iyi seçim, geri dönüş yok.
2. Doğru olması için iki özellik lazım: greedy-choice property ve optimal substructure.
3. Yanlışlığını göstermek için tek karşı örnek yeter. Küçük, 2-3 elemanlı örnek kur.
4. Etkinlik seçiminde ölçüt bitiş zamanıdır, başlangıç ya da süre değil.
5. Bölünebilen şeyde (kesirli) greedy çalışır, bölünemeyen 0/1’de çalışmaz.

Greedy ne zaman doğrudur?

İki özellik birlikte varsa greedy optimum verir:

• Greedy-choice property: En iyi görünen ilk seçimi içeren bir optimum çözüm her zaman vardır. Yani ilk adımda greedy seçim yapmak seni optimumdan uzaklaştırmaz.
• Optimal substructure: İlk seçimden sonra geriye kalan problem aynı türden daha küçük bir problemdir ve onun optimum çözümü, ilk seçimle birleşince bütünün optimumunu verir.

Bunu kanıtlamanın standart yolu değiştirme argümanıdır (exchange argument): herhangi bir optimum çözüm al, ilk elemanını greedy seçimle değiştir, çözümün hâlâ geçerli ve aynı iyilikte olduğunu göster.

Dinamik programlama (DP) ile fark: DP her alt problemin tüm seçeneklerini dener ve tabloya yazar. Greedy sadece birini seçer. DP daha güvenli, greedy daha hızlı.

Etkinlik seçimi (activity selection)

Bir salon var, her etkinliğin başlangıç ve bitiş zamanı belli. Çakışmayan en çok sayıda etkinliği seç. Bir etkinlik, öncekinin bittiği anda başlayabilir.

Greedy kural: Etkinlikleri bitiş zamanına göre sırala. En erken biteni al. Sonra başlangıcı son seçilenin bitişinden önce olmayan ilk etkinliği al. Böyle devam et.

Örnek: a(1,3), b(2,5), c(4,6), d(6,8), e(5,9), f(7,10), g(9,11), h(10,12), i(11,13).

zaman  0123456789012345
a  1-3  ==
b  2-5   ===
c  4-6     ==
d  6-8       ==
e  5-9      ====
f  7-10       ===
g  9-11         ==
h 10-12          ==
i 11-13           ==

etkinlik  başlangıç  sonBitiş  karar
a(1,3)    1 >= -∞     -∞      AL, son=3
b(2,5)    2 <  3      3       atla
c(4,6)    4 >= 3      3       AL, son=6
d(6,8)    6 >= 6      6       AL, son=8
e(5,9)    5 <  8      8       atla
f(7,10)   7 <  8      8       atla
g(9,11)   9 >= 8      8       AL, son=11
h(10,12)  10 < 11     11      atla
i(11,13)  11 >= 11    11      AL, son=13

earliest finish: [a(1,3), c(4,6), d(6,8), g(9,11), i(11,13)]
optimum count (brute force): 5

Neden doğru? En erken biten etkinlik, salonu en erken boşaltır. Optimum bir çözümün ilk etkinliğini onunla değiştirirsen hiçbir çakışma doğmaz (o daha erken ya da aynı anda bitiyor). Kalan problem “son bitişten sonra başlayanlar” alt problemi.

Yanlış kurallar ve karşı örnekleri

earliest start picks [p] vs finish [q(1,4), r(5,8)]
shortest picks [y] vs finish [x(0,5), z(6,11)]

TUZAK · “sınır” koşulu. Soruda “an activity may start when the previous one finishes” diyorsa karşılaştırma >=, demiyorsa >. d(6,8) bu yüzden c(4,6)‘dan sonra alınabildi.

Sırt çantası problemi (knapsack)

Kapasitesi W olan bir çanta ve her birinin ağırlığı ($w_i$) ve değeri ($v_i$) olan eşyalar var. Toplam değeri en büyük yap.

Örnek eşyalar: A(6 kg, 30), B(10 kg, 40), C(4 kg, 28), D(8 kg, 24). Kapasite 15.

Kesirli (fractional): greedy optimum

Eşyayı bölebiliyorsan (un, altın tozu gibi) kilo başına değeri en yüksek olandan başla, sığdığı kadar al, son eşyayı böl.

  take 4/4 of C (ratio 7.0) total=28.0
  take 6/6 of A (ratio 5.0) total=58.0
  take 5/10 of B (ratio 4.0) total=78.0
fractional value 78.0

Neden doğru? Çantadaki her kilo, en pahalı kilo ile doldurulmalı. Daha düşük oranlı bir kiloyu daha yüksek oranlı bir kiloyla değiştirmek her zaman değeri artırır.

0/1: greedy çöker

Eşyayı bölemiyorsan aynı kural yanlış sonuç verir:

  greedy 0/1 picks C A value 58
  optimal 0/1 picks B C value 68

C ve A’yı aldıktan sonra 5 kg boş kaldı ama B ve D sığmıyor. Kapasitenin bir kısmı boşa gitti. B + C ise 14 kg ile 68 yapıyor. 0/1 sırt çantası DP ile $O(nW)$ sürede çözülür (bu derste DP’ye girmiyoruz; greedy’nin neden çöktüğünü bilmen yeter).

TUZAK · oranı int bölmeyle hesaplama. v[i] / w[i] iki int ise 7/2 gibi değerler kesilir ve sıralama bozulur. (double) v[i] / w[i] yaz.

Para üstü (coin change)

Bir tutarı en az sayıda madeni parayla öde. Greedy kural: her adımda tutara sığan en büyük madeni parayı ver.

Madeni paralar {25, 10, 5, 1}, tutar 68:

kalan  verilen
68     25
43     25
18     10
 8      5
 3      1
 2      1
 1      1
 0      → 7 madeni para

Bu tür “standart” sistemlerde (25-10-5-1, ya da 50-20-10-5-1) greedy optimumdur. Ama her sistemde değil:

{1,4,6} 8 greedy [6, 1, 1] dp 2
{1,7,10} 14 greedy [10, 1, 1, 1, 1] dp 2

8 için 4 + 4 iki madeni para; greedy 6’yı kaptığı için kalan 2’yi 1’lerle ödemek zorunda kaldı. 14 için 7 + 7 yerine 10 + 1 + 1 + 1 + 1 verdi. Genel çözüm DP:

$dp[0] = 0,\qquad dp[a] = \min_{c \le a} \big(dp[a-c] + 1\big)$

Sınavda greedy sorusu nasıl çözülür?

Üç tip soru için üç kalıp:

"Run the greedy":
  ölçütü yaz (bitiş, oran, büyük para)
  sırala, tabloyla tek tek karar ver
"Is greedy optimal?":
  2-3 elemanlı karşı örnek ara
  bulamazsan değiştirme argümanı kur
"Write the method":
  indeksleri ölçüte göre sırala
  tek döngü, koşul tutuyorsa al

Karşı örnek ararken şu soruyu sor: “Greedy’nin ilk seçimi, daha iyi iki seçimi birden engelleyebilir mi?” Etkinlik seçiminde uzun ve erken başlayan bir etkinlik, para üstünde tutarı garip bir kalana bırakan büyük bir madeni para, 0/1 çantada boşluk bırakan küçük ama oranı yüksek bir eşya bu rolü oynar. Kesirli çantada ve “en erken biten” kuralında böyle bir engel kurulamaz; bu yüzden onlar doğrudur.

Greedy algoritmalar bu derste nerede?

Hepsinin doğruluğu, yukarıdaki iki özelliğin o problem için kanıtlanmasına dayanır. Dijkstra’nın negatif kenarda çökmesi de greedy-choice property’nin bozulmasıdır.

Sık yapılan hatalar

static int maxActivities(int[] s, int[] f) {
    int n = s.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> Integer.compare(f[a], f[b]));
    int count = 0, lastFinish = Integer.MIN_VALUE;
    for (int i : idx) {
        if (s[i] >= lastFinish) {
            count++;
            lastFinish = f[i];
        }
    }
    return count;
}

static double fractionalKnapsack(int[] w, int[] v, int cap) {
    int n = w.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> Double.compare((double) v[b] / w[b], (double) v[a] / w[a]));
    double total = 0;
    int left = cap;
    for (int i : idx) {
        if (left == 0) break;
        int take = Math.min(left, w[i]);
        total += (double) v[i] * take / w[i];
        left -= take;
    }
    return total;
}