Algoritmos de Busca

Visão geral: o que “busca” significa em IA

Em IA, algoritmos de busca (search algorithms) são métodos de propósito geral para resolver problemas explorando um espaço de estados (state space): um grafo (graph) (explícito ou implícito) cujos nós (nodes) representam estados do mundo e cujas arestas (edges) representam ações (transições). A busca é fundamental em planejamento (planning), busca de caminhos (path finding), resolução de restrições (constraint solving) e muitas tarefas de “raciocínio” em que a solução é uma sequência de decisões.

Exemplos típicos incluem:

Encontrar a rota mais curta em um mapa rodoviário
Resolver quebra-cabeças como o 8-puzzle (peças deslizantes)
Planejar as ações de um robô para alcançar um objetivo sem colisões
Encontrar uma sequência de operações para transformar uma string/programa/estrutura em outra

A busca está intimamente relacionada a tópicos clássicos de CS como filas de prioridade (priority queues), grafos e análise assintótica (asymptotic analysis) (veja Algoritmos e Estruturas de Dados e Complexidade), e se insere no tema mais amplo de Busca.

Formulação do problema: estados, ações e custos

Um problema de busca costuma ser definido por:

Estado inicial (s_0)
Teste de objetivo (goal test): predicado is_goal(s)
Função sucessora (successor function): successors(s) → lista de (action, s', step_cost)
Custo de caminho (path cost) (g(n)): custo acumulado do início até um nó/estado
(Opcionalmente) Heurística (heuristic) (h(n)): estimativa do custo restante até um objetivo (para busca informada)

Espaço de estados vs. árvore de busca

Mesmo que o mundo subjacente seja um grafo, muitos algoritmos constroem conceitualmente uma árvore de busca (search tree):

Um grafo de espaço de estados pode conter ciclos e múltiplos caminhos para o mesmo estado.
Uma expansão em árvore pode criar nós duplicados representando o mesmo estado alcançado por caminhos diferentes.

Como duplicatas e ciclos podem explodir o trabalho, algoritmos práticos geralmente implementam busca em grafo (graph search), que rastreia estados visitados e/ou os melhores custos conhecidos.

Esqueleto genérico de busca em grafo

A maioria dos algoritmos clássicos de busca difere principalmente em como escolhe o “próximo nó a expandir” a partir de uma fronteira (frontier) (também chamada de lista aberta).

def graph_search(start, is_goal, successors, pop_frontier, push_frontier):
    frontier = []
    push_frontier(frontier, node=(start, None, 0))  # (state, parent, g)
    best_g = {start: 0}  # best known cost-to-come for each state

    while frontier:
        state, parent, g = pop_frontier(frontier)  # strategy-specific
        if is_goal(state):
            return reconstruct_path(state, parent)

        for action, s2, step_cost in successors(state):
            g2 = g + step_cost
            if s2 not in best_g or g2 < best_g[s2]:
                best_g[s2] = g2
                push_frontier(frontier, node=(s2, (state, parent, action), g2))

    return None  # failure

Para busca em largura (BFS, breadth-first search), a fronteira é uma fila FIFO (FIFO queue).
Para busca em profundidade (DFS, depth-first search), a fronteira é uma pilha LIFO (LIFO stack).
Para busca de custo uniforme e busca A*, a fronteira é uma fila de prioridade indexada por uma pontuação.

A escolha da política de fronteira determina propriedades centrais: completude (completeness), otimalidade (optimality) e complexidade de tempo/espaço.

Principais critérios de avaliação e trade-offs

Ao comparar algoritmos de busca, normalmente você se importa com:

Completude: ele encontrará uma solução se ela existir?
Otimalidade: ele encontrará a melhor solução (de menor custo)?
Complexidade de tempo (time complexity): número de nós expandidos (frequentemente exponencial na profundidade da solução)
Complexidade de espaço (space complexity): memória usada (frequentemente o fator limitante na prática)

Símbolos comuns usados na análise:

(b): fator de ramificação (branching factor) (média de sucessores por estado)
(d): profundidade do objetivo mais raso (em número de ações)
(m): profundidade máxima (pode ser infinita)
(C^*): custo da solução ótima
(\varepsilon): menor custo de passo positivo (quando os custos são positivos)

Busca não informada (uninformed) (cega)

Métodos não informados usam apenas a definição do problema (sucessores e teste de objetivo), sem “orientação” extra sobre onde o objetivo pode estar.

Busca em largura (BFS)

Ideia: expandir primeiro os nós mais rasos (nível por nível).

Fronteira: fila FIFO
Encontra o caminho mais curto em número de arestas quando todos os custos de passo são iguais (ou não ponderados).

Propriedades

Completa se o fator de ramificação for finito.
Ótima para custos unitários (ou custos iguais).
Tempo: (O(b^d))
Espaço: (O(b^d)) (armazena uma camada inteira da fronteira)

Exemplo prático

Solução com menor número de movimentos em puzzles em que cada movimento tem o mesmo custo.
Caminhos mínimos não ponderados em uma grade (movimentos em 4 vizinhos, cada um com custo 1).

Busca em profundidade (DFS)

Ideia: seguir um caminho o mais profundamente possível antes de retroceder.

Fronteira: pilha LIFO (ou recursão)

Propriedades

Não completa em espaços de profundidade infinita ou cíclicos, a menos que você adicione verificações de ciclo e limites de profundidade.
Não ótima.
Tempo: (O(b^m)) no pior caso
Espaço: (O(bm)) (bem menor que BFS)

Exemplo prático

Útil quando a memória é limitada e você só precisa de alguma solução rapidamente.
Comum como sub-rotina em backtracking/resolução de restrições (com poda).

Busca com limite de profundidade (DLS, depth-limited search) e DFS com aprofundamento iterativo (IDDFS, iterative deepening DFS)

DLS: DFS com um limite máximo de profundidade (L).

Evita descida infinita, mas pode perder soluções mais profundas que (L).

IDDFS: executar DLS repetidamente com limites crescentes (L=0,1,2,\dots) até encontrar um objetivo.

Propriedades do IDDFS

Completo (fator de ramificação finito).
Ótimo para custos unitários (como BFS), porque encontra o objetivo mais raso.
Tempo: (O(b^d)) (pequena sobrecarga vs. BFS em muitos casos)
Espaço: (O(bd)) (como DFS)

Quando é usado

Quando você quer a completude/otimalidade da BFS para custos unitários, mas não pode arcar com a memória da BFS.

Busca sensível a custo: busca de custo uniforme (UCS)

Quando as ações têm custos diferentes, “caminho mais curto” deve significar menor custo total, e não menor número de passos.

Busca de custo uniforme (UCS) (estilo Dijkstra)

Ideia: sempre expandir o nó da fronteira com o menor custo de caminho (g(n)).

Fronteira: fila de prioridade por (g(n))
Equivalente ao algoritmo de Dijkstra (Dijkstra’s algorithm) quando executado em um grafo explícito a partir de uma fonte até um conjunto de objetivos.

Propriedades

Completa se todos os custos de passo forem (\ge \varepsilon > 0).
Ótima sob a mesma condição (encontra a solução de menor custo).
Tempo/espaço: ainda pode ser exponencial em problemas difíceis; muitas vezes é resumida como explorando todos os nós com (g(n) \le C^*) (o que pode ser muitos).

Exemplo prático

Planejamento de rotas em que arestas representam tempo de viagem ou distância e variam por tipo de via.

Busca informada (informed) (heurística)

Métodos informados usam uma função heurística (heuristic function) (h(n)) que estima o custo restante até um objetivo. O objetivo é reduzir o número de expansões “apontando” mais diretamente para o objetivo.

Uma heurística é conhecimento específico do problema codificado como uma estimativa rápida de calcular.

Busca gulosa pelo melhor primeiro (greedy best-first search)

Ideia: expandir o nó que parece mais próximo do objetivo de acordo com (h(n)).

Pontuação: (f(n) = h(n))
Fronteira: fila de prioridade por (h)

Propriedades

Não ótima (pode ignorar caminhos baratos que inicialmente parecem mais longos).
Nem sempre completa em espaços infinitos (pode ficar presa seguindo heurísticas enganosas), embora com verificação de ciclos e grafos finitos frequentemente termine.
Muitas vezes é muito rápida na prática quando (h) é informativa.

Exemplo prático

Busca de caminhos em tempo real quando você quer “uma rota razoável rapidamente”, não necessariamente a mais curta.

Busca A\*

A* combina o custo real até agora e o custo restante estimado:

[ f(n) = g(n) + h(n) ]

Ideia: expandir o nó com o menor custo total estimado da solução.

Se (h(n)=0) para todo (n), A* se reduz à busca de custo uniforme.
Se (h) é informativa, A* expande muito menos nós do que a busca de custo uniforme.

Condições-chave da heurística

Heurística admissível (admissible heuristic): (h(n) \le h^(n)), onde (h^(n)) é o verdadeiro custo mínimo restante até um objetivo.
Nunca superestima.
Heurística consistente (consistent heuristic) (monótona): para qualquer aresta (n \to n') com custo de passo (c), [ h(n) \le c + h(n') ] A consistência implica admissibilidade e garante que (f(n)) ao longo de um caminho é não decrescente.

Propriedades (busca em grafo)

Com (h) admissível e custos de passo positivos, A* é ótima (busca em árvore); para busca em grafo, a consistência é normalmente usada para garantir otimalidade sem lógica complexa de reexpansão.
Completa sob hipóteses padrão (ramificação finita, (\varepsilon>0)).

Por que A* pode ser dramaticamente mais rápida

A* concentra a exploração perto de regiões promissoras.
Quanto mais precisa for (h) (mantendo-se admissível), menos nós ela expande.

Exemplos práticos de heurísticas

Busca de caminho em grade (distância de Manhattan)

Se o movimento é em 4 direções (cima/baixo/esquerda/direita) com custo unitário, uma heurística padrão é:

[ h(n) = |x_n - x_{goal}| + |y_n - y_{goal}| ]

Ela é:

Admissível (você não pode chegar ao objetivo em menos do que esse número de passos)
Consistente (cada movimento altera a distância de Manhattan em no máximo 1)

Heurísticas do 8-puzzle

Heurísticas admissíveis comuns:

Peças fora do lugar: contagem de peças que não estão na posição objetivo
Distância de Manhattan das peças: soma, sobre as peças, da distância da posição atual até a posição objetivo

A heurística de distância de Manhattan é tipicamente mais informativa (domina) a de peças fora do lugar, então A* expande menos nós.

“Dominância” heurística e eficiência

Se duas heurísticas admissíveis (h_1) e (h_2) satisfazem:

[ h_2(n) \ge h_1(n) \quad \text{para todo } n ]

então diz-se que (h_2) domina (dominate) (h_1) e a A* usando (h_2) irá (sob condições típicas) expandir não mais nós do que a A* usando (h_1). Intuitivamente: estimativas melhores levam a menos busca desperdiçada.

Uma métrica empírica comum é o fator de ramificação efetivo (effective branching factor): o fator de ramificação que produziria o número observado de expansões na dada profundidade da solução. Boas heurísticas reduzem isso drasticamente.

Resumo de algoritmos comuns e garantias

Algoritmo	Prioridade da fronteira	Completo?	Ótimo?	Espaço típico
BFS	menor profundidade	Sim ( (b) finito)	Sim (custos unitários)	Alto (O(b^d))
DFS	mais profundo primeiro	Não (profundidade infinita)	Não	Baixo (O(bm))
IDDFS	limite de profundidade crescente	Sim	Sim (custos unitários)	Baixo (O(bd))
UCS	menor (g)	Sim ((\varepsilon>0))	Sim	Alto (pode ser grande)
Gulosa pelo melhor primeiro	menor (h)	Às vezes	Não	Médio–alto
A*	menor (g+h)	Sim ((\varepsilon>0))	Sim (admissível; consistência ajuda em grafos)	Alto (frequentemente limitante)

Considerações práticas em sistemas reais

Busca em grafo precisa lidar com duplicatas

Em grafos (ou espaços de estados implícitos com estados repetidos), detecção de duplicatas é essencial:

BFS/DFS normalmente rastreiam um conjunto de visitados (visited set) para evitar laços.
Busca de custo uniforme/A* tipicamente rastreiam o melhor custo acumulado conhecido (g(s)); se um caminho melhor for encontrado depois, o nó pode precisar ser atualizado (ou reinserido).

A consistência da heurística simplifica a A*:

Com (h) consistente, uma vez que um nó é expandido (removido da fila de prioridade), seu melhor (g) é finalizado (semelhante ao Dijkstra).

Detalhes da fila de prioridade importam

Busca de custo uniforme/A* dependem de operações eficientes:

push / pop-min (heap binário é comum)
Desempate (por exemplo, favorecer (g) maior quando (f) empata) pode afetar o desempenho, embora não a correção sob admissibilidade/consistência

Memória é frequentemente o gargalo

BFS e A* podem consumir muita memória porque armazenam muitos nós na fronteira.

Variantes comuns com limite de memória:

IDA* (Iterative Deepening A*): aprofundamento iterativo com limite de custo (f); usa memória no estilo DFS.
RBFS (Recursive Best-First Search): comportamento best-first com memória limitada via recursão e backtracking.

Elas podem trocar mais tempo por muito menos espaço.

Variantes subótimas, mas rápidas

Às vezes, a otimalidade é cara demais:

A* ponderado (Weighted A*): (f(n)=g(n)+w\cdot h(n)) com (w>1)
Expande menos nós, mas pode retornar caminhos subótimos.
A* a qualquer momento (Anytime A*) (e planejadores anytime relacionados): encontra rapidamente uma solução e depois a melhora se tiver mais tempo.

Isso é comum em robótica e jogos onde responsividade importa.

Casos de uso comuns em IA e além

Busca de caminhos e navegação (grafos e grades)

Navegação de NPCs em jogos em malhas de navegação (navmesh) ou grades (A*, A* ponderado)
Planejamento de movimento de robôs em espaços discretizados (A*, busca de custo uniforme)
Roteamento de rede (métodos tipo busca de custo uniforme/Dijkstra)

Planejamento clássico e escalonamento

Problemas de planejamento podem ser formulados como busca sobre sequências de ações:

Estados codificam fatos do mundo (o que é verdadeiro/falso, níveis de recursos, localização do agente)
Ações mudam o estado com pré-condições/efeitos

Muitos planejadores usam busca no estilo A* com heurísticas de domínio (frequentemente derivadas de relaxamentos do problema de planejamento).

Quebra-cabeças combinatórios e problemas de restrição

Puzzles deslizantes, problemas tipo Rubik (busca heurística, IDA*)
Satisfação de restrições frequentemente usa DFS com poda; quando há custos, busca de custo uniforme/A* podem aparecer.

PLN e predição estruturada

Alguns procedimentos de inferência podem ser vistos como busca:

Parsing pode ser baseado em tabelas (programação dinâmica) ou baseado em agenda (best-first)
Decodificação em modelos de sequência frequentemente usa busca em feixe (beam search) (uma aproximação heurística best-first)

Busca guiada por aprendizado (tendência moderna)

Em muitos sistemas modernos, heurísticas são aprendidas:

Um modelo prediz (h(n)) ou ranqueia ações promissoras
A busca fornece correção/estrutura; o aprendizado fornece orientação

Essa visão híbrida conecta busca a tópicos de aprendizado de máquina (machine learning), como Aprendizado por Reforço (Reinforcement Learning), em que agentes precisam planejar ou aproximar planejamento sob incerteza.

Escolhendo o algoritmo certo

Um guia prático de decisão:

Caminho mínimo não ponderado / poucos passos: BFS (se a memória permitir) ou IDDFS
Custos de passo diferentes e você precisa de otimalidade: busca de custo uniforme (ou A* com (h=0))
Você tem uma boa heurística e precisa de otimalidade: A* com heurística admissível (de preferência consistente)
Você precisa de algo rápido e “bom o suficiente”: gulosa pelo melhor primeiro, A* ponderado ou variantes anytime
Memória é a principal restrição: IDDFS (custos unitários) ou IDA* (heurística, limitado por custo)

Mini-exemplo trabalhado: A\* em uma grade

Suponha que um robô se mova em uma grade 2D com obstáculos, movimentos em 4 vizinhos, cada movimento com custo 1.

(g(n)): passos do início até a célula (n)
(h(n)): distância de Manhattan até o objetivo
(f(n)=g(n)+h(n))

A* expandirá preferencialmente células que sejam:

próximas do início (pequeno (g)), e
próximas do objetivo (pequeno (h))

Em comparação com BFS (que expande todas as células a distância 1, depois 2, depois 3, … independentemente da direção), A* “canaliza” a exploração em direção ao objetivo, frequentemente reduzindo as expansões em ordens de magnitude em mapas grandes.

Principais conclusões

Busca é uma estrutura geral para resolver problemas explorando um espaço de estados; a principal escolha de projeto é como priorizar a fronteira.
BFS/DFS são métodos não informados fundamentais com trade-offs claros de completude/espaço.
Busca de custo uniforme lida com custos de passo variáveis e é ótima sob custos positivos.
Heurísticas habilitam busca informada: a gulosa pelo melhor primeiro é rápida, mas não ótima; A* é a busca heurística ótima padrão quando a heurística é admissível (e tipicamente consistente para busca em grafo).
Na prática, limites de memória e qualidade da heurística dominam o desempenho; muitos sistemas reais usam variantes com memória limitada ou com subotimalidade limitada.

Se você quiser se aprofundar, os próximos tópicos naturais são construção de heurísticas (relaxamentos do problema, pattern databases), variantes de A* com limite de memória e aprender heurísticas a partir de dados.