Busca Informada: Heurísticas e o Algoritmo A*

No artigo anterior, a esforçada leitora percorreu o espaço de estados às cegas: nenhum dos quatro algoritmos usava qualquer informação sobre onde o objetivo estava. Eles expandiam nós por profundidade, por custo acumulado ou por limite, mas nunca por proximidade do alvo, simplesmente porque não tinham como medi-la. Neste artigo, damos a eles esse sentido que faltava. Uma heurística é uma estimativa de quão longe do objetivo um estado está, e um algoritmo que a use bem pode gastar uma pequena fração do trabalho de outro que ignore essa informação. A Seção 6 medirá essa diferença em uma instância concreta do 8-puzzle, com a mesma implementação, a mesma política de desempate e contagens reproduzíveis.

O ganho, porém, tem condições. Uma heurística é uma promessa sobre o futuro, e promessas podem ser honestas ou mentirosas. Uma estimativa que nunca supera o custo real é admissível e preserva a otimalidade do A* em árvore; no A* em grafo, a consistência permite fechar cada estado uma única vez, enquanto uma heurística apenas admissível exige que a implementação aceite reaberturas. Uma estimativa que superestima pode fazer o algoritmo escolher, com toda a confiança, o caminho errado. Demonstrar essas fronteiras com precisão é o coração matemático deste artigo. A atenta leitora sairá daqui sabendo não só usar o algoritmo A*, mas provar por que ele funciona e reconhecer quando uma heurística ou uma implementação o sabotaria.

Como sempre, o exemplo executável será C++23, compilado no MSVC.

1. Funções heurísticas

Uma função heurística $h(n)$ associa a cada nó $n$ uma estimativa do custo do caminho mais barato de $n$ até um estado objetivo. É uma função do estado para um número não negativo, com uma única exigência de sanidade: $h(n) = 0$ quando $n$ é um objetivo, pois não há distância a percorrer de quem já chegou. Fora isso, $h$ é livre; ela encapsula o conhecimento específico do domínio que temos sobre o problema, o palpite instruído que distingue a busca informada da cega.

Convém fixar, desde já, a notação que atravessa o artigo. Denotamos por $h^{}(n)$ o custo ótimo real de $n$ até o objetivo mais próximo, o número que uma heurística perfeita devolveria e que em geral não conhecemos, se o conhecêssemos, não precisaríamos buscar. Denotamos por $g(n)$ o custo do caminho já percorrido, do estado inicial até $n$, exatamente como no artigo anterior. A heurística $h(n)$ estima o que falta; $g(n)$ contabiliza o que já foi feito; e $h^{}(n)$ é a verdade sobre o que falta, contra a qual julgaremos as estimativas. Duas heurísticas concretas nos acompanharão, ambas para o 8-puzzle: a contagem de peças fora do lugar, que conta quantas peças não estão em sua posição final, e a distância de Manhattan, que soma, para cada peça, o número de casas que ela precisa andar na horizontal e na vertical até seu destino. As duas são estimativas do número de jogadas restantes, e compará-las será instrutivo.

2. Busca gulosa

A maneira mais direta de usar uma heurística é também a mais ingênua: expandir sempre o nó que parece mais próximo do objetivo, ou seja, o de menor $h(n)$. Esse é o algoritmo de busca gulosa pela melhor escolha (greedy best-first search), e ele é sedutor porque, quando a heurística é boa, corre direto ao alvo. A fila de prioridade da busca gulosa ordena por $h$, e não por $g$ como fazia a busca de custo uniforme.

A sedução esconde dois defeitos. A busca gulosa não é ótima: ao olhar apenas para o que falta e ignorar o que já custou, ela pode mergulhar por um caminho que começa promissor e termina caro, quando um caminho de início menos atraente seria mais barato no total. E ela não é completa em espaços com ciclos, se não guardarmos os estados explorados, porque pode oscilar entre estados que parecem próximos sem nunca chegar. O erro de fundo é claro: a busca gulosa considera $h(n)$ e esquece $g(n)$, enquanto a busca de custo uniforme fazia o oposto, considerando $g(n)$ e ignorando $h(n)$. Cada uma usa metade da informação disponível. A ideia que organiza o resto do artigo é somar as duas metades.

3. O algoritmo A*

Somar as duas metades é literalmente o que o algoritmo A* faz. Ele avalia cada nó pela função

na qual $g(n)$ é o custo já pago para chegar a $n$ e $h(n)$ é a estimativa do custo que falta a partir de $n$. A soma $f(n)$ é, então, uma estimativa do custo total do melhor caminho que passa por $n$: o que já gastamos mais o que ainda esperamos gastar. O A* expande sempre o nó de menor $f(n)$ na fronteira, usando uma fila de prioridade ordenada por $f$, e essa única escolha de projeto reúne o cuidado com o custo passado da busca de custo uniforme e o senso de direção da busca gulosa.

A Figura 1 separa as duas parcelas no próprio caminho. Essa separação evita a confusão mais comum sobre o A*: $g$ é conhecido porque pertence ao prefixo já percorrido; $h$ continua sendo uma estimativa porque pertence ao futuro.

Figura 1: O A* ordena a fronteira por $f(n)=g(n)+h(n)$, combinando o custo realizado com a estimativa do trecho restante.

O procedimento é o da busca de custo uniforme, trocando a chave de ordenação de $g$ para $g + h$. Mantemos uma fronteira como fila de prioridade e um registro do melhor $g$ conhecido para cada estado. Retiramos o nó de menor $f$; se for objetivo, terminamos; senão, para cada sucessor, calculamos o novo $g$ e, se ele melhora o valor conhecido, atualizamos e reinserimos o sucessor com prioridade $f = g + h$. Quando há empate em $f$, uma política comum é desempatar pelo menor $h$, ou equivalentemente pelo maior $g$, o que empurra a busca em direção ao objetivo em vez de espalhá-la. O desempate não altera o custo da solução quando a heurística satisfaz as condições de otimalidade, mas pode alterar muito a contagem de expansões. Por isso, qualquer número experimental precisa declarar a política de desempate e a ordem de geração dos sucessores. Os exercícios a seguir mostram o A* em ação e começam a revelar por que a escolha da heurística é tudo.

Exercícios resolvidos

Os quatro primeiros exercícios usam uma grade $4 \times 4$ com movimento nas quatro direções e custo de passo $1$. As células são pares $(\text{linha}, \text{coluna})$ com índices de $0$ a $3$; o início é $(0,0)$ e o objetivo é $(3,3)$; há paredes em $(1,1)$, $(1,2)$ e $(2,1)$. A heurística é a distância de Manhattan até o objetivo, $h(r,c) = \vert 3-r\vert + \vert 3-c\vert$.

1. Execute o A* nessa grade e exiba a ordem de expansão com os valores $g$, $h$ e $f$ de cada nó, o caminho e seu custo.

Solução: Vamos adotar desempate pelo maior $g$ e, persistindo o empate, pela ordem de geração cima, direita, baixo, esquerda. O A* expande, em ordem, os nós abaixo. Todos têm $f = 6$, mas o desempate pelo maior $g$ conserva a busca no caminho superior em vez de expandir todos os nós empatados da mesma camada.

O caminho devolvido é $(0,0) \to (0,1) \to (0,2) \to (0,3) \to (1,3) \to (2,3) \to (3,3)$, de custo $6$, contornando o bloco de paredes pela borda superior e direita. O A* expande sete nós, incluindo o objetivo. Se desempatássemos pelo menor $g$, ele se espalharia pela camada de $f=6$ e expandiria doze. O algoritmo e a heurística seriam os mesmos; mudaria apenas a política que antes parecia um detalhe.

2. Mostre que o A* com $h(n) = 0$ para todo $n$ se reduz à busca de custo uniforme.

Solução: Se $h(n) = 0$ em toda parte, então $f(n) = g(n) + 0 = g(n)$, e ordenar a fronteira por $f$ é ordená-la por $g$. Mas expandir sempre o nó de menor $g$ é exatamente a política da busca de custo uniforme do artigo anterior. A heurística nula é admissível, pois nunca superestima e $0 \le h^{*}(n)$ sempre. Por isso, o A* com ela continua ótimo; ele apenas perde todo o poder de direção e volta a explorar em anéis de custo crescente. A busca de custo uniforme é, nesse sentido, o A* mais pessimista possível sobre o próprio conhecimento: aquele que confessa não saber nada sobre a distância que falta.

3. Em uma fronteira do A*, há três nós com os seguintes valores: $P$ com $g = 4$ e $h = 3$; $Q$ com $g = 2$ e $h = 5$; $R$ com $g = 5$ e $h = 1$. Qual é expandido primeiro, aplicando o desempate pelo menor $h$?

Solução: Calculamos $f = g + h$ para cada nó: $f(P) = 4 + 3 = 7$, $f(Q) = 2 + 5 = 7$ e $f(R) = 5 + 1 = 6$. O menor $f$ é o de $R$, com $6$, então $R$ é expandido primeiro, sem sequer precisar do desempate. Se $R$ não existisse, $P$ e $Q$ estariam empatados em $f = 7$, e o desempate pelo menor $h$ escolheria $P$, com $h = 3$, à frente de $Q$, com $h = 5$: entre dois nós de mesmo custo total estimado, o A* prefere aquele que a heurística julga mais perto do fim, o que tende a mergulhar em direção ao objetivo em vez de alargar a fronteira.

A tabela confirma que o menor $f$ decide primeiro e que o menor $h$ resolve apenas o empate entre $P$ e $Q$.

4. Compare o número de nós expandidos pelo A* com a distância de Manhattan e pela busca de custo uniforme na grade deste bloco de exercícios.

Solução: Na grade $4 \times 4$ com as três paredes, restam treze células livres. Com a mesma ordem de sucessores, a busca de custo uniforme expande doze nós antes de retirar o objetivo da fronteira. O A* com Manhattan e desempate pelo maior $g$ expande sete, uma redução de $5/12\approx41{,}7\%$. A contagem não é uma propriedade abstrata da heurística: se o A* desempatar pelo menor $g$, ele também expandirá doze nós porque todas as células úteis permanecem empatadas em $f=6$. O poder de uma heurística aparece tanto nos nós com $f(n)>C^{}$, que ela deixa fora do caminho da solução, quanto na política usada para organizar os empates em $f(n)=C^{}$. Na instância reproduzível do 8-puzzle da Seção 6, a diferença deixa de ser de cinco nós e passa a duas ordens de grandeza.

Logo, a heurística permite a redução, mas a política de desempate determina se esta grade pequena consegue realizá-la.

5. Dê um exemplo em que uma heurística inconsistente faz o A* reabrir um nó já expandido.

Solução: Considere um grafo dirigido com nós $S$, $A$, $B$ e $G$ e as arestas $S \to A$ de custo $2$, $S \to B$ de custo $1$, $B \to A$ de custo $0$ e $A \to G$ de custo $3$. Os custos ótimos reais são $h^{}(S) = 4$, $h^{}(A) = 3$, $h^{}(B) = 3$ e $h^{}(G) = 0$. Tome a heurística $h(S) = 2$, $h(A) = 0$, $h(B) = 3$ e $h(G) = 0$: ela é admissível, pois cada valor é menor ou igual ao custo ótimo real, mas é inconsistente, porque na aresta $B \to A$ vale $h(B) = 3 > c(B, A) + h(A) = 0 + 0 = 0$.

Vamos seguir o A*. Expandimos $S$ ($g = 0$, $f = 2$) e geramos $A$ com $g = 2$, $f = 2 + 0 = 2$, e $B$ com $g = 1$, $f = 1 + 3 = 4$. O menor $f$ é o de $A$, então expandimos $A$ ($g = 2$) e o fechamos, gerando $G$ com $g = 5$. A seguir expandimos $B$ ($g = 1$, $f = 4$) e, pela aresta $B \to A$ de custo zero, descobrimos um caminho a $A$ com $g = 1$, menor que o $g = 2$ com que $A$ havia sido fechado. O A* é obrigado a reabrir $A$, reinseri-lo na fronteira com $f = 1 + 0 = 1$ e expandi-lo de novo, agora gerando $G$ com $g = 4$. Só então expande $G$, com o custo ótimo $4$.

O nó $A$ foi expandido duas vezes, uma reabertura causada exatamente pela incoerência da heurística entre $B$ e $A$. Com uma heurística consistente, isso jamais ocorreria: a Seção 5 prova que, sob consistência, todo nó é fechado já com seu $g$ ótimo, e a busca em grafo nunca precisa reabrir nada. É por essa economia prática que a consistência, e não a mera admissibilidade, é a propriedade que se deseja de uma heurística.

4. Admissibilidade

O A* só é útil se a solução que ele devolve for confiável, e a confiabilidade depende de uma propriedade da heurística. Dizemos que $h$ é admissível quando ela nunca superestima o custo real até o objetivo, isto é, quando

Em palavras, uma heurística admissível é otimista: ela pode subestimar quanto falta, mas nunca exagera. A intuição é que uma estimativa otimista jamais faz o A* descartar prematuramente um caminho que poderia ser o melhor, porque nenhum caminho parecerá pior do que de fato é. Dessa modéstia decorre o teorema central do artigo: o A* com uma heurística admissível, em busca em árvore, é ótimo, sempre que encontra uma solução, ela tem custo mínimo.

O argumento merece ser feito com cuidado, porque é o coração da garantia. Seja $C^{}$ o custo da solução ótima, e suponha, por absurdo, que o A* esteja prestes a expandir um nó objetivo subótimo $G_2$, com custo de caminho $g(G_2) > C^{}$. Como $G_2$ é objetivo, $h(G_2) = 0$, logo $f(G_2) = g(G_2) > C^{}$. Considere agora um nó $n$ que esteja na fronteira e sobre o caminho ótimo, sempre existe um, enquanto o objetivo ótimo não foi alcançado. Por admissibilidade, $f(n) = g(n) + h(n) \le g(n) + h^{}(n) = C^{}$, já que $g(n) + h^{}(n)$ é exatamente o custo do caminho ótimo que passa por $n$. Juntando as duas desigualdades, $f(n) \le C^{*} < f(G_2)$, de modo que o A* teria expandido $n$ antes de $G_2$. Isso contradiz a suposição de que $G_2$ seria expandido: o A* nunca expande um objetivo subótimo enquanto houver, na fronteira, um nó do caminho ótimo com $f$ menor. Portanto, o primeiro objetivo que o A* expande é ótimo.

Exercícios resolvidos

6. Prove que a distância de Manhattan é admissível para o 8-puzzle.

Solução: A distância de Manhattan de um estado soma, sobre todas as peças, o número de casas horizontais e verticais que separam cada peça de seu destino. Cada jogada do 8-puzzle move uma única peça uma única casa, para cima, para baixo, para a esquerda ou para a direita, e portanto reduz a distância de Manhattan daquela peça em no máximo uma unidade, sem afetar as demais. Logo, para levar uma peça de sua posição atual ao destino são necessárias pelo menos tantas jogadas quanto sua distância de Manhattan individual, e como as peças se movem uma de cada vez, o total de jogadas até o objetivo é pelo menos a soma dessas distâncias. Assim, $h_{\text{Manhattan}}(n) \le h^{*}(n)$ para todo estado $n$, que é a definição de admissibilidade. O argumento é um relaxamento: ele ignora que as peças disputam as mesmas casas, e por isso conta de menos, nunca de mais.

7. Prove que a contagem de peças fora do lugar é admissível.

Solução: A contagem de peças fora do lugar atribui a um estado o número de peças que não estão em sua posição final, sem contar o espaço vazio. Cada jogada move exatamente uma peça, e para que uma peça fora do lugar chegue ao seu destino é preciso, no mínimo, uma jogada que a mova. Como nenhuma jogada coloca duas peças em seus lugares ao mesmo tempo, o número de jogadas necessárias é pelo menos o número de peças fora do lugar. Portanto $h_{\text{fora}}(n) \le h^{*}(n)$, e a heurística é admissível. Ela é ainda mais tímida que a distância de Manhattan, pois conta apenas se a peça está ou não no lugar, ignorando o quão longe está, e essa timidez terá consequências na Seção 6.

8. Construa uma heurística que superestime e exiba o caminho subótimo que o A* então devolve.

Solução: Considere um grafo com nós $S$, $A$ e $G$ e as arestas $S \to A$ de custo $1$, $A \to G$ de custo $1$ e $S \to G$ direto de custo $3$. O caminho ótimo é $S \to A \to G$, de custo $2$. Adote uma heurística que superestima em $A$: $h(A) = 100$, com $h(S) = h(G) = 0$. O A* avalia, a partir de $S$, o sucessor $A$ com $f(A) = 1 + 100 = 101$ e o sucessor $G$ com $f(G) = 3 + 0 = 3$. Como $3 < 101$, ele expande $G$ e retorna o caminho direto $S \to G$, de custo $3$, superior ao ótimo $2$. A heurística mentirosa convenceu o A* de que passar por $A$ custaria uma fortuna, e ele fugiu do melhor caminho. Este é exatamente o dano que a admissibilidade proíbe: sem ela, a otimalidade se perde.

9. Enuncie e justifique por que o argumento de otimalidade do A* em árvore depende da admissibilidade.

Solução: O argumento da Seção 4 usa a admissibilidade em um único passo decisivo: a desigualdade $f(n) = g(n) + h(n) \le g(n) + h^{}(n) = C^{}$ para um nó $n$ do caminho ótimo. Essa desigualdade só vale porque $h(n) \le h^{}(n)$; se a heurística superestimasse, teríamos $f(n)$ possivelmente maior que $C^{}$, e nada garantiria que $n$ fosse expandido antes de um objetivo subótimo $G_2$ com $f(G_2) > C^{}$. Em outras palavras, é a admissibilidade que mantém todo nó do caminho ótimo com $f \le C^{}$, e é isso que impede o A* de fechar um objetivo caro cedo demais. Retirada a admissibilidade, como no exercício anterior, o A* pode e devolve soluções subótimas.

10. Mostre que, se $h_1$ e $h_2$ são admissíveis, então $h(n) = \max(h_1(n), h_2(n))$ também é.

Solução: Para todo nó $n$, a admissibilidade de cada heurística dá $h_1(n) \le h^{}(n)$ e $h_2(n) \le h^{}(n)$. O máximo de dois números, cada um menor ou igual a $h^{}(n)$, é também menor ou igual a $h^{}(n)$: se ambos os valores estão abaixo de um teto, o maior deles ainda está. Logo $\max(h_1(n), h_2(n)) \le h^{*}(n)$, e $h$ é admissível. Esse resultado é mais útil do que parece: como o A* expande menos nós quanto maior a heurística admissível, como mostra a Seção 6, combinar várias heurísticas admissíveis tomando o máximo produz uma heurística admissível pelo menos tão boa quanto a melhor delas, de graça.

5. Consistência

A admissibilidade garante otimalidade, mas, como vimos no quinto exercício da Seção 3, não impede que o A* em grafo reabra nós e desperdice trabalho. A propriedade que elimina esse desperdício é mais forte. Dizemos que $h$ é consistente, ou monotônica, quando, para todo nó $n$ e todo sucessor $n’$ alcançado por uma ação $a$, vale

Essa é uma desigualdade triangular: a estimativa a partir de $n$ não pode exceder o custo de dar um passo até $n’$ mais a estimativa a partir de $n’$. Intuitivamente, a heurística não pode cair mais rápido do que o custo real permite ao avançarmos um passo; ela decresce de forma coerente com o terreno. Duas consequências tornam a consistência a propriedade desejável na prática. A primeira é que toda heurística consistente é admissível, de modo que a consistência é a exigência mais forte e dá a otimalidade de brinde. A segunda é que, sob consistência, os valores de $f$ ao longo de qualquer caminho não decrescem, o que faz o A* fechar cada nó já com seu $g$ ótimo e nunca precisar reabri-lo. Os exercícios estabelecem as duas.

Exercícios resolvidos

11. Verifique se a heurística dada é consistente no grafo com arestas $S \to A$ de custo $2$, $A \to G$ de custo $2$ e $S \to G$ de custo $5$, com $h(S) = 4$, $h(A) = 1$ e $h(G) = 0$.

Solução: Testamos a desigualdade triangular em cada aresta. Para $S \to A$: precisamos de $h(S) \le c(S, A) + h(A)$, isto é, $4 \le 2 + 1 = 3$, que é falso. Já podemos concluir que a heurística não é consistente, pois basta uma aresta violando a desigualdade. Por completude, as outras: $A \to G$ exige $h(A) \le c(A, G) + h(G)$, ou $1 \le 2 + 0 = 2$, verdadeiro; e $S \to G$ exige $h(S) \le c(S, G) + h(G)$, ou $4 \le 5 + 0 = 5$, verdadeiro. A violação em $S \to A$ significa que a heurística promete, de $S$, uma proximidade ($h = 4$) incompatível com o que um único passo até $A$ revela: dali só faltaria $h(A) = 1$, mas o passo custou apenas $2$, de modo que a estimativa despencou de $4$ para $1$ com um passo de custo $2$, uma queda de $3$ que a desigualdade proíbe.

12. Prove que toda heurística consistente é admissível.

Solução: Seja $h$ consistente e considere um nó $n$ qualquer, do qual o caminho ótimo até o objetivo passa por $n = n_0, n_1, \dots, n_k = G$, com $n_k$ objetivo. Aplicando a consistência a cada passo, $h(n_i) \le c(n_i, n_{i+1}) + h(n_{i+1})$. Somando telescopicamente ao longo do caminho, ou aplicando indução do fim para o começo, obtemos $h(n_0) \le \sum_{i=0}^{k-1} c(n_i, n_{i+1}) + h(n_k)$. Como $n_k$ é objetivo, $h(n_k) = 0$, e a soma dos custos ao longo do caminho ótimo é justamente $h^{}(n_0)$. Logo $h(n_0) \le h^{}(n_0)$, que é a admissibilidade. A recíproca é falsa, como mostra o próximo exercício: há heurísticas admissíveis que não são consistentes.

13. Exiba uma heurística admissível que não seja consistente.

Solução: Retomamos o grafo do quinto exercício da Seção 3: arestas $S \to A$ de custo $2$, $S \to B$ de custo $1$, $B \to A$ de custo $0$ e $A \to G$ de custo $3$, com custos ótimos $h^{}(S) = 4$, $h^{}(A) = 3$, $h^{}(B) = 3$ e $h^{}(G) = 0$. A heurística $h(S) = 2$, $h(A) = 0$, $h(B) = 3$, $h(G) = 0$ é admissível, pois cada valor não excede o custo ótimo correspondente. Mas ela viola a consistência na aresta $B \to A$: $h(B) = 3 > c(B, A) + h(A) = 0 + 0 = 0$. É exatamente essa incoerência que, naquele exercício, obrigou o A* a reabrir o nó $A$. Admissível, portanto, sem ser consistente: a heurística é otimista em toda parte, mas otimista de forma desigual entre vizinhos.

14. Corrija uma heurística inconsistente pelo procedimento de pathmax no grafo do exercício anterior.

Solução: O pathmax impõe coerência ao longo do caminho substituindo, ao gerar um sucessor $n’$ a partir de $n$, o valor $h(n’)$ por $\max\bigl(h(n’), h(n) - c(n, a, n’)\bigr)$. Aplicando à aresta $S \to A$, na qual $h(S) = 2$ e $c(S, A) = 2$: o novo valor é $\max(h(A), h(S) - c(S, A)) = \max(0, 2 - 2) = 0$, sem alteração. O ponto interessante aparece quando a heurística de $A$ precisaria subir para respeitar o pai; em um caso em que $h(S) = 2$ e $c(S, A) = 1$, teríamos $\max(0, 2 - 1) = 1$, elevando $h(A)$ de $0$ para $1$ ao longo daquele caminho. O pathmax não conserta a heurística globalmente, mas garante que, ao longo de cada caminho explorado, os valores de $f$ não decresçam, recuperando parte da vantagem da consistência sem exigir uma heurística consistente.

15. Prove que, com $h$ consistente, os valores de $f$ não decrescem ao longo de qualquer caminho seguido pelo A*.

Solução: Seja $n’$ um sucessor de $n$ por uma ação $a$, de modo que $g(n’) = g(n) + c(n, a, n’)$ ao longo do caminho explorado. Então

Pela consistência, $c(n, a, n’) + h(n’) \ge h(n)$, e substituindo,

Logo $f(n’) \ge f(n)$: os valores de $f$ crescem de forma monotônica ao longo do caminho, o que justifica o nome heurística monotônica. A consequência operacional é a prometida: como o A* expande os nós em ordem não decrescente de $f$, quando ele fecha um nó pela primeira vez, todos os caminhos que ainda poderiam alcançá-lo têm $f$ maior ou igual, e portanto $g$ maior ou igual; o $g$ com que o nó foi fechado já é ótimo, e nenhuma reabertura será necessária. É essa a garantia que a admissibilidade sozinha não oferece.

6. Construindo heurísticas

Uma heurística admissível não cai do céu; ela é projetada, e há um método geral para projetá-la. A ideia é o relaxamento: tomamos o problema original, removemos uma ou mais restrições das ações, e resolvemos o problema mais fácil resultante; o custo ótimo do problema relaxado é uma heurística admissível para o problema original, porque qualquer solução do problema difícil também é solução do fácil, nunca mais barata. As duas heurísticas do 8-puzzle nascem assim. Se relaxarmos a regra uma peça só desliza para a casa vazia adjacente para uma peça pode saltar diretamente para seu destino, cada peça fora do lugar precisa de exatamente uma jogada, e obtemos a contagem de peças fora do lugar. Se relaxarmos apenas para uma peça pode mover-se para qualquer casa adjacente, ocupada ou não, cada peça precisa de sua distância de Manhattan, e obtemos a distância de Manhattan. Duas heurísticas, dois graus de relaxamento.

Que uma heurística seja melhor que outra tem significado preciso. Dizemos que $h_2$ domina $h_1$ quando $h_2(n) \ge h_1(n)$ para todo nó $n$, sendo ambas admissíveis. A dominância importa porque todo nó que satisfaz $g(n)+h_2(n)<C^{}$ também satisfaz $g(n)+h_1(n)<C^{}$, mas a recíproca pode falhar. Assim, antes de retirar um objetivo ótimo, o A* com $h_2$ não é obrigado a expandir mais nós com $f<C^{}$ do que com $h_1$. Nos nós com $f=C^{}$, a contagem ainda depende do desempate, como vimos na Seção 3. A distância de Manhattan domina a contagem de peças fora do lugar porque cada peça deslocada contribui ao menos uma unidade para Manhattan. Mantidas a implementação e a política de desempate, ela costuma reduzir muito o trabalho; o segundo exercício mede essa diferença em uma instância reproduzível.

Há um limite para essa escalada. A heurística perfeita seria $h = h^{}$, com a qual todo nó de um caminho ótimo tem $f=C^{}$ e nenhum nó com $f>C^{}$ precisa ser expandido antes do objetivo. A ordem entre os nós empatados em $C^{}$ ainda depende da política escolhida. Calcular $h^{}$, porém, equivale a resolver o próprio problema, o que anula o propósito. O ofício de projetar heurísticas é, portanto, uma busca por estimativas tão próximas de $h^{}$ quanto possível e, ao mesmo tempo, baratas de computar, como bancos de padrões, combinações por máximo e relaxamentos engenhosos. É um ofício ao qual voltaremos sempre que um problema desta série exigir busca em escala.

Antes dos exercícios, convém sentir na mão o efeito da heurística sobre o trabalho do A*. O laboratório abaixo executa o A* em uma grade e mostra, célula a célula, os valores de $f$ à medida que os nós são expandidos. O controle deslizante multiplica a heurística por um peso: em zero, a heurística some e o A* vira busca de custo uniforme, expandindo em anéis; em um, é o A* admissível padrão; acima de um, a heurística passa a superestimar, e a leitora verá o A* expandir menos nós porém, às vezes, devolver um caminho mais caro que o ótimo, a otimalidade quebrando diante dos olhos, exatamente como no terceiro exercício da Seção 4.

Exercícios resolvidos

16. Explique como a distância de Manhattan é obtida por relaxamento do 8-puzzle.

Solução: No 8-puzzle original, uma jogada só é possível quando a peça é adjacente à casa vazia e desliza para ela; há, portanto, duas restrições acopladas, a de adjacência à casa-alvo e a de que a casa-alvo esteja vazia. Relaxamos a segunda: permitimos que uma peça se mova para qualquer casa adjacente, esteja ela ocupada ou não. No problema relaxado, cada peça viaja independentemente até seu destino pelo caminho mais curto em uma grade, cujo comprimento é exatamente sua distância de Manhattan, e o custo total é a soma dessas distâncias. Como toda sequência de jogadas do 8-puzzle verdadeiro é também válida no problema relaxado, o custo ótimo relaxado, a soma das distâncias de Manhattan, nunca excede o custo verdadeiro, e é por construção uma heurística admissível.

17. Meça a diferença de nós expandidos entre as duas heurísticas do 8-puzzle na instância abaixo, cujo custo ótimo é vinte jogadas. O zero representa o espaço vazio.

Solução: Executamos a mesma busca A* três vezes, sempre com desempate pelo maior $g$, ordem de sucessores cima, direita, baixo, esquerda e teste de objetivo na expansão. Com a heurística nula, isto é, busca de custo uniforme, são expandidos $40\,280$ estados. Com a contagem de peças fora do lugar, o total cai para $2\,165$. Com a distância de Manhattan, cai para $342$. As três execuções devolvem o custo ótimo $20$; o que muda é o trabalho.

Manhattan usa apenas $342/40\,280\approx0{,}849\%$ das expansões da busca de custo uniforme, uma redução de aproximadamente $99{,}15\%$. Em relação às peças fora do lugar, usa $342/2\,165\approx15{,}8\%$, cerca de $6{,}33$ vezes menos expansões. Agora o experimento é reproduzível: outra leitora pode usar o mesmo tabuleiro, a mesma ordem e o mesmo desempate e exigir os mesmos números. Sem esses dados, “a heurística expandiu menos” seria uma anedota com roupa de benchmark.

18. Explique por que um banco de padrões (pattern database) fornece uma heurística admissível.

Solução: Um banco de padrões escolhe um subconjunto das peças, vamos dizer as peças de $1$ a $4$ do 15-puzzle, e pré-computa, para toda configuração possível desse subconjunto, o número exato de jogadas necessárias para levá-lo ao arranjo final, abstraindo as demais peças. Esse número é o custo ótimo de um problema relaxado e, por isso, é um limite inferior do custo real. Consultar a tabela durante a busca devolve uma heurística admissível.

Não basta dizer que qualquer banco de padrões domina Manhattan. Um banco pequeno pode ser mais fraco em alguns estados, pois ignora peças cuja contribuição Manhattan conta. A combinação segura é $h(n)=\max(h_{\text{Manhattan}}(n),h_{\text{PDB}}(n))$, admissível pelo quinto exercício da Seção 4 e dominante sobre as duas componentes. Bancos de padrões disjuntos podem ainda somar custos quando o custo de cada movimento é atribuído sem sobreposição entre os padrões; essa aditividade exige uma construção própria, não nasce apenas de guardar duas tabelas. O custo comprado é memória de pré-computação, trocada por menos expansões durante cada consulta.

19. A média de duas heurísticas admissíveis é admissível? E ela domina cada uma delas?

Solução: Sejam $h_1$ e $h_2$ admissíveis, com $h_1(n) \le h^{}(n)$ e $h_2(n) \le h^{}(n)$. A média $\bar{h}(n) = \tfrac{1}{2}\bigl(h_1(n) + h_2(n)\bigr)$ é uma combinação de dois valores, cada um no máximo $h^{}(n)$, logo $\bar{h}(n) \le \tfrac{1}{2}(h^{}(n) + h^{}(n)) = h^{}(n)$: a média é admissível. Mas ela não domina as componentes: se em algum nó $h_1(n) > h_2(n)$, então $\bar{h}(n) < h_1(n)$, de modo que a média é mais fraca que $h_1$ ali. Para combinar heurísticas sem perder força, a operação certa não é a média, e sim o máximo, $\max(h_1, h_2)$, que é admissível pelo quinto exercício da Seção 4 e domina ambas por construção. A média serve quando se quer suavizar; o máximo, quando se quer o melhor de cada uma.

20. Projete uma heurística admissível para uma grade em que o agente pode mover-se também nas diagonais, com custo unitário para qualquer dos oito vizinhos.

Solução: Quando as diagonais custam o mesmo que os passos ortogonais, um único movimento pode reduzir em uma unidade tanto a diferença horizontal quanto a vertical até o objetivo. O número mínimo de passos para cobrir uma diferença de $\Delta x$ colunas e $\Delta y$ linhas é, então, $\max(\vert\Delta x\vert, \vert\Delta y\vert)$, pois avançamos na diagonal enquanto ambas as diferenças forem não nulas e, esgotada uma delas, seguimos em linha reta na outra. Essa é a distância de Chebyshev, e ela é admissível para a grade com diagonais porque conta o número exato de passos do problema relaxado sem obstáculos, nunca mais que o real. Note que a distância de Manhattan seria inadmissível aqui: para ir de $(0,0)$ a $(3,5)$, Manhattan estima $\vert3\vert + \vert5\vert = 8$ passos, mas o movimento diagonal resolve em $\max(3, 5) = 5$; a estimativa de $8$ superestimaria o custo real de $5$, e o A* perderia a otimalidade. A heurística certa depende das ações permitidas, e trocá-las sem trocar a heurística é um erro clássico.

7. A* em C++23

O código a seguir implementa o A* na grade $4 \times 4$ dos exercícios da Seção 3, com distância de Manhattan, reabertura de estados quando aparece um $g$ melhor e desempate explícito pelo maior $g$. Ele reconstrói o caminho, conta expansões e valida o resultado. No MSVC 19.44, usamos cl /std:c++latest /permissive- /W4 /EHsc /utf-8 /O2 astar.cpp.

#include <algorithm>
#include <array>
#include <cmath>
#include <cstddef>
#include <expected>
#include <iostream>
#include <limits>
#include <queue>
#include <ranges>
#include <vector>

struct Celula {
    int linha;
    int coluna;
    friend bool operator==(const Celula&, const Celula&) = default;
};

constexpr int ordem = 4;
constexpr Celula inicio{0, 0};
constexpr Celula objetivo{3, 3};
constexpr std::array paredes{Celula{1, 1}, Celula{1, 2}, Celula{2, 1}};
constexpr std::array direcoes{
    Celula{-1, 0}, Celula{0, 1}, Celula{1, 0}, Celula{0, -1}};

enum class ErroBusca { sem_caminho };

struct Resultado {
    std::vector<Celula> caminho;
    int custo;
    std::size_t expandidos;
};

[[nodiscard]] constexpr std::size_t indice(const Celula celula) noexcept {
    return static_cast<std::size_t>(celula.linha * ordem + celula.coluna);
}

[[nodiscard]] constexpr bool valida(const Celula celula) noexcept {
    return celula.linha >= 0 && celula.coluna >= 0
        && celula.linha < ordem && celula.coluna < ordem
        && !std::ranges::contains(paredes, celula);
}

[[nodiscard]] int manhattan(const Celula celula) noexcept {
    return std::abs(objetivo.linha - celula.linha)
        + std::abs(objetivo.coluna - celula.coluna);
}

struct Entrada {
    int f;
    int g;
    std::size_t ordem_insercao;
    Celula celula;
};

struct Prioridade {
    [[nodiscard]] bool operator()(
        const Entrada& esquerda, const Entrada& direita) const noexcept {
        if (esquerda.f != direita.f) {
            return esquerda.f > direita.f;
        }
        if (esquerda.g != direita.g) {
            return esquerda.g < direita.g;
        }
        return esquerda.ordem_insercao > direita.ordem_insercao;
    }
};

[[nodiscard]] std::vector<Celula> reconstruir(
    const std::array<Celula, ordem * ordem>& pai) {
    std::vector<Celula> caminho{objetivo};
    for (Celula atual = objetivo; atual != inicio;) {
        atual = pai[indice(atual)];
        caminho.push_back(atual);
    }
    std::ranges::reverse(caminho);
    return caminho;
}

[[nodiscard]] std::expected<Resultado, ErroBusca> astar() {
    constexpr int infinito = std::numeric_limits<int>::max();
    std::array<int, ordem * ordem> melhor_g;
    melhor_g.fill(infinito);
    std::array<Celula, ordem * ordem> pai{};

    std::priority_queue<Entrada, std::vector<Entrada>, Prioridade> fronteira;
    std::size_t sequencia = 0;
    melhor_g[indice(inicio)] = 0;
    pai[indice(inicio)] = inicio;
    fronteira.push(Entrada{manhattan(inicio), 0, sequencia, inicio});

    std::size_t expandidos = 0;
    while (!fronteira.empty()) {
        const Entrada atual = fronteira.top();
        fronteira.pop();

        // Uma entrada só é vigente quando ainda carrega o menor g conhecido.
        if (atual.g != melhor_g[indice(atual.celula)]) {
            continue;
        }
        ++expandidos;

        if (atual.celula == objetivo) {
            return Resultado{reconstruir(pai), atual.g, expandidos};
        }

        for (const Celula direcao : direcoes) {
            const Celula vizinha{
                atual.celula.linha + direcao.linha,
                atual.celula.coluna + direcao.coluna};
            if (!valida(vizinha)) {
                continue;
            }

            const int candidato = atual.g + 1;
            if (candidato < melhor_g[indice(vizinha)]) {
                melhor_g[indice(vizinha)] = candidato;
                pai[indice(vizinha)] = atual.celula;
                fronteira.push(Entrada{
                    candidato + manhattan(vizinha),
                    candidato,
                    ++sequencia,
                    vizinha});
            }
        }
    }
    return std::unexpected{ErroBusca::sem_caminho};
}

int main() {
    const auto resultado = astar();
    if (!resultado) {
        std::cout << "sem solucao\n";
        return 1;
    }

    for (const Celula celula : resultado->caminho) {
        std::cout << '(' << celula.linha << ',' << celula.coluna << ") ";
    }
    std::cout << "\ncusto = " << resultado->custo
              << ", nos expandidos = " << resultado->expandidos << '\n';

    return resultado->custo == 6 && resultado->expandidos == 7 ? 0 : 2;
}

A saída lista o caminho pela borda superior e termina com custo = 6, nos expandidos = 7, reproduzindo os exercícios 1 e 4 da Seção 3. A estrutura Prioridade torna o desempate parte visível do algoritmo: menor $f$, depois maior $g$, depois menor ordem de inserção. O vetor melhor_g substitui um conjunto fechado rígido; se uma heurística admissível, porém inconsistente, revelar depois um caminho melhor para uma célula, a condição aceita o novo $g$ e o estado volta à fronteira. Assim, o código implementa a reabertura que a Seção 5 exige, em vez de prometer no texto algo que a estrutura de dados impediria.

8. O fim do começo

Demos visão à busca. Uma heurística estima o que falta, o A* a combina com o que já foi pago na função $f = g + h$, e a qualidade da heurística decide tudo. Em busca em árvore, a admissibilidade preserva a solução ótima; em busca em grafo, a consistência evita reaberturas, enquanto uma implementação que aceita reabrir estados preserva a correção com heurísticas admissíveis. Quando uma heurística admissível domina outra, ela pode reduzir drasticamente o trabalho. Provamos essas propriedades e vimos, na instância reproduzível do 8-puzzle, as $40\,280$ expansões da heurística nula caírem para $342$ com a distância de Manhattan.

Até aqui, porém, a busca sempre procurou um caminho: uma sequência de ações do início ao objetivo. Há problemas em que o caminho não interessa, só o destino, como arranjar, configurar ou otimizar, e para eles guardar a árvore de busca é desperdício. No próximo artigo, abandonamos a fronteira e a árvore: a busca local mantém um único estado e o melhora aos tropeços, trocando a garantia de otimalidade pela capacidade de enfrentar espaços grandes demais para qualquer A*.

Acrônimos e abreviações neste artigo

Referências

HART, P. E.; NILSSON, N. J.; RAPHAEL, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, New York, v. 4, n. 2, p. 100–107, 1968. DOI: https://doi.org/10.1109/TSSC.1968.300136. Acesso em: 24 jul. 2026.

KORF, R. E. Finding optimal solutions to Rubik’s Cube using pattern databases. In: NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 14., 1997, Providence. Proceedings […]. Menlo Park: AAAI Press, 1997. p. 700–705. Disponível em: https://ai.dmi.unibas.ch/_files/teaching/fs26/ai/material/ai-b09-korf-aaai1997.pdf. Acesso em: 24 jul. 2026.

LUGER, G. F. Artificial Intelligence: structures and strategies for complex problem solving. 6. ed. Albuquerque: University of New Mexico, 2009. Disponível em: https://www.cs.unm.edu/~luger/ai-final/. Acesso em: 24 jul. 2026.

MICROSOFT. Microsoft C/C++ language conformance by Visual Studio version. Redmond, 2026. Disponível em: https://learn.microsoft.com/en-us/cpp/overview/visual-cpp-language-conformance?view=msvc-170. Acesso em: 24 jul. 2026.

RUSSELL, S.; NORVIG, P. Artificial Intelligence: a modern approach. 4. ed. Hoboken: Pearson, 2020. Disponível em: https://aima.cs.berkeley.edu/. Acesso em: 24 jul. 2026.

UNIVERSITY OF CALIFORNIA, BERKELEY. Introduction to Artificial Intelligence: informed search. Berkeley, 2024. Disponível em: https://inst.eecs.berkeley.edu/~cs188/textbook/search/informed.html. Acesso em: 24 jul. 2026.

UNIVERSITY OF CALIFORNIA, BERKELEY. Project 1: search. Berkeley, 2026. Disponível em: https://inst.eecs.berkeley.edu/~cs188/sp26/projects/proj1/. Acesso em: 24 jul. 2026.