Please enable JavaScript.
Coggle requires JavaScript to display documents.
Aula 06 - Funções Heurísticas, Inventando Funções Heurísticas, Definição…
Aula 06 - Funções Heurísticas
Inventando Funções Heurísticas
Como escolher uma boa função heurística h?
São específicas para cada problema
ela deve ser
admissível
nunca superestimar o custo real da solução
Existem estratégias genéricas
Relaxar restrições do problema
"Aprender" a heurística a partir de exemplos
Aprendizagem de máquina
Pra que serve uma função heurística?
Economizar o custo de busca
Existe para
Ajudar o algoritmo de busca a convergir mais rápido
Encontrando uma solução ótima
Usuário nem sabe da existência dela
Definição com problema relaxado
O que é
Versão simplificada do problema original
onde os
operadores
são menos restritivos
Exemplo
Contexto
Jogo dos 8 números
Operador original
um número pode mover-se de A para B
se A é adjacente a B
e B está vazio
Busca exaustiva ~= 3²² estados possíveis
Operadores relaxados
Um número pode mover-se de A para B se A é adjacente a B (h2)
Um número pode mover-se de A para B se B está vazio
Um número pode mover-se de A para B (h1)
Problema:
"Quando uma função heurística relaxa demais o problema, acaba não ajudando o algoritmo a caminhar para uma solução"
Simplifica demais o problema
Hora da escolha
É sempre melhor usar uma função heurística com
valores mais altos
i.e., mais próximos do valor real do custo de caminho
contanto que ela seja admissível
Caso existam
muitas funções heurísticas
para o mesmo problema
e nenhuma delas domine as outras
usa-se uma
heurística composta
Para cada nó, seleciono a heurística que retorna o maior valor
Assim, h é admissível e domina cada individualmente
Definição com aprendizagem de máquina
Obs
Assunto não faz parte da disciplina
Funcionamento
Criar um corpus de
exemplos de treinamento
Resolver um conjunto grande de problemas
Armazenar cada solução ótima
que possui
estado no caminho "solução"
custo real da solução
a partir daquele ponto
Usar esse corpus para treinar um algoritmo de
aprendizagem indutiva
Que vai ser capaz de prever custos de outros estados
Qualidade da função heurística
O que é
Medida através do
fator de expansão efetivo (b*)
Menor o fator de expansão efetivo
=
Menor o custo de busca
Uma boa função heurística terá
b* muito próximo de 1
Cuidados...
Executar a função para cada novo nó na Fronteira tem um custo associado
Tempo
Memória
Se
O
custo de execução
da função for maior que o custo para expandir os nós extras
Então
Ela
não
deve ser usada
Uma
boa
função heurística deve ser
Eficiente
Econômica