Der Iterative Tiefensuche-Algorithmus (Iterative Deepening Depth-First Search, ID-DFS) ist ein Algorithmus, mit dem ein Knoten in einem Baum gefunden wird. Dies bedeutet, dass der Algorithmus bei einer Baumdatenstruktur den ersten Knoten in diesem Baum zurückgibt, der der angegebenen Bedingung entspricht. Die Kanten müssen ungewichtet sein. Dieser Algorithmus kann auch mit ungewichteten Diagrammen arbeiten, wenn ein Mechanismus zum Verfolgen bereits besuchter Knoten hinzugefügt wurde.

Beschreibung des Algorithmus

Das Grundprinzip des Algorithmus besteht darin, mit einem Startknoten zu beginnen und dann das erste untergeordnete Element dieses Knotens zu betrachten. Anschließend wird das erste untergeordnete Element dieses Knotens (Enkel des Startknotens) usw. angezeigt, bis ein Knoten keine untergeordneten Elemente mehr hat (wir haben einen Blattknoten erreicht). Es geht dann eine Ebene höher und schaut auf das nächste Kind. Wenn keine Kinder mehr vorhanden sind, wird eine weitere Ebene erhöht, bis weitere Kinder gefunden werden oder der Startknoten erreicht wird. Wenn der Zielknoten nach der Rückkehr vom letzten untergeordneten Element des Startknotens nicht gefunden wurde, kann der Zielknoten nicht gefunden werden, da bis dahin alle Knoten durchlaufen wurden.

Bisher wurde hier die Tiefensuche (Depth-First Search, DFS) beschrieben. Die iterative Vertiefung trägt dazu bei, dass der Algorithmus nicht nur eine Ebene im Baum zurückgibt, wenn der Knoten keine untergeordneten Elemente mehr zu besuchen hat, sondern auch, wenn eine zuvor festgelegte maximale Tiefe erreicht wurde. Wenn wir zum Startknoten zurückkehren, erhöhen wir die maximale Tiefe und starten die Suche von vorne, bis wir alle Blattknoten (untere Knoten) besucht haben und eine Erhöhung der maximalen Tiefe nicht dazu führt, dass wir mehr Knoten besuchen.

Im Einzelnen sind dies die folgenden Schritte:

1. Für jedes Kind des aktuellen Knotens
2. Wenn es sich um den Zielknoten handelt, kehren Sie zurück
3. Wenn die aktuelle maximale Tiefe erreicht ist, kehren Sie zurück
4. Setzen Sie den aktuellen Knoten auf diesen Knoten und kehren Sie zu 1 zurück.
5. Nachdem Sie alle Kinder durchlaufen haben, gehen Sie zum nächsten Kind des Elternteils (dem nächsten Geschwister).
6. Nachdem Sie alle untergeordneten Elemente des Startknotens durchlaufen haben, erhöhen Sie die maximale Tiefe und kehren Sie zu 1 zurück.
7. Wenn wir alle Blattknoten (unten) erreicht haben, existiert der Zielknoten nicht.

Beispiel des Algorithmus

Betrachten Sie den folgenden Baum:

Die Schritte, die der Algorithmus für diesen Baum ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

1. Besuche Knoten 0
2. Besuche Knoten 1
3. Aktuelle maximale Tiefe erreicht, Rückkehr …
4. Besuche Knoten 2
5. Aktuelle maximale Tiefe erreicht, Rückkehr …
6. Tiefe auf 2 erhöhen
7. Besuche Knoten 0
8. Besuche Knoten 1
9. Besuche Knoten 3
10. Aktuelle maximale Tiefe erreicht, Rückkehr …
11. Besuche Knoten 4
12. Aktuelle maximale Tiefe erreicht, Rückkehr …
13. Besuche Knoten 2
14. Besuche Knoten 5
15. Aktuelle maximale Tiefe erreicht, Rückkehr …
16. Besuche Knoten 6
17. Den gesuchten Knoten gefunden und zurückgegeben …

Laufzeit des Algorithmus

Wenn wir die maximale Tiefe jedes Mal verdoppeln, wenn wir tiefer gehen müssen, ist die Laufzeitkomplexität der iterativen vertiefenden Tiefensuche (ID-DFS) dieselbe wie bei der regulären Tiefensuche (DFS). da alle vorherigen addierten Tiefen dieselbe Laufzeit haben wie die aktuelle Tiefe (1/2 + 1/4 + 1/8 + … <1). Die Laufzeit der regulären Tiefensuche (DFS) beträgt O(| N|) (|N| = Anzahl der Knoten im Baum), da jeder Knoten höchstens einmal durchlaufen wird. Die Anzahl der Knoten ist gleich b^d, wobei b der Verzweigungsfaktor und d die Tiefe ist, sodass die Laufzeit als O(b ^ d) umgeschrieben werden kann.

Speicherkomplexität des Algorithmus

Die räumliche Komplexität der iterativen vertiefenden Tiefensuche (ID-DFS) entspricht der regulären Tiefensuche (DFS), dh, wenn wir den Baum selbst ausschließen, O(d), wobei d ist die Tiefe, die auch die Größe des Aufrufstapels bei maximaler Tiefe ist. Wenn wir den Baum einschließen, entspricht die Speicherplatzkomplexität der Laufzeitkomplexität, da jeder Knoten gespeichert werden muss.