Depth First Search(DFS) Algoritması
Algoritma, yapay zeka, veri yapıları , algoritma analizinde ve bir çok yerde çokça kullanılıyor.
Genelde ağaçlar üzerinde anlatılıyor ve ağaç dolaşma algoritması kategorisinde yer alıyor.
Temelde ilk önce alt seviyesinde bulunan komşuların aranması durumudur.
Yukarıdaki grafın en tepesinde bulunan düğüm root kabul edilir ve root dan başlayarak ağacı dolaşmamız gerekir.Algoritmanın en temel özellikleri mümkün olan en derin düğüm inmek gerekir.Burada dikkat edilmesi gereken nokta grafın özel bir ağaç türün olmaması gerektiğidir.Örneğin binary tree bir grafta arama yapılacaksa soldan başlayarak istenilen key bulunduğunda sağ dal da herhangi bir işlem yapmadan bırakabiliyorduk fakat burada istenilen bu değil.Burada istenilen temel kural gidebildiğimiz kadar derine gitmemizdir.
Öncelikle bir görsel üzerinde algoritma adımlarını anlatmaya çalışalım.Yandaki görselde 5 nolu düğüm root olarak kabul edelim.Birinci adımda 5 -7-3 nolu düğümleri geziyoruz ve gideceğimiz en derin nokta olan 3 nolu düğüm de duruyoruz.
Tabi burada çeşitli ihtimaller olabilir.Örneğin ;
LRN : Left Right Node (Sol Sağ Düğüm)
RLN : Right Left Node (Sağ Sol Düğüm)
RNL : Right Node Left (Sağ Düğüm Sol)
RLN : Right Left Node (Sağ Sol Düğüm)
Yani öncelikle düğüm sonra altındaki üyelere hareket edilir.Genelde Kitaplarda soldan başlatıldığı için biz literatürü bozmamak istedik.Kısacası en derin olan düğümün sağ ve sol düğümlerindeki değerler null olmalı.Bu şartı sağlayan en derin düğümün değerine bakıyoruz yani değerine bakılacak düğüm en derin düğüm olmalı bunu giderken yapmıyoruz.En derin bulduğumuz düğüm değerine bakıyoruz. Yani yukarıdaki görselde 5-7-3 nolu düğümleri gezdikten sonra 3 nolu düğümde durduk ve değerine baktık daha sonra 7 nolu düğüme bakıyoruz ve 7 Nolu düğümün çocuğunun olduğunu görüyoruz ve 7 nolu düğümün değerine bakmadan çocuğuna iniyoruz ve onun sağ ve sol çocukları null ise onun değerini alıyoruz.Daha fazla karıştırmadan buraya kadar değerine baktığımız düğümleri sırayla yazacak olursak. 3-2-7 şeklinde 3 adet düğüm bakmış olduk.Devamında ise en son 7 nolu düğümün değerine bakmıştık bunun üst düğümüne gidiyoruz 5 nolu düğüm, bu düğümün çocukları varmı diye bakıyoruz, evet var , çocuğuna iniyoruz 8 bu düğümün çocuğu varmı diyerek işlemlere devam ediyoruz.Günün sonunda ise değerine baktığımız düğümleri sırayla yazacak olursak,3,2,7,1,9,8,5 şeklinde olacaktır.
Yukarıdaki romanya haritasını incelediğimizde Arac şehrinden Bucharest şehrine gitmek istiyoruz.Burada tasarımı bağlı olarak en ağırlık yolu seçmek bizim yazımız için uygun olacaktır.
A =118> T
A => 50>S
A =75> Z
Şeklinde bir graf tasarlarken istediğimiz B node gitmek için oluşacak olan grafda bir döngü söz konusu olacaktır.Buda senaryoya bağlı olarak istenmeyen bir durumdur.Şimdi S düğümünden gidilebilecek olan yolları belirlediğimizde;
S=151>O
S=99>F
S=80>R
F=211>B(Gidilecek Şehir)
Şeklinde bir harita çizmiş oluruz burada a düğümünü yazmamızın sebebi sonsuz döngüye girmemektir.Bunun için gidilen düğümleri tuttuğumuz bir buffer tasarlamamız uygun olacaktır.
Burada riskli gördüğümüz senaryo s den a düğümüne gitmektir.Çünkü bu yolda bir receivers olmak ihtimali yüksektir.Bu sebeple a düğümünü s visited bufferından tutuyoruz. S yolunda a düğümünü siliyoruz.
Yani kısaca olarak A => S => O => Z => A=>Z=>O=>S=>F=>B şeklinde dfs algoritması kullanarak istediğimiz düğüme ulaşmış olduk.İstenmeyen durum Z düğümünde başlıyor burada çıkmaz sokağa giriyoruz ve tekrar A düğümünü ziyaret edip yolları tekrarlıyoruz bu optimum seviyesini bozan bir durum oluyor.
Karmaşıklığına gelirsek ilgili algoritmanın gidebilecek max derinlik m der isek ve gidilmesi istenilen düğümede LRN veya RLN algoritmalarından birini kullanarak ulaşmak istiyoruz buradaki düğüm sayısını(( 2^m+1) -1) formülü ile hesaplıyabiliriz. Tabi bunun karmaşıklığını hesaplarken yuvarladığımız için karmaşıklık O(2^m) ifadesiyle gösterebiliriz.Buradaki iki branch sayısıdır yani düğümlerin max 2 çocuğu olduğu senaryodur eğer bunu da formülize edersek O(B^m) şeklinde karmaşıklığı gösterebiliriz.
Breadth First Search (BFS) Algoritması
BFS algoritmasına geçicek olursak burada DFS algoritmasının tam tersi bir senaryo söz konusudur.
NLR : Node Left Right (Düğüm Sol Sağ)
NRL : Node Right Left (Düğüm Sağ Sol)
Senaryolarından biri uygulanabilir.Buradaki fark ise ilk bakılan düğümün,mevcut düğümün çocuğu olan düğüm yerine aynı seviyede olmasıdır.Yani DFS algoritmasının ,BFS algoritması dan farklı olarak önce düğümün çocuklarından aramaya başlanır.
Yandaki görseli tekrar düşünecek olursak burada aranmak istenen düğüm 1 nolu düğüm olsun.İlk olarak Node düğümden yani 5 nolu düğümden başlıyoruz ve bunun değerine bakıyoruz.Daha sonra 5 → 7 → 3 → 2 → 8 → 1 → şeklinde devam ediyoruz.Burada biz NLR ihtimalini düşünüyoruz.Düğüm olarak düşünürsek aranan düğüm ne kadar node düğümüne yakınsa o kadar hızlı bulunuyor.
Romanya haritasını tekrar düşünecek olursak Arac başlıyoruz gitmek istediğimiz yer Bucharest şimdi Arac yollarına bakıyoruz T == B mi ? Değil S == B mi ? Değil Z ==B mi ? değil burada hiçbir düğüm bulunamadı şimdi yapılması gereken gidilen düğümlerden Bucharest şehrine gitmeye çalışcaz.
Z => 0
S=> F || R
T=> L
Bu senaryolardan istediğimiz birini seçiyoruz.Birinci Adımda yaptığımız işlemlerin aynısını yapıyoruz.>O == B mi ? Değil,F == B mi ? Değil,R == B mi ? Değil,L == B mi ? Değil bu adımda istediğimiz yere ulaşamadık şimdi ise gittiğimiz düğümlerden yola çıkıyoruz yani ;
O => S burada bir optimizasyon yapmamız gerekir çünkü S düğümü zaten gidilmiş, ziyaret edilmiş düğünlerden biri tekrar buraya bakmamız lazım.
F=> B bu istenilen durumdur.
L=>M
R=> P || C
Bu algoritmanın karmaşıklığı ise derinlik formülü 2^Derinlik şeklinde hesaplanabilir.Karmaşıklık ise O(B^D) buradaki b branch sayısı D ise derinliktir.
Son
Buraya kadar okuduğunuz için çok teşekkür ederim.Algoritmalar dersinin ilk konusu olan arama algoritmalarını anlatmaya çalıştım.Bir sonraki yazılarımda ise bellman ford algoritması ve dijkstra algoritmasını anlatmaya çalışıcam.Herkese Sağlıklı Günler.