teste

Defina com suas próprias palavras os seguintes termos:
a) Estado;
b) Espaço de estados;
c) Árvore de busca;
d) Nó de busca;
e) Estado objetivo;
f) Função sucessor;
g) Custo do caminho.

2. Descreva o estado inicial, o estado objetivo, a função sucessor e a função de custo para os problemas (Escolha uma formulação que seja precisa o bastante para ser implementada):
a) Você tem um programa que lhe dá a mensagem “Registro de entrada ilegal” quando lhe é fornecido um certo arquivo de entrada. Você sabe que o processamento de cada registro é independente dos outros. Você quer descobrir que registro é ilegal.
b) Você tem três jarros, medindo 12 litros, 8 litros e 3 litros e uma fonte de água. Você pode encher ou esvaziar os jarros de um para o outro ou no chão. Você quer medir exatamente um litro.

3. Qual é a diferença entre uma busca informada e uma busca não informada?

4. Como se avalia, geralmente, as estratégias de busca (critérios)?

5. Quais são os principais métodos de busca cega? Porque são chamados “métodos de busca cega”?

6. Explique rapidamente cada uma das estratégias de busca abaixo e o desempenho de cada uma delas.
a) Busca em profundidade.
b) Busca em largura (ou em amplitude, ou em extensão).
c) Busca heurística pelo melhor primeiro (gulosa).
d) Busca A*.

7. Dê um exemplo de problema em que a “busca em largura” funcionaria melhor do que a “busca em profundidade”. Dê um exemplo de problema em que a “busca em profundidade” funcionaria melhor do que a “busca em largura”. Justifique os exemplos.

8. O que é uma heurística? E uma heurística admissível? E uma heurística consistente? Toda heurística consistente é também admissível?

9. Quais são as condições para que a busca A* seja ótima e completa?

10. Considere o espaço de busca a seguir. Cada nó é rotulado por uma letra. Cada nó objetivo é representado por um círculo duplo. Existe uma heurística estimada para cada dado nó (indicada por um valor ao lado do nó). Arcos