Busca com informação e exploração - busca heuristi (busca_com_informacao_e_exploracao_busca_heuristica.ppt)

Prévia do material em texto

*
*
Busca com informação e exploração - Busca Heurística
Jeneffer Ferreira Lázaro
email.: jenefferferreira@gmail.com
Capitulo 4 - Stuart Russel e Peter Norving
*
*
Busca informada (ou heurística)
 busca pela melhor escolha (best-first search)
Utiliza conhecimento sobre o domínio para encontrar soluções mais eficientes do que no caso de busca cega.
Exemplo: Dirigir em Recife sabe-se dos buracos, semáforos, assaltos, bicicleta, trânsito...
Busca pela melhor escolha: expande o nó que possui função de avaliação mais baixa
Essa função estima o custo do caminho do nó atual até o objetivo mais próximo utilizando uma função heurística.
*
*
Funções Heurísticas
Função de avaliação (f(n)): mede o custo de um nó até o objetivo.
Função heurística (h(n)): 
custo estimado do caminho mais econômico do nó n até o nó objetivo.
São específicas para cada problema
Exemplo:
Encontra uma rota mais curta entre duas cidades
Heurística = capacidade de usar conhecimento para resolver problemas
*
*
Busca pela melhor escolha (BME) 
Best-first Search
Busca genérica no qual o nó de “menor” custo na fronteira do espaço de estados é expandido primeiro
Duas abordagens básicas:
Busca gulosa (Greedy Search)
Algoritmo A* 
*
*
Busca gulosa (pela melhor escolha) 
Expande o nó mais próximo da meta, supondo que isso levará rapidamente a uma solução.
Semelhante à busca em profundidade com backtracking 
Tenta expandir o nó mais próximo ao nó final com base na estimativa feita pela função heurística h.
Custo de busca é minimizado 
Não expande nós fora do caminho
Escolhe o caminho mais econômico à primeira vista
Portanto: f(n) = h(n)
*
*
Busca gulosa: exemplo ir de Arad para Bucharest
*
*
*
Busca gulosa pela melhor escolha: exemplo
*
*
Busca gulosa pela melhor escolha: exemplo
*
*
Busca gulosa pela melhor escolha: exemplo
*
*
Busca gulosa pela melhor escolha: exemplo
*
*
Busca heurística (ou informada)
Busca Gulosa
Distância em linha reta para Bucharest:
*
*
Busca gulosa	
Custo de busca mínimo
No exemplo, não expande nós fora do caminho.
Não é ótima, pois segue o melhor passo considerando somente o momento atual.
 pode haver um caminho melhor seguindo algumas opções piores em alguns pontos da árvore de busca.
Não é completa:
Pode encontrar loop se não detectar a expansão de estados e seguir um caminho infinito.
 ex, não encontra melhor caminho Arad  Sibiu  Riminicu  Pitesti  Bucharest
Explora árvore de busca em profundidade primeiro
Sofre dos mesmos problemas da busca cega em profundidade
*
*
Busca A*
Tenta minimizar o custo total da solução combinando:
Busca gulosa
Econômica, porém não é completa
Avalia nós combinando o custo para alcançar cada nó (g(n)) e o custo estimado para ir deste nó até o objetivo (h(n)):
f(n) = g(n) + h(n)
g(n) = distância de n ao nó inicial
h(n) = distância estimada de n ao nó final 
Para a solução de custo mais baixo, seguir os estados de menor valor de g(n) + h(n).
A* expande o nó de menor valor de f na fronteira do espaço de estados
Olha o futuro sem esquecer do passado!
*
*
Exemplo de Busca A*
*
*
Exemplo de Busca A*
*
*
Exemplo de Busca A*
*
*
Exemplo de Busca A*
*
*
Exemplo de Busca A*
*
*
Exemplo de Busca A*
*
*
A*: exemplo
449
393
447
417
413
415
496
*
*
Algoritmo A*
Perceberam que A* tomou um rumo diverso do algoritmo guloso?
A* tomou o caminho ótimo! É completa e ótima.
Custo de tempo:
Exponencial com comprimento da solução, porém boas funções heurísticas diminuem significativamente esse custo.
*
*
Exercícios 
*
*
Represente o operação da busca A* aplicada ao problema de ir até Bucareste a partir de Lugoj usando a heurística de distância. Mostre a sequencia de nós e a pontuação de f, g e h para cada nó. 
*
*
No grafo abaixo cada arco indica o custo do operador e entre parênteses é indicado uma estimativa do custo até o nó objetivo. Apresente as mudanças da fronteira de busca para este problema quando realizadas as buscas A* e pelo melhor primeiro (gulosa).
*
*
Apresente as mudanças da fronteira de busca para este problema quando realizadas as buscas em largura, em profundidade, gulosa e A*.
Sua resposta forneça o seguinte:
A árvore de busca que é produzida, mostrando a função de custo em cada nó.
Defina a ordem em que os nós serão expandidos para cada estratégia citada acima.
A figura está localizada no próximo slide
*
*
*
*
Referencia
Baseado no Cap. 4 do livro de Stuart Russel e Peter Norving - “Inteligência Artificial”, 2a ed.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*