1. Modelo do Problema
Consideramos um problema de busca definido sobre um espaço de estados representado como um grafo ou árvore, onde cada nó corresponde a uma configuração e as arestas representam transições válidas.
Cada transição possui um custo associado, e o objetivo é encontrar um caminho do estado inicial até um estado objetivo com custo total mínimo.
1.1 Espaço de Estados
O problema é modelado como um espaço de estados (S, E), onde:
- S: conjunto de estados
- E: transições entre estados
A busca começa em um estado inicial s₀ e busca alcançar um estado objetivo s*.
1.2 Função de Custo
Cada caminho possui um custo associado:
g(n) = custo do nó inicial até n
O objetivo é minimizar o custo total do caminho.
1.3 Função Heurística
Uma função heurística estima o custo restante:
h(n) ≈ custo de n até o objetivo
A função de avaliação é:
f(n) = g(n) + h(n)
Essa função guia a busca para regiões promissoras.
1.4 Busca Limitada por Custo
Diferente do A*, o IDA* não expande nós globalmente usando uma fila de prioridade.
Em vez disso, ele realiza buscas em profundidade limitadas por um limiar de custo:
f(n) ≤ limite
Nós que excedem esse limite são podados.
1.5 Aprofundamento Iterativo por Custo
O algoritmo executa múltiplas iterações, cada uma aumentando o limite de custo.
- Inicia com limite inicial = h(s₀)
- Executa DFS com limite de custo
- Aumenta o limite para o menor valor excedido
Esse processo continua até encontrar o objetivo.
Próximo
Agora que o modelo do problema está definido, estudamos como os limites evoluem e como o aprofundamento iterativo funciona na prática.