Derinlik Öncelikli Arama Algoritması (DFS)

Derinlik Öncelikli Arama Algoritması (DFS)

Bu algoritmada tıpkı BFS algoritması gibi Sezgisel olmayan bir arama ağacı algoritmasıdır. Ağaca yeni eklenecekler kuyruğun başına yerleştirilir. En derindeki ilerlememiş düğüm ilerletilir. Adı üstünde derinlik önceliklidir. İlerlediğin yoldaki en derin düğüme kadar gidilir eğer düğüm kalmadıysa geri dönülerek uygun yollar seçilir.

Algoritmanın özellikleri;

– Optimal değildir.

– Bütünlük yoktur. Döngülü ağaçlarda sonuca ulaşılamaz.

– En iyi çözüm değildir.

– Algoritmanın performansı O(b^m) dir.

– Bellek gereksinimi çok azdır.

** Tekrarlanan durum veya ziyaret edilmiş durum varsa tekrar yazılmaz.

Bu örnektede görüldüğü gibi derinlik ön plandadır. İzlenecek yol A-B-D-I-J-E-C-F-G-H dir. Aynı örneğin BFS algoritmasına göre sonucu A-B-C-D-E-F-G-H-I-J dir.

İyi çalışmalar..