Özet - Backtracking
- Algoritmalar kursu
- Orta seviye
- Ders 72/80
- 4 dk
N-queens tarzı mini görevle backtracking'i pekiştirirsin.
Özet - Backtracking
Backtracking; deneme-yanılma, durum ağacı ve budama ile çözüm arar. N-queens, permütasyon ve alt küme toplamı buna örnektir.
Bu mini görevde alt küme toplamı problemini çözeceksin; tüm adımları birleştir.
Backtracking, çözüm uzayını sistemle gezdiği için kısıtlı problemlerde güçlü bir araçtır.
Uygulama Alt küme toplamı
subset_sum(arr, target) yaz. Backtracking ile bir alt kümenin toplamı target'a eşit mi kontrol et. print(subset_sum([3, 34, 4, 12, 5, 2], 9)) ile True yazdır.
Başlangıç kodu
def subset_sum(arr, target):
# Alt küme toplamı var mıÖrnek çözüm
def subset_sum(arr, target):
# Alt küme toplamı var mı
def backtrack(i, total):
if total == target:
return True
if i >= len(arr) or total > target:
return False
if backtrack(i + 1, total + arr[i]):
return True
if backtrack(i + 1, total):
return True
return False
return backtrack(0, 0)
print(subset_sum([3, 34, 4, 12, 5, 2], 9))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Backtracking: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
backtrack |
Geri dön |
prune |
Buda |
try |
Dene |
undo |
Geri al |
2 Geri alma
Soru
path.____()
Cevap
path.pop()Açıklama: pop doğru.
3 Backtracking ne zaman 'undo' yapar?
- Hiçbir zaman
- Her adımda
- Sadece başta
- Derinleşme başarısız olunca Doğru cevap
Açıklama: Derinleşme başarısız olunca.