Best-First Search

Fronteira <- { Estado Inicial }
Enquanto True
    Se não tem o que expandir Então Retorna Falha
    Nó <- Retira_Um( Fronteira ,  Funcao_Avaliacao(Nó) )
    Se chegou em Estado Meta Então Retorna Solução
    Senão  Fronteira <- Fronteira + Expande(Nó)

Função de Avaliação [ f(Nó) ]

- f(Nó) = g(Nó) : Custo até o Nó - Dijkistra  // Não é busca heurística
- f(Nó) = h(Nó) : Previsão de custo do nó atual até uma meta. - Greedy Search
- f(Nó) = g(Nó) + h(Nó) : A*

Greedy Search

Exemplos de Heurística:

Caminho Mínimo
- Distância em Linha Reta
8-Puzzle
- h1 - Total de peças fora do lugar
- h2 - Distância de Manhattan (Distância da peça sem contar diagonais).
Cubo Mágico
- Procurar informações sobre o programa ABSOLVER (Descobriu automaticamente uma heurística)

Problemas:

- Não garante melhor solução
- Não garante completude.
(Ver exemplo com distância em linha reta).

A*

Heurística Admissível
- Custo previsto nunca é maior que o custo real.

Monotonicidade (Não descresce).
- Custo Previsto nunca decresce.
- Função PATHMAX garante monotonicidade

Não possui as desvantagens do Greedy.

Eficiência das Heurísticas:

 

		CUSTO DA BUSCA
d	IDS	A*(h1)	A*(h2)
2	10	6	6
4	112	13	12
6	680	20	18
8	6384	39	25
10	47127	93	39
12	364404	227	73
14	3473941	539	113
16	-	1301	211
18	-	3056	363
20	-	7276	676
22	-	18094	1219
24	-	39135	1641

Dados estatísticos sobre 100 diferentes instância do 8-puzzle.

Fator de Ramificação Efetivo:

IDS - 3.78
A*(h1) - 1.46
A*(h2) - 1.26

* Pode ser usado em previsões sobre o desempenho do algoritmo.

IDA*

Iterative Deepening A*
Eficiente quando valores de f(Nó) repetem-se com freqüência.
(No pior caso, pode inserir apenas um novo nó a cada iteração).