Budama

Uygunsuz dalları erken keserek zaman kazanmayı öğrenirsin.

Budama

Budama (pruning), uygunsuz dalları erken keserek geri dönüş sayısını azaltır. Backtracking'i hızlandırır.

İyi budama, algoritmayı üsselten polinomsal hale getirebilir; bu yüzden önemlidir.

Budama, arama uzayını küçültür ve pratikte büyük fark yaratır; özellikle N-queens gibi sorunlarda.

Erken kontrol

Budama, adımı atmadan önce yapılan kontroldür. Uygun değilse dal hiç genişletilmez.

N-queens'te aynı sütun ya da çapraz kontrolü buna örnektir; vezir yerleşimi önceden elenir.

Erken kontrol, gereksiz recursion çağrılarını önler ve zaman kazandırır.

Uygulama N-queens say

count_n_queens(n) yaz. n×n tahtada n vezirin birbirini tehdit etmediği yerleşim sayısını backtracking ile bul. print(count_n_queens(4)) ile 2 yazdır.

Örnek çözümü göster

def count_n_queens(n):
    # Vezir say
    def safe(cols, row, col):
        for r in range(row):
            c = cols[r]
            if c == col or abs(c - col) == row - r:
                return False
        return True
    count = 0
    def backtrack(row, cols):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if safe(cols, row, col):
                cols[row] = col
                backtrack(row + 1, cols)
    backtrack(0, [0] * n)
    return count
print(count_n_queens(4))

Kendini test et

Budama: kavramları eşleştir

prune

Buda
early check

Erken kontrol
branch

Dal
feasible

Uygun
Budama ne zaman yapılır?
- Başta
- Adımdan önce
- Sonuçta
- Adımdan sonra
Cevabı göster

Adımdan önce — Adımdan önce.
Budama koşulu
```
if not ____:
```
Cevabı göster
```
if not feasible:
```

Sıradaki ders: Özet - Backtracking

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler