Matemática Discretapara Engenheiros

3. O Algoritmo IDA*

O IDA* combina duas ideias: avaliação heurística por f(n) = g(n) + h(n) e exploração em profundidade sob um limite de custo.

O algoritmo invoca repetidamente uma busca recursiva limitada, aumentando o limiar apenas quando necessário.

3.1 Estrutura de Controle Global

No nível superior, o IDA* mantém um limiar atual e executa repetidamente uma busca em profundidade a partir do estado inicial.

Cada iteração tem três possíveis resultados:

• o objetivo é encontrado
• todos os nós dentro do limiar são explorados
• um novo valor mínimo excedido é retornado

Se o objetivo não for encontrado, esse valor retornado se torna o limiar da próxima iteração.

3.2 Procedimento Recursivo

O núcleo do IDA* é uma função recursiva de busca em profundidade que explora os sucessores do nó atual.

Para cada nó visitado, o algoritmo calcula:

Se esse valor exceder o limiar atual, a recursão não continua abaixo desse nó.

3.3 Condição de Corte

Um nó é podado sempre que f(n) > T, onde T é o limiar atual.

Nesse caso, a função não retorna simplesmente falha.

Em vez disso, retorna o valor f(n), pois ele pode se tornar o próximo limiar.

3.4 Detecção de Objetivo

Antes de expandir os sucessores, o algoritmo verifica se o nó atual é um estado objetivo.

Se for, a busca termina com sucesso, e o caminho solução pode ser reconstruído a partir da pilha recursiva ou estrutura de predecessores.

A detecção do objetivo ocorre dentro da DFS limitada, não fora dela.

3.5 Propagação do Próximo Limiar

Durante uma busca limitada, vários nós podem exceder o limiar.

As chamadas recursivas propagam o menor valor excedido de f.

Esse valor define o menor limiar necessário para avançar na próxima iteração.

3.6 Evitando Ciclos no Caminho

Como o IDA* utiliza busca em profundidade, é necessário evitar ciclos triviais no caminho atual.

Uma estratégia comum é impedir recursão para estados já presentes no caminho corrente.

Isso é mais leve do que manter um conjunto global de visitados, preservando a eficiência de memória.

3.7 Template Clássico do IDA*

A estrutura geral do IDA* pode ser expressa assim:

IDA*(inicio):

    limite = h(inicio)

    while true:
        resultado = BUSCA(inicio, g=0, limite)

        if resultado é ENCONTRADO:
            return solução

        if resultado é ∞:
            return falha

        limite = resultado


BUSCA(no, g, limite):

    f = g + h(no)

    if f > limite:
        return f

    if no é objetivo:
        return ENCONTRADO

    minimo_excedido = ∞

    para cada sucessor s de no:
        temp = BUSCA(s, g + custo(no, s), limite)

        if temp é ENCONTRADO:
            return ENCONTRADO

        if temp < minimo_excedido:
            minimo_excedido = temp

    return minimo_excedido

3.8 Interpretação do Algoritmo

Cada iteração responde à pergunta:

Se não, o algoritmo calcula o menor limiar que permitiria continuar a exploração.

Nesse sentido, o IDA* alterna entre DFS limitada e revisão de limiar.

3.9 Resumo Operacional

• inicializar o limiar com a avaliação inicial
• executar DFS limitada por esse limiar
• podar nós com f alto
• registrar o menor valor excedido
• repetir até encontrar solução ou falhar

Essa estrutura dá ao IDA* seu equilíbrio característico: baixo uso de memória com custo de recomputação.