☆ Salvar Busca best-first — Expandir primeiro o nó que parece mais promissor

01/13/2026

Busca best-first é uma estratégia que atribui uma pontuação (função de avaliação) a cada nó e expande primeiro a opção que parece melhor naquele momento.

Intuição: ao comprar, você não olha todos os produtos em ordem; você combina sinais como “nota, preço, entrega” em um score e clica primeiro no que parece mais interessante. Na busca é igual: a fronteira é ranqueada por pontuação e o mais promissor é expandido primeiro.

Calcula-se f(n), ordena-se a fronteira com uma fila de prioridade e expande-se primeiro o nó mais promissor.

Como funciona (mecanismo e características)

Função de avaliação f(n)
- A ideia central é transformar “o quão bom este nó parece” em um número por meio de uma função de avaliação f(n).
- f(n) pode ser uma estimativa heurística até o objetivo, ou uma combinação de custo acumulado e estimativa.
- No mesmo problema, mudar f(n) pode acelerar muito a busca ou desviá-la.
- Por isso, “best-first” não é uma receita fixa, e sim o padrão de ranquear candidatos por pontuação.
Regra de expansão
- Escolhe-se na fronteira o nó não expandido com melhor pontuação.
- Ele é expandido, filhos são gerados, calcula-se f para cada filho e eles entram na fronteira.
- Repetindo, as opções “mais promissoras” ficam sempre na frente.
- Chegar rápido ao objetivo fica mais provável, mas a optimalidade depende de como f(n) é definido.
\[ n^*=\arg\min_{n \in frontier} f(n) \]

\[ frontier \leftarrow frontier \cup \{children(n^*)\} \]

Seleciona-se o nó com melhor f(n), expande-se e adicionam-se os filhos à fronteira, reordenando por score.
Implementação: fila de prioridade
- Como a fronteira precisa ficar “ordenada por score”, usa-se normalmente uma fila de prioridade.
- Assim, decidir o próximo nó a expandir vira um único pop.
- A cada inserção, a estrutura ajusta a ordem sem reordenar tudo do zero.
Casos comuns
- Busca gulosa (Greedy) usa uma heurística e expande o que parece mais perto do objetivo a cada passo.
- Busca A* combina custo acumulado e heurística para equilibrar velocidade e qualidade da solução.
- Ambas são casos particulares de best-first; a diferença principal é como f(n) é definido.

Importância e limitações

A busca best-first evita explorar “tudo de forma uniforme” ao focar o cálculo em candidatos promissores, o que ajuda em espaços grandes. Com uma boa f(n), ela se aproxima rapidamente do objetivo e oferece um quadro claro para entender métodos como a busca gulosa e a A*. Porém, se f(n) for enganosa, a busca pode cavar por muito tempo em caminhos que parecem bons, mas não são, e o trabalho total pode variar bastante dependendo de como estados duplicados são tratados.

Leituras prévias recomendadas (3/5)

Leituras recomendadas a seguir (5/18)