Metódos de Busca | Zé Moleza
Você está em Início » Metódos de Busca
3259 palavras
É uma estratégia simples em que o nó raiz é expandido primeiro, em seguida todos os sucessores do nó raiz são expandidos, depois os sucessores desses nós e assim Por diante. Em geral todos os nós em uma dada profundidade são expandidos antes que todos os nós no nível seguinte sejam expandidos. Em teoria essa é a melhor e mais completa solução para a nossa busca, pois todos os nós serão visitados até que se encontre o objetivo.
Agora vamos supor que nossa árvore tenha uma profundidade de nível 14:
Figura 1. Busca em extensão em uma árvore binária simples. Em cada fase, o nó a ser expandido em seguida é indicado por um marcador.
2 1100 0,11s 1 mbytes
6 10 ^7 19s 10 gbytes
12 10^13 35 anos 10pbytes
14 10^15 3.523 anos 1 ex
Existem duas lições a serem aprendidas a partir da fig. Acima, em primeiro lugar, os requisitos de memória são um problema maior para busca em extensão do que o tempo de execução. Trinta e uma horas não seria tempo demais para se esperar pela solução de um problema importante de profundidade 8, mas poucos computadores tem a memória principal da ordem de terabytes que ele exigiria. A segunda lição é que os requisitos de tempo ainda constituem um fator importante.Se seu problema tem uma solução na profundidade 12, então ele demorar 35 anos para que a busca o…