Backtracking nedir?
- Algoritmalar kursu
- Orta seviye
- Ders 69/80
- 4 dk
Deneme-yanılma ile çözüm arayan yöntemi öğrenirsin.
Backtracking nedir?
Backtracking, deneme-yanılma ile çözüm arar. Uygun olmayan adımda geri döner, başka yol dener.
Çözüm uzayını bir ağaç gibi gezer; budama ile hız kazanır ve gereksiz dalları keser.
Backtracking, N-queens, sudoku ve labirent çözümünde sıkça kullanılır; esnek yapısı sayesinde.
Deneme-yanılma
Backtracking bir adım atar, ilerleyebiliyor mu diye kontrol eder. Olumluysa derinleşir; olumsuzsa geri döner.
Bu, recursion ile doğal olarak uygulanır; her çağrı bir adımdır.
Recursion sayesinde geri izleme otomatik olur; çağrı yığını durumu saklar.
Uygulama Alt küme üret
subsets(arr) yaz. Backtracking ile bir dizinin tüm alt kümelerini üret. print(subsets([1, 2])) ile [[], [1], [2], [1, 2]] yazdır.
Başlangıç kodu
def subsets(arr):
# Alt kümeleri üretÖrnek çözüm
def subsets(arr):
# Alt kümeleri üret
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets([1, 2]))Beklenen çıktı
[[], [1], [2], [1, 2]]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Backtracking ne zaman geri döner?
- Her adımda
- Adım uygun değilse Doğru cevap
- Hiçbir zaman
- Sadece başta
Açıklama: Adım uygun değilse.
2 Recursion tabanı
if len(path) == ____:if len(path) == n:Açıklama: n doğru.
3 Backtracking nedir: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
backtrack |
Geri dön |
try |
Dene |
undo |
Geri al |
prune |
Buda |