Pesquisa de gráfico: largura primeiro vs. profundidade primeiro

79

Ao pesquisar gráficos, existem dois algoritmos fáceis: largura primeiro e profundidade primeiro (geralmente feito adicionando todos os nós gráficos auxiliares a uma fila (largura primeiro) ou pilha (profundidade primeiro)).

Agora, existem vantagens de um sobre o outro?

Os que eu conseguia pensar:

  • Se você espera que seus dados estejam bem abaixo do gráfico, a profundidade pode ser encontrada mais cedo, pois você está indo para as partes mais profundas do gráfico muito rapidamente.
  • Por outro lado, se você espera que seus dados estejam bem no gráfico, a amplitude pode fornecer o resultado mais cedo.

Há algo que eu perdi ou isso se resume principalmente à preferência pessoal?

malexmave
fonte

Respostas:

43

Gostaria de citar uma resposta do Stack Overflow de hstoerr que aborda bem o problema:

Isso depende muito da estrutura da árvore de pesquisa e do número e localização das soluções .
Se você sabe que uma solução não está longe da raiz da árvore, uma BFS (primeira pesquisa de largura) pode ser melhor. Se a árvore for muito profunda e as soluções forem raras, a DFS (Search First Deep) poderá se espalhar para sempre, mas o BFS poderá ser mais rápido. Se a árvore for muito larga, um BFS pode precisar de muito mais memória, portanto pode ser completamente impraticável. Se as soluções forem frequentes, mas localizadas no fundo da árvore, o BFS pode ser impraticável. Se a árvore de pesquisa for muito profunda, você precisará restringir a profundidade da pesquisa para a primeira pesquisa de profundidade (DFS), de qualquer maneira (por exemplo, com aprofundamento iterativo).

Mas estas são apenas regras de ouro; você provavelmente precisará experimentar.

Rafał Dowgird também observa:

Alguns algoritmos dependem de propriedades específicas do DFS (ou BFS) para funcionar. Por exemplo, o algoritmo Hopcroft e Tarjan para localizar componentes conectados a 2 aproveita o fato de que cada nó já visitado encontrado pelo DFS está no caminho da raiz para o nó atualmente explorado.

Gigili
fonte
5
Eu não posso entender por que esta resposta tem 27 upvotes e é exatamente a fusão de 2 outras respostas, que por sinal são pensamentos simplesmente gerais sobre ...
nbro
37

Um ponto importante em nosso mundo multicore: o BFS é muito mais fácil de paralelizar. Isso é intuitivamente razoável (enviar threads para cada filho) e pode ser provado que é assim também. Portanto, se você tiver um cenário em que possa usar o paralelismo, o BFS é o caminho a seguir.

Suresh
fonte
8
Se o DFS for de outra forma vantajoso na configuração fornecida, você poderá aplicar o BFS até gerar threads suficientes e continuar com o DFS. Mais especificamente, você pode fazer o DFS e sempre que descer e não houver threads suficientes, crie um para o próximo irmão.
Raphael
Esta resposta não merece 20 votos positivos. A questão é sobre o uso geral dos 2 algoritmos e não sobre um uso específico.
Nbro 31/05
31

(Criei um wiki da comunidade. Sinta-se à vontade para editar.)

E se

  • é o fator de ramificaçãob
  • é a profundidade em que a solução estád
  • é a altura da árvore (então, d h )hdh

Então

  • O(bh)O(h)
  • O(bd)O(bd)
  • O(bd)O(d)

Razões para escolher

  • DFS
    • deve ver a árvore inteira de qualquer maneira
    • d
    • não me importo se a resposta está mais próxima da raiz
  • BFS
    • resposta está perto da raiz
    • você quer a resposta mais próxima da raiz
    • tem múltiplos núcleos / processadores
  • IDDFS
    • você quer BFS, não tem memória suficiente, mas é aceitável um pouco mais devagar

IDDFS = pesquisa aprofundada aprofundada iterativa - primeira

rgrig
fonte
1
Esta é uma excelente resposta. Percebo, porém, que enquanto a pergunta é sobre gráficos, essa resposta se refere a árvores. Uma árvore é um gráfico, é claro, e pode ser que a palavra possa ser substituída ... mas que tal ha "altura da árvore". Isso se traduz diretamente na "altura do gráfico"?
precisa saber é o seguinte
Outro motivo para usar o IDDFS é que, dependendo de como você deseja usá-lo, após cada iteração, você pode ter uma resposta possível (se estiver procurando, digamos, um máximo ou um mínimo). Isso significa que você pode sair do algoritmo mais cedo se sua resposta for "boa o suficiente" ou você pode sair da entrada do usuário (como um mecanismo de xadrez usando o IDDFS para encontrar uma solução ideal, mas sendo interrompido por um jogador que está movendo uma peça).
jedd.ahyoung
Outro ponto a ser adicionado é que o DFS usa a pilha, enquanto o BFS usa a fila.
Karthik Balaguru
17

Um cenário (além de encontrar o caminho mais curto, que já foi mencionado) em que você pode escolher um sobre o outro para obter um programa correto seria infinitos gráficos:

Se considerarmos, por exemplo, uma árvore em que cada nó tem um número finito de filhos, mas a altura da árvore é infinita, o DFS pode nunca encontrar o nó que você está procurando - ele continuará visitando o primeiro filho de cada nó que veja, portanto, se o que você procura não é o primeiro filho de seu pai, ele nunca chegará lá. BFS, no entanto, é garantido para encontrá-lo em tempo finito.

Da mesma forma, se considerarmos uma árvore em que cada nó tem um número infinito de filhos, mas a árvore tem uma altura finita, o BFS pode não terminar. Ele visitará apenas os filhos do nó raiz e, se o nó que você procura for filho de outro nó, ele não será alcançado. Nesse caso, é garantido que o DFS o encontre em tempo finito.

sepp2k
fonte
7
Vale ressaltar que ambos produzem apenas algoritmos de semi-decisão para gráficos infinitos; você não pode decidir em um tempo finito que um elemento não está na árvore (obviamente). Quanto às aplicações práticas, observe que (conceitualmente) é possível definir estruturas de dados infinitas (consulte o parágrafo 3.4)!
Raphael
15

Largura primeiro e profundidade primeiro certamente têm o mesmo comportamento de pior caso (o nó desejado é o último encontrado). Eu suspeito que isso também seja verdade para o caso médio, se você não tiver informações sobre seus gráficos.

Um bom bônus da primeira pesquisa de largura é encontrar caminhos mais curtos (no sentido de menos arestas) que podem ou não ser interessantes.

Se a classificação média de nós (número de vizinhos) for alta em relação ao número de nós (ou seja, o gráfico é denso), a largura em primeiro lugar terá grandes filas, enquanto a profundidade em profundidade terá pequenas pilhas. Em gráficos esparsos, a situação é invertida. Portanto, se a memória é um fator limitante, o formato do gráfico em questão pode ter que informar sua escolha da estratégia de pesquisa.

Rafael
fonte
O comprimento da fila em bfs e a altura da pilha em dfs depende muito da implementação. Se no caso de dfs, você sempre expande toda a vizinhança na pilha, ela cresce muito, especialmente quando o gráfico é denso. Pressionar apenas a referência que informa onde continuar quando o dfs retorna da recursão economiza muito espaço.
1313 uli
3

Todas as opções acima estão corretas, mas é digno de nota que o BFS e o DFS criam suas próprias árvores, com base na ordem que eles usam para atravessar a árvore. Cada uma dessas árvores tem sua própria propriedade, que pode ser útil em algum tipo de problema.

Por exemplo, todas as arestas no gráfico original que não estão na árvore BFS são arestas transversais; arestas entre dois ramos da árvore BFS. Todas as arestas no gráfico original que não estão na árvore DFS são arestas traseiras; arestas que conectam dois vértices em uma ramificação da árvore DFS. Tais propriedades podem ser úteis para problemas como corantes especiais, etc.

MMS
fonte
1

A árvore DFS e BFS possui propriedades exclusivas que podem fornecer informações mais úteis sobre o gráfico. Por exemplo, com um único DFS, você pode fazer o seguinte:

  • Encontre pontes e pontos de articulação (para gráficos não direcionados)
  • Detecção de ciclo
  • Encontre componentes fortemente conectados (algoritmo de Tarjan)

Com o BFS, você pode encontrar os caminhos mais curtos entre o nó de origem e quaisquer outros nós no gráfico.

O capítulo Algoritmos de gráfico no CLRS resume essas propriedades do DFS e BFS muito bem.

Pitada
fonte
-2

Eu acho que seria interessante escrever os dois de uma maneira que somente alternando algumas linhas de código lhe desse um algoritmo ou outro, para que você veja que seu dillema não é tão forte quanto parece ser a princípio .

Pessoalmente, gosto da interpretação do BFS como inundação de uma paisagem: as áreas de baixa altitude serão inundadas primeiro e somente então as áreas de alta altitude se seguirão. Se você imaginar as altitudes da paisagem tão isoladas quanto os livros de geografia, é fácil ver que o BFS preenche toda a área sob o mesmo isoline ao mesmo tempo, assim como seria com a física. Assim, interpretar altitudes como distância ou custo escalonado fornece uma idéia bastante intuitiva do algoritmo.

Com isso em mente, você pode adaptar facilmente a ideia por trás da primeira pesquisa de largura para encontrar facilmente a árvore de abrangência mínima, o caminho mais curto e também muitos outros algoritmos de minimização.

Ainda não vi nenhuma interpretação intuitiva do DFS (apenas a padrão sobre o labirinto, mas não é tão poderosa quanto a do BFS e a inundação); portanto, para mim, parece que o BFS parece se correlacionar melhor com os fenômenos físicos, conforme descrito acima, enquanto O DFS se correlaciona melhor com o dillema de escolhas em sistemas racionais (ou seja, pessoas ou computadores decidindo qual mover-se em um jogo de xadrez ou sair de um labirinto).

Então, para mim, a diferença entre mentiras sobre qual fenômeno natural melhor combina com seu modelo de propagação (transversal) na vida real.

user5193682
fonte
2
Bem vindo ao site! No entanto, eu realmente não vejo como isso responde à pergunta. Parece ser seus sentimentos e intuições gerais sobre BFS e DFS, mas a pergunta não é sobre sentimentos e intuições: é sobre vantagens e desvantagens. Sua resposta parece não abordar isso.
precisa saber é o seguinte
A parte mais ligada à questão é sobre a adaptação do algoritmo para encontrar árvores abrangentes mínimas, caminho mais curto e assim por diante, e dizer que alguns fenômenos naturais são reproduzíveis pelo BFS, enquanto árvores de decisão pelo DFS
user5193682
1
A questão não está perguntando o que está relacionado ao BFS e DFS. Não se trata de encontrar árvores abrangendo ou caminhos mais curtos ou como "reproduzir fenômenos naturais".
precisa saber é o seguinte
Está pedindo vantagens. Se alguém pode modelar um fenômeno físico enquanto o outro não pode, é uma vantagem se você precisar modelar esse fenômeno. Acho que você está aderindo aos conceitos padrão de algoritmos livro ao interpretar a palavra 'vantagem', enquanto eu não sou
user5193682