Em 1959, um engenheiro da Bell Labs publicou um artigo sobre como atravessar labirintos e um holandês publicou três páginas de um algoritmo ...
Fronteira 01
Dois homens, um ano, quatro algoritmos
Em abril de 1957, no Simpósio Internacional sobre a Teoria da Comutação, em Harvard, Edward F. Moore apresentou um trabalho com o título mais modesto possível: The shortest path through a maze — o caminho mais curto através de um labirinto (MOORE, 1959). Moore trabalhava na Bell Labs e o labirinto era uma metáfora educada: o problema real era rotear chamadas telefônicas interurbanas por uma malha de centrais. Na época, isso era feito por tentativa e erro.
O algoritmo que ele descreveu cabe em uma frase. Dê ao ponto de partida o rótulo 0. Depois, para k = 0, 1, 2, …, dê o rótulo k+1 a todos os pontos ainda sem rótulo que sejam vizinhos de algum ponto com rótulo k. Quando o destino receber um rótulo, o número dele é a distância mínima. É a busca em largura, e ela não nasceu na inteligência artificial: nasceu para não deixar cair uma ligação.
Dois anos depois, do outro lado do Atlântico, um jovem programador do Centro de Matemática de Amsterdã precisava de uma demonstração para o computador ARMAC. Ele contou a história décadas depois, em entrevista (MISA, 2010):
"Certa manhã eu estava fazendo compras em Amsterdã com minha jovem noiva e, cansados, sentamos no terraço de um café para tomar um café, e eu estava justamente pensando se conseguiria fazer aquilo, e então projetei o algoritmo do caminho mais curto. Como eu disse, foi uma invenção de vinte minutos."
Edsger W. Dijkstra, em entrevista a Philip L. Frana
Dijkstra reduziu o mapa rodoviário dos Países Baixos a 64 cidades — porque 64 cabia em seis bits — e a demonstração funcionou. O artigo saiu em 1959, com três páginas (DIJKSTRA, 1959). Ele gostava de dizer que o texto ficou bom justamente porque foi concebido sem papel e lápis: quem não pode anotar é obrigado a evitar toda complexidade evitável.
Moore procurava o caminho com menos trechos. Dijkstra procurava o caminho mais barato. A diferença entre os dois problemas é exatamente a diferença entre dois dos algoritmos deste texto — e a semelhança entre os dois algoritmos é maior do que qualquer um dos dois teria previsto.
Fronteira 02
Um algoritmo só, quatro filas de espera
Em outra postagem tratamos da formulação de problemas: como se transforma um pedaço do mundo em estados, ações e custos. Suponha esse trabalho feito. Existe um estado inicial, existem ações que levam de um estado a outro, existe um teste que diz se chegamos. Falta percorrer.
Toda busca cega — "cega" porque nenhum destes quatro algoritmos faz a menor ideia de onde o objetivo está — segue o mesmo laço:
O laço comum às quatro
- Coloque o estado inicial na fronteira.
- Enquanto a fronteira não estiver vazia:
- Retire um nó da fronteira.
- Se ele passa no teste de objetivo, devolva o caminho.
- Senão, gere os sucessores dele e coloque-os na fronteira.
- Devolva "sem solução".
A fronteira é o conjunto dos nós já gerados mas ainda não expandidos — a borda entre o que a busca já conhece e o que ela ainda não olhou. E o laço acima tem um buraco proposital, no passo 3: qual nó retirar? Não há nada no problema que responda a isso. A resposta é uma decisão de engenharia, e é só ela que separa os quatro algoritmos (RUSSELL; NORVIG, 2021).
O laço é idêntico nos quatro casos. Troca-se o recipiente da fronteira e nasce outro algoritmo, com outras garantias e outro custo.
As quatro buscas cegas são o mesmo algoritmo; o que muda é a disciplina da fronteira. Guardar isso poupa metade do esforço de decorar as tabelas de complexidade que vêm a seguir — elas deixam de ser quatro listas soltas e viram consequências de uma escolha só.
Fronteira 03
Largura: a onda que não cabe na sala
A busca em largura expande primeiro o nó mais raso da fronteira. Visualmente, é uma onda circular saindo do ponto inicial: todos os vizinhos, depois todos os vizinhos dos vizinhos, e assim por diante. Ela tem duas propriedades excelentes e uma catastrófica.
As excelentes: é completa — se existe solução, ela acha (LUGER, 2013); e é ótima em número de passos, porque só chega ao nível d+1 depois de ter esgotado o nível d. Se todos os passos custam a mesma coisa, ótima em número de passos é o mesmo que ótima, ponto. Guarde essa condicional; ela reaparece daqui a duas seções.
A catastrófica é a memória. Para poder retomar depois, a busca precisa guardar a fronteira inteira — e a fronteira inteira de uma árvore de ramificação b na profundidade d tem b elevado a d nós. Não é uma lista grande. É uma lista impossível.
Tabela 1 — Memória exigida pela fronteira da busca em largura, por profundidade da solução, em árvore de ramificação 10
| Profundidade da solução | Nós na fronteira | Memória | Cabe em quê |
|---|---|---|---|
| 4 | 10 000 | 9,8 MiB | Qualquer celular |
| 6 | 1 000 000 | 976,6 MiB | Um notebook comum |
| 8 | 100 000 000 | 95,4 GiB | Um servidor caro |
| 10 | 10 000 000 000 | 9,3 TiB | Um rack inteiro |
| 12 | 1 000 000 000 000 | 931,3 TiB | Nada que você vá alugar |
| 14 | 100 000 000 000 000 | 90,9 PiB | Um centro de dados |
Fonte: elaborado pelo autor.Nota: contagem de nós igual a 10 elevado à profundidade; estimativa de 1 KiB por nó, praxe adotada em Russell e Norvig (2021). Unidades binárias: 1 MiB = 2²⁰ bytes; 1 GiB = 2³⁰; 1 TiB = 2⁴⁰; 1 PiB = 2⁵⁰.
A mesma árvore, duas ordens de visita. À esquerda, tudo o que a largura precisa guardar ao mesmo tempo. À direita, tudo o que a profundidade precisa guardar.
Repare no que a tabela diz de fato. Se o computador consegue gerar um milhão de nós por segundo, a profundidade 10 leva umas três horas — irritante, mas viável. A memória para a mesma profundidade são 9,3 TiB. A busca em largura não fica sem tempo: ela fica sem memória, e fica muito antes. Esse detalhe move o resto da história.
Fronteira 04
Profundidade: o fio de Ariadne
A busca em profundidade expande sempre o nó mais recente da fronteira, e por isso mergulha por um ramo até não haver mais para onde ir. Só então volta ao último ponto onde havia alternativa e tenta a próxima. É o método que Teseu usou com o novelo de Ariadne, e que foi descrito formalmente pelo menos desde o século XIX, nos estudos de percurso de labirintos de Trémaux e Tarry (SCHRIJVER, 2012).
A economia é espetacular. Como a busca só precisa lembrar o caminho atual mais os irmãos ainda não tentados de cada nó desse caminho, a memória é b × m, onde m é a profundidade máxima — produto, não potência. Na árvore da Tabela 1, na profundidade 14, a largura pediria 90,9 PiB e a profundidade pede cerca de 140 nós. Cento e quarenta. A profundidade troca as duas garantias da largura por um consumo de memória que é apenas linear.
E as garantias vão embora inteiras:
- Não é ótima. Ela devolve a primeira solução que encontrar, que pode estar a mil passos de distância enquanto outra, a dois, esperava no ramo vizinho.
- Não é completa em espaços infinitos. Se um ramo não termina — e num problema com estados gerados sob demanda isso é comum — ela desce por ele para sempre.
- Não é completa nem em espaços finitos, se a implementação não guardar os estados já visitados: um ciclo de três estados a prende indefinidamente. A versão que mantém esse conjunto — a busca em grafo, e não em árvore — é a que aparece nos livros de algoritmos (CORMEN et al., 2022), e custa memória de novo.
Há um detalhe que costuma escapar e que vale fixar: o resultado da busca em profundidade depende da ordem em que os sucessores foram listados. Trocar a ordem da lista de adjacência muda a resposta — e nenhuma das duas respostas é mais correta que a outra do ponto de vista do algoritmo. A busca em largura não tem essa fragilidade, porque o nível inteiro é varrido antes de qualquer decisão.
A versão domesticada chama-se busca em profundidade limitada: mergulhe, mas nunca além de um limite ℓ. Isso resolve o ramo infinito e cria um problema novo — se ℓ for menor que a profundidade da solução, a busca devolve "não achei" com toda a confiança do mundo. E quase nunca se sabe qual ℓ usar. Guarde essa pergunta em aberto; a Fronteira 06 vive dela.
Fronteira 05
Custo uniforme: quando o passo tem preço
Volte à condicional da Fronteira 03: a largura é ótima se todos os passos custarem a mesma coisa. Quase nunca custam. Uma via expressa e uma rua de terra são ambas "um passo" no grafo, e ninguém confunde as duas.
A busca de custo uniforme resolve isso trocando a fila comum por uma fila de prioridade ordenada pelo custo acumulado desde o início, o famoso g(n). Retira-se sempre o nó mais barato conhecido. A busca deixa de se espalhar em ondas de distância e passa a se espalhar em ondas de preço. É, em essência, o algoritmo de Dijkstra reescrito na linguagem de árvores de busca.
Menos trechos não é o mesmo que mais barato. Quando os custos deixam de ser iguais, os dois objetivos se separam — e só um deles é o que você queria.
O menor número de passos e o menor custo são objetivos diferentes, e confundi-los é o erro mais caro desta lista. Um voo direto pode custar o triplo de uma rota com duas conexões. Um caminho com poucas ruas pode levar por três quilômetros de congestionamento. A largura responde "menos passos" com perfeição; se a pergunta era outra, a perfeição não ajuda.
A armadilha que derruba gente em prova
Na busca em largura, pode-se testar o objetivo no momento em que o nó é gerado. Na busca de custo uniforme, isso está errado, e o erro é silencioso. É preciso testar o objetivo apenas quando o nó é retirado da fronteira para expansão.
O motivo: encontrar o objetivo não significa ter encontrado o caminho mais barato até ele. Pode existir, esperando na fronteira, um nó mais barato que ainda vai gerar uma rota melhor para o mesmo objetivo. Só quando o objetivo chega ao topo da fila de prioridade é que se sabe que nada mais barato restou. É por isso, aliás, que a busca de custo uniforme costuma expandir mais nós que a largura no mesmo grafo: ela precisa esgotar tudo o que é mais barato que a solução antes de poder declará-la ótima.
Duas outras condições fecham o quadro. A busca de custo uniforme é completa e ótima desde que nenhuma ação tenha custo negativo e que exista um custo mínimo ε maior que zero. Com custos zero encadeados, ela pode ficar presa girando de graça; com custos negativos, a lógica da fila de prioridade desmorona, porque um caminho já descartado poderia ficar barato mais adiante.
Fronteira 06
Aprofundamento iterativo: repetir para caber
Ficamos com um impasse. A largura tem as garantias e não cabe na memória. A profundidade cabe na memória e não tem garantia nenhuma. A profundidade limitada teria as duas, se soubéssemos o limite — e não sabemos.
A saída é de uma obviedade quase constrangedora: se não sabemos o limite, tente todos. Rode a busca em profundidade com limite 0. Não achou? Limite 1. Não achou? Limite 2. E assim por diante. É a busca em profundidade com aprofundamento iterativo.
Antes de ler o próximo parágrafo, responda de cabeça: refazendo do zero todos os níveis rasos a cada rodada, quanto trabalho a mais isso custa em relação a fazer a busca em largura uma vez só? Dobro? Dez vezes? Cem?
Em uma árvore de ramificação 10, custa 11% a mais.
A intuição erra porque conta rodadas, e o que importa é o tamanho delas. Numa árvore com ramificação b, o último nível sozinho tem quase tantos nós quanto todos os anteriores somados. Refazer os níveis rasos é refazer a parte barata. Richard Korf demonstrou o caso geral em 1985: a sobrecarga tende a b/(b−1), e o aprofundamento iterativo é assintoticamente ótimo em tempo, espaço e comprimento da solução entre todas as buscas em árvore sem informação de domínio (KORF, 1985).
Tabela 2 — Nós gerados pelo aprofundamento iterativo e pela busca em largura, com objetivo na profundidade 5, por fator de ramificação
| Ramificação b | Largura | Aprofundamento iterativo | Sobrecarga | b/(b−1) |
|---|---|---|---|---|
| 2 | 62 | 114 | 1,84 | 2,00 |
| 3 | 363 | 537 | 1,48 | 1,50 |
| 5 | 3 905 | 4 875 | 1,25 | 1,25 |
| 10 | 111 110 | 123 450 | 1,11 | 1,11 |
| 20 | 3 368 420 | 3 545 700 | 1,05 | 1,05 |
| 35 | 54 066 635 | 55 656 825 | 1,03 | 1,03 |
Fonte: elaborado pelo autor; a razão-limite b/(b−1) é o coeficiente demonstrado em Korf (1985).Nota: contagem de nós gerados até a profundidade 5, exclusive a raiz; no aprofundamento iterativo, o nível j é gerado 5−j+1 vezes. Cálculo do autor, conferido por enumeração.
Cada rodada refaz tudo o que a anterior fez. Como o último nível concentra quase todo o volume, refazer os anteriores sai barato.
Refazer os níveis rasos custa 11% a mais, não o dobro — e, em troca desses 11%, o algoritmo passa a guardar b × d nós em vez de b elevado a d. Na profundidade 14 da Tabela 1, é a diferença entre 90,9 PiB e cerca de 140 KiB. É por isso que o aprofundamento iterativo é o padrão de fato quando o espaço é grande, os custos são uniformes e não há heurística disponível.
O bônus que ninguém tinha planejado
Há um efeito colateral que transformou a técnica em obrigatória no xadrez computacional. O primeiro uso documentado é do programa Chess 4.5, da Universidade Northwestern, apresentado por David Slate e Larry Atkin em 1977 (SLATE; ATKIN, 1977). Eles não estavam economizando memória: estavam usando o resultado da rodada rasa para ordenar os lances da rodada seguinte. Com a poda alfa-beta, examinar primeiro o lance que já se mostrou bom corta ramos inteiros da árvore. O resultado é contraintuitivo até para quem já aceitou os 11%: buscar até a profundidade 8 passando por todas as profundidades anteriores costuma ser mais rápido do que ir direto à profundidade 8.
Há ainda uma terceira virtude, prática: como cada rodada termina com uma resposta válida, o programa pode ser interrompido a qualquer momento e ainda assim entregar o melhor lance encontrado até ali. Quem já jogou contra um computador com relógio se beneficiou disso sem saber.
Fronteira 07
As quatro no mesmo grafo
Descrições lado a lado convencem pouco. Abaixo, a mesma rede — oito aeroportos, doze trechos, tarifas fictícias em reais — percorrida pelos quatro algoritmos. O objetivo é sempre sair de Brasília e chegar a Salvador. Clique em uma estratégia e depois avance passo a passo, ou peça para rodar até o fim.
Busca em largura · fronteira em fila (FIFO)
Sai sempre o nó que entrou há mais tempo — e o mais antigo é sempre o mais raso. Clique em Próximo passo para expandir o primeiro aeroporto.
Fronteira BSB
expandidos 0
Vale rodar as quatro antes de seguir. O que aparece é o resumo desta postagem inteira: a largura acha a rota com menos conexões, que é também a mais cara da rede; a profundidade sai andando e aceita a primeira coisa que encontra; o custo uniforme acha a rota mais barata e, para poder garantir isso, precisa expandir a rede quase toda; o aprofundamento iterativo chega à mesma rota da largura sem nunca guardar mais que um punhado de nós.
Quadro 1 — Comportamento dos quatro algoritmos de busca cega na rede de exemplo, 2026
| Algoritmo | Rota devolvida | Voos | Tarifa (R$) | Nós visitados |
|---|---|---|---|---|
| Largura | BSB–CNF–SSA | 2 | 1 900 | 5 |
| Profundidade | BSB–CNF–GYN–VIX–IOS–PMW–AJU–SSA | 7 | 3 550 | 8 |
| Custo uniforme | BSB–PMW–IOS–SSA | 3 | 1 050 | 8 |
| Aprofundamento iterativo | BSB–CNF–SSA | 2 | 1 900 | 9 |
Fonte: elaborado pelo autor a partir da rede fictícia do simulador desta postagem.Nota: sucessores sempre visitados em ordem alfabética do código do aeroporto. No aprofundamento iterativo, "nós visitados" soma as três rodadas (limites 0, 1 e 2), com 1, 4 e 4 visitas respectivamente. A rede admite doze rotas sem repetição de aeroporto; a mais barata é BSB–PMW–IOS–SSA, a R$ 1 050, e a de menos voos é BSB–CNF–SSA, a R$ 1 900.
A segunda linha do quadro merece atenção. Entre as doze rotas possíveis nessa rede, a busca em profundidade encontrou exatamente a mais cara — sete voos e R$ 3 550, mais que o triplo da tarifa ótima. Não foi azar estatístico: foi a consequência direta de ela aceitar o primeiro caminho completo que apareceu, e o primeiro caminho a aparecer depende só da ordem em que os aeroportos foram listados. Reordene a lista de adjacência e o mesmo algoritmo devolve outra rota, com a mesma convicção.
Repare também que a profundidade visitou oito nós — tantos quanto o custo uniforme, que devolveu a resposta ótima. O apelo da busca em profundidade nunca foi velocidade: é memória. Nesta rede de oito aeroportos ninguém precisa economizar memória, e por isso ela aparece aqui só com as desvantagens à mostra. É na Tabela 1, lá na profundidade 14, que ela cobra a fatura a seu favor.
Quadro 2 — Propriedades formais dos quatro algoritmos de busca cega
| Critério | Largura | Profundidade | Custo uniforme | Aprofundamento iterativo |
|---|---|---|---|---|
| Completa? | Sim, se b é finito | Não | Sim, se todo custo ≥ ε > 0 | Sim, se b é finito |
| Ótima? | Só com custos iguais | Não | Sim | Só com custos iguais |
| Tempo | O(bd) | O(bm) | O(b1+⌊C*/ε⌋) | O(bd) |
| Memória | O(bd) | O(b m) | O(b1+⌊C*/ε⌋) | O(b d) |
| Fronteira | Fila (FIFO) | Pilha (LIFO) | Fila de prioridade por g(n) | Pilha com limite crescente |
Fonte: elaborado pelo autor com base em Russell e Norvig (2021), Luger (2013) e Korf (1985).Nota: b é o fator de ramificação; d, a profundidade da solução mais rasa; m, a profundidade máxima da árvore; C*, o custo da solução ótima; ε, o menor custo de ação. Quadro de natureza qualitativa.
Aplicação prática
Escolha o algoritmo em seis perguntas
Marque os itens conforme conseguir responder a cada um sobre um problema da sua própria área. As três primeiras perguntas quase sempre decidem sozinhas.
0 de 6 — comece pelos custos.
Para o dia a dia, um resumo grosseiro que raramente falha: custos diferentes pedem custo uniforme; custos iguais e espaço pequeno pedem largura; custos iguais e espaço grande pedem aprofundamento iterativo; e a busca em profundidade pura serve quando qualquer solução basta, ou como peça interna de outro algoritmo.
Fronteira vazia
O que sobra quando a fronteira esvazia
Moore queria completar ligações telefônicas. Dijkstra queria uma demonstração bonita para uma máquina nova. Korf queria caber na memória de 1985. Slate e Atkin queriam ganhar torneios de xadrez. Nenhum deles estava escrevendo um capítulo de livro-texto de inteligência artificial, e os quatro escreveram.
O que os une é o desconforto com o mesmo buraco: retire um nó da fronteira — qual? A largura respondeu "o mais antigo", a profundidade respondeu "o mais novo", o custo uniforme respondeu "o mais barato", o aprofundamento iterativo respondeu "o mais novo, mas com um teto que vai subindo". Quatro respostas, quatro algoritmos, uma linha de diferença.
Há uma quinta resposta, e ela abre o próximo capítulo do assunto: "o que parece estar mais perto do objetivo". Para dá-la, é preciso alguma coisa que nenhum dos quatro tem — conhecimento sobre o domínio, na forma de uma estimativa. É onde as buscas cegas terminam e as informadas começam, com o A* à frente. Mas convém lembrar da postagem anterior: nenhuma delas salva uma formulação ruim. Um algoritmo melhor apenas fracassa mais rápido.
Pense em uma decisão repetitiva do seu trabalho que hoje é tomada "no olho". Se você tivesse que automatizá-la, ela pediria a resposta com menos passos ou a de menor custo — e você conseguiria dizer, com números, qual é o custo de cada passo?
Nota do autor: os valores da Tabela 1 supõem 1 KiB por nó, estimativa de praxe em Russell e Norvig (2021), e usam unidades binárias; a contagem é da fronteira no nível d, não do total de nós gerados. Os valores da Tabela 2 são cálculo exato do autor sobre a contagem de nós gerados até a profundidade 5, conferidos por enumeração; a razão-limite b/(b−1) é o coeficiente demonstrado por Korf (1985), do qual as razões da tabela se aproximam por baixo em profundidade finita. No simulador e no Quadro 1, o teste de objetivo é aplicado no momento da retirada do nó da fronteira para as quatro estratégias; a formulação corrente da busca em largura permite testar já na geração, o que pouparia uma expansão, mas a escolha uniforme aqui mantém as quatro comparáveis e é a única correta para o custo uniforme, conforme discutido na Fronteira 05. A coluna "nós visitados" do Quadro 1 conta nós retirados da fronteira nas três primeiras estratégias e nós alcançados pela recursão no aprofundamento iterativo, somados nas três rodadas — não são grandezas idênticas, e a comparação entre elas serve apenas de ordem de grandeza. As quatro execuções foram conferidas por implementação independente em Python antes da redação. A rede de aeroportos e as tarifas são fictícias e servem apenas para separar o critério "menos conexões" do critério "menor tarifa"; não representam malha aérea nem preços reais. Sobre autoria: o algoritmo A de Moore (1959) é a busca em largura no sentido moderno, mas Moore não usou esse nome, e trabalhos independentes de Konrad Zuse (1945) e Chien Yi Lee (1961) chegaram ao mesmo procedimento; a busca de custo uniforme é a formulação do algoritmo de Dijkstra (1959) em árvore de busca, não uma reprodução literal do artigo dele; e a busca em profundidade não tem inventor único, remontando aos estudos de percurso de labirintos do século XIX (SCHRIJVER, 2012). 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
- CORMEN, Thomas H. et al. Introduction to algorithms. 4. ed. Cambridge: MIT Press, 2022.
- DIJKSTRA, Edsger Wybe. A note on two problems in connexion with graphs. Numerische Mathematik, Berlim, v. 1, n. 1, p. 269-271, dez. 1959. Disponível em: https://link.springer.com/article/10.1007/BF01386390. 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.
- MISA, Thomas J. (ed.). An interview with Edsger W. Dijkstra. Communications of the ACM, Nova York, v. 53, n. 8, p. 41-47, ago. 2010. Entrevista concedida a Philip L. Frana. Disponível em: https://cacm.acm.org/opinion/an-interview-with-edsger-w-dijkstra/. Acesso em: 23 ago. 2026.
- MOORE, Edward Forrest. The shortest path through a maze. In: INTERNATIONAL SYMPOSIUM ON THE THEORY OF SWITCHING, 1957, Cambridge. Proceedings: part II. Cambridge: Harvard University Press, 1959. p. 285-292. (The Annals of the Computation Laboratory of Harvard University, v. 30).
- RUSSELL, Stuart; NORVIG, Peter. Artificial intelligence: a modern approach. 4. ed. Hoboken: Pearson, 2021.
- SCHRIJVER, Alexander. On the history of the shortest path problem. Documenta Mathematica, Bielefeld, Extra Volume ISMP, p. 155-167, 2012. Disponível em: https://ems.press/content/book-chapter-files/27360. Acesso em: 23 ago. 2026.
- SLATE, David J.; ATKIN, Lawrence R. CHESS 4.5: the Northwestern University chess program. In: FREY, Peter W. (ed.). Chess skill in man and machine. Nova York: Springer-Verlag, 1977. p. 82-118.
Comentários