5. Comparações & Aplicações
- Como o IDA* se compara ao A*
- Como difere de DFS e aprofundamento iterativo
- Quais trade-offs definem seu uso
- Onde o IDA* é mais eficaz
- Como ele se encaixa no panorama geral de busca
O IDA* é melhor compreendido não isoladamente, mas como um ponto no espaço de design dos algoritmos de busca.
Ele combina orientação heurística, exploração em profundidade e controle iterativo de limiar em um compromisso característico entre uso de memória e trabalho repetido.
5.1 IDA* vs A*
A* e IDA* utilizam a mesma função de avaliação:
A diferença está em como a fronteira é gerenciada.
- A* mantém uma fila de prioridade global
- IDA* utiliza buscas em profundidade com limiares
A* geralmente economiza tempo usando mais memória, enquanto IDA* economiza memória recomputando estados.
5.2 IDA* vs Busca em Profundidade (DFS)
A DFS padrão explora profundamente sem utilizar estimativas de custo.
O IDA* mantém a estrutura recursiva da DFS, mas restringe a exploração com base em limites heurísticos.
- DFS → eficiente em memória, não informada
- IDA* → eficiente em memória, informada
5.3 IDA* vs Aprofundamento Iterativo
O aprofundamento iterativo clássico aumenta um limite de profundidade.
O IDA* aumenta um limiar de custo baseado em f(n).
Isso torna o IDA* mais adequado para problemas com pesos, onde a profundidade não reflete a qualidade do caminho.
5.4 IDA* vs Dijkstra
O algoritmo de Dijkstra resolve caminhos mínimos sem utilizar heurística.
O IDA* introduz estimativa heurística e altera completamente a ordem da busca.
Em troca de menor uso de memória, o IDA* pode revisitar estados muito mais vezes.
5.5 Quando usar IDA*
O IDA* é especialmente indicado quando:
- o espaço de busca é muito grande
- a memória é o principal limitante
- existe uma heurística admissível útil
- é necessário manter otimalidade
Nessas situações, o IDA* pode funcionar onde o A* se torna inviável.
5.6 Limitações
O IDA* não é universalmente superior.
- pode repetir muito trabalho
- pode ser lento com heurísticas fracas
- não lida bem com muitos estados repetidos globais
Seu valor depende do equilíbrio entre memória disponível e custo de recomputação.
5.7 Aplicações Típicas
O IDA* é muito utilizado em domínios com espaço de estados grande e memória limitada.
- quebra-cabeças combinatórios
- problemas de peças deslizantes
- Cubo de Rubik
- planejamento em grandes espaços de estados
Nesses casos, sua eficiência em memória é decisiva.
5.8 Visão Geral
O IDA* mostra que o design de algoritmos envolve trade-offs explícitos.
Ele não é simplesmente melhor que A* ou DFS.
Ele ocupa um nicho específico: busca informada sob restrições severas de memória.
Conclusão da Série
O IDA* deve ser entendido não apenas como “A* com menos memória”, mas como um método de busca fundamentado que combina heurística, recursão e iteração por limiar.
Ao longo desta série, estudamos seu modelo, funcionamento, propriedades teóricas e aplicações.