Tip:
Highlight text to annotate it
X
Já vimos dois algoritmos de busca.
Primeiro, busca em largura, onde nós sempre expandimos primeiro
os caminhos mais rasos, os caminhos mais curtos.
Segundo, busca de custo uniforme, onde sempre expandimos primeiro o caminho
com o menor custo total.
E vou aproveitar esta oportunidade para introduzir um terceiro algoritmo, busca em profundidade,
que é, de certa forma, o oposto da busca em largura.
Na busca em profundidade, nós sempre expandimos o caminho mais longo primeiro,
a rota que possui mais ramos.
Agora, o que irei pedir para vocês fazerem é, para cada um destes nós em cada um destas árvores,
nos indicar em qual ordem eles são expandidos,
primeiro, segundo, terceiro, quarto, quinto e assim por diante, colocando o número nas respectivas caixas.
E em caso de empate, coloque os números considerando a ordem de visita da esquerda para a direita.
Depois quero que façam mais uma pergunta, ou respondam mais uma pergunta
que é se estas buscas são ótimas.
Ou seja, é garantido que elas irão encontrar a melhor solução?
Para a busca em largura, ótima significa encontrar o caminho mais curto.
Se você acredita que é garantido o encontro do caminho mais curto, marque aqui.
Para a busca de custo uniforme, significa encontrar o caminho com o menor custo total.
Marque aqui se você acha que isto é garantido por este algoritmo
Sendo permitida a hipótese de que todos os custos são positivos.
E a busca em largura, menor custo ou ótima significa, novamente,
assim como na busca em largura, o caminho com o menor número de ramos.
Marque aqui caso considere que a busca em largura sempre encontrará este caminho.