Nesta história, vou comparar os dois algoritmos comumente usados para a fundação de inteligência artificial e redes neurais, nomeadamente profundidade-primeira busca e amplitude-primeira busca. Caso não tenha compreendido estes dois algoritmos, consulte os meus outros artigos para uma instrução de 5 minutos e será capaz de os compreender.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
Primeiro, ambos são algoritmos de busca não informados, o que significa que operam em modo de força bruta e não possuem informações adicionais sobre o estado ou espaço de busca além de como atravessar a árvore. Se você leu meus artigos anteriores sobre DFS ou BFS, você sabe que nenhum deles vai olhar para o peso de cada passo durante o processo de busca.
- Runtime: Ambos os algoritmos operam em O(n) como no pior caso, eles precisarão visitar cada nó no espaço de busca.
- when DFS>BFS: Se o nó que estamos procurando é muito profundo ou existem vários nós de objetivo que são bem profundos, nós devemos usar DFS. Neste caso, BFS tem que visitar todos os nós acima antes de visitar os nós profundos, o que leva muito tempo.
- when BFS>DFS: BFS pode ser usado para encontrar o caminho mais curto em um gráfico não-ponderado, porque em BFS, chegamos a um vértice com um número mínimo de bordas de um vértice fonte. Por outro lado, na DFS, podemos atravessar mais bordas para chegar a um vértice de destino a partir de um vértice de origem.
- search type: ambos são busca não informada
- memory comparison: BFS vai levar mais memória porque tem que voltar atrás mais do que DFS em geral.
- estrutura de dados: O DFS usa uma pilha, que contém nós da raiz para o nó que está sendo pesquisado. BFS usa uma fila, que contém nós na frente da pesquisa.