Busca Em Extensao

Busca em extensão

É uma estratégia simples, onde o nó raiz é expandido primeiro, logo os sucessores do nó raiz também serão expandidos, depois os sucessores desses nós e assim por diante., ou seja, todos os nós de uma profundidade na arvore são expandido, antes que todos os nós no nível seguinte sejam expandidos.

Pode ser implementada chamando-se em Busca-em-arvore com uma borda vazia que seja uma fila do tipo FIFO ( First -in-first-out), que coloca todos os sucessores recém – gerados no final da fila , ou seja, os nós de baixa profundidade serão expandidos antes de nós mais profundos.

A busca é completa, se o nó objetivo mais raso estiver em alguma profundidade finita d , a busca em extensão eventualmente o encontrará após expandir todos os nós mais rasos . O nó mais raso não é necessariamente o nó ótimo, pois a busca será ótima se o custo de caminho for uma função não-descrecente da profundidade do nó.

Todo nó gerado deve permanecer na memória, pois fazem parte da borda ou é um ancestral de nó de borda. Dessa forma, a complexidade de espaço é igual à complexidade de tempo.

A busca em largura tem a complexidade de tempo de O(B^d), onde b é o fator de ramificação da árvore e d a profundidade do nó objetivo na árvore.

...