logo

TechCodeview

Yinelemeli Derinleştirme Araması (IDS) veya Yinelemeli Derinleştirme Derinliği İlk Arama (IDDFS)

Bilgisayar biliminin ve yapay zekanın ayrılmaz bir bileşeni arama algoritmalarıdır. Satranç ve dama gibi oyunlar oynamaktan haritada en kısa rotayı bulmaya kadar çeşitli sorunları çözmek için kullanılırlar. En popüler arama algoritmalarından biri olan Derinlik İlk Arama (DFS) yöntemi, bir ağı veya ağacı, dönmeden önce her dal boyunca mümkün olduğunca uzağa giderek arar. Ancak DFS'nin kritik bir dezavantajı vardır: Grafik döngüler içeriyorsa sonsuz bir döngüye sıkışabilir. Yinelemeli Derinleştirme Aramasını (IDS) veya Yinelemeli Derinleştirme Derinliği İlk Aramasını kullanmak, bu sorunu çözmeye yönelik tekniklerden biridir (IDDFS).

IDS nedir?

IDS olarak bilinen bir arama algoritması, DFS'nin avantajlarını Genişlik İlk Arama (BFS) ile birleştirir. Grafik, DFS kullanılarak araştırılır ancak derinlik sınırı, hedef bulunana kadar sürekli olarak artırılır. Başka bir deyişle IDS, istenen sonuç elde edilene kadar her seferinde derinlik sınırını yükselterek DFS'yi sürekli olarak çalıştırır. Yinelemeli derinleştirme, aramanın kapsamlı olmasını (yani varsa bir çözüm bulmasını) ve verimli (yani hedefe giden en kısa yolu bulmasını) sağlayan bir yöntemdir.

IDS'in sözde kodu basittir:

Kod 

 function iterativeDeepeningSearch(root, goal): depth = 0 while True: result = depthLimitedSearch(root, goal, depth) if result == FOUND: return goal if result == NOT_FOUND: return None depth = depth + 1 function depthLimitedSearch(node, goal, depth): if node == goal: return FOUND if depth == 0: return NOT_FOUND for child in node.children: result = depthLimitedSearch(child, goal, depth - 1) if result == FOUND: return FOUND return NOT_FOUND

IDS nasıl çalışır?

iterativeDeepeningSearch işlevi, hedefe ulaşılana veya arama alanı bitene kadar girdi olarak bir kök düğümü ve bir hedef düğümü kullanarak grafik üzerinde yinelemeli derinleştirme araması gerçekleştirir. Bu, DFS'ye derinlik kısıtlaması uygulayan deepLimitedSearch işlevinin düzenli olarak kullanılmasıyla gerçekleştirilir. Hedef herhangi bir derinlikte bulunuyorsa arama sona erer ve hedef düğümünü döndürür. Arama alanı tükenirse arama Yok sonucunu verir (derinlik sınırına kadar tüm düğümler araştırılmıştır).

DeepLimitedSearch işlevi, bir düğümü, bir hedef düğümü ve bir derinlik sınırını girdi olarak alarak, belirtilen derinlik sınırıyla grafik üzerinde DFS'yi yürütür. İstenilen düğüm mevcut derinlikte bulunuyorsa arama FOUND sonucunu döndürür. Derinlik sınırına ulaşılırsa ancak hedef düğüm bulunamıyorsa arama BULUNAMADI sonucunu döndürür. Her iki kriter de doğru değilse, arama yinelemeli olarak düğümün yavrularına doğru ilerler.

Program:

Kod 

 from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def add_edge(self, u, v): self.graph[u].append(v) def iddfs(self, start, goal, max_depth): for depth in range(max_depth+1): visited = set() if self.dls(start, goal, depth, visited): return True return False def dls(self, node, goal, depth, visited): if node == goal: return True if depth == 0: return False visited.add(node) for neighbor in self.graph[node]: if neighbor not in visited: if self.dls(neighbor, goal, depth-1, visited): return True return False # Example usage g = Graph() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.add_edge(3, 3) start = 0 goal = 3 max_depth = 3 if g.iddfs(start, goal, max_depth): print('Path found') else: print('Path not found')

Çıktı 

 Path found

Avantajları

  • IDS birçok açıdan diğer arama algoritmalarından üstündür. İlk faydası kapsamlı olmasıdır, bu da arama alanında bir çözümün bulunması durumunda bulunmasını sağlar. Bu, belirli bir derinlik sınırı altındaki tüm düğümlerin, derinlik sınırlamalı bir DFS yapan IDS tarafından derinlik sınırı yükseltilmeden önce araştırılmasını sağlar.
  • IDS hafıza açısından verimlidir ve bu da ikinci faydasıdır. Bunun nedeni, IDS'nin arama alanındaki her düğümü hafızada saklamayarak algoritmanın hafıza ihtiyacını azaltmasıdır. IDS, düğümleri yalnızca geçerli derinlik sınırına kadar depolayarak algoritmanın bellek alanını en aza indirir.
  • IDS'in hem ağaç hem de grafik araması için kullanılabilmesi üçüncü faydasıdır. Bunun nedeni, IDS'nin bir ağaç veya grafik de dahil olmak üzere herhangi bir arama alanında çalışan genel bir arama algoritması olmasıdır.

Dezavantajları

  • IDS'in belirli düğümleri birden fazla kez ziyaret etme potansiyeli vardır ve bu da aramayı yavaşlatabilir. Tamlık ve optimalliğin faydaları sıklıkla bu dezavantajı aşar. Ayrıca hafıza veya önbellekleme gibi stratejiler kullanılarak tekrarlanan yolculuklar en aza indirilebilir.