Solução de Problemas com Busca
Prof. João Alberto Fabro
UNIOESTE
Solução de Problemas com Busca
Estratégias de Busca
– Não Informadas(Cegas):
• Largura
• Profundidade
• Largura com custo uniforme
• Busca Bidirecional
Solução de Problemas com Busca
Estratégias de Busca
– Informadas(Heurísticas):
• Baseadas em Heurísticas (Não-Numéricas)
• Baseadas em funções de Custo e Avaliação
– Melhor Escolha (Best First Search)
» Busca Gulosa (Greedy)
» A*
• Baseadas em Melhoramento Interativo
– Subida de Encosta
» pela trilha mais íngreme
– Recozimento Simulado
Solução de Problemas com Busca
Solução de Problemas com Busca
Busca Gulosa
Solução
de
Problemas
com
Busca
Solução de Problemas com Busca
Busca A*
Solução de Problemas com Busca
Busca A*
Solução de Problemas com Busca
Nosso Exemplo:
4
C
3
1
A
2
F
M
4
2
D 5 1
2
G
4
1
H
3
4
2
I
3
3
1
1
2
3
K
4
2
E
J
L
2
B
Solução de Problemas com Busca
Subida de Encosta:
Solução de Problemas com Busca
Problema: Pode ficar estacionado em um máximo local
Solução de Problemas com Busca
• Recozimento Simulado (Simulated Annealing)
– Simular mecanismo físico para ligas metálicas
– “Resolve” problema da subida de encosta:
• Permite que passos na direção “errada” sejam dados
aleatoriamente no início da busca
• Vai diminuindo a probabilidade destes passos
ocorrerem, bem como seu tamanho, de acordo com
um “cronograma”
Solução de Problemas com Busca
• Redução de problemas - Grafos E-OU
• Satisfação de Restrições – CriptoAritmética
– Heurística do Reparo - 8 rainhas
• Análise Meios-Fins