912380
Busca Informada Heurística
- Busca Exaustiva (CEGA)
- Encontram soluções para problemas pela
geração sistemática de novos estados, que
são comparados ao objetivo.
- São ineficientes na maioria dos casos
- São capazes de calcular apenas o
custo de caminho do nó atual ao nó
inicial (função g), para decidir qual o
próximo nó da fronteira a ser expandido.
- Essa medida não
necessariamente conduz a
busca na direção do
objetivo.
- São capazes de calcular apenas o
custo de caminho do nó atual ao nó
inicial (função g), para decidir qual o
próximo nó da fronteira a ser expandido.
- Como encontrar um barco perdido?
- Não podemos
procurar no oceano
inteiro.
- Observamos as correntes
marítimas, o vento, etc...
- Não podemos
procurar no oceano
inteiro.
- Encontram soluções para problemas pela
geração sistemática de novos estados, que
são comparados ao objetivo.
- Estrátégias de Busca Heuristica
- Utilizam conhecimento especifico do
problema na escolha do proximo nó
a ser expandido.
- Barco
perdido
- Correntes
marítimas,
vento, etc...
- Correntes
marítimas,
vento, etc...
- Barco
perdido
- Utilizam conhecimento especifico do
problema na escolha do proximo nó
a ser expandido.
- Aplica de uma função de avaliação a cada nó na fronteira do espaço
de estados.
- Essa função estima o custo de caminho do nó atual até o objetivo
mais próximo utilizando uma função heurística.
- Essa função estima o custo de caminho do nó atual até o objetivo
mais próximo utilizando uma função heurística.
- Classes de algoritmos para busca
heurística
- Busca pela melhor escolha (BME) (Best-First
Search)
- Busca genérica onde o nó de menor custo
"aparente" na fronteira do espaço de estados é
expandido primeiro.
- Algoritmo
- É uma especialização do
algoritmo de
BUSCA-EM-ARVORE ou
BUSCA-EM-GRAFO, no qual
um nó é selecionado para
expansão com base em uma
função de avaliação f(n),
que mede a distancia até o
objetivo.
- É uma especialização do
algoritmo de
BUSCA-EM-ARVORE ou
BUSCA-EM-GRAFO, no qual
um nó é selecionado para
expansão com base em uma
função de avaliação f(n),
que mede a distancia até o
objetivo.
- Abordagens
- Busca Gulosa
- Semelhante à busca em
profundidade com backtracking. Tenta
expandir o nó mais próximo do nó
final com base na estimativa feita pela
função heurística h
- Exemplos
- Encontrar a rota mais barata de Canudos a Petrolândia. hdd(n) =
distancia direta entre o nó n e o nó final. hdd é admissível!
- Encontrar a rota mais barata de Canudos a Petrolândia. hdd(n) =
distancia direta entre o nó n e o nó final. hdd é admissível!
- Custo de busca mínimo! não expande nós
fora do caminho. Porém não é ótima,
escolhe o caminho que é mais econômico
à primeira vista. Não é completa, pode
entrar em looping se não detectar a
expansão de estados repetidos, pode
tentar desenvolver um caminho infinito
- Semelhante à busca em
profundidade com backtracking. Tenta
expandir o nó mais próximo do nó
final com base na estimativa feita pela
função heurística h
- Algoritmo A*
- Tenta minimizar o custo total da solução
combinando: Busca Gulosa, econômica, porém não
é completa nem ótima. Busca de Custo Uniforme,
ineficiente, porém completa e ótima. Expande o nó
de menor valor de f na fronteira do espaço de
estados. Usa o algoritmo de BUSCA-EM-ARVORE
- Tenta minimizar o custo total da solução
combinando: Busca Gulosa, econômica, porém não
é completa nem ótima. Busca de Custo Uniforme,
ineficiente, porém completa e ótima. Expande o nó
de menor valor de f na fronteira do espaço de
estados. Usa o algoritmo de BUSCA-EM-ARVORE
- Busca Gulosa
- Busca genérica onde o nó de menor custo
"aparente" na fronteira do espaço de estados é
expandido primeiro.
- Busca com limite de memória
- SMA - (Simplified
Memory-Bounded A*) O número de
nós guardados em memória é
fixado previamente.
- SMA - (Simplified
Memory-Bounded A*) O número de
nós guardados em memória é
fixado previamente.
- Busca com melhora iterativa
- IDA - (Iterative Deepening A*) Igual
ao aprofundamento iterativo, porém
seu limite é dado pela função de
avaliação (f), e não pela
profundidade (d). Necessita de
menos memória do que A*
- IDA - (Iterative Deepening A*) Igual
ao aprofundamento iterativo, porém
seu limite é dado pela função de
avaliação (f), e não pela
profundidade (d). Necessita de
menos memória do que A*
- Busca pela melhor escolha (BME) (Best-First
Search)
- Funções Herísticas
- Função heuristica -h. Estima o custo do caminho mais barato do estado atual até o estado final mais próximo.
- Funções heurísticas são especificas para cada problema.
- Exemplos
- Encontrar a rota mais barata de Jeremoabo a Cajazeiras - hdd(n) = distancia direta entre o nó n e
o nó final
- Encontrar a rota mais barata de Jeremoabo a Cajazeiras - hdd(n) = distancia direta entre o nó n e
o nó final
- Como escolher uma boa função heuristica? Ela deve
ser admissível, nunca superestimar o custo real da
solução.
- Distancia direta (hdd) é admissível porque o caminho mais curto entre dois pontos é
sempre uma linha reta.
- Função heuristica -h. Estima o custo do caminho mais barato do estado atual até o estado final mais próximo.
Want to create your own Mind Maps for free with GoConqr? Learn more.