Yinelemeli Derinlik Araması (Iterative Deepining Search)

Yazan :Şadi Evren ŞEKER

Bilgisayar bilimlerinin çeşitli alanlarında (örneğin yapay zeka, veri yapıları veya şekil kuramı (graph theory) gibi) kullanılan arama algoritmalarından birsidir.

 

Algoritma, derin öncelikli drama (depth first search) üzerine kurulu olduğu için, literatürde “iterative deepening depth first search (yinelemeli derinleşen, derin öncelikli arama)” olarak da geçmektedir.

 

Algoritma basitçe derinlik değerini bir değişkende tutmakta ve bu değeri her adımda arttırmaktadır.
Yineleme yapısı (iteration) basit bir döngü (loop) olarak düşünülebilir ve her adımda derinliğin, bir döngü değişkeni (loop variable) gibi düşünülerek derinleştiği kabul edilebilir.

 

Örneğin aşağıdaki şekli (graph) ele alalım:

 

Ağaçta görüldüğü üzere iki adet döngü (cycle) bulunmaktadır. Iterative Deepening search algoritmasını bu ağaç üzerinde çalıştıracak olursak, algoritma öncelikle derinlik değerini (bundan sonra d değişkeni (variable) ile ifade edilecektir) 0’dan başlatarak her adımda bir ilerletecektir.

d=0 için arama:
A
d=1 için arama:
A (tekrar A değerine bakar) B C (sanki ağacın en üstteki üç düğümü, şekilde gösterildiği gibi bağlanmış kabul edilebilir, daha alttaki derinliklerde bulunan DEFG düğümlerine hiç bakamaz)
d=2 için arama:
A B D E C F G (Bu aramada sanki sondaki daireler (cycle) bulunmuyormuş gibi kabul edilebilir, çünkü belirtilen derinlik bu dairelere kadar inemez)
d=3 için arama:
A B D B E C F G A
d=4 için arama:
A B D B D E B C F G A B C

Yukarıdaki arma işlemi, derinlik arttıkça devam etmektedir.

 

Arama algoritmalarının değerlendirildiği bazı kriterler bulunmaktadır. Buna göre IDDFS (iterative deepening depth first search) algoriması “tam” algoritma olarak kabul edilebilir.
Tamlık teriminin (completeness) anlamı aşağıdaki şekilde tanımlanabilir:

Bir arama algoritması, bütün düğümleri dolaşarak aranan düğümü bulmayı garanti ediyorsa bu algoritmaya tam arama algoritması ismi verilir.

Örneğin yine yukarıdaki şekil için klasik derin öncelikli arama (depth first search) algoritmasını ele alsaydık, bu algoritmanın tam olmadığını söyleyebilirdik. Bunun sebebi DFS algoritmasının dolaşması sırasında, aşağıdaki döngüye girmesidir:

A B D B D B D ( B D ikilisi sosuza kadar tekrar eder)

Kısacası A B D düğümleri dışındaki düğümlere asla bakmaz. Bu anlamda tam olmadığını söyleyebiliriz.

BFS (breadth first search , yayılma öncelikli veya sığ öncelikli arama) algoritması ise her zaman için tam kabul edilebilir, sebebi bir sonraki derinlik seviyesine inmeden önce, bulunduğu seviyedeki düğümleri bitirmesi ve bu sayede bütün ağaca bakmayı garanti etmesidir.

Algoritmanın karmaşıklığına değinecek olursak. Aşağıdaki şekilde bir formül ile karşılaşırız.

Bu formülde görülen terimler şekil kuramında (graph theory) sıkça kullanılan bazı değerlere atıfta bulunur.
d değerinin derinlik olduğunu daha önce belirtmiştik. b ile gösterilen değer ise dallanma katasyısıdır (branching factor).

Kısaca her düğümün kaç çocuğu olduğu (out order, kaç düğüme gidilebildiği) olarak tutulur. Örneğin tam dolu ikili arama ağacının (binary search tree) b değeri 2’dir. Genelde en kötü durum analizinde bütün çocukların dolu olması ihtimali üzerinde durulur. Ayrıca istatistiksel olarak ortalamam çocuk sayısının da alındığı olur. Örneğin şehirlerin tutulduğu bir şekilde, her şehirden gidilebilecek şehir sayısı değişmektedir. Bu durumda b değeri ortalama değer olarak hesaplanabilir.

 

Bu açıklama ardından yukarıdaki denkleme tekrar bakarak anlamaya çalışalım.

 

IDDFS algoritmasında, en altta bulunan düğümlerin 1 kere (d sabitlendiğinde en altta kalan düğümler hangileri ise) dolaşıldığını, d-1 derinliğindeki düğümlerin ise 2 kere dolaşıldığını ve böylece kök düğüme (root) kadar her düğümün, bulunduğu seviyeye göre kaç kere dolaşıldığını hesaplayabileceğimize göre yukarıdaki denklem çıkarılabilir.

 

Diğer bir deyişle d=0 için kök 1 kere dolaşılırken d=1 olduğunda kök 2 ve kökün çocukları 1 kere dolaşılmış olur. d=3 olduğunda kök 3 kere ve çocukları 2 ve en alttaki çocuklar ise 1 kere dolaşılmış olur. Görüldüğü üzere derinliğin her artışında kök derinlik kadar altındaki her düğüm ise birer azalarak en nihayetinde yapraklar (leaf) tek bir kere dolaşılmış olmaktadır.

 

Sonuç olarak Yukarıdaki formülün ilk terimi kök (d+1)1 (tek düğüm d+1 kere dolaşılmıştır) , ikinci terimi kökün çocukları (db (kökün çocukları (ki sayısı b’dir) derinlik kadar (ki d ile gösterilir) dolaşılmıştır).

 

Yukarıdaki bu formülü daha toplu şekilde aşağıda gösterildiği gibi yazabiliriz:

 

Algoritmanın dolaşma (arama) zamanı karmaşıklığı yukarıda gösterildiği gibidir. Terimler birleştirildiğinde en kötü durum analizi (worst case analysis) için O(b^d) gösterimi kullanılabilir.

 

Hafıza karmaşıklığı ise O(bd) olarak ifade edilebilir. Bunun sebebi d derinliğindeki bir ağacın her seviyesinde b adet çocuğu bulunması durumunda bd kadar düğüm olacağıdır. Algoritma, çalışması sırasında ilave düğümlere ihtiyaç duymaz ve şeklin kendisi üzerinde dolaşarak sonuca ulaşır.