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

Algoritmos de Busca com Informação

Quando estudamos Inteligência Artificial, vemos que muitos problemas podem ser modelados como busca em um espaço de estados (como resolver um quebra-cabeça, encontrar o melhor caminho em um mapa ou planejar ações de um robô).

Até agora, vimos buscas cegas (sem informação), como:

• Busca em largura
• Busca em profundidade
• Aprofundamento iterativo

Essas estratégias exploram o espaço sem saber nada sobre onde está a solução.

Já os algoritmos de busca com informação usam heurísticas: estimativas inteligentes que ajudam a guiar a busca em direção ao objetivo de forma mais rápida e eficiente.

Conceitos principais

1. Função de avaliação f(n)

• Para decidir qual nó expandir, calculamos um valor f(n).
• A ideia é sempre expandir o nó mais promissor (com menor f).

2. Heurística h(n)

• É uma estimativa do custo para chegar do nó atual até o objetivo.
• Exemplo: no problema de encontrar uma cidade, h(n) pode ser a distância em linha reta até o destino.
• Regras importantes:
  • h(n) = 0 se n for o objetivo.
  • Se não superestimar o custo real, a heurística é chamada de admissível.

Principais Algoritmos

Busca de Custo Uniforme (UCS)

• Expande o nó com menor custo real acumulado g(n).
• Completa e ótima (quando os custos são positivos).
• Desvantagem: pode ser lenta em espaços grandes.

Busca de Melhor Escolha (Gulosa)

• Usa apenas a heurística: f(n) = h(n)
• Sempre escolhe o nó que parece mais próximo do objetivo.
• Rápida, mas nem sempre encontra o caminho ótimo.
• Exemplo: pode escolher uma rota mais curta em linha reta, mas que na prática sai mais cara.

Busca A*

• Combina o melhor dos dois mundos: f(n) = g(n) + h(n)
  • g(n): custo real até agora.
  • h(n): estimativa até o objetivo.
• Se a heurística for admissível e consistente, o A* é completo e ótimo.
• Muito usado em aplicações reais (GPS, jogos, robôs).

Exemplo prático (problema do mapa Arad → Bucareste)

Imagine que você está em Arad e quer chegar até Bucareste, percorrendo cidades conectadas por estradas com custos (distâncias).

O mapa simplificado é mais ou menos assim:

Arad

├─ Zerind (75) ─ Oradea (71)

├─ Sibiu (140) ─ Fagaras (99) ─ Bucareste (211)

│              └ Rimnicu Vilcea (80) ─ Pitesti (97) ─ Bucareste (101)

└─ Timisoara (118) ─ Lugoj (111) ─ ...

(números entre parênteses = distância em km)

Além disso, temos a distância em linha reta até Bucareste (heurística h(n)) para cada cidade. Por exemplo:

• h(Sibiu) = 253 km
• h(Fagaras) = 176 km
• h(Pitesti) = 100 km
• h(Bucareste) = 0 km

1. Busca de Custo Uniforme (UCS)

• Critério: sempre escolhe o caminho com menor custo acumulado g(n).
• Exemplo:
  • Arad → Sibiu (140 km).
  • Arad → Zerind (75 km) → Oradea (71 km) = 146 km.
  • UCS escolhe expandir Sibiu primeiro, pois 140 < 146.
• Ele vai somando custos reais até Bucareste.
• Resultado: encontra o caminho ótimo em distância, mas pode expandir muitas cidades até ter certeza.

2. Busca Gulosa (Greedy Best-First Search)

• Critério: sempre escolhe o nó com menor h(n) (distância em linha reta até Bucareste).
• Exemplo:
  • De Arad, candidatos: Zerind (h=374), Sibiu (h=253), Timisoara (h=329).
  • Escolhe Sibiu (h=253).
  • Depois escolhe Fagaras (h=176).
  • Depois Bucareste (h=0).
• Caminho encontrado: Arad → Sibiu → Fagaras → Bucareste.
• Problema: não garante o caminho mais curto (nesse caso dá certo, mas pode falhar em outros mapas).

3. Busca A*

• Critério: combina custo real e heurística: f(n) = g(n) + h(n)
• Exemplo:
  • Em Sibiu: g=140 (até aqui) + h=253 = 393.
  • Em Oradea: g=146 + h=380 = 526.
  • A* prefere Sibiu (menor f).
  • Continua assim até encontrar o caminho ótimo.
• Resultado: encontra o mesmo caminho ótimo que UCS, mas de forma muito mais eficiente, expandindo menos nós.

Algoritmo	Caminho	Custo total	Observação
UCS	Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucareste	418 km	Caminho ótimo, mas explorou bastante.
Gulosa	Arad → Sibiu → Fagaras → Bucareste	450 km	Mais rápido, mas não ótimo.
A*	Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucareste	418 km	Caminho ótimo e mais eficiente que UCS.

Conclusão

• Heurística = intuição do algoritmo sobre o caminho a seguir.
• Busca informada economiza tempo e memória em relação à busca cega.
• O algoritmo A* é o mais poderoso, pois consegue ser eficiente e ainda garantir a melhor solução.

• Esse conteúdo é a base para aplicações reais de IA: GPS, jogos, planejamento de rotas, diagnósticos médicos e muito mais.

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.