WikiDer > Iterative vertiefende Tiefensuche

Iterative deepening depth-first search

Iterative vertiefende Tiefensuche (IDDFS) ist ein Suchalgorithmus bei dem die Tiefenbegrenzte Sucheiterativ wird mit zunehmender Tiefengrenze jedes Mal durchgeführt, bis eine Lösung gefunden ist oder bis die gesamte Baum wurde durchsucht. Mit jeder Iteration wird die Knoten besucht in der zählung mit Tiefensuche bis zu einer bestimmten Tiefengrenze. Die Reihenfolge, in der die Knoten zuerst besucht werden, ist dieselbe wie bei einem bij Breitensuche.

IDDFS kombiniert die effiziente Speichernutzung der Tiefensuche mit der Vollständigkeit der Breitensuche (sofern die Verzweigungsfaktor ist endlich). Da IDDFS bestimmte Knoten mehrmals besucht, scheint der Algorithmus viel zu duplizieren. Dies stellt sich als nicht weiter schlimm heraus, da sich die meisten Knoten in der untersten Schicht des Baums befinden, so dass die zusätzliche Rechenzeit für die Knoten oben im Baum relativ einfach ist.

Beispiel

Beispiel für eine iterative Vertiefung der Tiefensuche

Für den obigen Graphen beginnen wir die Tiefensuche bei A, wobei wir annehmen, dass zuerst linke Knoten über rechten Knoten gewählt werden, und dann werden wir die Knoten in der folgenden Reihenfolge durchgehen: A, B, D, F, E C, G.

Wenn wir diese Suche durchführen, ohne über genügend Speicher zu verfügen, um sich an vorherige Knoten zu erinnern, durchsuchen wir die Knoten in der folgenden Reihenfolge: A, B, D, F, E, A, B, D, F, E usw. Wir wiederholen das ABDFE Schleife und erreiche niemals C oder G.

Iteratives Vertiefen verhindert diese endlose Wiederholung und erreicht die nächsten Knoten erst in einer bestimmten Tiefe. Wenn wir annehmen, dass die Suche von links nach rechts erfolgt:

  • 0: A
  • 1: A (wieder), B, C, E
    Beachten Sie, dass bei der iterativen Vertiefung jetzt C ausgewählt ist, während wir auf die mit einer herkömmlichen Tiefensuche nicht stoßen werden
  • 2: A, B, D, F, C, G, E, F
  • 3: A, B, D, F, E, C, G, E, F, B

Wenn wir die Tiefe für diesen Graphen für die Schleifen ABFE und AEFB erhöhen, erreicht der Algorithmus schließlich die maximale Tiefe und setzt die Suche auf einem anderen Zweig fort.