Algoritmos de Busca Buscas Heurísticas

Buscas Heurísticas

Palavra originada do grego “heuriskein” (descobrir). É a forma mais comum de aplicar conhecimento adicional do problema ao algoritmo de busca. Foi introduzida em Inteligência Artificial por George Polya em 1957 através do livro "How to Solve It".

A busca por heurísticas é uma busca realizada por meio da quantificação de proximidade a um determinado objetivo. Tem-se uma boa (ou alta) heurística se o objeto de avaliação está muito próximo do objetivo, do mesmo modo, diz-se de má (ou baixa) heurística se o objeto avaliado estiver muito longe do objetivo.

Simplificando, através das informações sobre o problema esse tipo de busca decide qual nó deve ser expandido na sequência. Essas informações são usadas para definir a função Heurística que será usada, desse modo, a função heurística varia de problema para problema.

Existem vários algoritmos heurísticos para serem implementados, estes algoritmos serão falados posteriormente ao decorrer deste trabalho, mas por hora vamos apenas destacar as Buscas Gulosas, que não é ótima porque escolhe o nó mais próximo a primeira vista, destacaremos também a busca A* que é completa e ótima.

Vários exemplos se aplicam a esse tipo de busca, um deles é o calculo do caminho mais curto entre duas cidades. Para esse calculo pode ser calculada a distância direta entre uma cidade n e outra final. Matematicamente temos h(n) = custo estimado do caminho mais econômico partindo do nó n até um nó objetivo. Caso nó n seja o objetivo, então h(n)=0.

Na programação podemos traduzir essas definições e criarmos um algoritmo com algumas funções que definem o algoritmo geral de Busca Heurística:

Funções Necessárias/Típicas:

Função-1: eh_estado_final(E) RETORNA /

Função-2: adjacentes(E) RETORNA [ E1 , E2 , ... , En ]

Função-3: adjacente(E) RETORNA RETROATIVAMENTE Ei [ E1, E2 , ... , En ]

 Função-4: heuristica(E) RETORNA

Busca Gulosa

        Consiste em expandir o nó mais próximo do objetivo, para dessa forma atingi-lo mais rapidamente. A palavra Gulosa é usada pelo fato do algoritmo cada vez tentar chegar mais próximo do objetivo.

Exemplo: Ir de Iasi para Fagaras:

[pic 1]

[pic 2][pic 3]

Nesse tipo de busca os nós são expandidos em níveis, até  atingir o objetivo.

Busca Best-first

A busca “Best-first”, é um procedimento não sistemático que visa como objetivo final, selecionar o menor número de nós que contemplem uma busca mais rápida. Ela usa informações específicas do domínio que indica qual “parece” ser o menor caminho para atingir o estado meta, ou seja, próximo melhor (com relação a distância)  nó a ser expandido.

Para aplicar esse procedimento, tem que ter primeiramente o conhecimento específico do problema, que pode ser representado pela função de avaliação “f(N)”. Através da função “f(n)”, incorpora-se no texto uma estimativa de custo entre o nó concorrente e o estado meta, recebendo descrições de estados, e desenvolvendo um valor real.

...