2. Limiar de Custo & Aprofundamento Iterativo
- O que significa o limiar de custo
- Como a poda é baseada em f(n)
- Por que o IDA* repete a busca em profundidade
- Como o limiar é atualizado
- Por que isso economiza memória
A ideia central do IDA* é substituir a fronteira global baseada em prioridade do A* por buscas em profundidade repetidas limitadas por custo.
Em vez de armazenar todos os nós da fronteira, o algoritmo explora apenas caminhos cujo custo estimado total permanece dentro de um limiar atual.
2.1 Significado do Limiar
No IDA*, cada iteração é controlada por um valor escalar chamado limiar de custo.
Um nó n é expandido apenas se f(n) = g(n) + h(n) ≤ T, onde T é o limiar atual.
Assim, o limiar determina qual parte do espaço de busca pode ser explorada na iteração atual.
2.2 Poda Baseada em Custo
Sempre que o custo estimado total de um nó excede o limiar, o ramo é interrompido imediatamente.
Essa regra de poda torna a busca seletiva sem exigir uma ordenação global dos nós da fronteira.
Os nós não são descartados permanentemente; eles podem ser reconsiderados em iterações futuras.
2.3 Limiar Inicial
O primeiro limiar geralmente é definido como a avaliação do estado inicial.
Como o custo acumulado inicial é zero, temos:
A busca começa então com o menor limite significativo possível.
2.4 Uma Iteração do IDA*
Para um limiar fixo, o IDA* realiza uma travessia em profundidade.
Durante essa travessia:
- nós dentro do limite são explorados recursivamente
- nós além do limite são podados
- o menor valor excedido é registrado
Se o objetivo não for encontrado, esse menor valor excedido se torna o próximo limiar.
2.5 Atualização do Limiar
O IDA* não aumenta o limiar arbitrariamente.
O próximo limiar é escolhido como o menor valor de f(n) entre todos os nós podados na iteração atual.
Isso garante progresso com o menor aumento possível.
2.6 Por que Repetir a Busca
Como o limiar restringe a exploração, uma única passagem em profundidade não é suficiente.
Alguns nós relevantes estão logo além do limite atual e só podem ser explorados quando o limiar aumenta.
Por isso, o IDA* revisita a busca múltiplas vezes, expandindo gradualmente a região explorada.
2.7 Vantagem de Memória
A principal vantagem dessa estratégia é a eficiência de memória.
Como cada iteração é em profundidade, o algoritmo armazena apenas o caminho atual e poucas informações auxiliares.
Diferente do A*, o IDA* não precisa manter toda a fronteira na memória.
2.8 Principal Trade-off
O preço da baixa utilização de memória é o retrabalho.
- uso de memória diminui
- revisitação de estados aumenta
O IDA* pode explorar os mesmos prefixos várias vezes ao longo das iterações.
Esse é o trade-off fundamental entre A* e IDA*.
Próximo: Parte 3 — O Algoritmo IDA*
Agora que o mecanismo de limiar está claro, o próximo passo é estudar a estrutura completa do algoritmo.
Na Parte 3, apresentamos o algoritmo em si, incluindo busca recursiva, propagação de limiar e pseudocódigo.