Warum wird angenommen, dass die DFS

Gemäß diesen Anmerkungen wird angenommen , dass DFS eine -Raumkomplexität aufweist, wobei der Verzweigungsfaktor des Baums und die maximale Länge eines Pfades im Zustandsraum ist. $O(bm)$ $b$ $m$

Das gleiche gilt für diese Wikibook-Seite zur uninformierten Suche .

In der "Infobox" des Wikipedia-Artikels über DFS wird nun Folgendes für die räumliche Komplexität des Algorithmus dargestellt:

, wenn der gesamte Graph ohne Wiederholung durchlaufen wird, längste gesuchte Pfadlänge für implizite Graphen ohne Eliminierung doppelter Knoten $O(|V|)$ $O($ $)$

Dies ähnelt eher der Raumkomplexität von DFS, dh , wobei die maximale Länge ist, die der Algorithmus erreicht. $O(m)$ $m$

Warum denke ich, dass dies der Fall ist?

Grundsätzlich müssen wir keine anderen Knoten als die Knoten des Pfads speichern, den wir gerade betrachten. Es macht also keinen Sinn, in der Analyse, die sowohl vom Wikibook als auch von den Notizen, auf die ich Sie verwiesen habe, bereitgestellt wird, mit multiplizieren zu. $b$

Darüber hinaus ist gemäß diesem Artikel über IDA * von Richard Korf die Raumkomplexität von DFS , wobei als "Tiefengrenzwert" betrachtet wird. $O(d)$ $d$

Was ist die richtige Speicherkomplexität von DFS?

Ich denke, es kann von der Implementierung abhängen, daher würde ich eine Erklärung der Raumkomplexität für die verschiedenen bekannten Implementierungen begrüßen.

graphs algorithm-analysis graph-traversal space-analysis nbro
quelle

DFS is considered to […] of the treeNicht jeder Graph, der zuerst die Tiefe durchquert, ist ein Baum .

Graubart

Es gibt einen Unterschied zwischen der Aussage "Dies hier hat die DFS-Implementierung X gekostet" und "DFS kann so implementiert werden, dass es X kostet". Es scheint also über verschiedene Aussagen der zweiten Art zu streiten, die überhaupt nicht widersprüchlich sein müssen. (Beachten Sie, dass es seit

überhaupt keinen Widerspruch gibt , wenn

überhaupt etwas bedeuten soll.)

O (b m) \supset O (m)

$O(bm) \supset O(m)$

O (b m)

$O(bm)$

Raphael

@greybeard Können Sie mir ein Beispiel nennen, bei dem eine Tiefenüberquerung in einem Diagramm nicht zu einem Baum führen würde?

nbro

example where a depth-first traversal on a graph would not result in a treeohne zu viel darüber nachzudenken: analysieren. (Warten Sie: Was meinen Sie : result in a tree? Die Frage ist über das Suchen / Durchlaufen eines Diagramms.)

Graubart

@ Greybeard Nach allen Definitionen, die ich bisher gefunden habe. Suchen Sie mir eine Definition, in der die Knoten erneut aufgerufen werden, und wir können darüber diskutieren.

nbro

Antworten:

Es hängt davon ab, wie genau Sie DFS nennen. Betrachten Sie zum Beispiel den in Wikipedia beschriebenen Algorithmus DFS-iterativ und nehmen Sie an, dass Sie ihn in einem Baum ausführen, damit Sie nicht verfolgen müssen, welche Knoten Sie bereits besucht haben. Angenommen, Sie führen es auf einem vollständigen Baum der Tiefe . Wir können Knoten in ihrem Baum mit Worten über identifizieren der Länge höchstens . Der Algorithmus funktioniert wie folgt: $b$ $m$ $[b]$ $m$

Beginnen Sie an der Wurzel. Schieben Sie auf den Stapel (in umgekehrter Reihenfolge). $1,2,\ldots,b$
Pop und schieben Sie auf den Stapel. $1$ $11,12,\ldots,1b$
Pop und schieben Sie auf den Stapel. $11$ $111,112,\ldots,11b$
$\ldots$
Pop und schieben Sie auf den Stapel. $1^{m-1}$ $1^m,1^{m-1}2,\ldots,1^{m-1}b$

Zu diesem Zeitpunkt enthält der Stapel

1^{m}, 1^{m - 1} 2, \dots, 1^{m - 1} b, \dots, 112, \dots, 11 b, 12, \dots, 1 b, 2, \dots, b,

$1^m,1^{m-1}2,\ldots,1^{m-1}b,\ldots,112,\ldots,11b,12,\ldots,1b,2,\ldots,b,$

für insgesamt Knoten. Sie können überprüfen, ob dies das Pint in der Zeit ist, in der die Größe des Stapels maximiert wird. $(b-1)m + 1$

Yuval Filmus
quelle

Ein halbes Liter hält den Arzt fern.

Graubart

Hier sind zwei Punkte zu beachten:

$O(bd)$ $b$ $d$ $d$ $b$ $b$ $O(d)$
$O(d)$ Sie in der Reihenfolge der Tiefe zuerst fortgefahren sind - tatsächlich benötigen Sie zu diesem Zeitpunkt nicht alle anderen Nachkommen $d$ $b$

$O(bd)$ $O(d)$ .

Hoffe das hilft,

Carlos Linares López
quelle