Busca

Busca em IA: planejamento e resolução de problemas

Em IA, busca é a família de algoritmos que resolve problemas por exploração sistemática de alternativas — possíveis sequências de ações, configurações ou hipóteses — até que um objetivo seja alcançado. Muitas tarefas de IA podem ser formuladas como:

  • Você tem um estado inicial
  • Você pode aplicar ações que geram estados sucessores
  • Você quer alcançar um estado objetivo (ou maximizar uma recompensa / minimizar um custo)
  • Você precisa fazer isso de forma eficiente apesar de um número potencialmente enorme de possibilidades

A busca é fundamental no planejamento clássico em IA, na navegação de robôs, em jogos, em escalonamento, e também aparece em sistemas modernos de aprendizado de máquina (machine learning) (por exemplo, decodificação de sequências com busca em feixe, planejamento com heurísticas aprendidas, busca em árvore no aprendizado por reforço).

Este artigo foca em algoritmos de busca em grafos — especialmente BFS, DFS e A* — e no papel das heurísticas.

Modelando problemas como busca

Formulação em espaço de estados

Um problema de busca normalmente é definido por:

  • Representação de estado s (por exemplo, posição do robô em uma grade, uma configuração do cubo de Rubik)
  • Estado inicial s0
  • Ações / função de transição: Succ(s) retorna sucessores (e opcionalmente custos das ações)
  • Teste de objetivo: Goal(s) é verdadeiro se s é uma solução
  • Custo do caminho: soma dos custos por passo, frequentemente escrito como g(s) para o custo do início até s

O trabalho do algoritmo de busca é encontrar um caminho (uma sequência de ações) de s0 até qualquer estado objetivo, idealmente minimizando o custo total.

Árvores vs grafos (e por que isso importa)

Mesmo que a exploração conceitual forme uma árvore, muitos problemas são naturalmente grafos:

  • Você pode chegar ao mesmo estado por múltiplos caminhos
  • Existem ciclos (por exemplo, mover para a esquerda e depois para a direita retorna você à mesma célula)

Na prática, a maioria das implementações sérias de busca são buscas em grafo que rastreiam estados visitados para evitar loops infinitos e trabalho redundante.

É aqui que estruturas de dados centrais — filas, pilhas, conjuntos hash, filas de prioridade — importam; veja Algoritmos e Estruturas de Dados.

Busca em Largura (BFS)

Ideia

BFS explora o espaço de busca nível por nível: primeiro todos os estados na profundidade 1, depois profundidade 2, e assim por diante. Ela usa uma fila FIFO para a fronteira.

Propriedades

  • Completa: sim, se o fator de ramificação for finito e existir uma solução.
  • Ótima: sim, quando todos os custos de passo são iguais (ou quando se minimiza o número de passos).
  • Complexidade de tempo: (O(b^d)), onde b é o fator de ramificação e d é a profundidade do objetivo mais raso.
  • Complexidade de espaço: (O(b^d)) (BFS pode consumir muita memória).

Esses limites exponenciais se conectam diretamente a Complexidade: até mesmo uma busca “simples” pode se tornar intratável à medida que b e d crescem.

Exemplo prático: caminho mais curto em uma grade não ponderada

Se cada movimento custa 1, BFS encontra o caminho com o menor número de passos.

from collections import deque

def bfs(start, is_goal, neighbors):
    q = deque([start])
    parent = {start: None}   # for path reconstruction

    while q:
        s = q.popleft()
        if is_goal(s):
            return reconstruct_path(parent, s)

        for n in neighbors(s):
            if n not in parent:          # visited check
                parent[n] = s
                q.append(n)

    return None

def reconstruct_path(parent, goal):
    path = []
    cur = goal
    while cur is not None:
        path.append(cur)
        cur = parent[cur]
    return list(reversed(path))

BFS é amplamente usada em:

  • caminhos mais curtos em grafos não ponderados
  • encontrar componentes conectados / alcançabilidade
  • planejamento base quando os custos são uniformes

Busca em Profundidade (DFS)

Ideia

DFS explora o mais longe possível ao longo de um ramo antes de fazer retrocesso. Ela usa uma pilha (frequentemente via recursão).

Propriedades

  • Completa: não necessariamente (pode ficar presa em caminhos de profundidade infinita sem verificação de ciclos ou limites de profundidade).
  • Ótima: não (pode encontrar primeiro uma solução muito profunda/cara).
  • Complexidade de tempo: (O(b^m)), onde m é a profundidade máxima de busca.
  • Complexidade de espaço: (O(b \cdot m)), frequentemente muito menor que a BFS.

DFS é atraente quando a memória é limitada, mas deve ser usada com cuidado.

Limites de profundidade e DFS com Aprofundamento Iterativo (IDDFS)

Uma correção comum é a DFS com limite de profundidade, que para na profundidade L. Para recuperar a completude semelhante à BFS (para custos unitários) com memória semelhante à DFS, use aprofundamento iterativo:

  • Execute DFS com L=0,1,2,... até encontrar uma solução.

IDDFS:

  • é completa (sob suposições padrão)
  • é ótima para problemas de custo unitário (como a BFS)
  • usa muito menos memória do que a BFS

DFS/IDDFS aparecem frequentemente na resolução de quebra-cabeças e em busca combinatória onde a memória é um gargalo.

Busca de Custo Uniforme (UCS) e algoritmo de Dijkstra

BFS só é ótima quando cada passo custa o mesmo. Quando ações têm diferentes custos não negativos, você quer Busca de Custo Uniforme (UCS), que é essencialmente o algoritmo de Dijkstra aplicado a partir do estado inicial.

  • A fronteira é ordenada pelo custo do caminho até agora g(n)
  • Sempre expande o nó atualmente mais barato

Propriedades (com custos de passo não negativos):

  • Completa: sim (dado fator de ramificação finito e custo mínimo de passo positivo)
  • Ótima: sim

UCS é a versão “sem heurística” do A*.

Heurísticas: guiando a busca

Uma heurística é uma função:

  • h(n) = custo estimado do nó/estado n até um objetivo

Heurísticas são a chave para escalar a busca: elas direcionam a exploração para estados promissores.

Admissibilidade e consistência

Duas propriedades importantes:

  • Heurística admissível (admissible heuristic): nunca superestima o custo real restante
    [ h(n) \le h^(n) ] onde (h^(n)) é o verdadeiro custo ótimo restante (cost-to-go).

  • Heurística consistente (monotone heuristic): obedece a uma desigualdade triangular ao longo das arestas
    [ h(n) \le c(n,n') + h(n') ] para todo sucessor (n') de (n).

Consistência implica admissibilidade (sob suposições típicas) e torna o A* mais fácil de implementar corretamente: uma vez que um nó é expandido, seu melhor custo de caminho é final.

Exemplos comuns de heurísticas (navegação em grade)

Para uma grade com 4 vizinhos e custos unitários:

  • Distância de Manhattan (Manhattan distance):
    h = abs(x - gx) + abs(y - gy)
    admissível e consistente.

Para uma grade com 8 vizinhos com custo diagonal √2:

  • Distância octil (Octile distance) é frequentemente usada.

Para espaço contínuo com custos euclidianos:

  • Distância euclidiana (Euclidean distance) é admissível (se obstáculos só puderem aumentar o custo real).

Construindo heurísticas na prática

Padrões comuns de projeto:

  • Relaxamentos (relaxations): resolver uma versão mais fácil do problema (por exemplo, ignorar obstáculos) e usar seu custo ótimo como h.
  • Abstrações (abstractions): agrupar estados em estados abstratos e pré-computar distâncias (bases de padrões em quebra-cabeças).
  • Marcos e subobjetivos (landmarks and subgoals): estimar a distância via restrições intermediárias obrigatórias.
  • Combinar heurísticas admissíveis (combine admissible heuristics):
    • max(h1, h2) é admissível se cada uma for admissível (frequentemente mais forte do que qualquer uma isoladamente).
    • A soma só é segura quando os componentes são garantidos como partes de custo disjuntas.

A força da heurística é crucial: quanto mais próximo h(n) estiver do custo real restante (sem superestimar), menos nós o A* tipicamente expande.

A\*: busca ótima com heurísticas

Ideia

A* classifica nós na fronteira por:

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

  • g(n): custo exato do início até n
  • h(n): custo estimado de n até o objetivo

Ele expande primeiro o nó com menor f(n).

Garantias

Com custos de passo não negativos:

  • Se h é admissível, A* é ótimo (busca em árvore; para busca em grafo, consistência é tipicamente exigida para a implementação mais simples com “conjunto fechado”).
  • Se h é consistente, a busca em grafo do A* é ótima e evita lógica complicada de reexpansão de nós.

Detalhes práticos de implementação

Uma busca em grafo típica com A* usa:

  • Conjunto aberto (open set) (fronteira): uma fila de prioridade por f
  • Conjunto fechado (closed set): um conjunto de estados visitados/expandidos
  • g_score[state]: melhor custo encontrado até agora
  • came_from[state]: ponteiro de retorno para reconstrução de caminho
import heapq
import math

def astar(start, is_goal, neighbors, h):
    open_heap = []
    heapq.heappush(open_heap, (h(start), 0, start))  # (f, g, state)

    came_from = {start: None}
    g_score = {start: 0}
    closed = set()

    while open_heap:
        f, g, s = heapq.heappop(open_heap)

        if s in closed:
            continue
        if is_goal(s):
            return reconstruct_path(came_from, s)

        closed.add(s)

        for (n, cost) in neighbors(s):   # cost >= 0
            tentative_g = g_score[s] + cost
            if n in closed:
                continue

            if tentative_g < g_score.get(n, math.inf):
                came_from[n] = s
                g_score[n] = tentative_g
                heapq.heappush(open_heap, (tentative_g + h(n), tentative_g, n))

    return None

Notas:

  • Muitas bibliotecas de fila de prioridade não oferecem suporte fácil a decrease-key; inserir duplicatas e ignorar entradas desatualizadas é comum.
  • Com heurísticas inconsistentes, você pode precisar permitir reabrir nós (remover de closed quando um caminho melhor é encontrado), ou mudar para uma formulação mais cuidadosa.

Exemplo: A\* em uma grade

Suponha que você queira o caminho mais curto para um robô em uma grade com obstáculos:

  • Estado: (x, y)
  • Ações: mover N/S/L/O com custo 1
  • Heurística: distância de Manhattan até o objetivo

A* vai priorizar fortemente células “mais próximas” do objetivo, mas desviará de obstáculos quando g aumentar.

É por isso que o A* é uma escolha padrão em jogos, navegação robótica e planejamento de rotas.

Comparando BFS, DFS e A\*

Principais trade-offs:

  • BFS

    • Ótima para: caminhos mais curtos com custo unitário, espaços de estado pequenos a médios
    • Fraqueza: explosão de memória

  • DFS / IDDFS

    • Ótima para: busca com pouca memória, encontrar alguma solução rapidamente em espaços profundos
    • Fraqueza: não é ótima em custo; pode se perder sem limites

  • A*

    • Ótima para: caminhos ótimos com heurísticas informativas
    • Fraqueza: ainda pode ser exponencial; pesada em memória em espaços grandes

Quando os custos variam, compare:

  • UCS: ótima, mas explora amplamente sem orientação
  • A*: ótima e guiada por h

Variantes e extensões que você verá na prática

Usa apenas f(n) = h(n). Muitas vezes é rápida, mas:

  • não é ótima
  • pode ser incompleta em alguns espaços infinitos
  • pode ficar presa explorando regiões “aparentemente próximas”, mas bloqueadas

A\* Ponderado (Weighted A\*) (busca com suboptimalidade limitada)

Usa:

[ f(n) = g(n) + w \cdot h(n), \quad w > 1 ]

Isso direciona a busca de forma mais agressiva em direção à heurística, frequentemente reduzindo expansões de maneira dramática, ao custo de soluções potencialmente subótimas. Muitos sistemas reais preferem esse trade-off.

IDA\* (A\* com Aprofundamento Iterativo) (Iterative Deepening A\*)

Uma variante do A* eficiente em memória:

  • realiza aprofundamento iterativo sobre um limiar de custo f
  • usa memória semelhante à DFS
  • frequentemente usada em quebra-cabeças com espaços de estado enormes (por exemplo, quebra-cabeças de peças deslizantes)

Busca bidirecional

Busca a partir do início e do objetivo e encontra um ponto de encontro no meio.

  • Funciona melhor quando o objetivo é bem definido e predecessores podem ser gerados.
  • Pode reduzir a complexidade de (b^d) para aproximadamente (b^{d/2}) em casos ideais.

Busca em feixe (beam search) (aproximada)

Mantém apenas os melhores k nós em cada profundidade (ou por pontuação). Comum na geração de sequências (por exemplo, tradução automática) e em outras tarefas de grande ramificação. A busca em feixe não garante encontrar a solução ótima, mas costuma ser eficaz na prática; veja também seu uso junto com Arquitetura Transformer.

Busca em planejamento clássico

No planejamento clássico (por exemplo, planejamento no estilo STRIPS), estados codificam fatos sobre o mundo, e ações têm pré-condições e efeitos. Sistemas de planejamento frequentemente usam:

  • Busca progressiva (forward search): do estado inicial em direção aos objetivos (comum com A*)
  • Busca regressiva (regression): das condições de objetivo de volta em direção ao início
  • Heurísticas derivadas de problemas de planejamento relaxados (relaxed planning problems) (ignoram efeitos de deleção), produzindo estimativas poderosas usadas em planejadores como o FF

Heurísticas de planejamento são essencialmente funções h(n) informadas pelo domínio. Elas podem fazer a diferença entre explorar bilhões de estados e encontrar um plano rapidamente.

A busca também se conecta a Aprendizado por Reforço: AR resolve problemas de decisão sequencial via funções de valor/políticas aprendidas, enquanto a busca/planejamento clássicos frequentemente assumem um modelo conhecido. Métodos híbridos (AR baseado em modelo, planejamento com heurísticas aprendidas) combinam ambos.

Considerações práticas de engenharia

Escolhendo representações

O desempenho frequentemente é dominado por:

  • quão compacto é o seu estado
  • quão rápido você consegue gerar sucessores
  • quão eficiente é o hashing/igualdade para verificações de visitados

Para problemas grandes, uma codificação cuidadosa do estado (bitsets, empacotamento em inteiros) pode gerar grandes ganhos de velocidade.

Detecção de duplicatas e “conjuntos fechados”

A busca em grafo tipicamente precisa de:

  • um conjunto de visitados/fechado para impedir ciclos
  • uma tabela de melhor custo (g_score) para evitar perder tempo com caminhos piores

Mas isso consome memória. Se a memória for restrita, considere IDDFS/IDA*, abstração ou busca limitada.

Quando heurísticas são difíceis (ou aprendidas)

Sistemas modernos podem usar heurísticas aprendidas (por exemplo, uma rede neural prevendo a distância restante). Elas podem ser eficazes, mas podem violar admissibilidade. Estratégias comuns:

  • Aceitar suboptimalidade (usar A* Ponderado / busca em feixe)
  • Calibrar ou limitar a heurística (difícil em geral)
  • Usar o modelo aprendido para propor candidatos, mas verificar com busca clássica

Essa é uma forma de como busca “simbólica” e Redes Neurais interagem na IA contemporânea.

Escala e paralelismo

Busca em grande escala pode ser paralelizada (dividindo a fronteira, conjuntos fechados distribuídos), mas sincronização e detecção de duplicatas tornam-se complexas. É aqui que ideias de Fundamentos de Sistemas Distribuídos começam a importar.

Aplicações

Algoritmos de busca e heurísticas impulsionam muitos sistemas de IA e de software:

  • Robótica: planejamento de caminho (modelos de grade/mundo), planejamento de tarefas (sequências de ações)
  • Jogos: navegação (A*), estratégia (busca em árvore; veja Busca em Árvore de Monte Carlo)
  • Compiladores e síntese de programas: explorar transformações ou programas candidatos
  • Escalonamento e roteamento: caminhos mais curtos, planejamento guiado por restrições
  • Decodificação em PLN: busca em feixe para selecionar sequências de saída prováveis

Resumo: o que lembrar

  • BFS: caminho mais curto em grafos não ponderados; simples, mas pesada em memória.
  • DFS: pouca memória; não é ótima; use limites de profundidade para garantir terminação.
  • UCS (Dijkstra): ótima para custos não negativos variáveis; sem orientação por heurística.
  • A*: ótima quando h é admissível (e tipicamente consistente para busca em grafo); desempenho depende fortemente da qualidade da heurística.
  • Heurísticas são centrais: elas codificam a estrutura do problema para reduzir a busca drasticamente.
  • Sistemas reais frequentemente trocam optimalidade por velocidade com A* Ponderado, busca em feixe ou heurísticas específicas do domínio.

A busca é um dos exemplos mais claros de como a IA combina teoria (garantias, complexidade, optimalidade) com engenharia prática (representações, estruturas de dados, heurísticas) para resolver problemas reais de forma eficiente.