CCT-UFCA/Ciência da Computação/Inteligência Artificial/Busca bidirecional

Busca Bidirecional - Definição

A busca bidirecional é uma estratégia de busca cega que executa duas buscas ao mesmo tempo:

1. Busca direta – a partir do estado inicial em direção ao objetivo.
2. Busca inversa – a partir do objetivo em direção ao estado inicial.

O processo termina quando as duas buscas se encontram em um ponto intermediário no espaço de estados.

Motivação

O grande ganho vem do fato de que:

• Se a profundidade da solução é d, uma busca simples em largura custaria O(b^d).
• Na busca bidirecional, cada busca percorre apenas até d/2, custando:
  • O(b^(d/2))+O(b^(d/2))≈O(b^(d/2))
• Esse ganho é enorme quando b e d são grandes.

Como funciona

1. Início: Coloca o estado inicial na fronteira da busca direta e o estado objetivo na fronteira da busca inversa.
2. Alternância: Executa uma expansão em cada lado (direta e inversa) ou alterna entre elas.
3. Encontro: A busca termina quando:
   • Um nó gerado pela busca direta já está na fronteira da busca inversa, ou
   • Um nó gerado pela busca inversa já foi encontrado na busca direta.
4. Reconstrução do caminho: Junta o caminho da busca direta com o da busca inversa.

Exemplo – Grafo de Cidades

Suponha o problema de ir de Arad até Bucareste, com profundidade mínima d=6 e fator de ramificação b=10.

• Busca em largura normal:
  • b^d=106=1.000.000 nós gerados
• Busca bidirecional:
  • Cada busca percorre até d/2=3:
    • 2×b^(d/2)=2×103=2.000 noˊs gerados
• Resultado: 500× menos nós gerados!

Desafios e Limitações

1. Busca inversa difícil – Nem sempre é simples gerar predecessores do objetivo.
2. Vários objetivos – Fica complexo definir a busca inversa se houver mais de um objetivo.
3. Objetivos abstratos – Em problemas como as 8 rainhas, não existe um único estado objetivo claro, tornando inviável a busca reversa.
4. Memória – Apesar de menor que BFS, ainda pode ser grande se b^(d/2) for alto.

Referências

1. RUSSELL, S. J.; NORVIG, P. Inteligência artificial. 3 ed. LTC, 2013. 1016 p.
2. COPPIN, B. Inteligência Artificial. 1a ed. LTC, 2010. 664 p.