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

11

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)bm

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 duplicadosO()

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.

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(bm)O(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
11
@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:

7

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 m . Podemos identificar nós em sua árvore com palavras com mais de [ b ] de comprimento, no máximo m . O algoritmo opera da seguinte maneira:bm[b]m

  1. Comece pela raiz. Pressione para a pilha (na ordem inversa).1,2,,b

  2. Estale e empurre 11 , 12 , , 1 b para a pilha.111,12,,1b

  3. Estale e empurre 111 , 112 , , 11 b para a pilha.11111,112,,11b

  4. Estale e empurre 1 m , 1 m - 1 2 , , 1 m - 1 b para a pilha.1m11m,1m12,,1m1b

Neste ponto, a pilha contém

1m,1m12,,1m1b,,112,,11b,12,,1b,2,,b,

para um total de nós. Você pode verificar se esse é o litro no tempo em que o tamanho da pilha é maximizado.(b1)m+1

Yuval Filmus
fonte
2
Um litro a tempo mantém o médico afastado.
7898
3

Há dois pontos aqui a serem destacados:

  1. Caso você introduza na pilha todos os descendentes do nó atual, efetivamente, a complexidade do espaço é onde b é o fator de ramificação ed é o comprimento máximo. A resposta de Yuval Filmus refere-se a este caso, de fato. No entanto, observe que, em geral, d é muito muito maior que b . Além disso, em muitos domínios, como o quebra-cabeça deslizante, b é 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 ( d ) .O(bd)bddbbO(d)

  2. É 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 momentoO(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, b .db

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 ( d ) .O(bd)O(d)

Espero que isto ajude,

Carlos Linares López
fonte