Busca em profundidade

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (358 palavras )
  • Download(s) : 0
  • Publicado : 18 de abril de 2013
Ler documento completo
Amostra do texto
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:...
tracking img