Baixe o app para aproveitar ainda mais
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. * * * * * * * * * * * * * * * * * * * *
Compartilhar