Greedy: Yerel seçim ne zaman doğrudur? | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython örnek paketi ↓

Greedy her adımda yerel en iyi seçimi yapar. Doğruluk için greedy-choice property ve optimal substructure gibi koşulları ispatlamak gerekir. “Mantıklı görünüyor” ispat değildir. Exchange argument, optimal bir çözümün ilk seçimini greedy seçimle değiştirince kötüleşmediğini gösterir; sonra kalan problemde tekrarlanır.

Interval scheduling'de en erken biten işi seçmek maksimum sayıda çakışmayan işi sağlar. En kısa işi veya en erken başlayanı seçmek aynı garantiye sahip değildir. Weighted interval scheduling'de ağırlık toplamı amaç olduğundan aynı greedy kural bozulur, DP gerekir.

Bozuk para greedy her denomination kümesinde doğru değildir: [1,3,4], hedef6 için greedy4+1+1, optimum3+3'tür. Fractional knapsack oranla seçilebilir; 0/1 knapsack bölünemeyen öğelerde bu ispatı kullanamaz. Matroid yapısı, hangi greedy seçimlerin genel optimalite verdiğini formalize eder.

Adım adım iz sürme

İşler [0,3),[1,2),[2,4): en erken biten[1,2), sonra[2,4) seçilir; iki iş. [0,3) ile başlamak bir işte bırakır.

Maliyet ve varsayımlar

Sıralama O(n log n), seçim O(n). İspat, objective ve interval sınırlarına bağlıdır.

Çalıştırılabilir örnek

Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.

Python 3

def schedule(intervals):
    chosen, end = [], float("-inf")
    for start, finish in sorted(intervals, key=lambda x:x[1]):
        if start >= end:
            chosen.append((start,finish)); end=finish
    return chosen
assert len(schedule([(0,3),(1,2),(2,4)])) == 2

KAVRADIĞINI KONTROL ET

Sıra sende

4+1+1 yerine3+3 bulamayan coin greedy'+'’yi nasıl düzeltirsin?

Çözümün mantığını göster

Genel denomination için DP kur: dp[x]=1+min dp[x−coin], başlangıç dp[0]=0. Ulaşılamayanları infinity tut.

Bir adım ileri

Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.

Temel kaynaklar ve ders notları

Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.

Jeff Erickson · Algorithms ↗

İlerlemeden önce alıştırmayı çöz.

RasimAtaberkŞahin