inteligencia

INF 1771 – Inteligência Artificial
Aula 04 – Busca Heurística

Edirlei Soares de Lima

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 Heurística
• Algoritmos de Busca Heurística:
– Busca Gulosa
– A*
• A busca heurística leva em conta o objetivo para decidir qual caminho escolher.
• Conhecimento extra sobre o problema é utilizado para guiar o processo de busca.

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 em linha reta direta entre o nó n e o nó final.

Função Heurística

Estado Atual

Estado Objetivo

Busca Heurística
• Algoritmos de Busca Heurística:
– Busca Gulosa
– 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.

Busca Gulosa
Arad
366

Sibiu

Timissoara

Zerind

253

329

374

Arad
380

193

Sibiu

Bucharest

263

0

Função Heurística (h):
Distancia em linha reta

234

160

Oradea

380

242