İçeriğe geç

Karar ağacı

Ders 1 / 5 · 5 dk

Karar ağacı

Adım 1/8

Her backtracking problemi bu ağaçtır. Kök boş yol; her seviye bir harf daha seçer.

Fikir

Backtracking, hiç kurmadığın bir ağaç üzerinde derinlik öncelikli arama (DFS) yapmaktır. Her düğüm (node) kısmi bir cevap, her kenar bir seçim, her yaprak da tamamlanmış bir adaydır.

Döngü hep aynı üç hamleden oluşur: bir seçimi yola push et, onu uzatmak için özyinelemeli çağır, sonra pop et. Bütün numara o pop'ta: yolu eski haline getirir, böylece sonraki seçenek tam olarak aynı durumdan başlar. Tek bir listenin bütün aramaya yetmesinin sebebi bu.

Gerçek hayattan örnek

Kilitli birkaç kapısı olan bir binada, etiketsiz anahtarlarla dolu bir halkadan anahtar denediğini düşün. Bir anahtar alıp daha içeri yürürsün; bir kapı açılmazsa sıradakini denemeden önce o anahtarı halkaya geri takarsın. Yoksa sonraki her denemede halka yanlış olur.

Kod

Sıra sende

Bu kod ne yazdırır?

out = []
walk(["a", "b"], [], out)
print(out)

Mini quiz

1 / 3

Her backtracking döngüsünün üç hamlesi nedir?