Aula 04 Busca Com Informa O I

Inteligência Artificial
Aula 04 – Busca com informação ou heurística Métodos de busca
! Busca Cega ou Exaustiva:
– Não sabe qual o melhor nó da fronteira a ser expandido. Apenas distingue o estado objetivo dos não objetivos.

• Busca Heurística:
– Estima qual o melhor nó da fronteira a ser expandido com base em funções heurísticas.

• Busca Local:
– Operam em um único estado e movem-se para a vizinhança deste estado. Busca com informação
(ou heurística)
• Utiliza conhecimento específico sobre o problema para encontrar soluções de forma mais eficiente do que a busca cega.
– Conhecimento específico além da definição do problema.

• Abordagem geral: busca pela melhor escolha.
– Utiliza uma função de avaliação para cada nó.
– Expande o nó que tem a função de avaliação mais baixa.
– Dependendo da função de avaliação, a estratégia de busca muda.

Busca Heurística
• Como encontrar um barco perdido?
– Busca Cega -> Procura no oceano inteiro.
– Busca Heurística -> Procura utilizando informações relativas ao problema.
• Exemplo: correntes marítimas, vento, etc.

Busca Heurística
• Função Heurística (h)
– Estima o custo do caminho mais barato do estado atual até o estado final mais próximo.
– São específicas para cada problema.

• Exemplo:
– Encontrar a rota mais curta entre duas cidades:
• h(n) = distância

Busca Heurística
• Algoritmos de Busca Heurística:
– Busca Gulosa (ou Busca Gulosa pela melhor escolha)
– A*

Busca Gulosa
• Estratégia:
– Expande os nós que se encontram mais próximos do objetivo (uma linha reta conectando os dois pontos no caso de distancias), desta maneira é provável que a busca encontre uma solução rapidamente.

• A implementação do algoritmo se assemelha ao utilizado na busca cega, entretanto utiliza-se uma função heurística para decidir qual o nó deve ser expandido.
• Função de avaliação f(n) = h(n) (heurística) = estimativa do custo de n até o objetivo

Busca Gulosa
• Exemplo:

Busca Gulosa

Arad

366