Ajude a dar forma ao GoConqr. O que a gente deve adicionar?

Mapa mental

Busca Informada Heurística

ajjaxbr Inteligência Artificial - P2 Graduação Português 5,0Avaliação média 5,0 de 5 (1 avaliação)

Mapa mental sobre busca informada heurística: busca exaustiva, funções heurísticas e classes de algoritmos

Mapa mental: Busca informada heurística

Conteúdo do mapa

Busca Informada Heurística

  1. 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...
  2. 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...
  3. 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.
  4. 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 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*
  5. 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.

Informações

Descrição
Graduação Inteligência Artificial - P2 Mapa Mental sobre Busca Informada Heurística, criado por ajjaxbr em 21-05-2014.
Criado por
ajjaxbr
Visualizações
20
Avaliação
Avaliação média 5,0 de 5 (1 avaliação)

Mais sobre Métodos de busca

Fale Conosco

Sobre o que é sua mensagem?

O que a gente deve adicionar?