Busca aplicada: recomendação, planejamento e otimização

Imagine, em fevereiro, uma secretaria municipal de educação do interior em que três problemas dividem a mesma mesa: as rotas do transporte e...

Imagine, em fevereiro, uma secretaria municipal de educação do interior em que três problemas dividem a mesma mesa: as rotas do transporte escolar, a grade de horários das escolas e a lista de conteúdos que a plataforma recém-contratada vai mostrar para cada aluno. Ninguém naquela sala chama isso de busca. Mas os três podem ser formulados dentro da mesma perspectiva de busca das duas postagens anteriores desta série, cada um com um tipo diferente de fronteira: um se resolve navegando de modo guloso num grafo de itens parecidos; outro, com um A* cuja heurística nasce de apagar uma regra do problema; e o terceiro, com uma busca que nem árvore tem. Esta postagem fecha a série mostrando como ideias das buscas cega e informada reaparecem em sistemas reais, quanto trabalho cada estratégia poupa em medições próprias sobre modelos didáticos, e quais garantias se mantêm ou se perdem quando o espaço de estados deixa de caber na tela (atualizado em 21/09/2026).

Caso 01

Fevereiro na secretaria

Fevereiro é o mês em que a educação básica brasileira resolve, no braço, alguns dos problemas mais estudados da ciência da computação. São 46,018 milhões de matrículas espalhadas por 178,76 mil escolas públicas e privadas, segundo o Censo Escolar de 2025 (Almeida; Verdélio, 2026). Cada uma dessas escolas precisa de uma grade de horários que caiba nas restrições dos professores. Boa parte precisa de rotas de transporte que caibam no orçamento e na jornada das crianças. E quase todas, hoje, têm alguma plataforma que precisa decidir qual conteúdo mostrar primeiro. A secretaria desta postagem é um cenário composto a partir dessas três tarefas: as pessoas que aparecem nela são personagens, não entrevistados.

Nas três salas onde esses problemas são resolvidos, a ferramenta costuma ser a mesma: uma planilha, um café e a experiência de quem já fez isso ano passado. Não há nada de errado nisso — mas há algo curioso. Os três problemas não são o mesmo problema, mas podem ser formulados dentro de uma perspectiva comum: busca em espaços de estados ou de soluções. Diferem no espaço, no objetivo, nas garantias e na literatura especializada de cada um — e é justamente por isso que vale olhar os três lado a lado.

Nas duas postagens anteriores, a série tratou das buscas cegas e das buscas informadas como máquinas de laboratório: uma malha quadriculada, um quebra-cabeça de oito peças, um robô que tremia. Esta postagem sai do laboratório. A pergunta agora é outra: quando alguém resolve um problema de verdade — recomendar, planejar, otimizar —, o que sobra do algoritmo do livro-texto?

Adianto a resposta, porque ela organiza o resto do texto: sobra o laço, e a garantia passa a ser negociada — às vezes se mantém, às vezes é trocada conscientemente por tempo.

Caso 02

O laço, pela terceira vez

Vale recompor o esqueleto em três linhas, porque ele é o fio de tudo o que vem depois. Uma busca precisa de um estado, de ações que levam de um estado a outro, de um custo por ação e de um teste de objetivo. O algoritmo mantém uma fronteira de estados conhecidos mas ainda não expandidos, retira um deles segundo alguma chave de ordenação, testa e gera os sucessores (Russell; Norvig, 2021). Busca cega e busca informada diferem apenas na chave.

Formular o problema — decidir o que é um estado — é a parte que o livro-texto resolve em meia página e a vida real cobra caro. Repare como a mesma frase muda de sentido nos três casos da secretaria:

recomendaçãoEstado = um item do catálogoAs ações são "pular para um item parecido". O objetivo é chegar perto do que o aluno quer. Custo: uma comparação.

planejamentoEstado = uma situação do mundoQuem está onde, o que já foi feito. As ações têm pré-condições e efeitos. O objetivo é uma condição, não um lugar.

otimizaçãoEstado = uma solução inteiraUma rota completa, uma grade completa. As ações não constroem: consertam. O objetivo é o menor custo possível.

A terceira ficha é a que quebra o padrão, e é bom encarar isso logo. Nos dois primeiros casos, um estado é um pedaço de solução e a busca vai construindo — é a busca em espaço de estados dos posts anteriores, com árvore, fronteira e caminho. No terceiro, cada estado já é uma solução completa, possivelmente ruim, e a busca não constrói: ela mexe. Quando o estado passa a ser a solução inteira, o caminho percorrido deixa de interessar e só o destino conta — e isso muda tanto o algoritmo quanto o que se pode prometer sobre ele.

Três seções, três casos. Em cada um, a mesma pergunta: qual é a fronteira, qual é a chave, e o que se perde.

Caso 03

Recomendação: navegar num grafo de vizinhos

Comece pelo problema que parece menos um problema de busca. Uma plataforma de conteúdo tem um catálogo — cem mil vídeos, dois milhões de produtos, quarenta mil questões de banco — e alguns milissegundos para escolher o que mostrar. A arquitetura padrão, descrita com clareza no artigo em que o YouTube abriu seu sistema de recomendação, tem dois estágios: um de geração de candidatos, que reduz milhões de itens a algumas centenas, e um de ordenação, que só então gasta um modelo pesado sobre esse punhado (Covington; Adams; Sargin, 2016).

O primeiro estágio é o que interessa aqui, e os autores o descrevem sem rodeios: cada item e cada usuário viram um vetor, e escolher os candidatos "se reduz a uma busca dos vizinhos mais próximos" nesse espaço. Um espaço de gosto, se quiser: itens parecidos ficam perto.

Por que não olhar todos

A solução óbvia é varrer o catálogo inteiro e ficar com os mais próximos. Ela é exata, trivial de programar e, num catálogo de milhões de itens sob um orçamento de dezenas de milissegundos, inviável na escala desses sistemas — os autores do artigo do YouTube pedem explicitamente um esquema aproximado, que não olhe o catálogo inteiro. É o mesmo beco da busca cega: correta, completa e cara demais.

Uma das saídas mais difundidas é construir, uma única vez, um grafo de proximidade: cada item guarda ponteiros para uns poucos itens parecidos. A consulta então não varre nada — ela caminha. Na versão mais simples, parte de um item qualquer, olha os vizinhos dele, pula para o que estiver mais perto do alvo e repete; quando nenhum vizinho melhora, para. O HNSW (Hierarchical Navigable Small World, algo como “mundo pequeno navegável e hierárquico”), um dos índices mais usados para esse fim, sofistica a ideia: organiza os itens numa hierarquia de grafos, construída incrementalmente, desce das camadas esparsas de cima (saltos longos) às densas de baixo (ajustes finos) e, na camada de baixo, mantém uma lista de candidatos em vez de um só (Malkov; Yashunin, 2018).

A consulta não varre o catálogo: ela salta de vizinho em vizinho, sempre para quem parece mais perto do alvo. A figura mostra um grafo plano, sem as camadas do HNSW — é o mecanismo mínimo, não o índice real.

Pare um segundo nesse mecanismo, porque ele é o ponto da seção. Um dos algoritmos que selecionam os candidatos que poderão aparecer na sua tela lembra de perto a busca gulosa do post anterior: quem orienta cada passo é só a distância ao alvo — o h —, sem nenhum g. A equivalência não é literal. A busca gulosa de melhor escolha clássica mantém uma fronteira global ordenada por h; a navegação no grafo, na forma mais simples, só olha os vizinhos do ponto em que está, e se parece mais com uma subida de encosta (hill climbing) do que com a gulosa do livro. E herda o defeito das duas: pode parar num mínimo local — um item que é melhor que todos os seus vizinhos e ainda assim não é o melhor do catálogo. Vale lembrar também que esse estágio só propõe candidatos: quem decide a ordem final na tela é o estágio de ordenação.

Guardar mais de um candidato

A saída é manter mais de um candidato. Em vez de guardar só o melhor ponto do momento, a busca mantém uma lista com os melhores candidatos encontrados e só para quando nenhum deles promete melhorar. No HNSW, o tamanho dessa lista é o parâmetro ef, e aumentá-lo tende a elevar o acerto e o custo ao mesmo tempo (Malkov; Yashunin, 2018). Há uma semelhança estrutural com a passagem da subida de encosta para a busca de melhor escolha: manter mais candidatos reduz a miopia da escolha puramente local. Não é, porém, a correção que define o A* — essa foi somar ao palpite o custo já percorrido, f = g + h (Hart; Nilsson; Raphael, 1968) —, e aqui não há g nenhum: não importa quantos saltos foram dados, só onde se chegou.

Modelo didático ≠ sistema de produção

As medições desta postagem usam modelos didáticos: pontos em duas dimensões, um grafo plano com cinco vizinhos por item, instâncias pequenas e sementes fixas. Chamo de largura da fronteira o número de candidatos mantidos — um análogo didático do ef, não uma implementação de HNSW. Sistemas em produção trabalham com vetores de alta dimensão, índices hierárquicos construídos e ajustados, restrições adicionais, objetivos múltiplos e métricas medidas com usuários reais. Os números abaixo ilustram mecanismos; não estimam o desempenho de nenhum sistema real.

Montei um catálogo fictício de 180 itens num plano de gosto de duas dimensões, liguei cada item aos cinco mais parecidos e rodei 300 consultas sorteadas, variando a largura da fronteira. O que ela compra aparece na proporção de vezes em que a busca devolve exatamente o item mais próximo:

fronteira 1 (gulosa)50,7%

fronteira 484,0%

fronteira 897,3%

fronteira 1698,7%

Acerto exato em 300 consultas, catálogo fictício de 180 itens, grafo plano com cinco vizinhos por item; largura da fronteira como análogo didático do ef. As comparações de distância por consulta sobem de 28,1 para 53,2 entre a primeira barra e a última — contra 180 da varredura completa.

A leitura é a de sempre nesta série: a garantia tem preço, e o preço é trabalho. A diferença é que aqui, em geral, ninguém paga o preço inteiro. Na recuperação aproximada de vizinhos, aceita-se deixar escapar de vez em quando o vizinho exato em troca de respostas mais rápidas — e o parâmetro existe justamente para que esse compromisso seja uma decisão explícita de engenharia, e não um acidente.

O que acontece quando o catálogo cresce

O argumento decisivo, porém, não está no acerto: está na escala. Repeti a medição com catálogos cada vez maiores, mantendo a fronteira em oito candidatos.

Tabela 1 — Navegação em grafo de proximidade plano (modelo didático, sem hierarquia) por tamanho do catálogo, em catálogos fictícios, 2026

Itens no catálogo	Acerto exato (%)	Comparações por consulta	Proporção do catálogo (%)
180	97,3	46,2	25,7
1 000	94,7	94,3	9,4
5 000	88,3	187,5	3,8
20 000	91,3	350,8	1,8

Fonte: elaborado pelo autor; medição própria em catálogos fictícios gerados em quatro agrupamentos, com 300 consultas sorteadas por tamanho.Nota: grafo de vizinhança com os cinco itens mais próximos de cada item, tornado simétrico; fronteira de oito candidatos; entrada sempre pelo item de índice zero. "Acerto exato" é a proporção de consultas em que a busca devolveu o mesmo item que a varredura completa devolveria. "Comparações" é a média de distâncias efetivamente calculadas por consulta.

Neste experimento, o catálogo foi multiplicado por 111 e o trabalho por consulta, por menos de oito. O número de comparações cresceu muito mais devagar que o catálogo. É esse descompasso — e não o acerto — que torna a abordagem atraente: numa varredura, multiplicar o acervo por 111 multiplica a conta por 111; aqui, a multiplicou por 7,6.

A coluna do acerto, porém, tem um recado incômodo: ela não sobe junto. Vai de 97,3% a 88,3% e volta a 91,3%, sem padrão claro. Não há como apontar uma causa única com este desenho — 300 consultas, uma semente, cinco vizinhos fixos, um grafo artificial —, e vários fatores concorrem: a densidade local, a posição do ponto de entrada, a distância média que a navegação precisa atravessar. O que o modelo mostra é que, sem ajuste, o acerto pode oscilar em silêncio conforme o acervo cresce. Atravessar distâncias longas por arestas curtas é justamente uma das dificuldades que a hierarquia do HNSW ataca, deixando os saltos longos numa camada de cima, esparsa, e os ajustes finos embaixo. O que medi aqui é a versão sem a hierarquia.

Caso 04

Planejamento: o neto do Shakey

O segundo problema da mesa é a van. Quatro alunos esperam em pontos diferentes de uma zona rural, a van leva dois por vez, e a escola fica na outra ponta. Qual é a sequência de ações que entrega todo mundo com o menor número de movimentos?

Repare que a pergunta mudou de natureza. No caso da recomendação, o objetivo era um lugar no espaço; aqui, o objetivo é uma condição — "todos entregues" —, e o que se procura não é um ponto, é uma sequência. Esse é o problema de planejamento, e ele tem uma certidão de nascimento: o STRIPS (Stanford Research Institute Problem Solver), escrito por Richard Fikes e Nils Nilsson em 1971 para dar um cérebro ao mesmo robô Shakey da postagem anterior (Fikes; Nilsson, 1971).

A ideia do STRIPS é de uma simplicidade que sobreviveu a cinquenta e cinco anos: um estado é um conjunto de fatos; uma ação tem pré-condições (os fatos que precisam valer para que ela possa ocorrer), uma lista de adição (os fatos que ela cria) e uma lista de remoção (os fatos que ela destrói). Planejar é buscar, no espaço desses estados, uma sequência que leve do estado inicial a um estado em que o objetivo valha. A notação mudou de nome — hoje se escreve em PDDL (Planning Domain Definition Language), a linguagem das competições internacionais de planejamento —, mas a anatomia é essa.

E o problema é o de sempre: o espaço explode. Na versão minúscula da van — sete pontos, quatro alunos, três situações possíveis por aluno — já são 567 combinações no papel, das quais 504 efetivamente alcançáveis. Troque por vinte alunos e trinta pontos e não há máquina.

A heurística que vem de apagar uma regra

A postagem anterior terminou com uma receita: para obter uma heurística admissível, apague uma restrição do problema, resolva exatamente o problema mais fácil que sobrar e use esse custo ótimo como estimativa (Luger, 2013). O planejamento heurístico moderno explora muito essa ideia — e a restrição que se apaga tem nome e endereço: a lista de remoção.

A intuição é bonita. Se as ações só adicionam fatos e nunca destroem nenhum, o mundo deixa de ter conflitos: nada do que você conquistou pode ser perdido depois. O custo do melhor plano desse problema relaxado — que a literatura chama de h⁺ — nunca supera o custo real, e por isso é admissível. O porém é que calcular h⁺ exatamente é, em geral, computacionalmente difícil (Betz; Helmert, 2009). O planejador FF (Fast-Forward), de Jörg Hoffmann e Bernhard Nebel, primeiro lugar na competição de 2000, contornou a dificuldade extraindo depressa, de forma gulosa, um plano relaxado — não necessariamente o melhor — e usando o tamanho dele como estimativa (Hoffmann; Nebel, 2001). Funciona muito bem na prática, e cobra um preço: a heurística do FF, h_FF, em geral não é admissível.

Atenção: relaxar não garante admissibilidade

O custo ótimo do problema relaxado, h⁺, é um limite inferior do custo real e, portanto, admissível. Heurísticas práticas que aproximam esse valor para caber no tempo, como a do FF (h_FF), podem perder essa propriedade — ela tende a superestimar h⁺. Já outras aproximações, como h_max, ficam sempre abaixo de h⁺ e continuam admissíveis (Betz; Helmert, 2009). Relaxamento é fonte de heurísticas; admissibilidade é uma propriedade que ainda precisa ser demonstrada ou verificada.

Tire a lista de remoção e o problema perde os conflitos. O custo do melhor plano relaxado é otimista; um plano relaxado achado às pressas pode não ser.

Para a van, não usei o FF: montei à mão uma estimativa inspirada no mesmo relaxamento, ignorando a capacidade e as remoções. Cada aluno que ainda espera exige pelo menos um embarque e um desembarque; cada aluno já a bordo exige pelo menos um desembarque; e é preciso, no mínimo, ir até o aluno pendente mais distante e voltar. Não é o h⁺ exato nem o h_FF: é um limite inferior simples. Verifiquei por enumeração que ela nunca supera o custo real em nenhum dos 504 estados alcançáveis — nesta instância, é admissível. Com ela na chave da fila, o resultado é este:

Tabela 2 — Desempenho de três estratégias no problema fictício da van escolar, 2026

Estratégia	Estados expandidos	Ações do plano	Plano ótimo?
Busca em largura (cega)	480	24	Sim, sempre
Busca em profundidade (cega)	35	28	Em 23 de 200 ordenações
A* com heurística de relaxamento	228	24	Sim, sempre

Fonte: elaborado pelo autor; medição própria por implementação independente em Python.Nota: problema fictício com sete pontos ligados em árvore, quatro alunos, capacidade de dois passageiros e custo 1 por ação (mover, embarcar, desembarcar); 504 estados alcançáveis. Os valores da busca em profundidade são as medianas de 200 execuções com ordens de sucessores sorteadas (expandidos: mínimo 25, máximo 49; plano: mínimo 24, máximo 32). O plano ótimo tem 24 ações, verificado por busca em largura.

Duas leituras, e a segunda é a interessante.

A primeira é a esperada: a heurística corta mais da metade do trabalho da busca em largura sem abrir mão de nada. Mesma resposta, 52,5% menos estados abertos.

A segunda é um contraexemplo que eu não planejava encontrar. A busca em profundidade — cega, sem nenhuma informação, a mais simplória do repertório — expandiu trinta e cinco estados, sete vezes menos que o A*. E devolveu um plano com 28 ações em vez de 24. Mudando apenas a ordem em que os sucessores entram na pilha, ela vai de 25 a 49 estados expandidos e de 24 a 32 ações no plano, acertando o ótimo em pouco mais de um décimo das tentativas. A busca em profundidade é barata porque é uma loteria: quando o problema não tem becos sem saída, quase qualquer caminho chega — e "quase qualquer caminho" é exatamente o que ela devolve.

Isso não é uma curiosidade de laboratório. É a razão pela qual tanto sistema em produção roda uma heurística construtiva simples e para por aí: em problemas sem armadilhas, o resultado fica perto o bastante. A diferença entre esse projeto e um erro é saber que se escolheu isso.

Caso 05

Otimização: quando a busca perde a árvore

O terceiro problema é a roteirização. Uma van, um depósito, treze paradas, e a pergunta clássica: em que ordem visitar todas e voltar, gastando o mínimo?

Aqui o espaço de busca muda de forma. Não há caminho parcial a expandir: qualquer ordem das treze paradas já é uma rota válida. O que existe é um conjunto de soluções completas, e ele tem 13!/2 = 3 113 510 400 elementos — três bilhões de rotas para treze entregas. Uma busca cega que enumerasse todas a um milhão por segundo levaria 52 minutos para decidir o itinerário de uma van. Com quinze paradas, seriam sete dias e meio.

Quando o estado é uma solução inteira, a busca deixa de ser uma árvore e vira um passeio: o algoritmo mantém uma solução na mão e tenta trocá-la por uma vizinha melhor. É a busca local (Russell; Norvig, 2021), e ela tem três peças: uma solução inicial, uma definição de vizinhança e uma regra de aceitação.

solução inicialVizinho mais próximoSaia do depósito e vá sempre à parada mais perto que ainda falta. É a gulosa outra vez, agora construindo uma rota.

vizinhançaTroca 2-optPegue dois trechos da rota, inverta o pedaço entre eles e veja se encurtou. Desfaz cruzamentos.

aceitaçãoSó se melhorarAceite a troca quando ela reduzir a distância. Simples, rápido — e é aqui que mora o mínimo local.

Rodei as três peças numa instância fictícia de um depósito e treze paradas, com o ótimo calculado exatamente por programação dinâmica (algoritmo de Held-Karp), para ter um parâmetro honesto de comparação:

Tabela 3 — Qualidade e esforço de quatro estratégias de roteirização em instância didática de 14 pontos, selecionada para evidenciar mínimo local, 2026

Estratégia	Distância	% do ótimo	Leituras de distância	Tempo (ms)
Ótimo exato (programação dinâmica)	1 406,7	100,0	319 514	107,9
Vizinho mais próximo	1 865,3	132,6	91	0,01
Vizinho mais próximo + 2-opt	1 528,0	108,6	1 263	0,14
2-opt com 200 reinícios aleatórios	1 406,7	100,0	347 064	38,9

Fonte: elaborado pelo autor; medição própria por implementação independente em Python sobre instância fictícia com coordenadas sorteadas e semente fixa.Nota: distâncias euclidianas em unidades arbitrárias do plano da instância. A instância foi escolhida entre quarenta sementes justamente porque nela o 2-opt fica preso acima do ótimo; na maioria das outras, ele o alcança. "Leituras de distância" usa a mesma unidade para todas as estratégias: cada leitura de uma distância entre dois pontos (o vizinho mais próximo lê uma por comparação; o 2-opt, quatro por troca avaliada; o Held-Karp, uma por transição da programação dinâmica). O tempo é a mediana de 15 execuções (5 nas duas mais lentas) na mesma máquina, em Python 3.11; serve para comparar as linhas entre si, não como referência absoluta. O 2-opt adota a regra da primeira melhora e para no primeiro mínimo local; os reinícios partem de ordens sorteadas.

A terceira linha é a aula inteira. O 2-opt saiu de 132,6% e chegou a 108,6% do ótimo com nove trocas e pouco mais de mil leituras de distância — e então parou, não porque tivesse chegado, mas porque nenhuma troca de dois trechos melhorava mais nada. Estava num mínimo local. Os 200 reinícios encontram o ótimo desta instância, mas fazem cerca de 275 vezes mais leituras — e nada garante que encontrariam em outra.

A primeira linha traz um recado que a tabela entrega de graça: com 14 pontos, o método exato ainda é perfeitamente viável — levou cerca de um décimo de segundo. O problema do Held-Karp é o crescimento, na ordem de n²·2ⁿ: passar de 14 para 28 paradas multiplica esse fator por mais de 65 mil. É nessa escala, e não na da instância didática, que as heurísticas deixam de ser opção e passam a ser necessidade.

Na recuperação aproximada, aceita-se às vezes perder o vizinho exato em troca de latência; no A*, uma boa heurística reduz o trabalho preservando as garantias; na busca local, aceita-se com frequência uma solução apenas localmente ótima em troca de velocidade. É por isso que boa parte da área gira em torno de estratégias para escapar de mínimos locais. O OR-Tools, biblioteca de otimização de código aberto do Google amplamente utilizada para roteirização, oferece, lado a lado, uma lista de construtores de solução inicial — vizinho mais próximo, economias de Clarke e Wright, varredura, Christofides — e uma lista de metaheurísticas para depois: descida gulosa, busca tabu, recozimento simulado e a busca local guiada, que a própria documentação indica como "geralmente a metaheurística mais eficiente para roteirização de veículos" (Google, 2026). Nenhuma delas promete o ótimo em geral; em compensação, a biblioteca permite fixar limites explícitos de tempo e de número de soluções.

Nesta busca local de solução única não existe uma fronteira como a do A*: existe uma bolinha num vale, e o trabalho é convencê-la a sair de um vale raso sem perder o que já ganhou. Outras variantes, como a busca tabu ou os métodos populacionais, guardam memórias ou conjuntos de candidatos.

Um aviso sobre o seu aplicativo de mapas

Vale desfazer um mal-entendido que esta série pode ter ajudado a criar. É verdade que o A* nasceu para achar caminhos e que ele está em todo lugar; não é verdade que o seu aplicativo de rotas rode um A* puro sobre a malha viária do país a cada consulta. Sistemas de rota em redes grandes fazem um pesado pré-processamento da malha — a técnica mais conhecida, as hierarquias de contração, adiciona atalhos calculados uma vez e depois responde consultas ordens de grandeza mais rápido que uma busca clássica (Geisberger, 2008). Em escala real, a maior parte do ganho não vem de buscar melhor: vem de ter buscado antes.

Caso 06

Os três no mesmo tabuleiro

Os números das três tabelas acima ficam mais convincentes quando se vê o formato do trabalho. Abaixo, os três problemas da secretaria, cada um com as estratégias da sua seção. Escolha um domínio, escolha uma estratégia e rode. O que interessa não é quem vence: é reparar que a mancha deixada por cada uma tem um desenho próprio — e que o desenho é o argumento. Cada aba mede o trabalho na sua própria unidade (comparações de distância, estados expandidos, comprimento da rota); os números não se comparam entre abas.

Recomendação · navegação gulosa · fronteira 1

Cada bolinha é um item do catálogo, ligado aos cinco itens mais parecidos (modelo didático plano, sem a hierarquia do HNSW). A busca parte de um item qualquer e salta sempre para o vizinho que parece mais perto do alvo — a cruz. Clique no palco para mudar o alvo e em Rodar para ver o caminho.

Rode as nove combinações antes de seguir. Na primeira aba, a gulosa toca algumas dezenas de itens e às vezes erra o alvo por pouco; a varredura acerta sempre e acende o catálogo inteiro. Na segunda, a busca em largura pinta quase todo o quadro de estados, a profundidade acende meia dúzia de quadradinhos espalhados e traz um plano pior, e o A* com a heurística de relaxamento fica no meio com a resposta da largura. Na terceira, a rota gulosa se cruza sozinha, o 2-opt desfaz os cruzamentos e trava, e os reinícios encontram o que o 2-opt sozinho não achou.

Caso 07

O que sobra do livro-texto

Juntando as três seções, dá para montar o quadro que eu gostaria de ter visto no começo do semestre:

Quadro 1 — Formulação e garantias da busca em três classes de aplicação

Aspecto	Recomendação	Planejamento	Otimização
O que é um estado	Um item do catálogo	Uma situação do mundo	Uma solução completa
O que é uma ação	Pular para um vizinho	Aplicar um operador	Alterar a solução
De onde vem a heurística	A distância no espaço de gosto	Relaxamento do problema	Não há: há função objetivo
O que se mede	Acerto e latência	Tamanho do plano e nós abertos	Distância do ótimo e tempo
Garantia realista	Nenhuma; acerto medido, não garantido	Ótimo, se a heurística for admissível	Nenhuma; melhor achado até agora
Quando parar	Quando nenhum vizinho melhora	Quando o objetivo sai da fronteira	Quando o relógio mandar

Fonte: elaborado pelo autor com base em Russell e Norvig (2021), Hoffmann e Nebel (2001), Malkov e Yashunin (2018) e na documentação da biblioteca OR-Tools (Google, 2026).Nota: o quadro descreve o uso corrente em sistemas de produção, não o conjunto de variantes possíveis de cada classe. Em planejamento, a garantia de otimalidade vale para a busca com heurística admissível; muitos planejadores de produção abrem mão dela em troca de velocidade.

A busca cega não morreu

Um risco desta série é deixar a impressão de que a busca cega é uma peça de museu, útil só para explicar a busca informada. Ela não é — e vale nomear onde ela continua sendo a escolha certa, não a escolha ingênua.

• Quando não existe heurística barata. Estimar o que falta pode custar mais que buscar. Se o palpite não sai de graça, a chave f = g volta a ser a melhor que existe.
• Quando o espaço é pequeno. Com poucas centenas de estados, projetar, validar e calcular uma heurística pode custar mais do que ela poupa.
• Quando a pergunta é "existe caminho?", não "qual o melhor?". Verificar alcançabilidade, resolver dependências entre pacotes, varrer o que um coletor de lixo ainda consegue enxergar: tudo isso é busca em profundidade, e nenhum desses problemas tem noção de "mais perto".
• Quando o custo é uniforme e a resposta é rasa. A busca em largura devolve o menor número de passos sem precisar de nada. É o algoritmo por trás de qualquer "graus de separação".

Busca cega e busca informada não são degraus de uma escada: são ferramentas com faixas de uso diferentes, e a faixa é decidida pelo custo do palpite.

Aplicação prática

Seis perguntas antes de escrever a primeira linha

Marque os itens conforme conseguir respondê-los sobre um problema de decisão da sua própria área — a escala do plantão, a distribuição das turmas, a fila de atendimento, a trilha de estudo.

Sei dizer o que é um estado no meu problema — e se ele é um pedaço de solução ou uma solução inteira. Sei quantos estados existem, pelo menos em ordem de grandeza. Se o espaço for pequeno, talvez uma heurística não compense seu custo de projeto e de cálculo — caber na memória não garante, sozinho, um tempo de busca aceitável. Sei o que é uma ação e quanto ela custa — e o custo é o que a organização realmente paga, não o que é fácil de medir. Tentei apagar uma restrição do problema para ver que estimativa sobra. Se o problema relaxado for fácil, tenho um bom candidato a heurística — e ainda preciso verificar suas propriedades e seu custo. Decidi o que faço quando o tempo acabar: entrego a melhor solução encontrada até então ou não entrego nada. Um sistema real precisa dessa resposta. Tenho um parâmetro honesto de comparação — o ótimo de uma instância pequena, ou a solução que o humano faz hoje — para saber se o algoritmo está ajudando.

0 de 6 — comece definindo o estado.

Caso encerrado

De volta à mesa de fevereiro

Uma coordenadora que monta a grade de horários no braço costuma fazer busca com retrocesso e uma heurística de ordenação de variáveis: começa pelo professor com menos janelas disponíveis, porque aprendeu que deixar esse para o fim dá retrabalho. É a heurística da variável mais restrita — MRV, de minimum remaining values —, que está no capítulo de satisfação de restrições dos livros da área (Russell; Norvig, 2021), e quem faz grade há anos chega a ela sozinho.

Um motorista que desenha a rota da van montando o trajeto pelo ponto mais próximo e depois desfazendo os cruzamentos que incomodam está fazendo, sem esse nome, algo muito parecido com vizinho mais próximo seguido de 2-opt.

E a plataforma contratada, se for como muitos sistemas desse tipo, pode usar algo parecido com uma navegação gulosa num grafo de vizinhos para escolher os candidatos que chegam à tela do aluno — só que esse componente costuma chegar pronto, embrulhado em contrato, sem que a secretaria saiba como inspecioná-lo ou ajustá-lo.

Essa assimetria é, para mim, a razão pedagógica de a série existir. Saber que ali pode haver uma busca aproximada com uma fronteira de tamanho configurável muda a conversa de "a inteligência artificial recomendou" para "qual é o critério, e quanto ele erra". É uma pergunta de licitação, não de laboratório.

Pense na decisão que a sua instituição toma todo ano no braço, sempre do mesmo jeito. Qual é o estado, qual é a ação, e qual é o palpite que a pessoa experiente usa sem saber que está usando?

Nota do autor: a secretaria de educação que abre e fecha o texto é um cenário composto, e as pessoas nela são personagens; nada do que se diz sobre a plataforma contratada se refere a um produto específico. Todos os números das Tabelas 1, 2 e 3 e do painel de barras são medição própria, obtida por implementação independente em Python durante a preparação deste texto, sobre modelos didáticos com sementes fixas; não são reproduções de tabelas de livro-texto nem de benchmarks publicados, e não estimam o desempenho de sistemas reais. O experimento de recomendação usa um grafo de proximidade plano, inspirado no mecanismo de navegação do HNSW mas sem a hierarquia nem a construção incremental do índice real; a "largura da fronteira" é um análogo didático do parâmetro ef. As medições usam distância euclidiana em duas dimensões; sistemas reais operam em dimensões muito maiores, regime em que o comportamento pode mudar substancialmente e depende da dimensionalidade intrínseca, da distribuição dos dados e dos parâmetros do índice — esse efeito não foi medido aqui. As instâncias foram escolhidas de propósito para separar os comportamentos: na roteirização, foram testadas quarenta sementes e escolhida uma em que o 2-opt trava acima do ótimo. Na Tabela 3, o esforço é medido numa única unidade para todas as estratégias — leituras de distância entre pontos — e complementado pelo tempo na mesma máquina; versões anteriores desta postagem misturavam células da programação dinâmica com cálculos de distância, o que não permitia comparar as linhas. A heurística usada no A* da van foi construída à mão a partir do relaxamento do problema; sua admissibilidade foi verificada por enumeração dos 504 estados alcançáveis, comparando a estimativa ao custo ótimo real de cada estado, e vale para esta instância — não é uma propriedade geral de heurísticas derivadas de relaxamento, como a do FF, que em geral não é admissível. Os valores da busca em profundidade são medianas de 200 ordens de sucessores sorteadas; no simulador, ela usa uma ordem fixa, e por isso seus números diferem da mediana da tabela. Sobre as fontes: o artigo do HNSW é citado na versão de acesso aberto do arXiv, conforme o critério de acesso livre desta série; a versão revisada foi publicada depois na IEEE Transactions on Pattern Analysis and Machine Intelligence (DOI 10.1109/TPAMI.2018.2889473). Para as hierarquias de contração, cita-se a dissertação aberta de Geisberger; o trabalho canônico, com Sanders, Schultes e Delling, saiu nos anais do WEA 2008 (DOI 10.1007/978-3-540-68552-4_24). O número de matrículas e de escolas vem da divulgação do Censo Escolar de 2025 noticiada pela Agência Brasil; as publicações do Inep não puderam ser consultadas durante a preparação do texto.

Glossário

Termos técnicos em ordem alfabética. Os termos com sublinhado pontilhado no texto trazem até aqui; o botão ao lado do verbete leva de volta.

2-opt

Movimento de busca local para rotas: remove dois trechos da rota e reconecta as pontas invertendo o pedaço entre eles. Aplicado só quando encurta a rota, desfaz cruzamentos; para quando nenhuma troca melhora. Caso 05

A* (A-estrela)

Busca informada que ordena a fronteira por f(n) = g(n) + h(n): o custo já percorrido mais a estimativa do que falta. Devolve a solução ótima quando a heurística é admissível. Tema da postagem sobre busca informada. Casos 03 e 04

Busca de vizinhos mais próximos

Encontrar, num conjunto de vetores, os itens mais próximos de uma consulta. É aproximada quando se aceita, de vez em quando, não devolver o vizinho exato em troca de velocidade — em inglês, approximate nearest neighbor (ANN). Caso 03

Busca local

Família de métodos que mantém uma solução completa e tenta trocá-la por uma solução vizinha melhor. Na forma mais simples, guarda uma única solução e pode terminar num mínimo local. Caso 05

ef

Parâmetro do HNSW: tamanho da lista dinâmica de candidatos mantida durante a busca. Valores maiores tendem a aumentar o acerto e o custo. No modelo didático desta postagem, corresponde à “largura da fronteira”. Caso 03

FF (Fast-Forward)

Planejador de Jörg Hoffmann e Bernhard Nebel, primeiro colocado na competição de planejamento de 2000. Estima a distância ao objetivo extraindo, de forma gulosa, um plano do problema sem listas de remoção. Caso 04

Fronteira

Conjunto de estados já gerados e ainda não expandidos. A ordem em que a busca retira estados dela define a estratégia: fila (largura), pilha (profundidade) ou prioridade por g, h ou g + h. Caso 02

Grafo de proximidade

Grafo em que cada item é ligado a alguns itens parecidos com ele. A busca navega por essas ligações em vez de comparar a consulta com o catálogo inteiro. Caso 03

h⁺, h_FF e h_max

Heurísticas derivadas do problema sem listas de remoção. h⁺ é o custo do melhor plano relaxado: admissível, mas difícil de calcular. h_FF usa um plano relaxado achado de forma gulosa: rápida e, em geral, não admissível. h_max fica sempre abaixo de h⁺: admissível, porém menos informativa. Caso 04

Held-Karp

Algoritmo exato, de programação dinâmica, para o problema do caixeiro-viajante. Garante a rota ótima, mas seu custo cresce na ordem de n²·2ⁿ, o que o limita a instâncias pequenas. Caso 05

Heurística admissível

Heurística é uma estimativa, h(n), do custo que falta de um estado até o objetivo. Ela é admissível quando nunca superestima esse custo: h(n) ≤ h*(n) em todo estado. Caso 04

HNSW (Hierarchical Navigable Small World)

“Mundo pequeno navegável e hierárquico”: índice para busca aproximada de vizinhos que organiza os itens em camadas de grafos de proximidade, das mais esparsas (saltos longos) às mais densas (ajustes finos). Proposto por Malkov e Yashunin. Caso 03

Metaheurística

Estratégia geral que guia uma busca local para escapar de mínimos locais. Exemplos: busca tabu (proíbe por um tempo desfazer movimentos recentes), recozimento simulado (aceita pioras com probabilidade decrescente) e busca local guiada (penaliza características das soluções em que a busca ficou presa). Caso 05

Mínimo local

Solução, ou item, melhor que todas as suas vizinhas, mas não necessariamente a melhor de todas. É onde a navegação gulosa e a busca local simples costumam parar. Casos 03 e 05

MRV (minimum remaining values)

Heurística da variável mais restrita, usada em satisfação de restrições: atribuir primeiro a variável com menos valores ainda possíveis — por exemplo, o professor com menos horários livres. Caso encerrado

PDDL (Planning Domain Definition Language)

Linguagem padrão para descrever domínios e problemas de planejamento automatizado, adotada nas competições internacionais da área. Herda do STRIPS a anatomia das ações. Caso 04

Relaxamento

Versão de um problema em que uma ou mais restrições são removidas. O custo ótimo do problema relaxado nunca supera o do original; por isso ele serve de base para heurísticas admissíveis. Caso 04

STRIPS (Stanford Research Institute Problem Solver)

Planejador criado em 1971 por Richard Fikes e Nils Nilsson para o robô Shakey. Deu nome à representação em que cada ação tem pré-condições, lista de adição e lista de remoção. Caso 04

Vizinho mais próximo (heurística de rota)

Constrói uma rota partindo do depósito e indo sempre à parada mais próxima ainda não visitada. É rápida e gulosa; a rota resultante costuma ter cruzamentos. Caso 05

Referências

1. ALMEIDA, Daniella; VERDÉLIO, Andreia. Censo registra queda de 1 milhão de matrículas na educação básica. Agência Brasil, Brasília, 26 fev. 2026. Disponível em: https://agenciabrasil.ebc.com.br/educacao/noticia/2026-02/censo-registra-queda-de-1-milhao-de-matriculas-na-educacao-basica. Acesso em: 20 set. 2026.
2. BETZ, Christoph; HELMERT, Malte. Planning with h+ in theory and practice. In: GERMAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, 32., 2009, Paderborn. KI 2009: advances in artificial intelligence. Berlim: Springer, 2009. Disponível em: https://ai.dmi.unibas.ch/papers/betz-helmert-ki2009.pdf. Acesso em: 21 set. 2026.
3. COVINGTON, Paul; ADAMS, Jay; SARGIN, Emre. Deep neural networks for YouTube recommendations. In: ACM CONFERENCE ON RECOMMENDER SYSTEMS, 10., 2016, Boston. Proceedings of the 10th ACM Conference on Recommender Systems. Nova York: ACM, 2016. p. 191-198. Disponível em: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/45530.pdf. Acesso em: 20 set. 2026.
4. FIKES, Richard E.; NILSSON, Nils J. STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, Amsterdã, v. 2, n. 3-4, p. 189-208, 1971. Disponível em: https://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/strips.pdf. Acesso em: 20 set. 2026.
5. GEISBERGER, Robert. Contraction hierarchies: faster and simpler hierarchical routing in road networks. 2008. Diplomarbeit (Diplom em Informática) – Institut für Theoretische Informatik, Universität Karlsruhe, Karlsruhe, 2008. Disponível em: https://ae.iti.kit.edu/download/diploma_thesis_geisberger.pdf. Acesso em: 20 set. 2026.
6. GOOGLE. Routing options: OR-Tools. [S. l.]: Google for Developers, 18 mar. 2026. Disponível em: https://developers.google.com/optimization/routing/routing_options. Acesso em: 21 set. 2026.
7. 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: 20 set. 2026.
8. HOFFMANN, Jörg; NEBEL, Bernhard. The FF planning system: fast plan generation through heuristic search. Journal of Artificial Intelligence Research, [s. l.], v. 14, p. 253-302, 2001. Disponível em: https://www.jair.org/index.php/jair/article/view/10276. Acesso em: 20 set. 2026.
9. LUGER, George F. Inteligência artificial. 6. ed. São Paulo: Pearson Education do Brasil, 2013.
10. MALKOV, Yury A.; YASHUNIN, Dmitry A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. [S. l.]: arXiv, 2018. Pré-publicação arXiv:1603.09320v4. Disponível em: https://arxiv.org/abs/1603.09320. Acesso em: 20 set. 2026.
11. RUSSELL, Stuart; NORVIG, Peter. Artificial intelligence: a modern approach. 4. ed. Hoboken: Pearson, 2021.