Tip:
Highlight text to annotate it
X
Dado que a busca em profundidade não é ótima,
por que alguém a utilizaria?
Bem, a resposta tem a ver com os requisitos de espaço.
Vamos ilustrar um espaço de estados
que consiste em uma árvore binária bem grande, ou mesmo infinita.
Conforme descemos os níveis 1, 2, 3, até o nível n,
a árvore se torna cada vez maior.
Vamos considerar a fronteira de cada um dos algoritmos de busca.
Na busca em largura, sabemos que a fronteira é dessa forma,
então quando atingimos o nível n, precisaremos de um espaço de
2^n nós armazenados.
Já na busca pelo menor custo, a fronteira é mais complicada de se analisar.
Ela terá a forma desse contorno de custo,
mas terá um número de nós similar.
Entretanto, na busca em profundidade, conforme descemos na árvore, seguimos esse ramo,
e então voltamos. Mas em qualquer ponto, nossa fronteira terá apenas n nós,
em vez de 2^n, o que é uma economia considerável para esse método.
Mas é claro que se armazenarmos o conjunto de explorados,
então não economizamos tanto.
Mas sem o conjunto de nós explorados, a busca em profundidade oferece uma vantagem enorme
em termos de espaço.
Outra propriedade dos algoritmos que devemos considerar
é a propriedade de completude, que significa que, se há um estado objetivo em algum lugar,
o algoritmo consegue encontrá-lo?
Vamos deixar as árvores grandes e passar para árvores infinitas.
Digamos que a solução esteja em algum ponto desconhecido mais embaixo na árvore.
A pergunta é: quais dos algoritmos abordados são completos?
Isto é, eles garantidamente encontram o caminho que leva ao objetivo?
Assinale os algoritmos que você acredita que sejam completos.