Tem
1
2011

DFS (Depth – First Search) (leap-frogging)

Algoritmalar ile ilgili yazılarıma devam ediyorum. Sırada dfs (depth – first search)
algoritması var. Yazımda algoritmanın nasıl işlediğini ve çözümleri kendime ait olan
örnekler üzerinde algoritmanın uygulanışını bulabilirsiniz.
DFS algoritması genel olarak iki farklı algoritma olarak karşımıza çıkar. Bunların ne
olduğunu merak etmenize fırsat vermeden hemen belirteyim. :)
- depth-first search (leap-frogging)
- depth-first search (backtracking)
Bu yazımda dept-first search (leap-frogging) algoritmasına değineceğim.

Yukarıdaki resim üzerinden çalışma prensibini açıklamaya çalışacağım. Gördüğünüz
gibi başlangıç noktamız A noktası olarak alınmış. Sonrasında A noktasının ulaşmak
istediğimiz yer olup olmadığının kontrolünü yaparız. Daha doğrusu aşağıda
vereceğim algoritma yapar. :) Burada varmak istediğimiz noktanın G noktası
olduğunu varsayalım. Görüyoruz ki A noktası varmak istediğimiz nokta değil. Bu
aşamada A noktasından gidilebilecek yollar bulunur. Bu yollar yukarıdaki şekle göre
B ve C noktalarıdır. Aynı zamanda bulunan bu noktaların kapalı yani daha önceden
gidilmiş bir nokta olup olmadığı ve açık yani daha önceden bulunmuş gidilebilecek
noktalar arasında olup olmadığı kontrolleri yapılır. Sonuç olarak açık veya kapalı
değillerse açık noktalar olarak belirlenmiş olurlar ki bu durumda o şekilde
belirlendiler. Artık yeni noktamız B noktasıdır. B noksanın aynı şekilde kontrolü yapılır
ve B noktasından gidilebilecek yerler yukarıdaki kontroller yapılarak bulunur. Bundan
sonrasında C noktasına değil D noktasına sonra I noktasına giderek algoritma
çalışmaya devam eder. Buradaki mantık sizinde gördüğünüz gibi sürekli aşağı doğru

gitmektir. Bu çalışma prensibini bilmemiz dfs algoritmasını bfs algoritmasından ayırt
edebilmemizde bize gerçekten yardımcı olur. Artık I noktasına geldik ve baktık ki
geldiğimiz noktada yine gitmek istediğimiz yeri bulamadık ama aşağı doğruda
gidemiyoruz çünkü başka yolumuz kalmadı. Bu durumda yanındaki J noktasına atlar
baktık ki bu noktada istediğimiz nokta değil, gitmediğimiz açık olarak belirtilmiş E
noktasına atlar, oda değil, bu sefer C noktasına atlar ve işlemler aynı şekilde devam
eder. Ve sonunda D noktasına ulaşmış oluruz. Buradaki I noktasından J noktasına
oradan E noktasına ve yine E noktasından C noktasına atlama işlemine leap-frogging
denir.
Algoritmada stack yapısı kullanılmıştır. Açık olan noktalar stack içerisinden alınır ve
açık olarak belirlenen noktalar stack içerisine eklenir. BFS algoritmasında ise durum
aynı şekilde olmakla beraber yapı olarak queue kullanılmıştır.(BFS algoritmasına
önceki yazılarımda değinmiştim.)

procedure depth_first_search;
begin
OPEN:=[START];
CLOSED:=[ ];
while OPEN<>[ ] do
begin
X := top(OPEN); (and remove X from OPEN)
if final(X)
then return(success);
else
begin
add X to CLOSED
find successors of X
kill the successors of X that are in CLOSED or OPEN;
push the surviving successors of X into OPEN;
end; {else}
end; {while}
return(failure);
end; {breadth_first_search}

Elimizde bir romania map olsun. Bu harita üzerinde Arad şehrinden Bucharest
şehrine gitmek isteyelim. Ayrıca bize fazladan koşullar verilmiş olsun.

 

KOŞUL-1
Yol: Arad-Bucharest
Aynı şehir üzerinden gidilebilen şehirler kendi aralarında alfabetik olarak sıralanmış olsun.
ÇÖZÜM:

Gördüğünüz gibi burada tüm şehirler kendi aralarında alfebetik olarak sıralanmıştır. Çözüm yolu ise
Arad-Sibiu-Fagaras-Bucharest’ tir. Çözüm yönteminde ise gidilen yollara bir daha gidilemez ve
gidilecek yollar olarak belirtilen yollarada başka bir yol üzerinden gidilemez. Yani open ve closed
olanlara tekrar open ve closed olmayan bir şehir üzerinden gitmenin anlamı yoktur. Closed olan
şehirlere daha önceden gidilmiş ve bir sonuç bulunamamıştır. Tekrar gidilmesinin anlamı yoktur. Yine
open olan şehirler içinde bu durum geçerlidir. Bu şehirler zaten açıktır ve gidilecektir. Öncesinde
gitmenin bir anlamı yoktur.

KOŞUL-2
Yol: Arad-Bucharest
Aynı şehir üzerinden gidilebilen şehirler kendi aralarında anti-alfabetik olarak sıralanmış olsun.
ÇÖZÜM:

Gördüğünüz gibi burada tüm şehirler kendi aralarında anti-alfabetik olarak sıralanmıştır. Çözüm yolu
ise Arad-Timisoara-Lugoj-Mehadia-Dobreta-Craiova-Pitesti-Bucharest’ tir. Bir önceki çözümle aynı
olmadığını görmüşsünüzdür. Buradan DFS algoritmasının en kısa yolu yani en az şehir dolaşılarak ulaşılan yolu bulmadığını anlayabiliyoruz.

Genel Karakteristik (İstisnai durumlar dışında)
- Bulunan yolun en kısa yada en ucuz yol olduğu garantisini vermez.
- Graph sonsuz uzunlukta değilse her zaman tamamlanır.

About the Author:

Leave a comment

Son Eklenen Video

Get the Flash Player to see this content.

Kategoriler

Arşiv