Heuristica

Inteligência artificial

Algoritmos de busca: O objetivo de uma busca é encontrar encontrar uma solução da forma mais rápida ao mesmo tempo tendo o menor custo possível.

Existe uma grande família de algoritmos do tipo BUSCA-PELA-MELHOR-ESCOLHA, cada um desses algorítimos com funções de avaliação diferentes.

Normalmente estes algoritmos são avaliados de acordo com sua: completude (se conseguem chegar a uma solução); otimalidade (que diz respeito a encontrar a solução ótima); complexidades de tempo e de espaço;

Um componente fundamental desses algoritmos e uma função, representada por h(n). h(n) ---> Custo estimado do caminho mais econômico até um nó objetivo.

Busca Heurística:
O que é?
“. . .”
Heurística = capacidade de resolver problemas.

Busca heurística é uma busca com informação. Essa informação serve para mostrar qual é o sucessor mais promissor par atingir o objetivo.

Estima qual é o melhor nó da fronteira a ser expandido com base em funções heurísticas. Função Heurística:
Toma um nó como entrada e depende apenas desse nó.
Estima o custo do caminho mais barato do estado atual até o objetivo final mais próximo.
São específicas para cada problema.

Uma boa função heurística deve ser admissível e nunca superestimar o custo real da solução.

Deverá levar em conta o objetivo para decidir qual o caminho escolher.

Como encontrar um barco perdido?

Busca cega: Procura no oceano inteiro;

Busca heurística: Faz a procura utilizando informações relativas ao problema;

Exemplo: ventos, correntes marítimas.

Estratégias Utilizam conhecimento específico do problema na escolha do próximo nó a ser expandido.
Aplicação
Essa função estima o custo de caminho do nó atual até o objetivo mais próximo utilizando uma função heurística.

Dentre os algorítimos que usam heurística temos os do tipo BUSCA-PELA-MELHOR-ESCOLHA dentre eles:
Busca Gulosa;
Busca A*;

Busca Gulosa

É um tipo de busca que