Busca em profundidade

Páginas: 2 (358 palavras) Publicado: 18 de abril de 2013
Busca em Profundidade
Explicação
É um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo, começando em um nó raiz e explorando tanto quanto possívelcada um dos seus ramos, antes de retroceder.
Exemplo:

Para o grafo acima, uma busca em profundidade começando em A, assumindo-se que as arestas esquerdas do grafo apresentado sejam escolhidas antesdas arestas direitas, e assumindo que a busca relembre os nós previamente visitados e que não os repita (desde que este seja um grafo pequeno), visitaremos os nós na seguinte ordem : A, B, D, F, E,C, G.
Modificando essa mesma busca, sem que nos recordemos dos nós previamente visitados, teríamos como resultado a seguinte ordem de visita dos nós: A, B, D, F, E, A, B, D, F, E, etc, eternamente,já que a busca ficaria presa no ciclo A,B,D,F,E e nunca alcançaria G ou C.
O aprofundamento iterativo previne esse looping, alcançando os seguintes nós, nas seguintes profundidades, assumindo-se queele prossiga da esquerda para a direita, como mostrado abaixo:
* 0: A
* 1: A (repetido), B, C, E
(Perceba que o aprofundamento iterativo agora enxergou C, ao passo que uma busca emprofundidade convencional não enxergaria.)
* 2: A, B, D, F, C, G, E, F
(Perceba que a busca ainda enxerga C, mas que ele vem depois. Perceba também que ele enxerga E via diferentes caminhos, e passa duasvezes pelo F .)
* 3: A, B, D, F, E, C, G, E, F, B
Para esse grafo, quanto maior for a profundidade aplicada, os dois ciclos “ABFE” e “AEFB” simplesmente ficarão maiores, antes que o algoritmodesista e tente outro ramo.

Vantagens:
Facilidade de implementação
Pouco uso de memória
Desvantagens
Pode – se demorar muito a chegar a soluções

Busca em Profundidade Limitada
DefiniçãoEste algoritmo opera como a busca em profundidade, porém ao invés de ficar examinando um determinado ramo indefinidamente, é colocado um limite na altura da árvore de busca.
Explicação e exemplos:...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Busca em Profundidade
  • busca em profundidade
  • Grafos busca em profundidade
  • Busca em Largura e Profundidade
  • PERCEBENDO PROFUNDIDADE
  • Plaqueamento por profundidade
  • Semiótica de profundidade
  • PEIXES DE PROFUNDIDADE

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!