Please enable JavaScript.
Coggle requires JavaScript to display documents.
Aula 5 - Busca Heurística, Estratégias de Busca Heurística (Informada),…
Aula 5 - Busca Heurística
Estratégias de Busca Heurística (Informada)
Utilizam
conhecimento específico do problema
na escolha do próximo nó a ser expandido
Aplicam
função de avaliação
essa
função heurística
estima
o custo do caminho mais barato do estado atual até o estado final mais próximo
a cada nó na fronteira do espaço de estados
Diferentemente das estratégias de Busca Cega
Agora eu olho pra frente
Não olho só pra trás
Busca pela melhor escolha (Best-First)
Conceito
O
nó de menor custo aparente
na fronteira do espaço de estados é expandido primeiro
"aparente" porque ocorre uma estimativa
ou seja, pode não representar o valor real
Algoritmo
função BuscaMelhorEscolha (problema, FunçãoAvaliação) retorna solução ou falha
BuscaGenérica (problema, FunçãoInsere)
Função Insere
insere novos nós na fronteira
ordenados
com base na
FunçãoAvaliação
2 Abordagens básicas
Busca gulosa (Greedy search)
Algoritmo A*
Algoritmo A*
Como essa estratégia é avaliada?
É completa e ótima
Sempre que houver uma solução, ela vai ser encontrada
Encontra sempre a melhor solução
Custo computacional
Pequeno
Tempo
exponencial com o comprimento da solução
porém, boas funções heurísticas diminuem muito esse custo
o fator de expansão da árvore de busca fica próximo de 1
Memória
Também é exponencial
porém com fator de expansão próximo de 1, poucos nós serão guardados na fronteira
Observações
Até o momento, é a melhor estratégia de busca que vimos
É completa, é ótima e gasta pouco tempo e memória
A* apresenta
eficiência ótima
Para garantir otimalidade:
o valor de f (f = g + h) em um caminho particular deve ser
não decrescente
f = g + h deve ser
não decrescente
g é não decrescente
(para operadores não negativos)
h
deve ser
não-crescente (consistente, monotônica)
Quando h não é consistente, para se garantir otimalidade do A* temos:
quando f(n+1) < f(n) usa-se:
f(n+1) = max ( f(n), g(n+1) + h(n+1) )
ou seja, quando h diminuir, repito o valor de f do nó anterior
Conceito
Tenta minimizar o custo total da solução combinando
Busca gulosa (h)
econômica, porém não é completa nem ótima
Busca de custo uniforme (g)
ineficiente, porém é completa e ótima
Função de avaliação
f(n) = g(n) + h(n)
g(n) = custo do caminho do nó inicial até n
h(n) = custo do caminho
estimado
de n até o nó final (objetivo)
Busca com limite de memória
IDA* (Iterative Deepening A*)
O que faz
É igual à estratégia de busca em profundidade com aprofundamento iterativo
Porém o limite da busca é dado pela função de avaliação (f) e não pela profundidade (d)
Necessita de menos memória que o A* padrão
Limita os nós que vão para fronteira
Elimina os que têm valor superior ao da função de avaliação
Como pode ser avaliado
Economiza tempo e memória
Porém, o algoritmo pode se perder
No caso de uma solução estar entre um dos nós descartados inicialmente
SMA* (Simplified Memory-Bounded A*)
O que faz
Limita o tamanho da fronteira
A quantidade de nós que podem ser guardados na memória ao mesmo tempo é fixado previamente
Como pode ser avaliado
Economiza memória
Porém gasta mais tempo
Funções Heurísticas
Exemplos
Encontrar a rota mais curta entre 2 cidades
h(n) = distância direta entre o nó atual n e o objetivo
Jogo dos 8 números
h(n) = quantidade de números fora da sua posição final na configuração do objetivo
Como escolher uma boa função heurística?
ela deve ser
admissível
nunca superestimar o custo real da solução
São específicas para cada problema
Busca Gulosa
Como essa estratégia é avaliada?
Não é completa
Pode entrar em looping se não detectar expansão estados repetidos
Pode tentar desenvolver um caminho infinito
Não é ótima
Escolhe o caminho que é mais econômico
à primeira vista
Por escolher o nó
imediatamente menor
Pode ser que o
custo total final
da solução escolhida não seja o melhor
Pois o algoritmo só olha pra frente
Custo computacional
Custo de tempo e de memória
Teoricamente é exponencial
Porque a heurística pode não ser boa
Ainda assim, tem
custo de busca mínimo
Não expande nós fora do caminho da solução
Observações
Semelhante à busca em profundidade com
backtracking
Conceito
A função de avaliação apenas
olha pra frente
Tenta expandir o
nó mais próximo do nó objetivo
com base na estimativa feita por uma função heurística h
Função de avaliação
Função heurística
h(n)
estima
o custo do caminho mais barato do estado atual n até o estado final mais próximo
não considera o custo de caminho da raiz até o nó atual (g(n))
É composta apenas pela função heurística