Durum ağacı

Çözümleri bir ağaçta dallandırarak gezmeyi öğrenirsin.

Durum ağacı

Backtracking, çözümleri bir ağaçta dallandırarak gezer. Her düğüm bir kısmı çözüm, her dal bir seçimdir.

Yapraklar tam çözümdür; iç düğümler ara durumlardır ve budama burada yapılır.

Durum ağacı, çözüm uzayını görselleştirmeyi sağlar; budama ile dallar erken kesilir.

Permütasyon örneği

Bir dizinin tüm permütasyonları, durum ağacında her seviyede kullanılmamış bir eleman seçilerek üretilir.

n elemanlı dizi için n! yaprak vardır; her biri farklı bir sıralama verir.

Permütasyon üretimi, backtrackingin en bilinen uygulamalarından biridir.

Uygulama Permütasyon üret

perms(arr) yaz. Backtracking ile bir dizinin tüm permütasyonlarını üret. print(perms([1, 2])) ile [[1, 2], [2, 1]] yazdır.

Örnek çözümü göster

def perms(arr):
    # Permütasyon üret
    result = []
    def backtrack(path, used):
        if len(path) == len(arr):
            result.append(list(path))
            return
        for i in range(len(arr)):
            if not used[i]:
                used[i] = True
                path.append(arr[i])
                backtrack(path, used)
                path.pop()
                used[i] = False
    backtrack([], [False] * len(arr))
    return result
print(perms([1, 2]))

Kendini test et

Seçim ekleme
```
path.____(arr[i])
```
Cevabı göster
```
path.append(arr[i])
```
Durum ağacı: kavramları eşleştir

tree

Ağaç
node

Kısmı çözüm
leaf

Tam çözüm
branch

Seçim
Durum ağacında bir yaprak neyi temsil eder?
- Tam çözüm
- Kısmı çözüm
- Başlangıç
- Budama
Cevabı göster

Tam çözüm — Tam çözüm.

Sıradaki ders: Budama

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler