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 artigos, um mesmo ano de publicação
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). O labirinto não era metáfora nenhuma. Moore contou depois de onde veio o problema: Claude Shannon, seu colega na Bell Labs, tinha construído uma máquina que resolvia labirintos, e numa demonstração um visitante perguntou por que ela não era capaz de achar sempre o caminho mais curto. Shannon e Moore saíram atrás de maneiras econômicas de fazer isso, cada um do seu jeito. Só meses depois alguém sugeriu que aquilo servia para redes de comunicação e de transporte (SCHRIJVER, 2012).
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. Ela não nasceu na inteligência artificial nem na engenharia de telefonia: nasceu de uma pergunta de plateia sobre um brinquedo.
O outro artigo de 1959 tinha nascido antes, e do outro lado do Atlântico. Em 1956, um jovem programador do Centro de Matemática de Amsterdã precisava de uma demonstração vistosa para a inauguração do computador ARMAC. Ele contou a história décadas depois, em entrevista (MISA, 2010, p. 42):
"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. Tradução do autor.
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 só saiu três anos depois, 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.
Os dois textos saíram em 1959, embora as ideias tenham nascido em momentos diferentes. 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 é o mesmo nos quatro casos, e trocar o recipiente da fronteira já faz nascer outro algoritmo, com outras garantias e outro custo. O quarto é o único que pede algo a mais: alguém do lado de fora que reinicie a busca com o teto um degrau mais alto.
As buscas cegas são o mesmo algoritmo; o que muda é a disciplina da fronteira. A frase vale ao pé da letra para as três primeiras: troque o recipiente e pronto. O aprofundamento iterativo é o caso que estica a regra — ele mantém o mesmo laço por dentro, mas precisa de um envoltório que o chame de novo a cada limite e saiba distinguir "não achei porque bati no teto" de "não achei porque não existe". Quem for ler o pseudocódigo formal vai encontrar esses dois controles a mais (RUSSELL; NORVIG, 2021). Ainda assim, guardar a frase 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 — que não é só o fio da descida, mas também, em cada nó dele, os irmãos ainda não tentados. Daí a memória ser b × m, e não apenas m.
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 é menos frágil, mas não imune: a ordem dos sucessores pode mudar qual das rotas mínimas ela devolve, quando há mais de uma. O que ela garante, e a profundidade não, é que o número de passos será sempre o menor possível.
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, para buscas em árvore cujo número de nós cresce exponencialmente com a profundidade: 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.
As árvores da esquerda são esquemáticas e servem só para mostrar que cada rodada refaz a anterior e acrescenta uma camada. As barras da direita e os 11% são de outra escala: a de uma árvore de ramificação 10, em que o último nível sozinho concentra quase todo o volume.
Numa árvore de ramificação 10, 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, e ela é própria do xadrez — não do aprofundamento iterativo em geral. Num jogo, cada rodada termina com um lance escolhido, porque existe uma função que avalia posições e ordena as opções; o programa pode então ser interrompido pelo relógio e ainda assim jogar o melhor lance encontrado até ali. Quem já jogou contra um computador se beneficiou disso sem saber. Na busca por um caminho é diferente: as rodadas anteriores à profundidade da solução não devolvem solução nenhuma — devolvem "não achei até aqui". Interromper antes da hora, nesse caso, não entrega meia resposta: não entrega resposta.
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.
O painel conta nós visitados, e não nós expandidos, de propósito. A conta inclui o próprio destino, que é reconhecido no momento em que sai da fronteira e por isso nunca chega a gerar sucessores, e inclui, no aprofundamento iterativo, as visitas que morrem no teto de cada rodada sem gerar nada. São grandezas vizinhas, mas não idênticas — e misturá-las é o jeito mais fácil de comparar duas buscas de forma injusta.
Nas quatro estratégias, os vizinhos de um aeroporto são gerados em ordem alfabética do código — convenção arbitrária, adotada só para que o exemplo seja reproduzível. O que muda de uma estratégia para outra não é a ordem em que os nós entram na fronteira: é a ordem em que saem dela.
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
nós visitados 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, e essa rota custa quase o dobro da mais barata; 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.
Estar na fronteira não é ter chegado
Rode a busca em profundidade e pare no segundo passo. A pilha já mostra SSA — Salvador, o destino. E a busca continua andando por mais seis passos, cada vez para mais longe. Se o destino já foi encontrado, por que ninguém parou?
Porque ele não foi encontrado. Estar na fronteira é ter sido gerado, não ter sido testado. Um nó na fronteira é só uma promessa anotada — "de onde eu estava, dá para ir até aqui" — e a busca não olha para o conteúdo dessa promessa enquanto ela está na fila. O teste de objetivo só acontece no instante em que o nó é retirado. Até lá, Salvador é um papelzinho no meio de outros papelzinhos, indistinguível dos demais.
E quem decide a ordem da retirada é o recipiente, que não tem opinião sobre qual nó é importante. Na pilha, sai o último que entrou. Salvador entrou quando Belo Horizonte foi expandido, mas Goiânia entrou logo depois — então Goiânia sai primeiro, e leva a busca para um mergulho por cinco aeroportos — Goiânia, Vitória, Ilhéus, Palmas e Aracaju — antes que alguém volte a olhar para o papelzinho de Salvador. A busca cega não ignora o destino por teimosia: ela não tem como saber que aquele nó vale mais que os outros.
O mesmo acontece nas outras três, em graus diferentes. Na largura, Salvador espera dois passos na fila enquanto Goiânia e Palmas são atendidas por ordem de chegada. No custo uniforme, espera muito mais: entra na fronteira valendo R$ 1.500, pela rota que passa por Goiânia e Belo Horizonte, e fica lá sendo ultrapassado por todo nó mais barato, até reaparecer valendo R$ 1.050 por Palmas e Ilhéus. E essa espera não é um defeito — é ela que compra a otimalidade. Se o custo uniforme testasse o objetivo na hora de gerar, teria devolvido essa rota de R$ 1.500 e ido embora satisfeito, sem nunca descobrir a de R$ 1.050.
Guarde essa cena, porque ela é exatamente o que uma busca informada resolve. Para um algoritmo que tenha uma estimativa do quanto falta até o destino, Salvador não é um papelzinho qualquer: é o único nó do problema cuja estimativa vale zero. Ele vai para o topo da fila no instante em que é gerado. A diferença entre olhar seis aeroportos à toa e ir direto ao ponto não está no laço, nem no recipiente — está em ter, ou não ter, um palpite sobre a distância que falta.
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). Sobre a origem da busca em largura: o problema chegou a Moore pela máquina de resolver labirintos de Claude Shannon, e a aplicação a redes de comunicação e transporte só foi sugerida meses depois, conforme o relato do próprio Moore reproduzido por Schrijver (2012, p. 162-163); uma versão anterior deste texto invertia essa ordem e apresentava o roteamento telefônico como motivação original. A cronologia de Dijkstra também foi corrigida: o algoritmo é de 1956, ano da inauguração do ARMAC, e não posterior à apresentação de Moore em 1957; as três páginas saíram em 1959. As quatro ilustrações desta postagem foram geradas pelo autor com auxílio de inteligência artificial (modelo Gemini 3 Pro Image), a partir de descrições próprias, e conferidas uma a uma antes da publicação; os números que aparecem dentro delas são os mesmos apurados no texto.
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