Sınırlı Derin Öncelikli Arama (Depth-Limited Search)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan arama algoritmalarından birisidir. Bu algoritma esas olarak derin öncelikli arama (depth first search DFS) ile aynı çalışmaktadır ancak tek farkı arama işlemi sırasında özellikle dairelere (cycles) takılma ihtimaline karşı sınır önlemi alınmış olmasıdır.

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

Yukarıdaki şekil tanım itibariyle bir ağaç özelliği göstermektedir. Yani yönlü ve daire içermeyen bir şekildir (directed acyclic graph). Ancak aynı şekle aşağıdaki gibi basit bir bağlantı daha eklenseydi artık ağaç olmayacaktı:

Yukarıdaki yeni şekilde derin öncelikli bir arama yaptığımızı ve A düğümünden işleme başladığımızı düşünelim. Örneğin orta sıra (infix) ve L N R ( sol üst sağ , left node right) sırasıyla arama yaptığımızı düşünelim. Daire içermeyen ilk şekilde LNR sırasına göre aşağıdaki sonucun çıkması beklenir:

DBEAFC

Ancak ikinci şekilde LNR sırasına göre önce en soldaki terim yazılmaya çalışılacak, Böylece A->B->D->A->B->D->A->B->D->A sırasıyla namütenahi dönülecek ve hiçbir zaman bitmeyecek bir fasit daireye girilecektir (Sonsuz döngü). Bu durum literatürde sol özyineleme (left recursion) olarak geçer. Yani şeklimizin (veya herhangi bir yapının) sol tarafında kendini tekrarlayan bir durum bulunmakta dolayısıyla derin öncelikli arama yapılamamaktadır.

Çözüm olarak bu yazının da konusu olan sınırlı derin öncelikli arama (depth limited search, DLS) algoritması kullanılabilir. Bu algoritmada gidilebilecek düğüm sayısına bir tahdit konulmakta ve ancak verilen sayıda düğüme gidilebilmektedir.

Algoritmanın kodlanması

Yukarıda izah edilen algoritma aşağıdaki şekilde kodlanabilir:

Yukarıdaki özyineli fonksiyonda (recursive function) bakılan düğüm hedef olana kadar dolaşma işlemi devam etmektedir. Dolaşma işlemi sırasında klasik derin öncelikli aramalarda kullanılan yığın (stack) kullanılmış ve geçilen düğümler geri dönülüp aranmak üzere yığında tutulmuştur.

Şayet aranan düğüm verilen derinlikten daha derin değilse arama işlemi devam etmektedir ancak verilen derinlik geçildiği zaman arama işlemi daha derine gitmemekte ve artık o ana kadar aranmak üzere yığınladığı düğümleri işlemektedir.

Yukarıda anlatılan algoritma bilgisiz bir arama algoritmasıdır (uninformed search algorithm) ve ayrıca algoritmanın hafıza karmaşıklığı (memory complexity) sınırlıdır çünkü algoritmada aranabilecek düğüm sayısında bir sınır bulunmaktadır.