4. Otimalidade & Complexidade
- Quando o IDA* retorna soluções ótimas
- O papel de heurísticas admissíveis
- Por que completude é importante
- Como a complexidade de tempo se comporta
- Por que o uso de memória é a principal vantagem do IDA*
O IDA* é atraente porque combina orientação heurística com uma estratégia de busca em profundidade eficiente em memória.
No entanto, esses benefícios vêm com condições teóricas e trade-offs computacionais que precisam ser bem compreendidos.
4.1 O que significa Otimalidade
O IDA* é ótimo se retorna uma solução de custo mínimo sempre que ela existe.
Se C* denota o custo ótimo, então o caminho retornado pelo IDA* também deve ter custo C*.
A principal questão é sob quais condições essa garantia vale.
4.2 Heurísticas Admissíveis
A corretude do IDA* depende fundamentalmente de a heurística não superestimar o custo restante.
Isso significa que a heurística é admissível.
Com uma heurística admissível, a sequência de limiares evolui sem pular o custo da solução ótima.
4.3 Por que o Limiar Funciona
Em cada iteração, o IDA* explora todos os nós cujo custo estimado total respeita o limiar atual.
Se nenhuma solução é encontrada, o próximo limiar passa a ser o menor valor excedido de f.
Como os limiares aumentam de forma controlada, o nível de custo ótimo eventualmente é atingido.
4.4 Completude
O IDA* também é completo sob hipóteses usuais de busca em espaço de estados.
Se uma solução existe, os custos são positivos, e o espaço de busca é bem definido, o algoritmo eventualmente encontrará uma solução.
Essa propriedade é essencial porque a otimalidade só faz sentido se a busca sempre termina quando há solução.
4.5 Complexidade de Tempo
No pior caso, o IDA* ainda pode exigir tempo exponencial.
A complexidade de tempo no pior caso é exponencial na profundidade da solução ótima.
Isso ocorre porque o algoritmo pode revisitar os mesmos estados várias vezes em diferentes iterações.
4.6 Reexpansão de Nós
A principal fonte de custo extra no IDA* é a reexpansão repetida de nós.
Nós próximos da raiz podem ser gerados diversas vezes ao longo das iterações.
Esse é o preço computacional pago pela economia de memória.
4.7 Complexidade de Espaço
A principal vantagem do IDA* está no uso de memória.
Como a busca é em profundidade, o algoritmo armazena basicamente o caminho atual.
A complexidade de espaço é linear na profundidade da busca.
4.8 Influência da Heurística
Assim como no A*, heurísticas melhores melhoram o desempenho.
- heurística fraca → mais iterações e reexpansões
- heurística forte → menos trabalho redundante
Uma heurística admissível mais informativa reduz significativamente o tempo na prática.
4.9 IDA* vs A*: Trade-off Central
O A* reduz reexpansões armazenando muitos nós em memória.
O IDA* reduz memória aceitando recomputação.
Em resumo: A* troca memória por tempo, enquanto IDA* troca tempo por memória.
4.10 Casos Extremos
- h(n) = 0 → comportamento similar a aprofundamento iterativo por custo
- h(n) = h*(n) → progressão de limiar extremamente eficiente
Esses casos mostram como a qualidade da heurística impacta diretamente o desempenho.
Próximo: Parte 5 — Comparações & Aplicações
Agora que entendemos garantias e custos do IDA*, o próximo passo é compará-lo com outros algoritmos.
Na Parte 5, posicionamos o IDA* entre A*, DFS e outras técnicas, além de estudar aplicações práticas.