Backtracking, pruning ve branch-and-bound | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython örnek paketi ↓

Backtracking kısmi çözüm kurar, geçerli aday seçer, alt aramaya iner ve değişiklikleri geri alır. Choose→explore→unchoose kuralı, komşu dalların birbirini kirletmesini önler. N-queens sütun ve iki diagonal kümesiyle tehdit kontrolü yapar; Sudoku en az adaylı hücreyi önce seçerek dallanmayı azaltabilir.

Pruning yalnız hiçbir geçerli/iyi çözümün kalmadığını gerekçelendirebildiğinde güvenlidir. Branch-and-bound optimizasyonda mevcut en iyi cevaba göre umut verici alt/üst sınır kullanır. Heuristic dal sırasını değiştirir; yanlış bound optimumu kaybettirir. Alpha-beta adversarial minimax ağacını budar, her backtracking problemi aynı değildir.

Çıktı sayısı üstel ise bütün sonuçları üretmek de üstel iş gerektirir. Generator tepe belleğini azaltabilir ama toplam zaman sınırını ortadan kaldırmaz. Tekrarlı girdide duplicate branches'i kontrol et; early return kullanırken shared state'i temizlemeyi unutma.

Adım adım iz sürme

Alt kümeler [1,2]: []→[1]→[1,2], geri dön→[2]. Geri almazsan ikinci dal önceki1'+'’i yanlış taşır.

Maliyet ve varsayımlar

Alt küme2ⁿ, permütasyon n!. Yaprakta kopyalama varsa çıktı boyutu da çarpılı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 subsets(a):
    out, path = [], []
    def visit(i):
        if i == len(a): out.append(path.copy()); return
        visit(i+1)
        path.append(a[i]); visit(i+1); path.pop()
    visit(0)
    return out
assert len(subsets([1,2,3])) == 8

KAVRADIĞINI KONTROL ET

Sıra sende

out.append(path) neden hatalı?

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

Aynı mutable liste referansı bütün sonuçlara eklenir. Sonraki pop işlemleri eski çıktıları değiştirir. Snapshot için copy gerekir.

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