Backtracking nedir?

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.

Örnek çözümü göster

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]))

Kendini test et

Backtracking ne zaman geri döner?
- Her adımda
- Adım uygun değilse
- Hiçbir zaman
- Sadece başta
Cevabı göster

Adım uygun değilse — Adım uygun değilse.
Recursion tabanı
```
if len(path) == ____:
```
Cevabı göster
```
if len(path) == n:
```
Backtracking nedir: kavramları eşleştir

backtrack

Geri dön
try

Dene
undo

Geri al
prune

Buda

Sıradaki ders: Durum ağacı

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler