Aestrela

Implementação do algoritmo A* EM LISP

O algorítmo A* é uma busca do tipo branch & baund com estimativa de distância restante combinada com o princípio da programação dinâmica. Este algorítmo produz uma solução ótima quando a estimativa da distância restante for menor que a distância real, ou seja, o algorítmo será ótimo (caso exista um caminho, ele sempre será o de menor custo, examinando o menor número de nós).

Ex:

Representação da Árvore: (S 0 ( A 3 ( B 4 ( C 4 ) ( E 5)) ( D 5 ( E 2 ( B 5) ( F 4 )))) ( D 4 ( A 5 ( B 4 )) (E 2 ( B 5 ) ( F 4 ( G 3 )))))

ESTIMATIVAS:

Representação das Estimativas: ( (C 4) (B 6,7) (A 10,4) (S 11) ( D 8,9) (E 6,9) (F 3))

Princípio da Programação dinâmica: Na procura do melhor caminho de S para G, todos os caminhos de S para qualquer nó intermediário I, exceto os de comprimento mínimo podem ser ignorados.

O ALGORÍTMO A*

Para todo nó n, temos:

 (n) = g(n) + h(n), onde g - custo do menor caminho percorrido; h - custo estimado para chegar ao nó destino.

Entrada: ARVORE ESTIMATIVAS

Procedimento:
1. Ler ARVORE, DESTINO e ESTIMATIVAS
1. Inserir o nó raiz em ABERTOS que deve estar ordenado como uma fila de prioridade:
ABERTOS  (NORAIZ g)
1. CAMINHO  nil
1. FECHADOS  nil
1. MENORCUSTO  0
1. MELHORNO  nil;
1. Enquanto ABERTOS <> nil faça
MELHORNO  primeiro da fila em ABERTOS
ABERTOS  ABERTOS - MELHORNO
CAMINHO  CAMINHO U MELHORNO
FECHADOS  FECHADOS U MELHORNO
MENORCUSTO  MENORCUSTO + custo do melhor no
Se MELHORNO = DESTINO, então Sucesso! Imprima CAMINHO, CUSTO e abandone
Para todo SUCESSOR J de MELHORNO faça Calcule  (n) = g(n) + h(n) Se NOSUCESSORABERTOS e NOSUCESSOR FECHADOS Então INCLUIR NOSUCESSOR EM ABERTOS Senão Se NOSUCESSOR  ABERTOS e (NOSUCESSOR) <  (no em abertos)
Então
ABERTOS  ABERTOS -