Resolução de Problemas por Busca: Espaço de Estados e Busca Não Informada

No artigo anterior, deixamos a curiosa leitora diante de um agente baseado em objetivos: um agente que, de posse de um modelo do mundo e de um objetivo a alcançar, precisa descobrir como alcançá-lo. Vimos que descobrir esse como é escolher uma sequência de ações que leve do estado atual a um estado que satisfaça o objetivo. Esse problema tem um nome, busca, e é o assunto dos próximos quatro artigos. Começamos pelo caso mais austero: buscar sem nenhuma informação sobre onde o objetivo está, guiados apenas pela estrutura do problema.

Austero não quer dizer inútil. A busca não informada é o esqueleto sobre o qual toda busca informada será construída, e os conceitos que fixarmos aqui, espaço de estados, fronteira, completude, otimalidade, os custos de tempo e de memória, reaparecerão em cada artigo desta série, inclusive nos que tratam de redes neurais e algoritmos genéticos, nos quais buscar continua sendo o verbo, ainda que disfarçado. A esforçada leitora que dominar este artigo terá o vocabulário de tudo que vem depois.

Como combinado, o exemplo executável será C++23, compilado no MSVC. Vamos começar definindo, com precisão, o que é um problema de busca.

1. Formulação de um problema

Antes de buscar, é preciso dizer o que se busca, e dizer aqui tem significado técnico. Formular um problema de busca é especificar cinco componentes, e a atenta leitora deve reparar que nenhum deles menciona o algoritmo que resolverá o problema; a formulação é independente do método, e essa separação é o que nos permitirá aplicar quatro algoritmos diferentes à mesma formulação.

O primeiro componente é o estado inicial, o estado do mundo em que o agente começa. O segundo é o conjunto de ações disponíveis em cada estado, que descrevemos por uma função sucessora $\text{Succ}(s)$, a qual devolve, para um estado $s$, o conjunto de pares $(a, s’)$ formados por uma ação $a$ aplicável em $s$ e o estado $s’$ resultante. O terceiro é o teste de objetivo, uma função que decide se um dado estado satisfaz o objetivo; ele pode ser explícito, quando comparamos com um estado-alvo fixo, ou implícito, quando verificamos uma propriedade, como o cômodo está limpo. O quarto é o custo de passo $c(s, a, s’)$, o custo numérico de ir de $s$ a $s’$ pela ação $a$, que suporemos sempre não negativo. O quinto, derivado dos anteriores, é o custo de caminho, a soma dos custos de passo ao longo de uma sequência de ações; uma solução é um caminho do estado inicial a um estado objetivo, e uma solução ótima é a de menor custo de caminho.

Vamos tornar isso concreto com dois problemas que reaparecerão nos exercícios. No problema das jarras de água, dispomos de duas jarras, uma de quatro litros e outra de três, sem marcações intermediárias, e uma torneira. Queremos medir exatamente dois litros. O estado é um par $(x, y)$, com $x$ litros na jarra de quatro e $y$ na de três; o estado inicial é $(0, 0)$; as ações são encher uma jarra na torneira, esvaziá-la no ralo, ou despejar uma na outra até que a primeira esvazie ou a segunda encha; o teste de objetivo verifica se $x = 2$ ou $y = 2$; e o custo de passo é $1$ por ação, de modo que o custo de caminho conta o número de ações. É um problema pequeno, com no máximo $5 \times 4 = 20$ estados, e por isso ideal para calcular à mão.

O segundo é o 8-puzzle, um tabuleiro $3 \times 3$ com oito peças numeradas e um espaço vazio, no qual uma jogada desliza para o vazio uma peça adjacente. O estado é uma configuração das nove posições; o estado inicial é um embaralhamento dado; o teste de objetivo compara com a configuração ordenada; e o custo de passo é $1$ por jogada. O 8-puzzle é maior e mais interessante, e nos servirá para falar de tamanho de espaço de estados e de fator de ramificação. Fixadas as duas formulações, vamos resolver os exercícios antes de escolher um algoritmo.

Exercícios resolvidos

1. Formule o problema das jarras de água como espaço de estados e exiba uma solução. Dê o estado, as ações, o teste de objetivo e a sequência de ações de uma solução de custo mínimo.

Solução: O estado é $(x, y)$ com $0 \le x \le 4$ e $0 \le y \le 3$; o estado inicial é $(0, 0)$; o teste de objetivo é $x = 2 \lor y = 2$. As seis ações são encher $A$, dando $(4, y)$; encher $B$, dando $(x, 3)$; esvaziar $A$, dando $(0, y)$; esvaziar $B$, dando $(x, 0)$; despejar $A$ em $B$, que transfere $\min(x, 3 - y)$ litros; e despejar $B$ em $A$, que transfere $\min(y, 4 - x)$ litros. Uma busca em largura a partir de $(0,0)$ encontra a solução de custo mínimo, com quatro ações: encher $B$, levando a $(0, 3)$; despejar $B$ em $A$, levando a $(3, 0)$; encher $B$ de novo, levando a $(3, 3)$; e despejar $B$ em $A$, que transfere apenas $\min(3, 4-3) = 1$ litro, levando a $(4, 2)$. O estado final $(4, 2)$ satisfaz $y = 2$: medimos dois litros na jarra menor em quatro passos.

A tabela explicita que cada transição é válida e que o objetivo aparece pela primeira vez ao custo $4$.

2. No 8-puzzle, calcule o número de estados alcançáveis a partir de uma configuração e o fator de ramificação médio.

Solução: Há $9!$ maneiras de dispor as nove posições, oito peças mais o vazio, mas apenas metade delas é alcançável de qualquer configuração dada. Em uma grade de largura ímpar, como a do 8-puzzle, a paridade do número de inversões entre as oito peças numeradas é invariante: removemos o vazio da sequência lida linha a linha e contamos os pares de peças que aparecem em ordem contrária à numérica. Uma jogada horizontal não altera essa contagem; uma jogada vertical desloca uma peça por duas outras posições numeradas e altera o total por um número par. Assim, uma configuração de paridade par nunca alcança outra de paridade ímpar. Como exatamente metade das permutações tem cada paridade, o número de estados alcançáveis é

O fator de ramificação depende de onde está o vazio. Nas quatro quinas, o vazio tem dois vizinhos, gerando duas jogadas; nas quatro bordas centrais, três; no centro, quatro. Como as nove posições são igualmente prováveis em um embaralhamento uniforme, o fator de ramificação médio é

Esse número modesto, e o espaço de $181\,440$ estados, explicam por que o 8-puzzle é resolvível por busca cega, ao contrário de seu irmão maior, o 15-puzzle, cujo espaço tem mais de $10^{13}$ estados.

3. Formule o problema dos missionários e canibais e determine o número mínimo de travessias. Três missionários e três canibais estão em uma margem de um rio com um barco que leva no máximo duas pessoas; em nenhuma margem os canibais podem superar em número os missionários presentes.

Solução: O estado é uma tripla $(m, c, b)$, na qual $m$ e $c$ são os missionários e canibais na margem original e $b \in {0, 1}$ indica se o barco está lá. O estado inicial é $(3, 3, 1)$ e o objetivo é $(0, 0, 0)$. As ações levam uma ou duas pessoas na direção em que o barco está: os cinco carregamentos possíveis são um missionário, dois missionários, um canibal, dois canibais, ou um de cada. Uma ação só é válida se o estado resultante mantiver, em ambas as margens, os canibais em número não superior ao dos missionários, a menos que não haja missionário algum naquela margem, caso em que qualquer número de canibais é seguro. Uma busca em largura sobre esse espaço encontra a solução de custo mínimo com onze travessias. A restrição é o que torna o problema não trivial: sem ela, bastariam poucas viagens; com ela, mais da metade dos carregamentos aparentemente úteis leva a estados proibidos.

4. Formule a navegação em um labirinto $n \times n$ com paredes e conte os estados.

Solução: O estado é a célula ocupada pelo agente, um par $(i, j)$ com $0 \le i, j < n$. O estado inicial é a célula de entrada; o teste de objetivo compara com a célula de saída; as ações movem o agente para uma das quatro células adjacentes que não seja parede nem esteja fora da grade; e o custo de passo é $1$. Se $w$ das $n^2$ células são paredes, o número de estados é $n^2 - w$, e cada estado tem no máximo quatro sucessores. Para um labirinto $10 \times 10$ com $20$ paredes, são $80$ estados, pequeno o bastante para qualquer algoritmo deste artigo, e é justamente esse o mundo que o laboratório interativo mais adiante usa.

5. Estime o tamanho do espaço de estados do cubo mágico $2 \times 2$ e explique por que a busca cega já começa a sofrer.

Solução: O cubo $2 \times 2$ tem oito cubinhos de quina, que podem ser permutados de $8!$ maneiras, e cada um pode assumir três orientações, o que daria $3^8$; mas a orientação do último cubinho é determinada pelos outros sete, reduzindo o fator para $3^7$, e como o cubo não tem centros fixos, dividimos por $24$ orientações do cubo inteiro no espaço. O total é

São mais de três milhões e meio de estados. Ainda cabe na memória de um computador moderno, mas já obriga a busca cega a visitar milhões de nós, e antecipa por que problemas realistas exigirão as heurísticas do próximo artigo. Aumente o cubo para $3 \times 3$ e o espaço salta para mais de $4{,}3 \times 10^{19}$ estados, e a busca cega deixa de ser uma opção.

2. O espaço de estados como grafo

A formulação da seção anterior define, sem que tenhamos dito com essas palavras, um grafo. Os nós do grafo são os estados; as arestas são as ações, cada uma ligando um estado ao seu sucessor e rotulada pelo custo de passo. Buscar uma solução é encontrar um caminho, nesse grafo, do nó inicial a algum nó objetivo. Toda a teoria da busca é, no fundo, teoria de caminhos em grafos, e nomear esse grafo com precisão evita confusões que custam caro adiante.

A primeira confusão a desarmar é a diferença entre o grafo do espaço de estados e a árvore de busca. O grafo do espaço de estados é o mapa do mundo: existe um nó por estado, e se dois caminhos diferentes levam ao mesmo estado, eles chegam ao mesmo nó. A árvore de busca é o registro do que o algoritmo explorou: cada nó da árvore representa um caminho a partir do estado inicial, e o mesmo estado pode aparecer em vários nós da árvore, um para cada caminho distinto que a ele conduz. O grafo tem tantos nós quantos estados; a árvore pode ter infinitos nós, mesmo quando o grafo é finito, se houver ciclos. A leitora que confundir os dois vai superestimar ou subestimar custos de forma grosseira.

A Figura 1 torna visível a duplicação que essa distinção produz. O estado $C$ existe uma vez no mundo, mas aparece uma vez para cada caminho que o alcança no registro da busca.

Figura 1: O grafo reúne caminhos pela identidade do estado; a árvore os mantém separados até que o controle de explorados reconheça a duplicata.

A distinção vira uma obrigação de implementação: estados semanticamente iguais precisam ter uma representação canônica igual. No 8-puzzle, uma matriz plana com nove valores produz uma chave estável; no mundo das jarras, o par $(x,y)$ já é a chave; em um labirinto, a célula pode ser codificada por $i\cdot n+j$. Se duas representações diferentes descrevem o mesmo estado, o conjunto de explorados não percebe a duplicata e a busca volta a construir uma árvore redundante. O custo do teste também importa. Uma tabela de dispersão oferece consulta esperada $O(1)$ e paga memória adicional; um vetor indexado pelo identificador inteiro do estado oferece consulta $O(1)$ com menos sobrecarga quando o espaço é denso e conhecido. Escolher a chave e a estrutura de visitados é parte do algoritmo, não arrumação posterior.

Precisamos de três grandezas para falar de custo. O fator de ramificação $b$ é o número máximo de sucessores de um nó, quantos filhos cada nó da árvore de busca pode ter. A profundidade $d$ é o comprimento, em número de ações, do caminho-solução mais raso, aquele que a busca em largura encontrará primeiro. A profundidade máxima $m$ é o comprimento do caminho mais longo no espaço de estados, possivelmente infinito. Uma árvore de busca com fator de ramificação $b$ tem, no nível $k$, até $b^{k}$ nós; essa explosão exponencial é a inimiga que todos os algoritmos deste artigo enfrentam, cada um com uma tática diferente.

A segunda arma contra a explosão, além da estrutura do problema, é lembrar de onde já estivemos. Um algoritmo de busca em grafo mantém um conjunto de explorados, também chamado de conjunto fechado, com os estados já expandidos, e evita repetir trabalho. Na BFS e na DFS, um sucessor já alcançado pode ser descartado. Nos algoritmos ordenados por custo, porém, reencontrar um estado por um caminho mais barato exige atualizar seu melhor custo e recolocá-lo na fronteira; descartar toda repetição quebraria a correção. Um algoritmo de busca em árvore não guarda esse controle e pode reexpandir o mesmo estado inúmeras vezes, seguindo caminhos que apenas dão voltas. A diferença entre os dois pode ser a diferença entre terminar e se perder em um ciclo; salvo quando o espaço é comprovadamente acíclico, usaremos busca em grafo. Falta ainda um nome central, a fronteira: o conjunto de nós já gerados mas ainda não expandidos, dos quais o próximo a ser expandido será escolhido. É a política de escolha na fronteira que distingue um algoritmo de busca de outro, e é a ela que dedicamos o resto do artigo.

3. Análise de um algoritmo de busca

Antes de conhecer os algoritmos, precisamos das quatro perguntas com que os julgaremos, porque comparar sem critério é apenas ter preferências. As quatro são padrão, e cada uma tem definição precisa.

A primeira pergunta é a completude: o algoritmo tem garantia de encontrar uma solução quando ela existe, e de reportar a ausência quando não existe? Um algoritmo incompleto pode rodar para sempre, ou parar de mãos vazias mesmo havendo solução, e isso o desqualifica para muitos usos. A segunda é a otimalidade: quando o algoritmo encontra uma solução, é garantido que ela seja de custo mínimo? Um algoritmo completo mas não ótimo acha alguma saída, não necessariamente a melhor. A terceira é a complexidade de tempo: quantos nós o algoritmo gera, no pior caso, em função de $b$, $d$ e $m$? A quarta é a complexidade de espaço: quantos nós o algoritmo precisa manter em memória simultaneamente? Em busca, a memória costuma ser o recurso que se esgota primeiro, e a atenta leitora fará bem em olhar para a coluna de espaço antes da de tempo.

Essas grandezas não são acadêmicas; elas decidem se um algoritmo roda ou trava. Um algoritmo cujo consumo de memória cresce como $b^{d}$ pode precisar de gigabytes onde outro, que cresce como $b \cdot d$, precisa de kilobytes, para exatamente o mesmo problema. Os exercícios a seguir tornam essa diferença tangível, com números, e são a razão pela qual, mais adiante, preferiremos um algoritmo aparentemente mais lento a um aparentemente mais rápido.

Exercícios resolvidos

6. Para um problema com fator de ramificação $b = 10$ e solução na profundidade $d = 8$, estime o número de nós que a busca em largura gera e a memória necessária, supondo $100$ bytes por nó.

Solução: A busca em largura expande todos os nós até a profundidade da solução. O número de nós no nível $d$ é $b^{d} = 10^{8} = 100$ milhões, e o total gerado até esse nível é a soma da progressão geométrica

Como a busca em largura precisa manter em memória toda a fronteira, que no pior caso é da ordem de $b^{d}$ nós, o consumo de memória é de aproximadamente $1{,}11 \times 10^{8} \times 100$ bytes, ou cerca de $11$ gigabytes. Guarde esse número: ele é a razão pela qual a busca em largura, apesar de ótima, é impraticável em problemas fundos.

7. Compare os custos de tempo e de espaço, no pior caso, da busca em largura e da busca em profundidade para $b = 8$ e profundidade máxima $m = 12$.

Solução: No pior caso, ambas geram um número de nós exponencial na profundidade que exploram: a busca em profundidade pode gerar até $b^{m} = 8^{12} \approx 6{,}87 \times 10^{10}$ nós antes de encontrar uma solução profunda, e a busca em largura, quando a solução está no fundo, é da mesma ordem. Em tempo, portanto, empatam no pior caso. Em espaço, separam-se drasticamente: a busca em largura mantém a fronteira inteira, da ordem de $b^{m}$ nós, enquanto a busca em profundidade guarda apenas o caminho atual e os irmãos não expandidos ao longo dele, da ordem de $b \cdot m = 8 \cdot 12 = 96$ nós. Noventa e seis nós contra dezenas de bilhões: é essa a vantagem da profundidade, e é só de espaço.

A síntese confirma que a vantagem da profundidade está na memória, não no limite assintótico de tempo.

8. Mostre, com um exemplo, que a busca em profundidade pode ser incompleta enquanto a busca em largura é completa.

Solução: Considere um espaço de estados com um ramo infinito. A partir do estado inicial, um sucessor leva a uma cadeia infinita de estados $s_1, s_2, s_3, \dots$ que nunca contém o objetivo, enquanto outro sucessor leva, em um único passo, ao objetivo. A busca em profundidade, ao escolher primeiro o ramo infinito, desce por ele para sempre e nunca volta para tentar o outro sucessor; ela é incompleta. A busca em largura, que expande por níveis, encontra o objetivo no nível $1$ antes de se aprofundar no ramo infinito; ela é completa. A moral é que a completude da busca em profundidade depende de o espaço ser finito ou de impormos um limite de profundidade, e é dessa segunda ideia que nascerá o aprofundamento iterativo.

9. Para $b = 10$ e $d = 12$, contraste a memória exigida pela busca em largura e pela busca em profundidade.

Solução: A busca em largura mantém a fronteira da ordem de $b^{d} = 10^{12}$ nós, um trilhão de nós, dezenas de terabytes, inviável em qualquer máquina. A busca em profundidade mantém da ordem de $b \cdot d = 10 \cdot 12 = 120$ nós, cabe folgadamente em qualquer memória. O mesmo problema, portanto, é trivial em memória para um algoritmo e impossível para o outro, e a única diferença entre eles é a política de escolha na fronteira. É por isso que insistimos que a coluna de espaço merece a primeira olhada.

10. Monte a tabela de completude, otimalidade, tempo e espaço para busca em largura (BFS), custo uniforme (UCS), profundidade (DFS) e aprofundamento iterativo (IDS), supondo fator de ramificação finito e custos de passo positivos.

Solução: A tabela abaixo resume o que os algoritmos das próximas seções entregam. Denotamos por $C^{*}$ o custo da solução ótima e por $\varepsilon$ o menor custo de passo.

A leitora deve ler a tabela como um mapa de compromissos: a busca em largura e a de custo uniforme compram otimalidade ao preço de memória exponencial; a busca em profundidade compra memória barata ao preço de perder completude e otimalidade; e o aprofundamento iterativo, na última linha, é a tentativa de ficar com o melhor das duas colunas, otimalidade e memória linear, pagando um preço em tempo que os exercícios da Seção 7 mostrarão ser pequeno. As seções seguintes justificam cada célula.

4. Busca em largura (BFS)

A busca em largura (breadth-first search, BFS) adota a política mais igualitária possível na fronteira: expande sempre o nó mais raso ainda não expandido. Ela explora o espaço em ondas concêntricas, terminando o nível $0$ antes de tocar o nível $1$, e este antes do nível $2$. A estrutura de dados que implementa essa política é uma fila FIFO (first-in, first-out, primeiro a entrar é o primeiro a sair): sucessores recém-gerados entram no fim da fila, e o próximo a expandir sai da frente, o que garante que nós rasos sejam expandidos antes dos profundos.

O procedimento, em busca em grafo, é o seguinte. Colocamos o nó inicial na fronteira e o marcamos como alcançado. Antes de qualquer expansão, testamos se ele já é objetivo; esquecer esse caso faz o algoritmo falhar no problema mais curto possível, cuja solução tem zero ações. Enquanto a fronteira não estiver vazia, retiramos o nó da frente e, para cada par $(a, s’)$ em $\text{Succ}(s)$, descartamos $s’$ se já tiver sido alcançado. Caso contrário, registramos seu pai, marcamos o estado e testamos o objetivo; se satisfeito, reconstruímos o caminho; senão, inserimos $s’$ no fim da fronteira. Na BFS com custos unitários, testar na geração é seguro porque a primeira geração de um estado ocorre pelo caminho mais raso. Na UCS, como veremos, a mesma antecipação seria um erro.

A busca em largura é completa, pois se a solução está na profundidade $d$, ela é gerada após esgotarmos os finitos nós dos níveis anteriores. Ela é ótima quando todos os custos de passo são iguais, porque nesse caso o caminho mais raso é também o mais barato; se os custos variam, o caminho mais raso pode custar mais que um caminho mais fundo, e a otimalidade se perde. Esse defeito é exatamente o que a busca de custo uniforme corrige.

5. Busca de custo uniforme (UCS)

A busca de custo uniforme (uniform-cost search, UCS) troca a política expanda o mais raso por expanda o mais barato. Em vez de contar arestas, ela conta custo acumulado: para cada nó $n$, seja $g(n)$ o custo do caminho do estado inicial até $n$; a UCS expande sempre o nó de menor $g(n)$ na fronteira. A estrutura que implementa essa política é uma fila de prioridade ordenada por $g$, e a diferença para a busca em largura é apenas essa; quando todos os custos de passo são iguais, $g(n)$ é proporcional à profundidade e a UCS reproduz a busca em largura.

Há duas sutilezas que separam a UCS correta da ingênua. A primeira é que o teste de objetivo deve ser feito na expansão, não na geração: um nó objetivo gerado por um caminho caro pode estar na fronteira ao mesmo tempo que um caminho mais barato para o mesmo objetivo ainda não descoberto, e parar cedo demais devolveria o caminho errado. A segunda é que, ao gerar um sucessor já presente na fronteira por um caminho mais caro, devemos substituí-lo pelo mais barato. Com esses dois cuidados, a UCS é completa e ótima sempre que os custos de passo forem positivos, e a leitora que já conhece o algoritmo de Dijkstra para caminhos mínimos vai reconhecê-lo: a busca de custo uniforme é o algoritmo de Dijkstra apresentado como busca, com a diferença de que a UCS gera o grafo sob demanda, enquanto Dijkstra costuma recebê-lo pronto.

Exercícios resolvidos

Os exercícios usam o grafo ponderado com nós $S, A, B, C, G$ e as arestas dirigidas $S \to A$ de custo $1$, $S \to B$ de custo $4$, $A \to B$ de custo $2$, $A \to C$ de custo $5$, $B \to C$ de custo $1$, $B \to G$ de custo $7$ e $C \to G$ de custo $3$. O estado inicial é $S$ e o objetivo é $G$.

11. Execute a busca de custo uniforme nesse grafo e dê o caminho e o custo da solução.

Solução: Expandimos sempre o nó de menor $g$. Começamos com $g(S) = 0$. Expandindo $S$, geramos $A$ com $g = 1$ e $B$ com $g = 4$. O menor é $A$ ($g = 1$); expandindo $A$, geramos $B$ por $A$ com $g = 1 + 2 = 3$, que melhora o $B$ anterior de $g = 4$, e $C$ com $g = 1 + 5 = 6$. A fronteira tem $B$ ($g = 3$) e $C$ ($g = 6$). Expandimos $B$ ($g = 3$); geramos $C$ por $B$ com $g = 3 + 1 = 4$, que melhora o $C$ de $g = 6$, e $G$ com $g = 3 + 7 = 10$. Expandimos $C$ ($g = 4$); geramos $G$ por $C$ com $g = 4 + 3 = 7$, que melhora o $G$ de $g = 10$. Expandimos $G$ ($g = 7$): é o objetivo. O caminho ótimo é $S \to A \to B \to C \to G$, de custo

Portanto, a UCS finaliza $G$ com o menor custo possível, $7$, e o encadeamento dos predecessores reconstrói $S\to A\to B\to C\to G$.

12. Mostre que a busca em largura devolve, nesse mesmo grafo, um caminho de custo maior que o da busca de custo uniforme.

Solução: A busca em largura conta arestas, não custos. A partir de $S$, ela alcança $G$ pelo caminho com o menor número de arestas, que é $S \to B \to G$, de apenas duas arestas. O custo desse caminho é $4 + 7 = 11$, contra os $7$ do caminho ótimo $S \to A \to B \to C \to G$, que tem quatro arestas. A busca em largura, portanto, devolve um caminho mais curto em número de ações porém mais caro em custo, e é essa exata discrepância, mais raso não é mais barato quando os custos variam, que a busca de custo uniforme foi desenhada para eliminar.

A BFS vence apenas na quantidade de arestas; a UCS vence no critério definido pelo problema, o custo acumulado.

13. Argumente que a busca de custo uniforme e o algoritmo de Dijkstra computam a mesma coisa.

Solução: Ambos mantêm, para cada nó, o menor custo conhecido do início até ele, e ambos expandem repetidamente o nó de menor custo ainda não finalizado, relaxando seus vizinhos, isto é, atualizando o custo de um vizinho quando o caminho pelo nó atual é mais barato. A ordem de finalização dos nós é idêntica nas duas, e a propriedade que garante a corretude é a mesma: com custos não negativos, quando um nó é expandido pela primeira vez, seu $g$ já é o mínimo definitivo, pois qualquer caminho alternativo passaria por um nó de custo maior ou igual na fronteira. A única diferença é de contexto: Dijkstra pressupõe o grafo dado explicitamente, enquanto a busca de custo uniforme o descobre chamando a função sucessora, o que a torna aplicável a espaços grandes demais para caber na memória de uma vez.

14. Explique por que, quando todas as ações têm o mesmo custo, a busca de custo uniforme se reduz à busca em largura.

Solução: Se todo custo de passo vale a mesma constante $\varepsilon > 0$, então o custo acumulado de um nó na profundidade $k$ é $g = k\varepsilon$, proporcional à profundidade. Ordenar a fronteira por $g$ é, então, ordená-la por profundidade, que é precisamente a política da busca em largura. As duas expandem por níveis. A diferença remanescente é o instante do teste de objetivo: a BFS pode parar na geração, enquanto a UCS testa na expansão e, dependendo do desempate, pode retirar antes outros nós da mesma profundidade. Isso não altera o custo da solução encontrada. Com custos uniformes, portanto, a busca de custo uniforme não oferece vantagem e pode pagar trabalho administrativo adicional; ela existe para custos variados.

15. Uma aresta de custo zero e um ciclo poderiam fazer a busca de custo uniforme não terminar? Explique o papel do conjunto de explorados.

Solução: Sem cuidado, uma aresta de custo zero dentro de um ciclo permitiria dar voltas sem aumentar $g$, e uma busca em árvore ingênua poderia reexpandir os mesmos estados indefinidamente. A busca de custo uniforme em grafo evita isso porque, ao expandir um nó pela primeira vez, o insere no conjunto de explorados e nunca mais o expande; qualquer reaparição do estado pela aresta de custo zero é descartada. A terminação fica garantida sempre que o número de estados é finito, porque cada estado é expandido no máximo uma vez. Custos de passo estritamente positivos dispensariam até o conjunto de explorados para a otimalidade, mas o custo zero mostra por que, na prática, mantê-lo é a escolha segura.

6. Busca em profundidade (DFS)

A busca em profundidade (depth-first search, DFS) inverte a política da busca em largura: expande sempre o nó mais profundo da fronteira, mergulhando por um ramo até o fundo antes de recuar. A estrutura que a implementa é uma pilha LIFO (last-in, first-out, último a entrar é o primeiro a sair), e na prática a recursão da linguagem de programação já fornece essa pilha de graça.

O interesse da busca em profundidade é inteiramente de memória. Ela precisa manter apenas o caminho da raiz até o nó atual, mais os irmãos ainda não expandidos ao longo desse caminho, o que dá um consumo da ordem de $b \cdot m$ nós, linear na profundidade máxima, contra o consumo exponencial da busca em largura. Foi esse o ponto dos exercícios da Seção 3: para $b = 10$ e $d = 12$, são cento e vinte nós contra um trilhão.

O preço dessa economia é alto. A busca em profundidade não é ótima, porque pode encontrar uma solução profunda e cara antes de uma rasa e barata que estava em outro ramo. E ela não é completa em espaços infinitos ou com ciclos não controlados, porque pode descer por um ramo sem fim e nunca voltar, como vimos no terceiro exercício da Seção 3. Impor um limite de profundidade $\ell$, abandonando qualquer ramo que o ultrapasse, restaura a terminação e dá a busca com profundidade limitada; mas ela introduz um novo dilema, o de escolher $\ell$: pequeno demais, e a busca perde soluções mais fundas que o limite; grande demais, e ela desperdiça o esforço que queríamos evitar. Resolver esse dilema sem adivinhar $\ell$ é a ideia elegante da próxima seção.

7. Aprofundamento iterativo (IDS)

O aprofundamento iterativo (iterative deepening search, IDS) resolve o dilema do limite de profundidade da forma mais direta possível: em vez de escolher $\ell$, tenta todos. Ele executa uma busca com profundidade limitada com $\ell = 0$; se não achar solução, refaz com $\ell = 1$; depois $\ell = 2$, e assim por diante, até encontrar. Cada iteração descarta o que a anterior construiu e recomeça do zero, guardando apenas a memória linear da busca em profundidade.

À primeira vista, refazer tudo a cada iteração parece um desperdício grosseiro. A atenta leitora tem o direito de exigir, neste ponto, a garantia de que o desperdício é pequeno, e a garantia existe. A razão é que uma árvore de busca é dominada pelo seu nível mais profundo: o nível $d$ tem $b^{d}$ nós, mais do que todos os níveis anteriores somados. No aprofundamento iterativo, o nível mais fundo é gerado uma vez, o penúltimo duas vezes, o antepenúltimo três, e o nível da raiz $d + 1$ vezes. Os nós refeitos são os rasos, que são poucos; os nós caros, os fundos, são gerados quase o número mínimo de vezes. O terceiro exercício desta seção quantifica isso e mostra que, para fatores de ramificação típicos, o custo extra é da ordem de dez por cento.

O resultado é que o aprofundamento iterativo é completo e ótimo para custos de passo iguais, como a busca em largura, mas com consumo de memória da ordem de $b \cdot d$, como a busca em profundidade. Ele é, para busca não informada em espaços grandes com custos uniformes, o algoritmo de escolha, e a última linha da tabela da Seção 3 é a promessa que esta seção cumpre.

Antes dos exercícios, convém ver os quatro algoritmos lado a lado. O laboratório abaixo é um labirinto em grade, como o do quarto exercício da Seção 1. Marque paredes clicando nas células, escolha o algoritmo e avance a busca, observando três coisas ao mesmo tempo: a fronteira, os nós já gerados à espera de expansão; os explorados, os já expandidos; e a ordem de expansão, que revela a personalidade de cada método. Compare quantos nós cada algoritmo expande e que caminho devolve. Ative o modo de custo, que torna algumas células lentas, para ver a busca de custo uniforme divergir da busca em largura, exatamente como no segundo exercício da Seção 5.

Exercícios resolvidos

16. Para $b = 10$ e $d = 5$, calcule o número de nós gerados pelo aprofundamento iterativo e pela busca em largura, e o excesso relativo do primeiro sobre o segundo.

Solução: Na busca em largura, o total de nós gerados até a profundidade $d$ é $\sum_{k=0}^{d} b^{k}$, que para $b = 10$ e $d = 5$ vale $111\,111$. No aprofundamento iterativo, o nó do nível $k$ é gerado uma vez em cada iteração que alcança pelo menos a profundidade $k$, ou seja, $d - k + 1$ vezes, de modo que o total é

contra $N_{\text{BFS}} = 111\,111$. O excesso relativo é

ou seja, cerca de onze por cento a mais de nós gerados. Pagar onze por cento em tempo para trocar memória exponencial por memória linear é, na esmagadora maioria dos casos, um excelente negócio.

17. Deduza o excesso relativo assintótico do aprofundamento iterativo sobre a busca em largura quando $d \to \infty$.

Solução: A razão entre os dois totais tende, para $d$ grande, a um valor que depende só de $b$. Cada nível $k$ contribui com $(d-k+1)b^k$ no aprofundamento iterativo e com $b^k$ na busca em largura; a soma é dominada pelos níveis próximos ao fundo. Somando a série, obtém-se que a razão $N_{\text{IDS}} / N_{\text{BFS}}$ converge para

Para $b = 10$, isso dá $10/9 \approx 1{,}111$, o excesso de onze por cento do exercício anterior; para $b = 2$, dá $2$, um excesso que no limite chega a cem por cento. O aprofundamento iterativo é barato quando o fator de ramificação é alto, que é o caso interessante, o dos espaços que explodem, e caro quando o fator é baixo, situação em que a busca em largura já cabe na memória e o problema não se coloca.

18. Calcule a memória exigida pelo aprofundamento iterativo para $b = 10$ e $d = 5$ e compare com a da busca em largura.

Solução: O aprofundamento iterativo, sendo em cada iteração uma busca em profundidade limitada, guarda apenas o caminho atual e os irmãos ao longo dele, da ordem de $b \cdot d = 10 \cdot 5 = 50$ nós. A busca em largura guarda a fronteira do nível mais profundo, da ordem de $b^{d} = 10^{5} = 100\,000$ nós. São cinquenta nós contra cem mil, uma diferença de três ordens de grandeza a favor do aprofundamento iterativo, obtida ao custo dos onze por cento de tempo do primeiro exercício. É essa troca, memória linear por um pequeno excesso de tempo, que define o algoritmo.

O IDS reduz a estimativa por um fator de $100\,000/50=2\,000$, ao preço das regenerações já quantificadas.

19. Argumente que o aprofundamento iterativo é ótimo quando todas as ações têm o mesmo custo.

Solução: Como o aprofundamento iterativo aumenta o limite de profundidade de um em um, a primeira iteração que encontra uma solução é aquela cujo limite iguala a profundidade $d$ da solução mais rasa; nenhuma iteração anterior, de limite menor, poderia tê-la alcançado. Dentro dessa iteração, a solução encontrada está na profundidade $d$, e não existe solução em profundidade menor, senão uma iteração anterior a teria achado. Com custos de passo iguais, a solução mais rasa é a de menor custo, e portanto a que o aprofundamento iterativo devolve é ótima. O argumento é o mesmo que garante a otimalidade da busca em largura, e falha pela mesma razão quando os custos variam.

20. Calcule o excesso relativo do aprofundamento iterativo para $b = 2$ e $d = 5$ e compare com o caso $b = 10$.

Solução: Para $b = 2$ e $d = 5$, a busca em largura gera $\sum_{k=0}^{5} 2^{k} = 63$ nós, e o aprofundamento iterativo gera $\sum_{k=0}^{5} (5 - k + 1) 2^{k} = 120$ nós. O excesso relativo é

cerca de noventa por cento, próximo do limite assintótico de cem por cento previsto por $b/(b-1) = 2$. Comparado aos onze por cento do caso $b = 10$, isso confirma a lição do segundo exercício: o aprofundamento iterativo cobra caro quando o fator de ramificação é pequeno e quase nada quando é grande. Felizmente, os problemas que realmente precisam de economia de memória são os de fator de ramificação alto, e é neles que o algoritmo brilha.

A tabela torna explícita a consequência: o custo relativo das regenerações diminui rapidamente quando o fator de ramificação cresce.

8. Implementação em C++23

Fechamos com código que separa a formulação do algoritmo, como insistimos na Seção 1. O programa representa o grafo ponderado dos exercícios da Seção 5 como uma lista de adjacência e resolve o mesmo problema por dois algoritmos: busca em largura, que minimiza arestas, e busca de custo uniforme, que minimiza o custo acumulado. É C++23 completo. No MSVC 19.44, a linha de compilação usada é cl /std:c++latest /permissive- /W4 /EHsc /utf-8 /O2 busca.cpp.

#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <expected>
#include <iostream>
#include <limits>
#include <queue>
#include <ranges>
#include <span>
#include <string_view>
#include <utility>
#include <vector>

using No = std::size_t;
using Custo = std::uint64_t;

struct Aresta {
    No destino;
    Custo custo;
};

using Grafo = std::vector<std::vector<Aresta>>;

enum class ErroBusca { vertice_invalido, sem_caminho, custo_excedeu_limite };

struct Resultado {
    std::vector<No> caminho;
    Custo custo;
    std::size_t expandidos;
};

using Resposta = std::expected<Resultado, ErroBusca>;

[[nodiscard]] std::span<const Aresta> vizinhos(
    const Grafo& grafo, const No no) noexcept {
    return std::span<const Aresta>{grafo[no]};
}

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

[[nodiscard]] Resposta bfs(
    const Grafo& grafo, const No inicio, const No objetivo) {
    if (inicio >= grafo.size() || objetivo >= grafo.size()) {
        return std::unexpected{ErroBusca::vertice_invalido};
    }

    constexpr No ausente = std::numeric_limits<No>::max();
    std::vector<No> pai(grafo.size(), ausente);
    std::vector<Custo> custo(grafo.size(), 0);
    std::queue<No> fronteira;

    pai[inicio] = inicio;
    fronteira.push(inicio);
    std::size_t expandidos = 0;

    if (inicio == objetivo) {
        return Resultado{std::vector<No>{inicio}, 0, 0};
    }

    while (!fronteira.empty()) {
        const No atual = fronteira.front();
        fronteira.pop();
        ++expandidos;

        for (const Aresta aresta : vizinhos(grafo, atual)) {
            if (pai[aresta.destino] != ausente) {
                continue;
            }
            if (aresta.custo > std::numeric_limits<Custo>::max() - custo[atual]) {
                return std::unexpected{ErroBusca::custo_excedeu_limite};
            }
            pai[aresta.destino] = atual;
            custo[aresta.destino] = custo[atual] + aresta.custo;
            if (aresta.destino == objetivo) {
                return Resultado{
                    reconstruir(pai, inicio, objetivo),
                    custo[aresta.destino],
                    expandidos};
            }
            fronteira.push(aresta.destino);
        }
    }
    return std::unexpected{ErroBusca::sem_caminho};
}

[[nodiscard]] Resposta ucs(
    const Grafo& grafo, const No inicio, const No objetivo) {
    if (inicio >= grafo.size() || objetivo >= grafo.size()) {
        return std::unexpected{ErroBusca::vertice_invalido};
    }

    constexpr No ausente = std::numeric_limits<No>::max();
    constexpr Custo infinito = std::numeric_limits<Custo>::max();
    using Item = std::pair<Custo, No>;

    std::priority_queue<Item, std::vector<Item>, std::greater<>> fronteira;
    std::vector<Custo> melhor(grafo.size(), infinito);
    std::vector<No> pai(grafo.size(), ausente);

    melhor[inicio] = 0;
    pai[inicio] = inicio;
    fronteira.emplace(0, inicio);
    std::size_t expandidos = 0;

    while (!fronteira.empty()) {
        const auto [custo_atual, atual] = fronteira.top();
        fronteira.pop();

        // Uma melhora reinsere o nó; só a entrada que coincide com "melhor" vale.
        if (custo_atual != melhor[atual]) {
            continue;
        }
        ++expandidos;

        if (atual == objetivo) {
            return Resultado{
                reconstruir(pai, inicio, objetivo), custo_atual, expandidos};
        }

        for (const Aresta aresta : vizinhos(grafo, atual)) {
            if (aresta.custo > infinito - custo_atual) {
                return std::unexpected{ErroBusca::custo_excedeu_limite};
            }
            const Custo candidato = custo_atual + aresta.custo;
            if (candidato < melhor[aresta.destino]) {
                melhor[aresta.destino] = candidato;
                pai[aresta.destino] = atual;
                fronteira.emplace(candidato, aresta.destino);
            }
        }
    }
    return std::unexpected{ErroBusca::sem_caminho};
}

void imprimir(
    const std::string_view algoritmo,
    const Resposta& resposta,
    const std::span<const std::string_view> nomes) {
    if (!resposta) {
        std::cout << algoritmo << ": sem caminho\n";
        return;
    }
    std::cout << algoritmo << ": ";
    for (const No no : resposta->caminho) {
        std::cout << nomes[no] << ' ';
    }
    std::cout << "(custo = " << resposta->custo
              << ", expandidos = " << resposta->expandidos << ")\n";
}

int main() {
    const Grafo g{
        std::vector<Aresta>{ {1, 1}, {2, 4}},
        std::vector<Aresta>{ {2, 2}, {3, 5}},
        std::vector<Aresta>{ {3, 1}, {4, 7}},
        std::vector<Aresta>{ {4, 3}},
        std::vector<Aresta>{}
    };
    constexpr std::array nomes{
        std::string_view{"S"}, std::string_view{"A"}, std::string_view{"B"},
        std::string_view{"C"}, std::string_view{"G"}};

    imprimir("BFS", bfs(g, 0, 4), nomes);
    imprimir("UCS", ucs(g, 0, 4), nomes);
    return 0;
}

A saída informa S B G com custo $11$ para a BFS e S A B C G com custo $7$ para a UCS, reproduzindo os dois primeiros exercícios da Seção 5. As duas funções recebem o mesmo grafo e diferem na estrutura da fronteira e no critério de melhora. std::span expõe os vizinhos sem copiar nem transferir propriedade; std::expected obriga quem chama a tratar vértice inválido, ausência de caminho e estouro de custo; std::uint64_t torna explícita a faixa não negativa do custo. A verificação antes da soma preserva essa faixa em vez de confiar em um estouro silencioso. A entrada obsoleta da fila de prioridade não é um detalhe de biblioteca: ela é o preço de inserir uma prioridade melhor sem procurar e alterar o item antigo dentro do heap.

9. O fim do começo

Transformamos planejar em encontrar um caminho em um grafo e conhecemos quatro maneiras de percorrê-lo sem pista alguma. A busca em largura e a de custo uniforme compram otimalidade com memória que pode crescer exponencialmente; a busca em profundidade compra memória barata perdendo completude e otimalidade em espaços sem limite; e o aprofundamento iterativo recupera o melhor dos dois mundos. No exemplo com fator de ramificação $10$, ele paga cerca de $11\%$ de gerações adicionais; com fatores menores, o excesso relativo cresce. Em cada caso, o que muda entre um algoritmo e outro é a política de escolha na fronteira e, quando há custos, a regra de atualização do melhor caminho.

Buscar às cegas, porém, é caro por definição: nenhum desses algoritmos usa qualquer conhecimento sobre onde o objetivo está. Se dispuséssemos de uma estimativa da distância até o objetivo, poderíamos dirigir a busca e evitar expandir nós que claramente nos afastam. Essa estimativa tem um nome, heurística, e um algoritmo que a usa de forma ótima também. No próximo artigo, a busca deixa de ser cega: uma função heurística passa a sussurrar, a cada nó, quão longe ainda estamos, e o algoritmo A* transforma esse sussurro em caminhos ótimos com uma fração do trabalho.

Acrônimos e abreviações neste artigo

Referências

DIJKSTRA, E. W. A note on two problems in connexion with graphs. Numerische Mathematik, Berlin, v. 1, p. 269–271, 1959. Disponível em: https://eudml.org/doc/131436. Acesso em: 24 jul. 2026.

KORF, R. E. Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence, Amsterdam, v. 27, n. 1, p. 97–109, 1985. DOI: https://doi.org/10.1016/0004-3702(85)90084-0. Acesso em: 24 jul. 2026.

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

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

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

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

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