Busca Heurística e A*

A busca heurística utiliza uma estimativa específica do problema do custo restante para um objetivo para guiar quais estados explorar primeiro; A* é o seu algoritmo canônico, expandindo estados na ordem da soma do custo até o momento e do custo estimado restante.

Definition

A busca heurística é uma busca informada que ordena a fronteira usando uma função de avaliação que combina o custo conhecido desde o início com uma estimativa heurística do custo restante; A* usa f(n) = g(n) + h(n) e é ótima quando h é admissível.

Scope

Este tópico abrange estratégias de busca informada (heurística), centradas na busca "best-first" e no algoritmo A*, incluindo o design e as propriedades das funções heurísticas (admissibilidade, consistência/monotonicidade), as garantias de otimalidade e eficiência que essas propriedades conferem, e variantes com limite de memória, como o A* de aprofundamento iterativo (IDA*). Ele aborda como as heurísticas são construídas (problemas relaxados, bancos de dados de padrões) e como elas equilibram precisão e computação. O aprendizado de heurísticas a partir de dados pertence ao subcampo de aprendizado de máquina.

Core questions

• O que torna uma heurística admissível e por que a admissibilidade garante a otimalidade do A*?
• Como a consistência (monotonicidade) fortalece as garantias e evita a reexpansão de nós?
• Como as boas heurísticas são projetadas, por exemplo, a partir de versões relaxadas do problema?
• Como as variantes com limite de memória, como o IDA*, preservam a otimalidade com espaço limitado?

Key concepts

• função de avaliação f = g + h
• heurística admissível
• heurística consistente (monótona)
• busca "greedy best-first"
• busca A*
• A* de aprofundamento iterativo (IDA*)
• dominância heurística
• problema relaxado e bancos de dados de padrões

Key theories

Otimidade do A* sob heurísticas admissíveis

Quando a heurística h nunca superestima o verdadeiro custo restante, A* expande os nós aumentando f = g + h e tem garantia de retornar um caminho de menor custo; entre os algoritmos que usam a mesma informação heurística, A* é otimamente eficiente.

Design heurístico via relaxamento

Heurísticas admissíveis podem ser derivadas sistematicamente resolvendo uma versão relaxada do problema (uma com menos restrições nas ações), uma vez que o custo exato de um problema mais fácil é um limite inferior para o original; heurísticas dominantes (mais informadas) expandem menos nós.

Busca heurística com limite de memória

O A* de aprofundamento iterativo realiza buscas em profundidade sucessivas limitadas por um limiar crescente de custo f, alcançando otimalidade semelhante ao A* com memória linear na profundidade da solução.

Clinical relevance

A busca heurística impulsiona a localização de rotas em mapas e jogos, o planejamento de movimento em robótica e os motores de busca dentro de planejadores automatizados e solucionadores de quebra-cabeças; a arte prática do design heurístico determina diretamente se grandes problemas são solucionáveis em tempo aceitável.

History

O algoritmo A* foi introduzido por Hart, Nilsson e Raphael (1968), dando à busca heurística uma base formal de otimalidade. A monografia de Pearl de 1984, Heuristics, forneceu o tratamento teórico definitivo, e o IDA* de Korf de 1985 abordou o custo de memória do A*. Esses resultados permanecem material central na educação em IA.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

O que é uma heurística admissível?

Uma heurística é admissível se nunca superestimar o custo real para atingir o objetivo a partir de qualquer estado. A admissibilidade é a condição sob a qual o A* tem garantia de encontrar uma solução ótima (de menor custo).

Qual é a diferença entre a busca "greedy best-first" e A*?

A busca "greedy best-first" expande o estado que parece mais próximo do objetivo de acordo apenas com a heurística (h), o que é rápido, mas pode estar longe do ideal. O A* adiciona o custo real incorrido até o momento (g), expandindo por f = g + h, o que preserva a otimalidade quando a heurística é admissível.