Entre 1966 e 1972, um robô de rodas com uma antena de rádio no topo passeava pelos corredores do Stanford Research Institute empurrando caix...
Palpite 01
O robô que tremia
Shakey foi construído no Centro de Inteligência Artificial do Stanford Research Institute, sob a coordenação de Charles Rosen, Nils Nilsson e Peter Hart (SHAKEY…, 2026). Era o primeiro robô móvel capaz de raciocinar sobre as próprias ações: recebia uma ordem em inglês, decompunha-a em passos e executava. Do projeto saíram o planejador STRIPS, a transformada de Hough e o método do grafo de visibilidade. Saiu também o algoritmo que interessa aqui.
O problema de Shakey era o de qualquer coisa que se desloca: existe um mapa, existe um ponto de partida, existe um destino, e existem obstáculos. As buscas cegas, tratadas em outra postagem, resolviam o problema — e resolviam mal, porque examinavam o espaço inteiro sem nunca olhar para onde o destino estava. Um robô com uma bateria e uma sala pela frente não podia se dar a esse luxo.
Em 1968, Peter Hart, Nils Nilsson e Bertram Raphael publicaram A formal basis for the heuristic determination of minimum cost paths (HART; NILSSON; RAPHAEL, 1968). O artigo faz duas coisas ao mesmo tempo, e é por isso que ficou. Primeiro, descreve um algoritmo — que eles chamam de A*, com asterisco. Segundo, e mais importante, demonstra sob qual condição esse algoritmo devolve a resposta certa. A contribuição de 1968 não foi a ideia de usar um palpite: foi o preço exato que o palpite tem de pagar para não estragar a garantia.
Há um detalhe humano na história que vale contar: quatro anos depois, os próprios autores publicaram uma correção ao artigo (HART; NILSSON; RAPHAEL, 1972). O algoritmo estava certo; parte do que se afirmou sobre ele, não. O tratamento definitivo de quais garantias valem sob quais hipóteses só apareceu em 1985, com Rina Dechter e Judea Pearl (DECHTER; PEARL, 1985). Dezessete anos entre o algoritmo funcionar e a comunidade entender exatamente por quê.
Palpite 02
A mesma fila, outra chave
Na postagem anterior, a conclusão foi que as quatro buscas cegas são o mesmo laço, mudando apenas o recipiente da fronteira. A busca de custo uniforme usava uma fila de prioridade ordenada pelo custo acumulado desde o início, o g(n). Guarde essa fila, porque ela não vai mudar. Tudo o que separa a busca cega da busca informada é a chave de ordenação dessa mesma fila.
São três chaves possíveis, e cada uma tem um nome:
A função h(n) é a heurística: uma estimativa, calculada rapidamente, do custo que ainda falta de n até um objetivo. Ela não sai do algoritmo — vem do domínio. Em um mapa rodoviário, a distância em linha reta. Em uma malha quadriculada, a distância em quarteirões. Em um quebra-cabeça deslizante, o número de peças fora do lugar. O algoritmo não sabe de onde veio o número, e não pergunta.
A fila é a mesma das buscas cegas. Muda o número escrito na etiqueta de cada nó — e, com ele, tudo o mais.
Vale fixar o vocabulário, porque as três letras aparecem em toda a literatura e trocá-las custa caro em prova: g(n) é o custo conhecido do início até n; h(n) é o custo estimado de n até o objetivo; f(n) = g(n) + h(n) é a estimativa do custo total da melhor rota que passa por n (RUSSELL; NORVIG, 2021). E existe um quarto símbolo, que o algoritmo nunca conhece: h*(n), o custo real do melhor caminho de n até o objetivo. A postagem inteira é sobre a relação entre h e h*.
Palpite 03
Gulosa: o algoritmo que só olha para frente
A busca gulosa de melhor escolha expande sempre o nó de menor h(n). O ancestral da ideia é o Graph Traverser, de James Doran e Donald Michie, apresentado em 1966 — dois anos antes do A*, e já com a proposta de usar uma função de avaliação do domínio para escolher qual nó abrir (DORAN; MICHIE, 1966).
O comportamento é exatamente o que o nome sugere. A cada passo, a busca escolhe o vizinho que parece mais próximo do objetivo e vai. Não pondera o quanto já andou; não guarda arrependimento. Em terreno limpo, isso é ótimo: ela vai direto ao alvo e mal olha para os lados. Em terreno com obstáculo, é uma armadilha — porque "parecer mais próximo" e "estar mais próximo" são coisas diferentes, e a diferença é justamente o obstáculo.
As consequências formais:
- Não é ótima. Ela devolve a primeira rota que encontrar, e a primeira rota que a atração do palpite produz pode ser muito pior que a melhor.
- Não é completa na versão em árvore: pode entrar num vaivém entre dois nós que se acham mutuamente promissores. Com uma lista de estados visitados e um espaço finito, fica completa.
- É rápida. E é por isso que ela não desaparece dos livros: quando qualquer rota serve e o tempo é curto, ela entrega.
A gulosa é a prova de que informação, sozinha, não basta. Um palpite excelente sobre o futuro não corrige a decisão de ignorar o passado.
Palpite 04
A*: somar o que já se andou
A correção do A* é de uma economia quase irritante: em vez de ordenar por h(n), ordene por g(n) + h(n). Só isso.
O efeito é fácil de sentir se você traduzir f(n) para o português. A gulosa pergunta "quanto falta daqui?". O A* pergunta "quanto vai custar a viagem inteira, se eu passar por aqui?". A segunda pergunta é a que um viajante faz de verdade. Um desvio que reduz muito o que falta, mas que só se alcança depois de um trecho caríssimo, é uma má ideia — e a soma percebe isso; o h sozinho, não.
O parentesco com a busca de custo uniforme é literal: se h(n) = 0 para todo nó, f = g e o A* é a busca de custo uniforme. A heurística nula é uma heurística legítima — apenas inútil. E o outro extremo também vale: se o peso do g for a zero, sobra a gulosa. Ira Pohl formalizou essa família em 1970, com f = g + w·h e um botão w para girar entre um extremo e outro (POHL, 1970). Custo uniforme, A* e gulosa não são três algoritmos: são três posições do mesmo botão.
A armadilha que se repete
Vale repetir o alerta da postagem sobre buscas cegas, porque no A* ele é ainda mais traiçoeiro: o teste de objetivo se aplica quando o nó é retirado da fronteira, nunca quando é gerado. Encontrar o objetivo não é o mesmo que ter encontrado a melhor rota até ele. Enquanto houver na fronteira um nó com f menor que o f do objetivo, ainda pode existir por ali uma rota mais barata. Testar na geração é o erro mais comum em implementações caseiras de A*, e ele não dá erro nenhum: apenas devolve, de vez em quando, uma rota pior.
Palpite 05
Admissibilidade: o preço da garantia
Chegamos ao ponto do artigo de 1968. O A* devolve a rota ótima sob uma condição sobre h, e a condição é esta:
Uma heurística é admissível quando nunca superestima o custo que falta.
Formalmente: h(n) ≤ h*(n) para todo nó n. Em uma palavra, a heurística precisa ser otimista. Pode errar para baixo o quanto quiser — inclusive devolver zero sempre, que é o caso degenerado da busca de custo uniforme. O que não pode é prometer que falta menos do que de fato falta.
A heurística otimista pode errar muito, desde que erre por baixo. Basta um ponto acima da curva para a garantia cair.
A razão de o otimismo funcionar cabe em um parágrafo. Suponha que o A* esteja prestes a retirar da fronteira um nó-objetivo alcançado por uma rota subótima, de custo C maior que o ótimo C*. Como o objetivo foi alcançado, h nele vale zero, então seu f é o próprio C. Ora, a rota ótima está começada em algum lugar: existe na fronteira um nó n sobre ela. Para esse nó, f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C* — a desigualdade é exatamente a admissibilidade. Como C* < C, o nó n tem f menor e sai da fila antes. O objetivo subótimo nunca chega a ser retirado: alguém melhor está sempre na frente dele. Tire a admissibilidade e a corrente arrebenta no elo do meio.
Admissível não é o mesmo que consistente
Existe uma segunda propriedade, mais forte, que costuma ser confundida com a primeira. Uma heurística é consistente (ou monotônica) quando, para todo nó n e todo sucessor n′ alcançado por uma ação de custo c, vale h(n) ≤ c + h(n′). É a desigualdade triangular aplicada às estimativas: dar um passo não pode fazer o palpite despencar mais do que o passo custou.
Toda heurística consistente é admissível; a recíproca é falsa. E a diferença tem consequência prática: com heurística consistente, os valores de f nunca diminuem ao longo de um caminho, e um nó já expandido nunca precisa ser reaberto — o A* pode fechar cada estado de uma vez por todas. Com heurística apenas admissível, um estado pode ser reencontrado por um caminho mais barato depois de fechado, e uma implementação que não reabre nós perde a otimalidade. Felizmente, quase toda heurística útil que se constrói na prática é consistente, inclusive as duas deste texto.
Palpite 06
As três no mesmo campo
Descrições convencem pouco; formatos convencem. Abaixo, a mesma malha — 449 células livres, um muro com um corredor em serpentina escavado por dentro — percorrida pelas três estratégias, mais uma quarta que serve de contraexemplo. Escolha uma e veja onde o algoritmo gasta o trabalho.
Busca de custo uniforme · f = g
Ordena a fronteira só pelo que já andou. Não faz ideia de onde fica o objetivo, então se espalha igualmente para todos os lados — inclusive para trás. Clique em Rodar a busca.
Rode as quatro antes de seguir; o resumo do texto inteiro está no formato das manchas. A busca de custo uniforme pinta um disco quase completo, porque não tem para onde olhar. A gulosa dispara um feixe fino na direção do objetivo, mergulha na serpentina e sai de lá com uma rota 30% mais longa. O A* desenha uma elipse deformada na direção do alvo, gasta um terço a menos que o custo uniforme e ainda assim devolve a rota ótima. E o A* inflado gasta menos que todos os outros, exceto a gulosa — e paga por isso exatamente o mesmo preço que ela.
Quadro 1 — Comportamento das estratégias na malha de exemplo, 2026
| Estratégia | Chave da fila | Células expandidas | % da malha | Passos da rota | Ótima? |
|---|---|---|---|---|---|
| Custo uniforme | g | 400 | 89 | 40 | Sim |
| Gulosa | h | 73 | 16 | 52 | Não |
| A* | g + h | 267 | 59 | 40 | Sim |
| A* inflado | g + 3h | 150 | 33 | 52 | Não |
Fonte: elaborado pelo autor a partir da malha fictícia do simulador desta postagem.Nota: malha de 30 × 17 posições, 449 células livres, deslocamentos apenas na horizontal e na vertical, custo 1 por passo; heurística de Manhattan. Percentuais calculados sobre as 449 células livres. A rota ótima tem 40 passos, verificada por busca em largura. Sucessores sempre visitados na ordem cima, esquerda, direita, baixo.
A última linha do quadro é o contraexemplo prometido. Multiplicar a heurística de Manhattan por três a torna inadmissível em 447 das 449 células desta malha — ela passa a prometer que falta menos do que falta. O algoritmo continua rodando, continua rápido, continua devolvendo uma rota. Só não devolve mais a melhor. A inadmissibilidade não quebra o A*: ela o transforma, sem avisar, em outra coisa.
Há um uso legítimo disso, e ele tem nome: A* ponderado. Quando o problema é grande demais e uma rota 10% pior sai a tempo enquanto a ótima não sai, inflar a heurística de propósito é uma decisão de engenharia defensável — desde que seja uma decisão, e não um acidente. O que o quadro mostra é o acidente.
Palpite 07
Uma heurística melhor que a outra
Se toda heurística admissível preserva a otimalidade, resta escolher entre elas por outro critério: quanto trabalho cada uma poupa. E aqui existe uma regra limpa. Diz-se que h₂ domina h₁ quando h₂(n) ≥ h₁(n) para todo nó, sendo ambas admissíveis. Uma heurística dominante é sempre pelo menos tão eficiente quanto a dominada — porque, sendo maior sem nunca ultrapassar h*, ela empurra para cima o f dos nós ruins e faz com que o A* expanda menos.
O laboratório clássico é o quebra-cabeça de 8 peças, o mesmo dos 181.440 tabuleiros alcançáveis que apareceu na postagem sobre formulação de problemas. Duas heurísticas concorrem:
As duas são admissíveis, e h₂ ≥ h₁ em todos os 181.440 estados — logo h₂ domina. Falta ver quanto isso vale em nós poupados.
Tabela 1 — Células expandidas pelo A* no quebra-cabeça de 8 peças, por profundidade da solução e heurística, 2026
| Profundidade | A* com h₁ | A* com h₂ | Razão | b* de h₁ | b* de h₂ |
|---|---|---|---|---|---|
| 4 | 5 | 5 | 1,0 | 1,10 | 1,09 |
| 8 | 17 | 12 | 1,4 | 1,17 | 1,09 |
| 12 | 98 | 36 | 2,7 | 1,30 | 1,16 |
| 16 | 563 | 114 | 4,9 | 1,37 | 1,21 |
| 20 | 3 391 | 453 | 7,5 | 1,41 | 1,25 |
| 24 | 18 561 | 1 782 | 10,4 | 1,43 | 1,28 |
| 28 | 72 652 | 7 771 | 9,3 | 1,31 | 1,31 |
Fonte: elaborado pelo autor; medição própria por enumeração do espaço de estados do quebra-cabeça de 8 peças.Nota: médias sobre 120 tabuleiros sorteados por profundidade (16 na profundidade 4, que só tem 16 tabuleiros). As profundidades reais foram obtidas por busca em largura a partir do estado-objetivo. b* é o fator de ramificação efetivo, raiz da equação em que a soma das potências de b* até a profundidade iguala o número de nós expandidos mais um.
A coluna da razão é o argumento inteiro. Nas profundidades pequenas, tanto faz. A partir da profundidade 16, a distância de Manhattan já poupa cinco sextos do trabalho; na profundidade 24, dez em cada onze nós. Trocar de heurística rende mais do que trocar de algoritmo. E o fator de ramificação efetivo mostra por quê: com h₂, o A* se comporta como se cada estado tivesse pouco mais de um sucessor — está praticamente andando em linha reta até a solução.
De onde vem uma heurística admissível
Não do acaso. A receita mais confiável é relaxar o problema: apague uma restrição das regras e resolva o problema mais fácil que sobrar; o custo exato dessa solução é uma heurística admissível para o problema original (LUGER, 2013), porque toda solução do problema original também é solução do relaxado, nunca ao contrário.
As duas heurísticas da tabela saem exatamente daí, e é bonito ver. No quebra-cabeça, a regra é que uma peça só desliza para a casa vazia vizinha. Apague "para a casa vazia" e sobre "uma peça pode ir para qualquer casa vizinha": o custo ótimo desse jogo relaxado é a soma das distâncias de Manhattan. Apague também "vizinha" e sobre "uma peça pode ir para qualquer casa": o custo ótimo passa a ser o número de peças fora do lugar. Quanto menos regras você apaga, mais forte é a heurística que sobra — e é por isso que h₂ domina h₁.
Cada regra apagada facilita o problema e enfraquece a estimativa. A arte está em apagar o mínimo que ainda dá um cálculo rápido.
Aplicação prática
Construa uma heurística em seis perguntas
Marque os itens conforme conseguir responder a cada um sobre um problema de busca da sua própria área.
0 de 6 — comece pela noção de distância.
Palpite exato
O limite que ninguém alcança
Vale imaginar o caso extremo. Se a heurística fosse perfeita — se h(n) = h*(n) em todo nó —, o A* sairia do início e caminharia direto até o objetivo, sem expandir um único nó fora da rota ótima. Não haveria busca: haveria execução. Esse é o limite superior de tudo o que uma heurística pode fazer, e a razão pela qual heurística é o assunto, e não o algoritmo. O A* é apenas o mecanismo que converte qualidade de palpite em economia de trabalho.
Do lado prático, sobra uma fraqueza que a tabela não mostra e que merece registro: o A* guarda todos os nós gerados na memória. É a mesma doença da busca em largura, e pela mesma razão. Em problemas grandes, ele não fica sem tempo — fica sem memória. A resposta clássica é a mesma da postagem anterior, aplicada agora ao caso informado: repetir para caber. O IDA*, de Richard Korf, roda buscas em profundidade sucessivas com um teto sobre f em vez de sobre a profundidade, e assim mantém as garantias do A* gastando memória linear (KORF, 1985).
Shakey levava horas para atravessar uma sala. O robô foi desligado, virou peça de museu e ganhou um marco do IEEE em 2017, quarenta e cinco anos depois de parar de andar. O algoritmo que ele deixou continua rodando alguns milhões de vezes por segundo, em toda parte, e a pergunta que ele resolve é a mesma de 1968: dado que não dá para olhar tudo, para onde olhar primeiro?
Pense em uma decisão do seu trabalho em que você já usa um palpite para não examinar todas as opções. Esse palpite é otimista ou pessimista — e o que você perde, exatamente, quando ele erra para o lado errado?
Nota do autor: os números do Quadro 1 e da Tabela 1 são medição própria, feita por implementação independente em Python durante a preparação deste texto, e não reproduções de tabelas de livro-texto; valores equivalentes circulam na literatura com pequenas variações, porque dependem do desempate na fila de prioridade, do sorteio das instâncias e de se o teste de objetivo ocorre na geração ou na expansão. Aqui o desempate é por ordem de inserção, o teste de objetivo ocorre sempre na expansão, e as médias da Tabela 1 vêm de 120 tabuleiros sorteados por profundidade, com semente fixa. A admissibilidade e a consistência da distância de Manhattan na malha do simulador foram verificadas por enumeração das 449 células, assim como a inadmissibilidade do triplo dela em 447 delas; no quebra-cabeça, a admissibilidade de h₁ e h₂ e a dominância de h₂ sobre h₁ foram verificadas nos 181.440 estados alcançáveis. Sobre a história: a correção de 1972 é aqui apenas registrada, a partir de sua referência bibliográfica; o autor não teve acesso ao texto integral, e o tratamento definitivo das condições sob as quais valem as garantias de otimalidade e de eficiência do A* é o de Dechter e Pearl (1985), que deve ser a fonte consultada por quem precisar do enunciado preciso. A atribuição do A* ao projeto Shakey segue o registro do próprio projeto e a literatura corrente; o artigo de 1968 não menciona o robô no título. A malha do simulador é fictícia e foi desenhada de propósito para separar os quatro comportamentos: sem o corredor em serpentina, a busca gulosa encontraria a rota ótima nesta malha, e o contraste do quadro desapareceria. A quarta edição de Russell e Norvig não tem tradução brasileira publicada até a data deste texto; a terminologia em português segue o uso corrente em Luger (2013).
Referências
- DECHTER, Rina; PEARL, Judea. Generalized best-first search strategies and the optimality of A*. Journal of the ACM, Nova York, v. 32, n. 3, p. 505-536, jul. 1985. Disponível em: https://dl.acm.org/doi/10.1145/3828.3830. Acesso em: 23 ago. 2026.
- DORAN, James E.; MICHIE, Donald. Experiments with the Graph Traverser program. Proceedings of the Royal Society of London: Series A, Londres, v. 294, n. 1437, p. 235-259, set. 1966. Disponível em: https://royalsocietypublishing.org/doi/10.1098/rspa.1966.0205. Acesso em: 23 ago. 2026.
- HART, Peter E.; NILSSON, Nils J.; RAPHAEL, Bertram. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, Nova York, v. 4, n. 2, p. 100-107, jul. 1968. Disponível em: https://ieeexplore.ieee.org/document/4082128/. Acesso em: 23 ago. 2026.
- HART, Peter E.; NILSSON, Nils J.; RAPHAEL, Bertram. Correction to "A formal basis for the heuristic determination of minimum cost paths". SIGART Newsletter, Nova York, n. 37, p. 28-29, dez. 1972. Disponível em: https://dl.acm.org/doi/10.1145/1056777.1056779. Acesso em: 23 ago. 2026.
- KORF, Richard E. Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence, Amsterdã, v. 27, n. 1, p. 97-109, set. 1985. Disponível em: https://www.cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf. Acesso em: 23 ago. 2026.
- LUGER, George F. Inteligência artificial. 6. ed. São Paulo: Pearson Education do Brasil, 2013.
- POHL, Ira. First results on the effect of error in heuristic search. In: MELTZER, Bernard; MICHIE, Donald (ed.). Machine Intelligence 5. Edimburgo: Edinburgh University Press, 1970. p. 219-236.
- RUSSELL, Stuart; NORVIG, Peter. Artificial intelligence: a modern approach. 4. ed. Hoboken: Pearson, 2021.
- SHAKEY the robot. In: WIKIPEDIA: the free encyclopedia. [São Francisco]: Wikimedia Foundation, 2026. Disponível em: https://en.wikipedia.org/wiki/Shakey_the_robot. Acesso em: 23 ago. 2026.
Comentários