Logo Passei Direto
Buscar

Módulo V - Busca Heuristica

Ferramentas de estudo

Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 1/3
Heuristica ­ Fundamentos
Heurísticas podem ser interpretadas como estratégias em busca da solução do problema proposto de forma mais rápida em
comparação a investigação de todas as possibilidades de respostas. Entretanto, o uso de heuristicas em buscas no espaço de
estados não garante a solução do problema  ou que a solução ótima seja encontrada, mas em determinados casos se torna a
única possibilidade em resolver problemas onde a busca da solução se torna impossivel de ser processada, como por exemplo o
jogo de damas ou de xadrez. O jogo de damas gera uma árvore de possibilidades (espaço de estados) com
100.000.000.000.000.000.000.000.000.000.000.000.000 estados possiveis de busca. Neste caso, a busca heuristica se torna a
única opção.
Heurística = é um atalho entre o nó inicial e objetivo no espaço de estados;
Heurística é uma função de avaliação h(n), representado por uma estimativa de custo de um caminho de um nó “n” até o
nó objetivo.
h(n) deve ser simples de ser computada
 
Exemplos de Heuristicas
h(n) = distância em linha reta de n até o objetivo mais próximo;
Se é um grafo de queries da derivação de uma base. h(n) = número de átomos da query.
h(n) = distância até o objetivo, dividida pela velocidade máxima
Buscas Heuristicas
Gulosa (Greedy best­first search)
A* e IDA*
RBFS e SMA*
Subida na Montanha (Hill­Climbing)
Algorítmos Genéticos
 
 
Busca Gulosa
Normalmente, expande o nó mais próximo do nó objetivo, supondo que isso levará rapidamente a uma solução;
Formulação:  f(n) = h(n). Cada nó representado por n, é afeta por uma heuristica h(n).
Ex: Para problemas baseado em rota, encontrar uma rota no mapa da Rominia usando uma heuristica da dist^ancia em
linha reta.
 A heuristica a ser utilizada para a  busca gulosa refere­se à distancia em linha reta do nó inicial (a ser escolhido) ao nó objetivo,
conforme apresentado na figura abaixo que representa o mapa da Romenia. Para esta figura, as distâncias em linha reta
calculadas faz mensão ao nó objetivo "Bucharest".
 
Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern Approach. 2.Edition. New Jersey: Prentice Hall, 2003
A heuristica da distancia em linha reta pode ser utilizada neste caso, onde a busca Gulosa permite selecionar a menor distancia
entre os estados analisados. A figura abaixo é dividida em três fases, onde a primeira corresponde do Nó inicial "Arad". A partir
deste momento, é possivel calcular a função heuristica de cada nó para saber qual é o nó que apresenta a menor distancia.
 
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 2/3
Fonte: RUSSEL Stuart; NORVING Peter. Artifical Intelligence: A modern Approach. 2.Edition. New Jersey: Prentice Hall, 2003 
Portanto, o caminho percorrido foi {Arad, Sibiu, Fagaras, Bucharest}
 Avaliação da Busca Gulosa
COMPLETA: Não é completa, pois pode seguir caminhos infinitos (Ex: Depth­First Search)
ÓTIMA: Não é ótima, pois considera somente o estado atual;
TEMPO: O(bm), mas uma boa heuristica pode melhorar sua complexidade;
ESPAÇO: O(bm), mantem todos os nós na memória.
 
 
 
 
 
Exercício 1:
Conceitue Heuristica referente a busca no espaço de estados.
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 3/3
A ­ Heuristica representa um busca 
B ­ Heuristica é um modelo matemático idealizado para criar um caminho com atalhos no espaço de estados. 
C ­ Heuristica é um modelo de raciocínio lógico, pouco utilizado pelas buscas cegas. 
D ­ Heuristica é o caminho mais longo entre o nó inicial e objetivo. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 2:
Em um dado problema necessitamos resolvê­lo com o uso de heuristica. Quantas heuristicas podemos ter para resolver um único
problema?
A ­ Apenas 1 heuristica 
B ­ Quantas heuristica o problema necessitar 
C ­ Nenhuma heuristica 
D ­ Somente 2 heuristicas 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 3:
Uma das formas de avaliação das buscas em inteligência artificial é através de critérios bem estabelecidos.
Quais são os critérios de avaliação no que diz respeito a complexidade de uma estratégia de busca? 
A ­ Tempo e Espaço 
B ­ Completo, Ótimo, Complexidade de Tempo e Espaço 
C ­ Planejamento, Análise e Pontos por função 
D ­ Indução e Dedução do conhecimento 
Comentários:
Essa disciplina não é ED ou você não fez comentários

Mais conteúdos dessa disciplina