A Inteligência Artificial

Inteligência Artificial

Metodologias de Busca

● Um problema pode ser considerado como um objetivo

● Um conjunto de ações pode ser praticado 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

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.

– 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

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.

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,

● A busca retrocederá ao primeiro nó anterior que tenha um caminho não explorado

● Utiliza um método chamado de retrocesso cronológico:

● Volta na árvore de busca, uma vez que um caminho sem saída seja encontrado

● É assim chamado por desfazer escolhas na ordem contrária ao momento em que foram tomadas

● É um método de busca exaustiva ou de força bruta

Exemplo

Ordem: A, B, D, H, I, E, C, F, G

Busca em Largura (Extensão)

● Percorre a árvore em largura ao invés de profundidade

● Começam examinando todos os nós de um nível abaixo do nó raiz

● Se não encontrar o objetivo, buscam um nível abaixo

● Melhor em árvores que tenham caminhos mais profundos

● Utilizado em árvores de jogos

Exemplo

Comparação

Cenário Profundidade Largura

Caminhos muito longos ou infinitos Funciona mal Funciona bem

Caminhos com comprimentos parecidos Funciona bem Funciona bem

Todos caminhos tem comprimentos parecidos e todos levam a um estado objetivo Funciona bem Desperdício de tempo e memória

Alto fator de ramificação O desempenho depende de outros fatores Funciona precariamente

O problema de caminhos infinitos pode ser evitado na busca em profundidade pela aplicação de um limiar de profundidade

Propriedades dos métodos de busca

● Complexidade:

● Ligado ao tempo e espaço utilizados na busca; ● Completude:

● Se é completo, ou seja, se sempre acha o objetivo;

● Obs.: se houver objetivo; ● Quanto a ser ótimo:

● Garantir achar a melhor solução que exista; ● Não garante que seja pelo menor caminho ou tempo. ● Admissibilidade:

● Garantir achar a melhor solução pelo melhor caminho. ● Irrevogabilidade:

● Não retrocedem, examinando assim somente um caminho.

Humanos utilizam busca em profundidade

● É o modo mais fácil e natural;

● Exemplos:

● Percorrendo um labirinto;

● Comprando um presente em um shopping;

Implementando a busca...

Profundidade:

Lista = []

Estado = no_raiz; Repita:

Se eh_objetivo( estado ) Então retorne SUCESSO

Senão inserirNaFrenteDaLista(sucessores(estado))

Se Lista estiverVazia

Então retorne FALHA

Estado