Algoritmos de Busca Heurísticos
Sumario
• Heurísticos
– Best-first
– Greedy best-first
– A*
– Algoritmos de Busca local
– Hill-climbing
• Metaheuristicos
– Simulated annealing
– Algoritmos Geneticos
Best-first
• Idéia: usar uma função de avaliação f(n)
para cada nodo
– Estimar se ele é “promissor”
Expandir o mais desejável
• Casos Especiais:
– greedy best-first
– A*
Romania
Greedy best-first (guloso)
•
•
•
•
Função de avaliação f(n) = h(n) (heurística)
= estima o custo de n ao objetivo
hSLD(n) = linha reta desde n a Bucharest
O Algoritmo “Greedy best-first” expande o
nodo que parece mais perto do objetivo
Greedy best-first
Greedy best-first search
example
Greedy best-first search
example
Greedy best-first search
example
Propriedades do Algoritmo
greedy
• Completo? Não
• Tempo? O(bm), uma boa heurística pode
melhorar ele muito
• Espaço? O(bm) – mantém todos os nodos
em memória
• Ótimo? Não
A*
• Idéia: evitar a expansão de caminhos que
estão muito custosos
• Função de Avaliação f(n) = g(n) + h(n)
• g(n) = custo de atingir n
• h(n) = custo estimado de n ao objetivo
• f(n) = custo total estimado de caminho
através de n ao objetivo
A*
A*
A*
A*
A*
A*
Heurística Admissível
• Uma heurística h(n) é admissível se para cada
nodo n,
h(n) ≤ h*(n), donde h*(n) é o custo real de
atingir o estado objetivo desde n.
• Uma heurística admissível nunca sobreestima o
custo de atingir o objetivo, ela é otimista
• Exemplo: hSLD(n) (nunca sobreestima a
distancia da rodovia)
• Teorema: Se h(n) é admissível, A* é ótima
Propriedades de A*
• Completa? Sim (ao menos que existam
infinitos nodos com f ≤ f(G) )
• Tempo? Exponencial
• Espaço? Mantém todos os nodos em
memória
• Ótima? Sim
Algoritmos de Busca Local
• Em muitos problemas de otimização , o caminho
até o objetivo é irrelevante; o objetivo é a
solução
• Espaço de Estados = conjunto de
configurações completas
• Encontrar a configuração que satisfaz as
restrições, exemplo as n- rainhas
• Em tais casos, podem ser usados algoritmos de
busca local
• Manter um estado atual,tentar melhorar ele
Exemplo: n-rainhas
• Coloque as n rainhas em um tabuleiro de
n × n, as rainhas não podem estar na
mesma coluna, linha ou diagonal
Hill-climbing
• “Igual que escalar o Everest "
Hill-climbing
• Problema: dependendo do estado inicial,
pode ficar em máximos locais
Busca Local
• Manter k estados como alternativa a um
• Comece gerando k estados aleatoriamente
• A cada iteração, todos os sucessores de todos
os k estados devem ser gerados
• Se qualquer um deles for o objetivo, pare; caso
contrario selecione k melhores sucessores da
lista completa e repita
• Algoritmos Genéticos