logo

TechCodeview

Iterative Deepening Search (IDS) oder Iterative Deepening Depth First Search (IDDFS)

Ein integraler Bestandteil der Informatik und der künstlichen Intelligenz sind Suchalgorithmen. Sie werden verwendet, um eine Vielzahl von Problemen zu lösen, vom Spielen von Spielen wie Schach und Dame bis hin zum Auffinden der kürzesten Route auf einer Karte. Die DFS-Methode (Depth First Search), einer der beliebtesten Suchalgorithmen, durchsucht ein Netzwerk oder einen Baum, indem sie so weit wie möglich an jedem Zweig entlang fährt, bevor sie umkehrt. Allerdings hat DFS einen entscheidenden Nachteil: Wenn der Graph Zyklen enthält, könnte er in einer Endlosschleife gefangen sein. Die Verwendung von Iterative Deepening Search (IDS) oder Iterative Deepening Depth First Search ist eine Technik zur Lösung dieses Problems (IDDFS).

Was ist IDS?

Ein als IDS bekannter Suchalgorithmus kombiniert die Vorteile von DFS mit der Breadth First Search (BFS). Das Diagramm wird mit DFS erkundet, die Tiefenbegrenzung wird jedoch stetig erhöht, bis das Ziel lokalisiert ist. Mit anderen Worten: IDS führt kontinuierlich DFS aus und erhöht jedes Mal die Tiefenbegrenzung, bis das gewünschte Ergebnis erzielt wird. Die iterative Vertiefung ist eine Methode, die sicherstellt, dass die Suche gründlich (d. h. sie findet eine Lösung, falls vorhanden) und effizient (d. h. sie findet den kürzesten Weg zum Ziel) ist.

Der Pseudocode für IDS ist einfach:

Code 

 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

Wie funktioniert IDS?

Die Funktion „iterativeDeepeningSearch“ führt eine iterative Tiefensuche im Diagramm durch und verwendet dabei einen Wurzelknoten und einen Zielknoten als Eingaben, bis das Ziel erreicht ist oder der Suchraum aufgebraucht ist. Dies wird durch die regelmäßige Verwendung der Funktion „deepLimitedSearch“ erreicht, die eine Tiefenbeschränkung auf DFS anwendet. Die Suche endet und gibt den Zielknoten zurück, wenn sich das Ziel in einer beliebigen Tiefe befindet. Die Suche ergibt „None“, wenn der Suchraum aufgebraucht ist (alle Knoten bis zur Tiefengrenze wurden untersucht).

Die Funktion DepthLimitedSearch führt DFS für das Diagramm mit der angegebenen Tiefenbeschränkung durch, indem sie als Eingaben einen Knoten, einen Zielknoten und eine Tiefenbeschränkung verwendet. Die Suche gibt FOUND zurück, wenn sich der gewünschte Knoten in der aktuellen Tiefe befindet. Die Suche gibt „NICHT GEFUNDEN“ zurück, wenn die Tiefengrenze erreicht ist, der Zielknoten jedoch nicht gefunden werden kann. Wenn keines der Kriterien zutrifft, geht die Suche iterativ zu den Nachkommen des Knotens über.

Programm:

Code 

 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')

Ausgabe 

 Path found

Vorteile

  • IDS ist anderen Suchalgorithmen in vielerlei Hinsicht überlegen. Der erste Vorteil besteht darin, dass es umfassend ist, was sicherstellt, dass eine Lösung gefunden wird, wenn eine im Suchraum vorhanden ist. Auf diese Weise werden alle Knoten unter einer bestimmten Tiefenbeschränkung untersucht, bevor die Tiefenbeschränkung durch IDS angehoben wird, das ein tiefenbegrenztes DFS durchführt.
  • IDS ist speichereffizient, was sein zweiter Vorteil ist. Dies liegt daran, dass IDS den Speicherbedarf des Algorithmus verringert, indem nicht jeder Knoten im Suchbereich im Speicher gespeichert wird. IDS minimiert den Speicherbedarf des Algorithmus, indem es nur die Knoten bis zur aktuellen Tiefengrenze speichert.
  • Der dritte Vorteil von IDS besteht darin, dass es sowohl für die Baum- als auch für die Diagrammsuche genutzt werden kann. Dies liegt daran, dass IDS ein generischer Suchalgorithmus ist, der in jedem Suchraum funktioniert, einschließlich eines Baums oder eines Diagramms.

Nachteile

  • IDS hat den Nachteil, dass bestimmte Knoten möglicherweise mehr als einmal besucht werden, was die Suche verlangsamen kann. Die Vorteile von Vollständigkeit und Optimalität überwiegen häufig diesen Nachteil. Darüber hinaus können durch den Einsatz von Strategien wie Speicher oder Caching die wiederholten Fahrten minimiert werden.