Mapa mental
Busca Informada Heurística

Mapa mental: Busca informada heurística
Contenido del mapa
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.
- Como encontrar um barco perdido?
- Não podemos procurar no oceano inteiro.
- Observamos as correntes marítimas, o vento, etc...
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...
- 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.
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.
- 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!
- 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
- 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
- Busca Gulosa
- Busca com limite de memória
- 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*
- 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
- 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.
Información
- Descripción
- Graduação Inteligência Artificial - P2 Mapa Mental sobre Busca Informada Heurística, creado por ajjaxbr el 21/05/2014.
- Creado por
- ajjaxbr
- Visitas
- 20
- Valoración