Por que o DFS é considerado como tendo complexidade de espaço ?

De acordo com essas notas , o DFS é considerado como tendo complexidade de espaço , em que é o fator de ramificação da árvore em que é o comprimento máximo de qualquer caminho no espaço de estado. $O(bm)$ $b$ $m$

O mesmo é dito nesta página do Wikibook na Pesquisa não informada .

Agora, a "caixa de informações" do artigo da Wikipedia sobre DFS apresenta o seguinte para a complexidade espacial do algoritmo:

$O(|V|)$ , se o gráfico inteiro for percorrido sem repetição, comprimento do caminho mais longo pesquisado para gráficos implícitos sem eliminação de nós duplicados $O($ $)$

que é mais parecido com o que eu pensava ser a complexidade espacial do DFS, ou seja, , onde é o comprimento máximo atingido pelo algoritmo. $O(m)$ $m$

Por que eu acho que esse é o caso?

Bem, basicamente não precisamos armazenar outros nós além dos nós do caminho que estamos vendo atualmente, então não há nenhum ponto de multiplicar por na análise fornecida pelo Wikibook e pelas notas que você me referiu. para. $b$

Além disso, de acordo com este documento sobre a IDA * de Richard Korf , a complexidade espacial do DFS é , onde é considerado o "corte de profundidade". $O(d)$ $d$

Então, qual é a complexidade de espaço correta do DFS?

Eu acho que isso depende da implementação, então eu apreciaria uma explicação da complexidade do espaço para as diferentes implementações conhecidas.

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

DFS is considered to […] of the treenem todo gráfico percorrido primeiro a profundidade é uma árvore .

7897

Há uma diferença entre dizer "aqui a implementação do DFS custou X" e "o DFS pode ser implementado para custar X". Assim, parece estar discutindo sobre diferentes afirmações do segundo tipo, que não precisam ser contraditórias. (Observe que não há nenhuma contradição, pois , se significar alguma coisa.)

O (b m) \supset O (m)

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

O (b m)

$O(bm)$

Raphael

@greybeard Você pode me dizer um exemplo em que uma travessia em profundidade em um gráfico não resultaria em uma árvore?

Nbro 07/01

example where a depth-first traversal on a graph would not result in a treesem pensar demais: analisar. (Wait: o que quer dizer: result in a tree? A questão é de como pesquisar / atravessando um gráfico.)

greybeard

@greybeard De acordo com todas as definições que encontrei até agora. Encontre-me uma definição em que ele revise os nós, para que possamos discutir sobre isso.

Nbro 07/01

Respostas:

Depende do que exatamente você chama de DFS. Considere, por exemplo, o algoritmo DFS-iterativo descrito na Wikipedia e suponha que você o execute em uma árvore para não precisar acompanhar quais nós já visitou. Suponha que você executá-lo em um completo árvore -ary de profundidade . Podemos identificar nós em sua árvore com palavras com mais de de comprimento, no máximo . O algoritmo opera da seguinte maneira: $b$ $m$ $[b]$ $m$

Comece pela raiz. Pressione para a pilha (na ordem inversa). $1,2,\ldots,b$
Estale e empurre para a pilha. $1$ $11,12,\ldots,1b$
Estale e empurre para a pilha. $11$ $111,112,\ldots,11b$
$\ldots$
Estale e empurre para a pilha. $1^{m-1}$ $1^m,1^{m-1}2,\ldots,1^{m-1}b$

Neste ponto, a pilha contém

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 um total de nós. Você pode verificar se esse é o litro no tempo em que o tamanho da pilha é maximizado. $(b-1)m + 1$

Yuval Filmus
fonte

Um litro a tempo mantém o médico afastado.

7898

Há dois pontos aqui a serem destacados:

Caso você introduza na pilha todos os descendentes do nó atual, efetivamente, a complexidade do espaço é onde é o fator de ramificação é o comprimento máximo. A resposta de Yuval Filmus refere-se a este caso, de fato. No entanto, observe que, em geral, é muito muito maior que . Além disso, em muitos domínios, como o quebra-cabeça deslizante, é delimitado por uma constante (nesse caso específico, 4) e, portanto, podemos dizer com segurança que o DFS tem uma complexidade de espaço que é . $O(bd)$ $b$ $d$ $d$ $b$ $b$ $O(d)$
É certo que, no entanto, esse nem sempre é o caso. Por exemplo, no quebra-cabeça Panqueca, o fator de ramificação aumenta com o comprimento da solução ideal e ambos têm valores semelhantes. Ainda assim, a complexidade do espaço é . Para ver isso, basta ajustar o procedimento de expansão de qualquer nó: em vez de inserir todos os descendentes do nó atual (como sugerido por Yuval Filmus), insira-os em ordem. Você primeiro gera o primeiro descendente e imediatamente depois de prosseguir em uma ordem de profundidade - por uma questão de fato, você não precisa de todos os outros descendentes neste momento $O(d)$ . Caso você volte para este nó, seu descendente será removido da pilha. Em seguida, gere o segundo descendente e prossiga na ordem da profundidade primeiro. Caso você retorne a esse nó, gere o terceiro e assim por diante até que não haja mais descendentes. Procedendo dessa maneira, você terá apenas nós na pilha, independentemente do fator de ramificação, . $d$ $b$

Resumindo, eu nunca diria que o DFS tem uma complexidade de espaço que é e, em vez disso, afirmo que sua complexidade de espaço é . $O(bd)$ $O(d)$

Espero que isto ajude,

Carlos Linares López
fonte