Na busca informada, o processo de escolha de um estado é acompanhado de um processo de avaliação. A estratégia de controle de um processo de avaliação utiliza o conhecimento específico do problema, além da definição do próprio problema, e pode encontrar soluções de forma mais eficiente que uma estratégia sem informação.

O algoritmo geral de busca que utiliza esta estratégia de avaliação é chamado de algoritmo “best-first” ou busca pela melhor escolha. Na busca pela melhor escolha, um nó n é selecionado para expansão (é visitado) com base na sua função de avaliação, denotada por f(n). A função de avaliação f(n) mede a distância do nó n até um nó objetivo, fornecendo uma medida de qualidade ao vértice n. Geralmente, é selecionado o nó n com a função de avaliação mais baixa e dizemos que n é o vértice mais promissor, ou seja, o vértice que tem maior possibilidade de pertencer ao caminho ótimo. Logo, esta busca utiliza uma fila de prioridades que é ordenada por valores crescentes de f.

Um componente fundamental dos algoritmos de busca pela melhor escolha, é a função heurística, denotada por h(n), que informa o custo estimado do caminho mais econômico do nó n até um nó objetivo. Portanto, se n é um nó objetivo então h(n) = 0. As funções heurísticas são a forma mais comum de aplicar conhecimento adicional do problema ao algoritmo de busca.

A heurística h(n) é dita admissível se ela nunca superestimar o custo para o nó n alcançar o objetivo, ou seja, se estimar que o custo da resolução do problema seja menor do que ele é na realidade.

Uma heurística h(n) é consistente (monotonicidade) se, para todo nó n e todo sucessor m de n, o custo estimado de alcançar o objetivo a partir de n (h(n)) não é maior que o custo do passo de sair de n e chegar a m (C(n, m)) somado ao custo estimado de alcançar o objetivo a partir de m (h(m)):

Isto é chamado de desigualdade de triângulos, que estipula que cada lado de um triângulo não pode ser maior que a soma dos outros dois lados. No caso, o triângulo é formado por n, m e o objetivo mais próximo a n.

Tem-se que toda heurística consistente também é admissível, mas o contrário não é verdadeiro. Dizemos que um algoritmo de busca é admissível se, para qualquer grafo de estados, ele encontra a solução ótima, se ela existir.

1. Busca Gulosa

A busca gulosa tenta expandir o nó mais próximo à meta. Ela avalia o nó usando apenas a função heurística: f(n) = h(n).

1.1. Problema 1

No grafo abaixo, as cidades A, B, C, D e E representam cidades de uma região e os valores aos lados das arestas representam as distâncias ao longo das rodovias entre as cidades. Nosso problema seria encontrar um caminho entre as cidades A e D.

Vamos utilizar como função heurística a distância aérea ou DLR (distância em linha reta) entre cada cidade e a cidade objetivo – no caso D. Evidentemente, a distância em linha reta entre duas cidades é menor que (ou na melhor hipótese, igual) a distância medida na rodovia. Então, com essa estimativa, temos que a heurística h(n) é admissível.

Vértice	A	B	C	D	E
h (DLR)	4	3	2	0	1

1.2. Problema 2

Dado o mapa de parte da Romênia abaixo, considere a tabela, ao lado, que apresenta as distâncias aéreas (DLR) até Bucareste das cidades presentes no mapa:

Aplique a busca gulosa para encontrar um caminho de Arad até Bucareste.

A busca gulosa é semelhante à busca em profundidade pelo fato de preferir seguir um único caminho até um objetivo, mas “voltará” ao encontrar um estado de impasse. Ela tem os mesmos defeitos da busca em profundidade:

2. Busca A*

A busca A* avalia os nós combinando o custo para alcançar cada nó n e o custa para ir do nó n até o nó objetivo: f(n) = g(n) + h(n).

O algoritmo visita primeiro o nó com o menor valor de avaliação – f – a fim de encontrar a solução de custo mais baixo.

A busca A* será ótima (encontra a melhor solução) se a heurística h(n) for admissível. A distância aérea (DLR) entre duas cidades é um exemplo de heurística admissível, porque o caminho mais curto entre dois pontos é uma linha reta passando por eles. Seja C* o custo da solução ótima e suponha que um nó objetivo não-ótimo t apareça na lista de abertos. Então, sabemos que h(t) = 0 e como t não é ótimo, segue que: f(t) = g(t) + h(t) = g(t) > C*. Agora, considere um nó n na lista de abertos que pertence a um caminho de solução ótimo, se h(n) é admissível, temos que f(n) = g(n) + h(n) >= C*. Com isso, mostramos que f(n) ? C* < f(t) e assim temos que t não será visitado e A* deve retornar uma solução ótima.

Se h(n) é consistente, então os valores de f(n) ao longo do caminho são não-decrescentes: f(m) = g(m) + h(m) = g(n) + C(n, m) + h(m) >= g(n) + h(n) = f(n), onde m é sucessor de n. Logo, só serão fechados pelo A* os vértices n tais que f(n) ? C* e os vértices na lista de fechados estão por valores crescentes de f.

Segue que a lista de abertos em A* fica ordenada por valores crescentes de f(n). Assim, o primeiro nó objetivo visitado tem de ser uma solução ótima. Além disso, tem-se que A* não expande nenhum nó n cuja f(n) > C*. Então, dizemos que a sub-árvore abaixo de n foi podada (o conceito de poda consiste em deixar de considerar certas possibilidades sem ter de examiná-las).

2.1. Problema 1

Aplique a busca A* para encontrar um caminho da cidade A até a cidade D. Os valores de g(n) são calculados a partir das distâncias ao longo das rodovias entre as cidades presentes no grafo do item 1.1 e os valores de h(n) são dados na tabela abaixo do grafo.

2.2. Problema 2

Aplique a busca A* para encontrar um caminho de Arad até Bucareste. Os valores de g(n) são calculados a partir das distâncias ao longo das rodovias entre as cidades do mapa do item 1.2 e os valores de h(n) são dados na tabela ao lado do mapa.

3. Busca IDA* ou AIA* - Algoritmo A* de aprofundamento iterativo.

O caminho mais simples de reduzir requisitos de memória de A* é adaptar a idéia de aprofundamento iterativo ao contexto de busca heurística, resultando no algoritmo IDA* ou AIA*.

A principal diferença entre o algoritmo IDA* e a busca em profundidade iterativa, é que o corte usado é o valor de f (g+h) em vez da profundidade. O IDA* utiliza um valor de corte chamado patamar. A cada iteração, são expandidos os vértices n cujas f(n) ? patamar e sempre que for gerado um vértice m com f(m) > patamar, este é inserido em uma lista de descartados. Na primeira iteração, o valor de patamar é f(S), sendo S o estado inicial (raiz da árvore de busca), e, nas iterações seguintes, o valor de patamar é o menor custo f(n), dentre todos os nós n presentes na lista de descartados (lista que contém qualquer vértice que tenha excedido o corte na iteração anterior).

O IDA* constrói a árvore de busca da mesma forma que o backtracking, gerando um filho de cada vez, mas utilizas o patamar como limite de profundidade. Se a heurística h(n) for consistente, temos que o algoritmo IDA* encontra a solução ótima, e o seu tempo de processamento tende, assintoticamente, ao tempo de processamento do A*.

3.1. Problema 1

Aplique a busca IDA* para encontrar um caminho da cidade A até a cidade D. Os valores de g(n) são calculados a partir das distâncias ao longo das rodovias entre as cidades presentes no grafo do item 1.1 e os valores de h(n) são dados na tabela abaixo do grafo.

3.2. Problema 2

Aplique a busca IDA* para encontrar um caminho de Arad até Bucareste. Os valores de g(n) são calculados a partir das distâncias ao longo das rodovias entre as cidades do mapa do item 1.2 e os valores de h(n) são dados na tabela ao lado do mapa.

4. Funções Heurísticas

Para entendermos a natureza das heurísticas em geral, vamos considerar duas heurísticas, comumente utilizadas, para o Jogo dos 8:

Ex.: No nosso exemplo temos que h2 do estado inicial é: h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18.

Temos que h2 é admissível porque o resultado de qualquer movimento é deslocar o número o mais próximo do objetivo.

É fácil verificar que para qualquer nó n, h2(n) >= h1(n). Então, dizemos que h2 domina h1 e a dominância se traduz, diretamente, em eficiência: A* usando h2 não expandirá mais nós que A* usando h1. Conseqüentemente, sempre é melhor usar uma função heurística com valores mais altos, desde que ela não superestime o custo real e que o tempo de computação da heurística não seja muito grande.

Mas como criar funções heurísticas admissíveis?

Se as regras do jogo dos 8 fossem alteradas de forma que um número pudesse se deslocar para qualquer lugar, e não apenas para o quadrado vazio adjacente, então h1 forneceria o número exato de passos da solução mais curta. De modo semelhante, se um número pudesse se mover em qualquer direção, mesmo sobre um quadrado ocupado, então h2 forneceria o número exato de passos na solução mais curta. Um problema com menos restrições sobre as ações é chamado problema relaxado. O custo de uma solução ótima para um problema relaxado é uma heurística admissível para o problema original. Isto porque a solução ótima no problema original também é, por definição, uma solução no problema relaxado e, tem de ser pelo menos tão dispendiosa quanto a solução ótima no problema relaxado. Uma vez que a heurística é um custo exato para o problema relaxado, então ela deve obedecer à desigualdade de triângulos e, portanto, deve ser consistente.

Por exemplo, se as ações do josgo dos 8 forem descritas como :

Um número pode se mover do quadrado A para o quadrado B se

Podemos gerar três problemas relaxados removendo uma ou ambas as condições:

a) Um número pode se mover do quadrado A para o quadrado B se A é adjacente a B.
b) Um número pode se mover do quadrado A para o quadrado B se B está vazio.
c) Um número pode se mover do quadrado A para o quadrado B.