¿Por qué se considera que DFS tiene una complejidad de espacio

Según estas notas , se considera que DFS tiene una complejidad de espacio , donde es el factor de ramificación del árbol es la longitud máxima de cualquier ruta en el espacio de estado. $O(bm)$ $b$ $m$

Lo mismo se dice en esta página de Wikibook en Búsqueda desinformada .

Ahora, el "cuadro de información" del artículo de Wikipedia sobre DFS presenta lo siguiente para la complejidad espacial del algoritmo:

, si se recorre todo el gráfico sin repetición, busca la longitud de ruta más larga para gráficos implícitos sin eliminación de nodos duplicados $O(|V|)$ $O($ $)$

que es más similar a lo que pensé que era la complejidad espacial de DFS, es decir, , donde es la longitud máxima alcanzada por el algoritmo. $O(m)$ $m$

¿Por qué creo que este es el caso?

Bueno, básicamente no necesitamos almacenar ningún otro nodo que no sea el nodo de la ruta que estamos viendo actualmente, por lo que no tiene sentido multiplicarlo por en el análisis proporcionado tanto por Wikibook como por las notas que le envié. a. $b$

Además, según este documento sobre IDA * de Richard Korf , la complejidad espacial de DFS es , donde se considera el "límite de profundidad". $O(d)$ $d$

Entonces, ¿cuál es la complejidad espacial correcta de DFS?

Creo que puede depender de la implementación, por lo que agradecería una explicación de la complejidad del espacio para las diferentes implementaciones conocidas.

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

DFS is considered to […] of the treeno todas las gráficas de profundidad atravesada primero son árboles .

barba gris

Hay una diferencia entre decir "aquí la implementación de DFS ha costado X" y "DFS puede implementarse de modo que haya costado X". Parece estar discutiendo sobre diferentes declaraciones del segundo tipo, que no tienen por qué ser contradictorias. (Tenga en cuenta que no hay contradicción en absoluto ya que

, si

significa algo en absoluto.)

O (b m) \supset O (m)

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

O (b m)

$O(bm)$

Raphael

@greybeard ¿Puede decirme un ejemplo en el que un recorrido en profundidad en un gráfico no resulte en un árbol?

nbro

example where a depth-first traversal on a graph would not result in a treesin pensarlo demasiado: análisis. (Espera: ¿a qué te refieres result in a tree? La pregunta es sobre buscar / atravesar un gráfico)

Barba gris

@greybeard Según todas las definiciones que he encontrado hasta ahora. Búscame una definición donde vuelva a visitar los nodos, luego podremos discutirlo.

nbro

Respuestas:

Depende de lo que llames exactamente DFS. Considere, por ejemplo, el algoritmo DFS-iterativo descrito en Wikipedia , y suponga que lo ejecuta en un árbol para no tener que realizar un seguimiento de los nodos que ya ha visitado. Supongamos que se ejecuta en un completo árbol ary de profundidad . Podemos identificar nodos en su árbol con palabras de más de de longitud como máximo . El algoritmo funciona de la siguiente manera: $b$ $m$ $[b]$ $m$

Comience en la raíz. Empuje a la pila (en orden inverso). $1,2,\ldots,b$
Pop , y empuja a la pila. $1$ $11,12,\ldots,1b$
Pop , y empuja a la pila. $11$ $111,112,\ldots,11b$
$\ldots$
Haga estallar y empuje a la pila. $1^{m-1}$ $1^m,1^{m-1}2,\ldots,1^{m-1}b$

En este punto, la pila contiene

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,$

para un total de nodos. Puede comprobar que esta es la pinta en el tiempo en que se maximiza el tamaño de la pila. $(b-1)m + 1$

Yuval Filmus
fuente

Una pinta a tiempo mantiene al médico alejado.

barba gris

Hay dos puntos aquí para hacer:

$O(bd)$ $b$ $d$ $d$ $b$ $b$ $O(d)$
$O(d)$ $d$ $b$

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

Espero que esto ayude,

Carlos Linares López
fuente