Durum ağacı
- Algoritmalar kursu
- Orta seviye
- Ders 70/80
- 4 dk
Çö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.
Başlangıç kodu
def perms(arr):
# Permütasyon üretÖrnek çözüm
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]))Beklenen çıktı
[[1, 2], [2, 1]]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Seçim ekleme
path.____(arr[i])path.append(arr[i])Açıklama: append doğru.
2 Durum ağacı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
tree |
Ağaç |
node |
Kısmı çözüm |
leaf |
Tam çözüm |
branch |
Seçim |
3 Durum ağacında bir yaprak neyi temsil eder?
- Tam çözüm Doğru cevap
- Kısmı çözüm
- Başlangıç
- Budama
Açıklama: Tam çözüm.