busca em profundidade

Inteligência Artificial
Metodologias de Busca

1

Solução de problemas como Busca
●
●

●

Um problema pode ser considerado como um objetivo
Um conjunto de ações podem ser praticadas para alcançar esse objetivo
Ao buscar um objetivo, estamos em um determinado estado
●
●

●

O estado inicial é quando iniciamos a busca
O estado que satisfaz a meta é o estado objetivo

Busca
●

●

Método que examina o espaço de um problema, buscando um objetivo

O espaço de um problema é seu Estado de Busca

2

Busca guiada por
Dados ou Objetivos
●

Abordagens para fazer uma árvore de busca
●

De-cima-para-baixo:
–
–
–

●

Encadeamento para frente;
Busca guiada por Dados;
Parte de um estado inicial e usa ações permitidas para alcançar o objetivo.

De-baixo-para-cima
–
–
–

Encadeamento para trás;
Busca guiada por Objetivos;
Começa de um objetivo e volta para um estado inicial, vendo quais deslocamentos poderiam ter levado ao objetivo.
3

Busca guiada por
Dados ou Objetivos

●

Ambas atingem o mesmo resultado;

●

Um dos métodos pode ser mais rápido que o outro
–

Depende da natureza do problema

4

Metodologias
●

Gerar e Testar – técnica de busca cega
●
●

●

●

A mais simples abordagem de busca;
Funcionamento: gerar cada nó no espaço de busca e testá-lo para verificar se este é um nó objetivo;
É a forma mais simples de busca de força bruta ou busca exaustiva;

Precisa de um Gerador que satisfaça:
●

●

●

Ele deve ser completo, garantir que todas as soluções possíveis serão geradas. Pois assim não descartará uma solução adequada;
Ele não deve ser redundante, não gerando a mesma solução duas vezes; Ele deve ser bem informado, só deve propor soluções adequadas e que combinem com o espaço de busca.

5

Busca em Profundidade
●

●

Segue cada caminho até sua maior profundidade antes de seguir para o próximo caminho
Se a folha não representar um estado objetivo,
●