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 bestfirst search)
A* e IDA*
RBFS e SMA*
Subida na Montanha (HillClimbing)
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 referese à 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: DepthFirst 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