Unterschied zwischen der ersten Suche und einer iterativen Vertiefung

Question

Ich verstehe BFS und DFS, aber für mein Leben kann ich den Unterschied zwischen iterativen Vertiefungen und BFS nicht herausfinden. Anscheinend hat die iterative Vertiefung die gleiche Speicherverwendung wie DFS, aber ich kann nicht sehen, wie dies möglich ist, da es sich wie BFS weiter erweitert. Wenn jemand klarstellen kann, wäre das großartig.

Baum, um bei Bedarf zu arbeiten:

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

Soweit ich weiß, dass die iterative Vertiefung DFs bis in die Tiefe 1 macht, wird DFS bis zur Tiefe von 2 ... bis zur Tiefe n und so weiter, bis es keine Levels mehr findet

Zum Beispiel denke ich, dass dieser Baum gelesen würde

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

Ich glaube, es macht so ziemlich separate DFs mit Tiefengrenze für jedes Level und warf die Erinnerung weg.

Answer 2

Nach meinem Verständnis des Algorithmus ist IDDFS (iterativen Tiefensuche) einfach eine mehrmals durchgeführte Tiefe-First-Suche, wobei die bei jeder Iteration gesuchte Knotenniveau vertieft. Daher entsprechen die Speicheranforderungen über die Tiefensuche, da die maximale Tiefen-Iteration nur die vollständige Tiefensuche ist.

Für das Beispiel des Baumes, den Sie gegeben haben, würde die erste Iteration den Knoten A besuchen, die zweite Iteration würde die Knoten A, B und C besuchen, und die dritte Iteration würde alle Knoten des Baumes besuchen.

Der Grund, warum es so implementiert wird, ist, dass der Algorithmus, wenn die Suche eine Zeitbeschränkung hat der Baum.

Dies unterscheidet sich von einer Breite-First-Suche, da bei jeder Iteration die Knoten genauso besucht werden, als wären sie bei einer Tiefe-First-Suche, nicht wie bei einer Breite-First-Suche. Normalerweise würden IDDFS -Algorithmen wahrscheinlich den "besten Punkte" -Knoten aus jeder Iteration speichern.

Answer 3

Die Speicherverwendung ist die maximale Anzahl von Knoten, die sie zu jedem Zeitpunkt spart. Nicht die Anzahl der besuchten Knoten.

IDFs müssen jederzeit nur die Knoten in der Niederlassung speichern. Er expandiert nur das A und C, wenn wir C (in Ihrem EG) erweitern. BFS muss alle Knoten der Tiefe speichern, die es sucht. Um zu sehen, dass der Effekt einen Baum mit Verzweigungsfaktor 8 anstelle von 2 nimmt. Um bis zu einer Tiefe von 3 zu suchen, muss BFS massive 64 Knoten speichern. IDFs benötigen nur 3.

Answer 4

Bei jeder Iteration der iterativen Seufferen haben wir eine Grenze und durchqueren den Diagramm mit dem DFS . Das ist der Speichern im Speicher.

Schauen Sie sich beispielsweise die letzte Reihe des Bildes unten an. Wenn wir BFS verwendet haben, mussten wir alle Knoten bis in die Tiefe 2 verfolgen. Aber weil wir DFS verwenden, müssen wir nicht alle im Gedächtnis behalten, da entweder einige Knoten bereits besucht sind, damit wir es nicht tun brauche sie oder noch nicht besucht, damit wir es später hinzufügen. Wir halten nur unseren Weg zur Wurzel (den grauen Pfad).

Das Bild stammt aus künstlichem Intelligenzbuch von Peter Norvig und Stuart Russel