Busca Heurística

Universidade Estadual de Goiás

Novas Aplicações de Sistemas de Informação

Trabalho

Dentro da problemática apresentada, foi selecionada o método de busca por A*.

O A* busca o menor caminho dentre os estados.

Será solicitado ao usuário informar os pontos iniciais e final para que o algoritmo de busca mencioando calcule a melhor e menor opção.

Supondo que o usuário escolha ARAD como a cidade inicial, o algoritmo buscará os menores caminhos dentre as diversas possibilidades de caminho, até chegar nosso ponto final (BUCARESTE).

Avalia os nós do espaço combinando g(n), que representa o custo para alcançar cada nó e h(n), o custo para ir do nó atual até o nó final.

Representamos com a função :

f(n) = g(n) + h(n)

Nenhum outro algoritmo ótimo garante expandir menos nós.

Custo de tempo:

– Embora seja uma estratégia completa e ótima é considerada exponencial com o comprimento da solução, porém boas funções heurísticas diminuem consideravelmente esse custo.

• Custo memória: O(bd)

– Olha para o futuro, mas não perde o passado: Guarda todos os nós expandidos na memória.

Pseudo – Codigo

Require: noAlvo

Require: noInicial

lista.Adiciona(noInicial, 0) // adiciona o nó inicial na lista e o custo 0

loop

menorCaminho⇐ selecionaCaminho(lista) // Caminho = caminho de menor custo

noCorrente ⇐ selecionaUltimoNo(menorCaminho)

if noCorrente = noAlvo then

QUIT

end if

lista.Apaga(menorCaminho) // apaga o caminho de menor custo da lista

for noCorrente ⇒ noSucessor do

G = custo(noInicial, noSucessor) // Custo do nó inicial até o nó corrente

H = heurística(noSucessor, noAlvo) // Custo estimado do nó sucessor até o nó alvo

caminho ⇐ menorCaminho + noSucessor

custo ⇐ G + H

lista.Adiciona(caminho, custo) // adiciona a lista os novos caminhos candidatos e o

//custo deles

end for

end loop