Budama
- Algoritmalar kursu
- Orta seviye
- Ders 71/80
- 4 dk
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.
Başlangıç kodu
def count_n_queens(n):
# Vezir sayÖrnek çözüm
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))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Budama: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
prune |
Buda |
early check |
Erken kontrol |
branch |
Dal |
feasible |
Uygun |
2 Budama ne zaman yapılır?
- Başta
- Adımdan önce Doğru cevap
- Sonuçta
- Adımdan sonra
Açıklama: Adımdan önce.
3 Budama koşulu
if not ____:if not feasible:Açıklama: feasible doğru.